Сложность связанного списка, который устраняет избыточные элементы
Я хочу рассчитать сложность этой функции. Следующий код удаляет избыточные элементы из упорядоченного списка.
Мой ответ на его сложность: 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);
}
Заранее спасибо.
@wildplasser спасибо за ответ. Список уже отсортирован
В этом случае дубликаты могут быть только прямыми помощниками. (и вам не понадобится алгоритм O (n * n))
@wildplasser я не понимаю твоего ответа. Вы имеете в виду, что мне не нужен цикл while?
Если список отсортирован, алгоритм становится линейным. «Совпадает ли предыдущее значение с текущим, затем удалите текущее» Один проход по списку.
Ответы 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), очевидно. (внутренний цикл укорачивает цепочку или выполняется только один раз)
"дель" не инициализирован? и почему вы использовали объявление ll как указатель в параметре функции? То же самое, я не понимаю эту нотацию «llist ** pp»
Я не печатаю указатели (так как это плохая привычка), а ; del = *pp; — это присваивание.
а по сложности?
Сложность O(n), очевидно. (внутренний цикл укорачивает цепочку или выполняется только один раз)
Да, именно так.
Внешний цикл проходит через все элементы, а внутренний цикл проходит через все элементы после, на которых находится внешний цикл.
В среднем внутренний цикл проходит через половину элементов, но это не имеет значения для сложности, которая по-прежнему равна O(n²).
Итак, список не отсортирован?