Какова амортизированная временная сложность вставки элемента в эту структуру?

Предположим, вы реализуете кучу, используя массив, и каждый раз, когда массив заполняется, вы копируете его в массив, удвоенный по размеру. Какова амортизированная временная сложность (в худшем случае) вставки элементов в кучу?

Я думаю, что у нас есть T(n) = n * n (это верхняя граница общей стоимости последовательности из n операций в худшем случае), и тогда амортизированная сложность по одной формуле равна T(n) / n = n^n / n = n.

Но я думаю, что это очень неправильно, потому что из интуиции очень ясно, что я должен получить log(n) или ниже ... Итак, как мне это рассчитать?


algorithm data-structures time-complexity heap amortized-analysis
person UFC Insider    schedule 13.06.2016    source источник
comment
Не по теме. Не программный вопрос. Попробуйте cs.stackexchange.com   -  person Marc B    schedule 13.06.2016
comment
Почему? Здесь есть тег для структур данных и много подобных вопросов. я думаю ты ошибаешься   -  person UFC Insider    schedule 13.06.2016

Ответы (1)


arrow_upward
2
arrow_downward

Представьте, что вы вставляете n элементов в кучу, представленную таким образом. Необходимо учитывать два разных источника затрат:

  1. Стоимость операций с кучей без учета изменения размера базового массива.
  2. Стоимость массива изменяется, игнорируя всеобъемлющие операции с кучей.

Стоимость (1) составляет O (n log n) для n полных операций, поскольку каждая вставка кучи занимает время O (log n).

Что касается стоимости (2), обратите внимание, что работа, проделанная для удвоения размера массива, прямо пропорциональна размеру массива в момент его удвоения. Это означает, что вы сделаете 1 единицу работы, чтобы удвоить массив размера 1, 2 единицы работы, чтобы удвоить массив размера 2, 4 единицы работы, чтобы удвоить массив размера 4, и т. д. Это означает, что общая проделанная работа

1 + 2 + 4 + 8 + 16 + ... + 21 + log n 4n - 1 = O(n)

Эта математика использует тот факт, что вы удваиваете массив не более 1 + log n раз, прежде чем он достигнет размера n, и что 1 + 2 + 4 + 8 + ... + 2k = 2 k+1 - 1. Это означает, что для всех n вставок вы делаете O(n) работу, удваивая массив.

В целом, общая работа, выполненная за n операций, равна O(n log n), поэтому амортизированная стоимость операции равна O(log n).

person templatetypedef    schedule 13.06.2016
comment
Единственная часть, с которой я не согласен (или не понимаю), это <= 4n-1. Пример, начальный размер массива 1, конечный размер массива 16. Элементов перемещено 1+2+4+8 = 15. Или начальный размер 32, конечный размер 256. Элементов перемещено 32+64+128 = 224. Таким образом, кажется, что так и должно быть <= n-1. - person user3386109; 13.06.2016
comment
Я понимаю, что изменение размера стоит O(n). Мой вопрос: какова формула расчета амортизированной временной сложности? И что означает амортизированная временная сложность для наихудшего случая? - person UFC Insider; 14.06.2016
comment
@user3386109 user3386109 Поскольку в любом случае все выходит за O (n), я просто даю красивую и свободную верхнюю границу. - person templatetypedef; 14.06.2016
comment
@UFCInsider Формулы как таковой не существует. Вы просто суммируете общую работу, проделанную по всем операциям, и делите на количество операций. Тогда амортизированная стоимость в наихудшем случае будет равна максимально возможному объему работы, который может быть выполнен, деленному на количество операций. - person templatetypedef; 14.06.2016