Понимание лямбда в применении к основной теореме

Question

Предположим, у меня есть случай, подобный T (n) = 2T (n / 4) +1. f (n) = 1 a = 2 и b = 4. Таким образом, п ^ (1/2)> 1. Это должно быть в случае 1. Однако в случае 1 также существует лямбда, так что f (n) = O (n ^ ((1/2) -lambda)) для некоторой лямбды> 0. В этом случае лямбда будет 1/2?

Answer 1

Да, это правильно. Обратите внимание, что в этом случае мы имеем, что a = 2 и b = 4. Функция f (n) в этом случае равна 1, и мы имеем, что 1 = & Theta; (n ^{1/2 - & epsilon;} ) для некоторых & epsilon; > 0, где в этом случае & epsilon; = 1/2 Следовательно, по основной теореме вы получите, что T (n) = & Theta; (n ^1/2 ).

Суть этого & epsilon; заключается в том, что если объем работы, выполненной на уровне, достаточно мал (ниже log _b a), то в работе преобладает разделение, а не работа на уровень. Тот факт, что вы можете вычесть & epsilon; > 0 от показателя степени указывает, что работа на уровне должна расти строго асимптотически медленнее, чем скорость расщепления, и должна делаться на некоторое полиномиальное значение.

Надеюсь, это поможет!