Substitucni metoda

Úvodní přednáška o základních typech algoritmů a datových strukturách potřebných pro jejich implementaci.
Garett

Substitucni metoda

Příspěvek od Garett »

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
waseq123

Re: Substitucni metoda

Příspěvek od waseq123 »

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:
kolage

Re: Substitucni metoda

Příspěvek od kolage »

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(n2) , neboli T(n) = sum od 1 do k (T(ai*n) + theta(nd) tak vezmeme x jako reseni rovnice sum od 1 do k (aix) = 1 a pokud je:
1) x <> d --> T(n) = theta(nmax{x,d})
2) x = d --> T(n) = theta(nd*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:
Odpovědět

Zpět na „TIN060 Algoritmy a datové struktury I“