Учитывая уравнение T(n)=sqrt(2)T(n/2)+log(n).Решая рекуррентность: T (n) = sqrt (2) T (n/2) + log (n)
Решение указывает на случай 1 М.Т. с классом сложности O (sqrt (n)). Однако после моего понимания log (n) многочлен больше, чем sqrt (n). Я что-то упускаю?
Я использовал определение следующим образом: n^e = log_b (a), где a = sqrt (2) и b = 2. Это дало бы мне e = 1/2 < 1. log n, очевидно, многочлен больше, чем п^е.
Номер журнала х п не больше, чем √n.
Рассмотрим n=256,
√n = 16,
и
Журнал 2 256 = 8 (допустим базу x=2, как и многие из вычислительных задач).
В вашем рецидиве,
T(n)= √2 T(n/2) + log(n)
a = √2, b = 2 and f(n) = log(n)
журнала б а = войти √2 = 1/2.
Поскольку журнал п < п , для a > 0, мы имеем случай 1 Мастера теоремы.
Идет для T(n) = Θ(√n).
Используя теорему мастера, вы получаете: a=sqrt(2), b = 2 и, следовательно, c = logb(a) = 1/2. Ваш f(n) = log(n) и, следовательно, вы попадаете в первый случай.
Так что ваша сложность O(sqrt(n))
Мой плохо только для тестирования несколько низких чисел вместо фактически смотря на то, что произойдет, если мы используем большой N. Спасибо за подробный ответ, это очень помогло мне! – optional