Põhiteoreem (koos näidetega)

Lang L: none (table-of-contents)

Põhiteoreem
Lahendatud näide põhiteoreemist
Peamine teoreemi piirangud

Selles õpetuses saate teada, mis on põhiteoreem ja kuidas seda kasutatakse kordussuhete lahendamiseks.

Põhimeetod on vormi korduvussuhete lahendamise valem:

T (n) = aT (n / b) + f (n), kus, n = sisendi suurus a = rekursioonis olevate alamprobleemide arv n / b = iga alamprobleemi suurus. Eeldatakse, et kõigil alamprobleemidel on sama suurus. f (n) = väljaspool rekursiivset kõnet tehtud töö maksumus, mis sisaldab probleemi jagamise ja lahenduste ühendamise kulu Siin on a ≧ 1 ja b> 1 konstandid ja f (n) on asümptootiliselt positiivne funktsioon.

Asümptootiliselt positiivne funktsioon tähendab, et piisavalt suur n väärtus on meil olemas f(n)> 0.

Peamist teoreemi kasutatakse korduvussuhete (jagamise ja vallutamise algoritmide) ajalise keerukuse arvutamiseks lihtsal ja kiirel viisil.

Põhiteoreem

Kui a ≧ 1ja b> 1on konstandid ja f(n)on asümptootiliselt positiivne funktsioon, siis rekursiivse seose aja keerukuse annab

T (n) = aT (n / b) + f (n) kus, T (n) on järgmised asümptootilised piirid: 1. Kui f (n) = O (n ^{log _b a-ϵ} ), siis T (n ) = Θ (n ^{log _b a} ). 2. Kui f (n) = Θ (n ^{log _b a} ), siis T (n) = Θ (n ^{log _b a} * log n). 3. Kui f (n) = Ω (n ^{log _b a + ϵ} ), siis T (n) = Θ (f (n)). ϵ> 0 on konstant.

Kõiki ülaltoodud tingimusi võib tõlgendada järgmiselt:

Kui alamprobleemide lahendamise hind igal tasandil tõuseb teatud teguri võrra, muutub väärtus f(n)polünoomiliselt väiksemaks kui . Seega rõhub aja keerukust viimase taseme maksumus st.n^{log_b a}n^{log_b a}
Kui kulud lahendamiseks sub-probleem igal tasandil on peaaegu võrdne, siis väärtus f(n)on . Seega saab aja keerukus korrutada tasemete koguarvu st.n^{log_b a}f(n)n^{log_b a} * log n
Kui alamprobleemide lahendamise maksumus igal tasandil väheneb teatud teguri võrra, muutub väärtus f(n)polünoomiliselt suuremaks kui . Seega surub aja keerukus alla maksumus .n^{log_b a}f(n)

Lahendatud näide põhiteoreemist

T (n) = 3T (n / 2) + n2 Siin a = 3 n / b = n / 2 f (n) = n ² log _b a = log ₂ 3 ≈ 1,58 <2 st. f (n) <n ^{log _b a + ϵ} , kus, ϵ on konstant. Juhtum 3 tähendab siin. Seega T (n) = f (n) = Θ (n ² )