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

Question

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

我对其复杂性的回答是 O(n²) = O(n*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²)。