У овом упутству ћете научити шта је главна теорема и како се користи за решавање релација понављања.
Главна метода је формула за решавање релација понављања облика:
Т (н) = аТ (н / б) + ф (н), где је, н = величина улаза а = број потпроблема у рекурзији н / б = величина сваког потпроблема. Претпоставља се да сви подпроблеми имају исту величину. ф (н) = трошак посла обављеног изван рекурзивног позива, који укључује трошкове поделе проблема и трошкове обједињавања решења Овде су а ≧ 1 и б> 1 константе, а ф (н) је асимптотички позитиван функцију.
Асимптотички позитивна функција значи да за довољно велику вредност н имамо f(n)> 0.
Главна теорема се користи за израчунавање временске сложености односа понављања (алгоритми подели и освоји) на једноставан и брз начин.
Мастер теорема
Ако су a ≧ 1и b> 1константе и f(n)је асимптотички позитивна функција, тада је временска сложеност рекурзивне релације дата са
Т (н) = аТ (н / б) + ф (н) где Т (н) има следеће асимптотске границе: 1. Ако је ф (н) = О (н лог б а-ϵ ), тада је Т (н ) = Θ (н лог б а ). 2. Ако је ф (н) = Θ (н лог б а ), тада је Т (н) = Θ (н лог б а * лог н). 3. Ако је ф (н) = Ω (н лог б а + ϵ ), тада је Т (н) = Θ (ф (н)). ϵ> 0 је константа.
Сваки од горе наведених услова може се протумачити као:
- Ако се трошкови решавања подзадатака на сваком нивоу повећају за одређени фактор, вредност од
f(n)постаће полиномски мања од . Дакле, временску сложеност потлачују трошкови последњег нивоа, тј.nlogb anlogb a - Ако су трошкови решавања под-проблема на сваком нивоу приближно једнаки, тада ће вредност
f(n)бити . Тако ће временска сложеност бити помножена са укупним бројем нивоа тј.nlogb af(n)nlogb a * log n - Ако се трошкови решавања потпроблема на сваком нивоу смање за одређени фактор, вредност од
f(n)постаће полиномски већа од . Дакле, временску сложеност потлачују трошкови .nlogb af(n)
Решени пример мастер теореме
Т (н) = 3Т (н / 2) + н2 Овде је а = 3 н / б = н / 2 ф (н) = н 2 лог б а = лог 2 3 ≈ 1,58 <2 тј. ф (н) <н лог б а + ϵ , где је ϵ константа. Случај 3 овде подразумева. Дакле, Т (н) = ф (н) = Θ (н 2 )
Ограничења главне теореме
Главна теорема се не може користити ако:
- Т (н) није монотон. на пример.
T(n) = sin n f(n)није полином. на пример.f(n) = 2n- а није константа. на пример.
a = 2n a < 1
