Алгоритмы: основная теорема

Основная теорема может использоваться для решения рекуррентных отношений, таких как T(n)= aT(n/b)+f(n).

Итак, если f(n)=O(n) или f(n)=cn оба значения одинаковы? Могу ли я использовать основную теорему для f(n)=cn также?


algorithm master-theorem asymptotic-complexity
person pratik watwani    schedule 18.05.2016    source источник
comment
Такие константы, как c, часто игнорируются при рассмотрении асимптотических соотношений. Это связано с тем, что по мере того, как n становится достаточно большим, константа очень затрудняет расчет потребления памяти и времени выполнения. Это означает, что f(n)=n эквивалентно f(n)=O(n).   -  person Evan Bechtol    schedule 18.05.2016

Ответы (2)


arrow_upward
3
arrow_downward

Предполагая, что c является константой и что я правильно понимаю ваш вопрос, решение будет одинаковым как для f(n) = O(n), так и для f(n) = cn, поскольку cn = O(n) и, следовательно, основную теорему можно применить для решения повторяемости.

person mort    schedule 18.05.2016

arrow_upward
2
arrow_downward

Если я правильно понял вопрос, f(n)=cn (где c — константа) находится в O(n); основная теорема может быть применена.

person Codor    schedule 18.05.2016