Основная теорема предоставляет четкий способ определения времени выполнения широкого спектра алгоритмов «разделяй и властвуй» с помощью тета-нотации (с жестким верхним и нижним ограничением времени выполнения в худшем случае). Время выполнения многих алгоритмов «разделяй и властвуй» на входе размера n можно выразить с помощью рекуррентного уравнения T (n). Предположим, что у нас есть:
- Для достаточно малого ввода T (n) является постоянным.
- Для достаточно большого ввода T (n) = a * T (n / b) + f (n), где a - это число подзадач, к которым рекурсивно вызван алгоритм, каждая подзадача имеет размер n / b и общее количество нерекурсивных накладных расходов это f (n) . Нерекурсивные издержки - это то, что алгоритм тратит на шаг деления и шаг завоевания.
Теперь рассмотрим также критическую функцию: n ^ (log_b (a)), то есть n для мощность базы журнала б а. Учитывая рекуррентное уравнение, вы можете рассчитать, что это такое, потому что вы знаете, что такое a и b.
Основная теорема в основном гласит:
- Если f (n) полиномиально меньше, чем n ^ (log_b (a)), то алгоритм работает во времени, пропорциональном n ^ (log_b (a)).
- Если f (n) = n ^ (log_b (a)), то алгоритм выполняется за время, пропорциональное n ^ (log_b (a)) * log (n)
- Если f (n) полиномиально больше, чем n ^ (log_b (a)), то алгоритм выполняется за время, пропорциональное f (n).
Обратите внимание, что не все алгоритмы «разделяй и властвуй» имеют время выполнения, которое можно записать в этой форме для некоторых a , b , и f (n) , но многие из них могут - включая бинарный поиск.
Бинарный поиск принимает ввод размера n, тратит постоянное количество не -рекурсивные накладные расходы, сравнивающие средний элемент с искомым элементом, разбивают исходный ввод на половину и рекурсивные только для одной половины массива. Теперь включите это в основную теорему с a = 1, подзадачами размера n / b, где b = 2, и нерекурсивными накладными расходами f (n) = 1. Вычислить критическую функцию n ^ (log_b (a)) = n ^ (log_2 (1)) = n ^ 0 = 1. Итак, теперь мы сравним f (n) = 1 с критической функцией n ^ (log_b (a) ) = 1. Они равны, поэтому мы в случае 2 основной теоремы. Следовательно, общее время работы пропорционально n ^ (log_b (a)) * logn = logn.