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

Question

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

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

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

Answer 1

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

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

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

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

1 + 2 + 4 + 8 + 16 + ... + 2 + 1 ^{войти п} ≤ 4n - 1 = о (п)

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

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