Сложность связанного списка, который устраняет лишние элементы

Question

Я хочу рассчитать сложность этой функции.Следующий код удаляет избыточные элементы из упорядоченного списка.

Мой ответ на его сложность: O(n²) = O(n*n) «n» для первого while и «n» для второго while.

Правильный ли мой ответ?Если нет, то как правильно рассчитать сложность?

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), очевидно.(внутренний цикл сокращает цепочку или выполняется только один раз)