从单链表的末尾删除元素的操作的复杂性是什么？

Question

从单链表的末尾删除元素的操作的复杂性是什么？我在C中实现了链表.这是从链表的末尾删除元素的代码.现在我的问题是如何计算这个片段的复杂性.涉及的因素有哪些.还有其他涉及的操作

1. 在开始时插入
2. 插入中间
3. 最后插入
4. 在开始,中间,结束时删除
5. 翻转清单

我怎样才能计算它们？

struct node {
       int val;
       struct node * next;
    };

    typedef struct node item;
    item * head = NULL;

 /* DELETION AT THE END OF THE LIST */     
        deleteatend() {
        item * temp, * curr;
        if(head == NULL) {
            printf("\n Linked list is Empty ");
            return;
          }
        temp = head;
        if(head->next == NULL) { /* When There is atleast 1 NODE */
            head=NULL;
         } 
        else {
            while(temp->next != NULL) { /* Traversing the list upto second-last NODE */ 
              curr=temp;
              temp=temp->next;
              } 
            curr->next =NULL;  /* When TEMP points to last NODE */ 
        }
        free(temp);
       }    

反向列表的代码:

 /* Reverse Printing of list */
      reverselist() {
          item * curr, * nextnode, * prev;
          curr = head;
          nextnode = curr-> next; /* NEXTNODE traverses till the end of the list */
          prev = NULL;
          curr-> next = NULL; /* Making the first Node as Last node */
          while(nextnode != NULL) {
            prev = curr; /* Generally holding the last element of the reversed list */
            curr = nextnode; 
            nextnode = curr-> next;
            curr-> next = prev;
           } /* End of WHILE */
          head = curr;
        }  

Answer 1

我将给出一些厨房食谱来找出算法的(明显的)复杂性.这在数学上并不严谨,因为你必须咨询你的教科书.

1. 找到分析的代码所依赖的参数.N表示列表中的元素数量.其他算法还有其他参数,字符数,数组中的元素数.

2. 找到循环.看看他们依赖什么参数.

   1. 要插入列表的第一个元素,您不需要循环,因此如果列表包含1或10亿个元素,则操作相同.

   2. 要在中间插入,您必须完全循环遍历列表,并且根据您实现它的方式,您必须第二次循环到中间,因此您有1.5次N次迭代.复杂性仅取决于列表的长度,因此其复杂度为O(N).如果仅通过循环一次来实现它,那么将有N次迭代并且仍然具有复杂度O(N).选择实现它的方式可能取决于每次迭代的个别时间(以及实现它的时间).

   3. 与上面相同,你必须经历整个列表一次,因此复杂度为O(N).

   4. 与插入相同.

   5. 要反转列表,您只需要在列表上循环一次,因此复杂度为O(N).

   6. 仅仅是为了另一个复杂性的例子.如果要删除列表中的所有双重条目.如果它等于列表中的任何其他元素,则必须检查每个元素,这意味着您必须遍历所有元素,获取元素并将其与列表中的每个其他元素进行比较.在最坏的情况下,列表中没有双打意味着列表不会缩小,因此您倾向于进行N*(N-1)比较.在O符号中 O(N*(N-1)) = O(N²-N) N²占主导地位,因此我们有O(N²)一个二次算法的复杂性.

PS:我在开头写的是apparent因为有时会有一些依赖于N的术语,这些术语在程序本身中是不可见的,但却是你正在进行的抽象的一部分.对于您的列表,如果它变得如此之大以至于您的系统开始交换,那么您会遇到真正复杂性的隐藏术语之一,这些术语被隐藏在操作系统的虚拟内存抽象中.