Решение T(n) = 2T(n/2) + log n

Итак, мое рекурсивное уравнение T(n) = 2T(n/2) + log n

Я использовал главную теорему и обнаружил, что a = 2, b = 2 и d = 1.

это случай 2. Таким образом, решение должно быть O(n^1 log n), которое равно O (n log n)

Я посмотрел в Интернете, и некоторые нашли это O (n). Я смущен

Может ли кто-нибудь сказать мне, как это не O (n log n)?


algorithm time-complexity complexity-theory master-theorem
person asmazizou    schedule 27.10.2020    source источник
comment
Покажите мне угол python.   -  person greybeard    schedule 27.10.2020

Ответы (2)


arrow_upward
3
arrow_downward

Это должен быть не случай 2, а случай 1.

С T(n) = 2T(n/2) + log n критический показатель c_crit = log_2(2) = 1 как вы нашли, думаю правильно. Но, безусловно, log n является O(n^c) для некоторых c < 1, даже для всех 0 < c < 1, поэтому применяется случай 1, и все это O(n^c_crit) = O(n^1) = O(n).

person WorldSEnder    schedule 27.10.2020

arrow_upward
0
arrow_downward

Я не знаком с d в основной теореме. В статье в Википедии об Главной теореме говорится, что вам нужно найти c = log_b a, критический показатель. Здесь c = 1. Случай 2 требует, чтобы у нас было f(n) = Theta(n log n), но на самом деле у нас есть f(n) = log n. Вместо этого эта проблема попадает в случай 1 (посмотрите, сможете ли вы понять, почему!), что означает T(n) = Theta(n), как вы нашли в другом месте.

person Jace    schedule 27.10.2020
comment
я не понял, как log n может быть записан как n ^ чего-то - person asmazizou; 27.10.2020
comment
Помните, что функция, являющаяся O(n), означает, что функция ограничена константой, кратной n. Ограничено ли log n сверху константой, кратной n? Попробуйте изобразить их в виде графика на desmos.com/calculator. - person Jace; 27.10.2020