Да предположим, че имам случай като 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 от експонентата, показва, че работата на ниво трябва да нараства строго асимптотично по-бавно от скоростта на разделяне и трябва да го прави с някаква полиномиална сума.
Надявам се това да помогне!
person
templatetypedef
schedule
01.02.2012
