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
2) , neboli T(n) = sum od 1 do k (T(a
i*n) + theta(n
d) tak vezmeme x jako reseni rovnice sum od 1 do k (a
ix) = 1 a pokud je:
1) x <> d --> T(n) = theta(n
max{x,d})
2) x = d --> T(n) = theta(n
d*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
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: