амортизированная граница отсортированного связанного списка

Я пытаюсь доказать, что амортизированная сложность операции вставки в отсортированный LinkedList составляет O (1). Я знаю, что время наихудшего случая - O (n), но мне трудно найти подходящую потенциальную функцию. Буду рад, если кто-то сможет помочь.

Спасибо.


sorting data-structures linked-list sorted amortized-analysis
person BK Tomer    schedule 08.01.2015    source источник
comment
Утверждение, которое вы пытаетесь доказать, настолько очевидно ложно, что я подозреваю, что вы имеете в виду нечто иное, когда пишете «амортизированный». Каков контекст и что вы понимаете под амортизированной сложностью?   -  person    schedule 08.01.2015
comment
@delnan амортизируется, я имею в виду, что это что-то среднее. и идея о том, что амортизированная стоимость составляет O (1), взята из Википедии.   -  person BK Tomer    schedule 08.01.2015
comment
Среднее по количеству операций (в отличие от времени на одну операцию со средними параметрами), да. Где конкретно Википедия об этом говорит?   -  person    schedule 08.01.2015
comment
en.m.wikipedia.org/wiki/Search_data_structure   -  person BK Tomer    schedule 08.01.2015
comment
О, это заблуждение. Добавление узла — это O(1), когда у вас есть ссылка на узел до/после, но сначала вам нужно найти эту позицию. См. также: stackoverflow.com/q/3899456/395760   -  person    schedule 08.01.2015

Ответы (1)


arrow_upward
0
arrow_downward

O(1) с амортизацией означает, что последовательность из n вставок стоит O(n) времени в худшем случае. В данном случае это неверно, потому что вставка элементов в обратном порядке занимает O(n*n).

person mrk    schedule 19.01.2015