Публикации по теме 'recurrence-relation'
Анализ основной теоремы, часть 2: доказательство
Часть 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..