Сложность двух методов

Question

Если у меня есть метод, который вставить элемент в куче с помощью следующего кода:

(1) Если массив полон - создать новый массив и размер в соответствии с его original.length * 2, а затем скопировать каждый элемент из исходного массива в новый.

(2). Чтобы выполнить кучу, просто переверните/переверните каждый элемент в положение своего костюма.

Так худшем случае сложности являются - (1) является O(n) и (2) его O(logn)

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

Спасибо!

Answer 1

Для таких ситуаций, если следовать учебнику подход худшем случае сложность алгоритма будет

= O(n) + O(logn) 
= O(n) 

Таким образом, сложность будет O(n)

---

На самом деле название наихудшая сложность дает вам ответ. Вы должны задать свой вопрос,

Есть ли в случае, если сложность O(n).

Если да, то вот в худшем случае сложность

Answer 2

При вставке п элементов по одному, то siftUp/siftDown процесс выполняется каждый раз, и время, отведенное для этих процедур O (NlogN) (в виде суммы от log1+log2+...log(N-1)+log(N))

Но расширение массива происходит редко. Последнее расширение занимает N шагов, предыдущих N/2 шагов и так далее. Время посвящена эти процедуры

N + N/2 + N/4 + ...+1 = N*(1 + 1/2 +1/4+...) = N*2 = O(N) 

Так амортизируются время расширения части является O (1) и амортизируется время для вставки части является O (LogN)

В целом сложностью для N элементы является
O (N) + O (NlogN) = О (NlogN)
или
O (LogN) на элемент