Учитывая уравнение 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. Спасибо за подробный ответ, это очень помогло мне! – optional