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

Простое решение распространенных рецидивов Вам было сложно решить временную сложность повторяющихся отношений ? Я покажу вам, как быстро и легко решить некоторые из наиболее распространенных повторяющихся соотношений, не используя никаких других методов, кроме запоминания. Ниже приведены наиболее часто встречающиеся случаи. Примечание. a, b, d и k - постоянные значения. T(n) = T(n-1)+b, T(1) = a T(n) = O(n) T(n) = T(n-1) + bn, T(1) = a T(n) = O(n²) T (n) = T (n / 2) + b, T..