链表的复杂性消除了冗余元素

Question

我想计算这个函数的复杂性。以下代码从有序列表中删除了冗余元素。

我对其复杂性的回答是第一个O(n²) = O(n*n)的while“n”和第二个while的“n”。

我的回答是否正确？如果没有，如何正确计算复杂性？

liste redondance(liste l){
liste red,p,prev;
if(l==NULL)
   return l;
red=l;
while(red!=NULL){
   p=red->suivant;
   prev=red;
   while(p!=NULL){
       if(p->val==red->val){
           prev->suivant=p->suivant;
           free(p);
           p=prev->suivant;
       }
       else{
           p=p->suivant;
           prev=prev->suivant;
       }
   }
   red=red->suivant;
   }
  return(l);
}

先感谢您。

Answer 1

是的，这是正确的。

外部循环遍历所有元素，内部循环遍历外部循环打开后的所有元素。

平均而言，内环通过一半的元素，但这对复杂性没有影响，复杂性仍为O（n²）。

Answer 2

void undup(struct llist* ll)
{
for( ;ll; ll=ll->next) {        //walk the chain
        struct llist **pp,*del;
        for(pp = &ll->next; del = *pp;) {
                // since the list is sorted, duplicates MUST be adjecent.
                // if the next node has a different value, there are no more dups
                // (wrt ll->val) in the rest of the chain
                if (del->val != ll->val) break;
                *pp = del->next;
                free(del);
                }
        }
return;
}

---

复杂性显然是O（n）。 （内循环缩短链，或只执行一次）