Проблема: у вас есть алгоритм, который делит задачу размера n на шесть подзадач размером четверть исходной. Для деления алгоритм делает 100 шагов, а для слияния 75n. Какова временная асимптотическая сложность алгоритма?
Итак, формула основной теоремы
и для этой задачи a = 6 и b = 4, но я не знаю, где разместить деление и объединить информацию.
Приемлемые результаты: O(n1,2924), omega(n< sup>1,2) и O(1,001n)
Каждый раз, когда вы решаете подзадачу, вы должны разделить текущий экземпляр на большее количество подзадач (стоимость = 100 шагов). Затем вам нужно объединить результаты подзадач (стоимость = 75n шагов).
Это означает f(n) = 75n + 100, потому что f(n) представляет стоимость решения одной подзадачи (исключая стоимость рекурсии).
f(n) = 75n + 100 is O(n).
Таким образом, вы смотрите на: T(n) = 6 * T(n/4) + O(n)
И мы знаем, что:
a = 6
b = 4
f(n) = 75n + 100
Далее вычисляем log_b(a) = log_4(6) = log(6)/log(4) = 1.2924...
Давайте рассмотрим случай I Главной теоремы:
Если f(n) = O(n^c) где c < log_b(a), то T(n) = Ө(n^(log_b(a)).
Мы знаем, что f(n) = O(n^1), попробуем c = 1.
c < log_b(a)? Ну, 1 < 1.2924..., так что да.
Таким образом, T(n) = Ө(n^(log_b(a)) => T(n) = Ө(n^1.2924...).
