Доказывая нижнюю границу рецидива путем преобразования базы

Question

журнала Там проблема в «Введении в Алгоритмы», который говорит: (4.4-6)

Утверждают, что решение рецидива T(n) = T(n/3) + T(2*n/3) + cn
где c является константа равна Ω (n log n) путем обращения к дереву рекурсии.

Я использую дерево рекурсии и, наконец, получаю T(N) >= n log3n.
Я не знаю, следующий шаг, чтобы показать, что T(N) >= n log2n,
я Googled его и как-то я чувствую что-то не так с ответами, потому что они говорят, когда T(N) >= n log3n затем T(N) >= n log2n (но log3n не больше log2n).

Answer 1

В асимптотических пределах, основание логарифма не имеет значения, так как это только константа variation.This происходит из-за изменения базы в логарифме.

журнал х = войти _б х/б _войти

Вот почему люди не подписывают базу в асимптотических границах.

Answer 2

the definition of big omega Напомним: f(n) в Omega(g(n)), если f ограничена снизу g асимптотически. Или, если вам это нравится больше Mathy:

Давайте определим f(n) = n * log_3(n) и g(n) = n * log_2(n).

Теперь, если мы сможем найти постоянную c так, чтобы f(n) > c * g(n), то мы показали, что f(n) находится в Omega(g(n)).

log_3(n) = log_2(n)/log_2(3) 
    log_2(3) ~= 1.585 < 2 
=> log_3(n) > 2 * log_2(n) 
=> n * log_3(n) > 2 * n * log_2(n) 
=> f(n) > c * g(n) 

для нашего выбранного значения c = 2 (Вы можете, конечно, выбрать любое другое значение, пока c > log_2(3).