Понимание лямбды как она применима к основной теореме
Предположим, что у меня есть случай, подобный T(n)=2T (n/4)+1. f (n)=1 a=2 и b=4. Таким образом, n^(1/2)>1. Это должен быть случай 1. Однако существует также лямбда в случае 1, так что f(n)=O (n^(1/2)-лямбда)) для некоторой лямбды >0. В этом случае лямбда будет 1/2?
1 ответ:
Да, это верно. Заметим, что в этом случае мы имеем, что a = 2 и b = 4. Функция f (n) в этом случае равна 1, и мы имеем, что 1 = Θ(n1/2 - ε) для некоторого ε > 0, где в этом случае ε = 1/2. Следовательно, по основной теореме вы получите, что T (n) = Θ (n1/2).
Суть этого ε заключается в том, что если объем работы, выполняемой на уровне, достаточно мал (ниже logb a), то работа доминирует в основном за счет расщепления, а не за счет работы на уровне уровень. Тот факт, что вы можете вычесть ε > 0 из экспоненты, указывает на то, что работа на уровне должна расти строго асимптотически медленнее, чем скорость расщепления, и должна делать это на некоторую полиномиальную величину.
Надеюсь, это поможет!