# Substitucni metoda

<{ForumPost(poster="Garett", timestamp=2009-06-22 14:29:34)}>
Ahoj, pořád si nějak nejsem jistej s dokazováním složitosti přes substituční metodu :oops: . Mohla by mi nějaká dobrá duše prozradit jak se má v správně postupovat v tomto příkladu?  
  
substitucni metodou dokazte ze slozitost T(n)=3T(n/3)+T(2n/3)+bn  
je O(N^2)  
  
Předem díky
<{/ForumPost}>

<{ForumPost(poster="waseq123", timestamp=2010-06-09 15:05:36)}>
Ahoj,  
jenom nástřel:   
1) musíš vědět (uhodnout) složitost              -- v tomto případě ano  
2) pak jdeš na to indukcí   
Aspoň tak je to na Čepkovo slajdech. Snad to bude k něčemu. :wink:
<{/ForumPost}>

<{ForumPost(poster="kolage", timestamp=2010-07-02 12:05:24)}>
Taky jsem to dlouho hledal a myslim ze jsem nasel jak na to...  
  
Pokud je rekurentni rovnice typu T(n) = T(n/2) + 2T(n/3) + O(n<sup>2</sup>) , neboli T(n) = sum od 1 do k (T(a<sub>i</sub>*n) + theta(n<sup>d</sup>) tak vezmeme x jako reseni rovnice sum od 1 do k (a<sub>i</sub><sup>x</sup>) = 1 a pokud je:  
1) x <> d --> T(n) = theta(n<sup>max{x,d}</sup>)  
2) x = d --> T(n) = theta(n<sup>d</sup>*log n)  
  
Je to takova rozsirena verze master theoremu, pak se klasicky odhad vezme a dokaze substitucni metodou. Nasel jsem to na nejakych strankach a zkousel jsem, ze to funguje, tak snad to nekomu pomuze  :wink:
<{/ForumPost}>