Временная сложность алгоритма, который объединяет стек связанных списков

Question

Я пытаюсь найти сложность (в больших обозначениях O) следующего псевдокода в терминах k и n.

d - это стек размером n, и каждый элемент в Стек - это связанный список длиной k. Функция merge выполняется за время O (a + b), где a и b - длины двух связанных списков, которые она объединяет.

while d.size >= 2
    L = d.pop()       // O(1) 
    L1 = d.pop()      // O(1)
    L2 = merge(L, L1) // O(a + b)
    d.push(L2)

Answer 1

Сложность по времени равна O (kn ² ), где n - размер исходного стека. Чтобы понять почему, подумайте о длине списков, которые объединены; результат предыдущего слияния всегда находится сверху стека, поэтому это всегда один из списков, который объединяется следующим образом:

• Первое слияние имеет длину k + k = 2k.
• Следующее слияние имеет длину 2k + k = 3k.
• Следующее слияние имеет длину 3k + k = 4k.
• ...
• окончательное слияние имеет длину (n-1) k + k = nk.

Время выполнения операций слияния пропорционально длине результирующих списков после слияния, поэтому мы можем добавить их :

2k + 3k + 4k + ... + nk = k × (2 + 3 + ... + n) = k × ((n ² + n ) / 2 - 1)

Если отбрасывать доминирующие члены и постоянный множитель 1/2, получим O (kn ² ). Обратите внимание, что размеры вычислений на самом деле увеличиваются при продолжении l oop; на более поздних итерациях объединяется больше данных, а не меньше.

---

Для интуиции следует ожидать квадратичного времени c в количестве списков по той же причине, по которой наивно объединяются строки занимает квадратичное c время в количестве строк.

В качестве отступления, если вы используете очередь вместо стека, то вместо этого требуется время O (kn log n). Я оставлю тебя с этим, чтобы подумать!