Анализ кучи снизу вверх

Question

Я пытаюсь выполнить анализ временной сложности на основе анализа кучи снизу вверх, и я застрял. Я провел математическую оценку, которая показывает, что это O (n), и я полностью понимаю, почему. Часть, которую я застрял в понимании, заключается в том, как в «коде» это достигается. Я знаю, что внешний for выполняет этаж (n / 2) раз, и я считаю, что while выполняет время журнала, но я не знаю, как перейти с этажа (n / 2) на O (n).

Псевдокод: Анализ времени:

for i = n/2-1; i <=0; i--         n/2+1
  k=i                             n/2
  while(2*k-1 <= n)               n/2(????)+1  <-- this is where I'm stuck. Should run log n times?
    j = k*2-1                     ...
    if(j<n && H[j] < H[j+1])      ...
      j++                         ...
    if(H[k] < h[j])               ...
      break                       ...
    swap(H[k],H[j])               ...
    k=j                           ...

Итак, я вижу, что while, вероятно, запускает log n раз, но я не вижу, как оттуда (n / 2) log n to O (п). Я ищу только наихудший случай, поскольку я знаю, что лучший случай - n / 2 + 1, поскольку он ломается, когда поддерево является кучей. Любая помощь или направление для чтения приветствуются.

Answer 1

Лучший совет, который я могу дать по поводу определения большой стоимости различных петель, следующий:

«Если есть сомнения, работайте наизнанку!»

Другими словами, вместо того, чтобы начинать с самого внешнего l oop и работать внутрь, начните с самого внутреннего l oop и двигайтесь наружу.

В этом случае у нас есть этот код:

for i = n/2-1; i >= 0; i--
  k=i                           
  while (2*k-1 <= n)
    j = k*2-1
    if(j<n && H[j] < H[j+1])
      j++
    if(H[k] < h[j])
      break
    swap(H[k],H[j])
    k=j

Поскольку мы работаем наизнанку, давайте сначала сосредоточимся на этом l oop: Начнем с анализа самого внутреннего l oop:

  while (2*k-1 <= n)
    j = k*2-1
    if(j<n && H[j] < H[j+1])
      j++
    if(H[k] < h[j])
      break
    swap(H[k],H[j])
    k=j

Я собираюсь предположим, что это анализ наихудшего случая и что мы никогда не запускаем внутренний оператор break. В этом случае это означает, что l oop прогрессирует, поскольку k перемещается в 2k - 1 или 2k после каждого шага l oop. Это означает, что k примерно удваивается с каждой итерацией l oop. L oop заканчивается, когда k превышает n, поэтому количество итераций l oop равно количеству раз, которое мы должны удвоить k, прежде чем k превысит n. Это работает до O (log (n / k)) всего l oop итераций. Обратите внимание, что это не константа; по мере того, как k становится меньше, мы в конечном итоге выполняем все больше и больше работы за итерацию.

Мы можем заменить внутренний l oop на более простой «do O (log (n / k)) work», чтобы получите это:

for i = n/2-1; i >= 0; i--
  k=i                           
  do O(log (n / k)) work;

И, поскольку k = i, мы можем переписать это как

for i = n/2-1; i >= 0; i--
  do O(log (n / i)) work;

Итак, сколько всего здесь делается работы? Суммируя работу, выполненную за итерацию на всех итерациях, мы получаем, что выполненная работа составляет

log (n / (n / 2)) + log (n / (n / 2 - 1)) + log (n / (n / 2 - 2)) + ... + log (n / 2) + log (n / 1).

Теперь «все», что нам нужно сделать упростить эту сумму. : -)

Используя свойства логарифмов, мы можем переписать это как

(log n - log (n / 2)) + (log n - log (n / 2 - 1)) + (журнал n - журнал (n / 2 - 2)) + ... + (журнал n - журнал 1)

= (журнал n + журнал n + ... + журнал n) - (журнал (n / 2) + (журнал (n / 2 - 1) + ... + журнал 1)

= (n / 2) (журнал n) - журнал ((n / 2) (n / 2 - 1) (n / 2 - 2) ... 1)

= (n / 2) (log n) - журнал ((n / 2)!)

Теперь мы можем использовать приближение Стирлинга , чтобы переписать

log ((n / 2)!) = (N / 2) log (n / 2) - n log e + O (log n)

И, следовательно, чтобы получить это:

(n / 2) (log n) - log ((n / 2)!)

= (n / 2) (log n) - (n / 2) log (n / 2) + n log e - O (log n)

= ( n / 2) (журнал (2n / 2)) - (n / 2) журнал (n / 2) + O (n)

= (n / 2) (журнал 2 + журнал (n / 2 )) - (n / 2) журнал (n / 2) + O (n)

= (n / 2) (1 + журнал (n / 2)) - (n / 2) журнал (n / 2) + O (n)

= n / 2 + O (n)

= O (n) .

Таким образом, вся эта сумма составляет O (n) .

Как видите, это решительно нетривиальная величина для вычисления! В самом деле, это намного сложнее, чем просто подсчет работы, выполненной за итерацию, и умножение на количество итераций, потому что способ, которым работа на итерацию изменяется на итерациях, делает это намного сложнее. Скорее, вместо этого мы должны провести более детальный анализ того, сколько работы выполняется каждым l oop, затем преобразовать результаты в суммирование и вытащить некоторые нетривиальные (хотя и не полностью неожиданные) трюки (приближение Стирлинга и свойства логарифмов) чтобы все заработало, как ожидалось.

Я бы отнес этот конкретный набор циклов к категории довольно сложных для работы и не особо репрезентативных для того, что вы «обычно» видите, выполняя al oop анализ. Но, надеюсь, представленные здесь методы дадут вам представление о том, как работать с более сложными oop анализами и получить представление о некоторых красивых математических вычислениях, которые входят в их состав.

Надеюсь, это поможет!