Часть 2: Доказательство

Итак, как мы видели в Части 1 и поняли концепцию рекуррентного отношения. Теперь мы готовы понять, как работает основная теорема. Напомним, в предыдущем посте мы определили что а как количество повторений, b как коэффициент, на который мы делим наш ввод, d степень сложности, до которой выполняется работа вне повторений, а n — это размер ввода. Мы также определили, что у нас обычно есть aʲ количество подзадач, каждая из которых имеет размер n/bʲ на уровне j в дереве рекурсии (см. часть 1, если вы не помню, что означает дерево рекурсии).

Итак, теперь мы хотим рассчитать, сколько работы выполняется на уровне j. Давайте представим, что у нас есть Домашнее задание, состоящее из 4 задач, и мы хотим выяснить, сколько времени/работы нам нужно. Мы можем подумать о том, чтобы умножить каждую проблему на требуемое время/работу, верно?
Какое это имеет отношение к нашему делу? Мы хотим рассчитать общую работу, проделанную в нашем дереве рекурсии. Таким образом, мы умножаем количество проблем с проделанной работой на размер проблемы. Заменив английский на определения, получим: aʲ. cnᵈ . Напомним, что cnᵈ — это работа, выполняемая вне повторений в определении рекуррентного отношения. Но на самом деле размер входных данных на уровне j равен не «n», а n/bʲ. Итак, мы получаемaʲ . c[n/bʲ]ᵈ что имеет смысл, поскольку по мере того, как мы углубляемся в повторения, размер входных данных делится на коэффициент, на который мы делим нашу проблему, чтобы усилить уровень, на котором мы находимся.

Однако это для некоторого уровня j. Мы хотим рассчитать всю проделанную работу. Итак, сначала давайте перестроим наше уравнение, чтобы оно выглядело аккуратнее, разделив члены, зависящие от уровня j, и независимые члены, мы получим cnᵈ. [а/бᵈ]ʲ. Таким образом, работа, проделанная для всех уровней, будет суммой по всем j. Поскольку n является степенью b, длина дерева равна logb(n). Поэтому мы суммируем ∑ от 0 до длины дерева logb(n). Наконец, у нас есть cnᵈ. ∑ⱼ[a/bᵈ]ʲгде j = от 0 до logb(n).

Чтобы интерпретировать общие случаи в соответствии с рекуррентными соотношениями:

T(n) ≤ a T(n/b) + c nᵈ

Будь то a = bᵈ , a ‹ bᵈ или a › bᵈ. Давайте победим каждый из них по отдельности, а затем поймем, что каждый из них на самом деле означает. Для a = bᵈ заменим cnᵈ. ∑ⱼ[a/bᵈ]ʲгде мы находим, что терминa/bᵈ будет равен 1 и 1 в степени всего, равного 1. Таким образом, сумма будет равна 1⁰, а остальные суммирование до logb(n). Мы получаем [logb(n) +1]. Итак, мы получаем cnᵈ . [logb(n)+1], что равно O(nlogn). Напоминаем, что это происходит при сортировке слиянием, где a = 2 и bᵈ = 2.

Во-вторых, для a ‹ bᵈ и a › bᵈ эти случаи указывают, меньше или больше a/bᵈ 1 соответственно. Давайте воспользуемся хорошим доказательством, которое показывает, что любая сумма 1 + a¹ + a² + a³ …….. aᵏ = aᵏ⁺¹-1 / a-1 . Мы можем быстро и легко доказать это по индукции. Если вы не помните, что такое доказательство индукции, посетите эту лекцию на YouTube.

Индуктивное доказательство состоит из двух частей: Доказательство.

  1. Базовый случай верен и
  2. индуктивный шаг верен, и мы увидим, как.

Базовый случай мы индуцируем 0 и проверяем правильность нашего утверждения.

a⁰ -1 / a-1 = 1, так что это верно для базового случая.

Затем индуктивный шаг предполагает, что для k чисел утверждение верно, а затем проверяет k + 1, является ли оно также истинным или нет. Итак, мы заменим каждое k и поставим k+1: 1 + a¹ + a² + a³ …….. aᵏ + aᵏ⁺¹ и aᵏ⁺² -1 / a-1.

Используя эту сумму 1 + a¹ + a² + a³ …….. aᵏ = aᵏ⁺¹-1 / a-1, мы получаем aᵏ⁺¹-1 / a-1 + aᵏ⁺¹.

Затем мы умножаем отдельный член aᵏ⁺¹ на a-1/a-1, чтобы получить:

aᵏ⁺¹.a- aᵏ⁺¹ / a-1 равно aᵏ⁺²-aᵏ⁺¹/a-1.

Складывая члены, мы получаем:

aᵏ⁺²-aᵏ⁺¹+-aᵏ⁺¹-1/a-1, чтобы получить aᵏ⁺² -1 / a-1.

Итак, индукция верна. Действительно ценный совет при использовании индукции — всегда использовать утверждение F(k) для доказательства F(k+1), и если вы его не использовали, вы делаете что-то не так.

Вернемся к нашей основной теореме: для случая a/bᵈ меньше 1 мы находим, что aᵏ⁺¹-1/a-1 ограничено 1/1-a, которое является константой, не зависящей от того, сколько терминов у нас есть. Итак, cnᵈ. ∑ⱼ[a/bᵈ]ʲ будет равно cnᵈ.(1/1-a), что равноO(nᵈ). И это наш второй кейс. Наконец, у нас осталось a/bᵈбольше 1. Вернемся к нашему суммированию, где в этом суммировании будет доминировать самый большой член, равный logb(n), поэтому мы получим cnᵈ.(a/bᵈ)ˡᵒᵍᵇⁿ.

Чтобы упростить этот страшный термин, мы сначала берем (b⁻ᵈ)ˡᵒᵍᵇⁿ и заменяем d на logb(n), чтобы получить (bˡᵒᵍᵇⁿ)⁻ᵈ > и отмените мощность b с помощью logb, чтобы получить n⁻ᵈ. Затем мы отменяемnᵈсn⁻ᵈи оставляем сaˡᵒᵍᵇⁿ (также можно сформулировать как nˡᵒᵍᵇᵃчто вfact - это количество листьев дерева рекурсии, количество рекурсивных вызовов, мощность последнего уровня - это последнее количество узлов в дереве, которые являются листьями.

Три случая:

  1. O(nlogn)
  2. O(nᵈ)
  3. O(nˡᵒᵍᵇᵃ).

Давайте подведем итог, что каждый из них означает отдельно. В первом случае выполненные рекурсивные вызовы были равны разделению ввода, что указывает на то, что на каждом уровне выполняется одна и та же работа. Во втором случае рекурсивные вызовы меньше, чем разделение ввода, что означает, что чем глубже мы погружаемся в дерево, тем меньше работы мы делаем, представьте, что у нас есть два рекурсивных вызова и мы разделяем ввод на две половины, но мы делаем квадратичный работать вне рекурсивных вызовов. Это означает, что рекурсия экономит нам только 25% работы на каждом уровне. Таким образом, работа вне рекурсии доминирует в нотации с большим O. И в последнем случае рекурсивные вызовы больше, чем то, насколько мы делим нашу задачу, поэтому в нотации с большим O преобладают листья дерева.

Вам не нужно запоминать эти значения, просто поймите это cnᵈ. ∑ⱼ[a/bᵈ]ʲ и вы получите формулу за считанные секунды. Я попробовал это, и это работает на 100%.

Надеюсь, вы найдете этот пост полезным. Обратная связь высоко ценится.