Stránka 1 z 1
T(n) = T(n/3) + 3T(n/4) + 3n ?
Napsal: 3. 7. 2005 21:29
od kavos
hm, predposledni termin se blizi a ja porad nevim, kolik ma vyjit tohle. Uvaha "oba logaritmy jsou mensi jak jedna, tak vyhraje 3n a je to linearni" asi nebude spravna, nebot napriklad T(n) = T(n/2) + T(n/2) + n zrejme linearni neni.
Nevite nekdo co s tim?
Diky, kav.
reseni
Napsal: 29. 5. 2007 12:39
od univ
Nejprve si vyjadris T(n) jako n^x a resis rovnici bez 3n na prave strane,
tj.: T(n) = T(n/3) + 3T(n/4)
Hledas nejvetsi x, ktere pro vsechna n splnuje:
n^x = (n/3)^x + 3(n/4)^x
1 = 1/(3^x) + 3/(4^x) = L(x)
Pro x>=2 je L(x) < 1.
Pro x=1 je L(x) > 1.
Maximalni x, ktere splnuje tuto rovnici, je teda v otevrenem
intervalu (1;2).
Protoze x > 1, tak vysledek je, ze T(n)=theta(n^x) .
Je divny, ze x vychazi tak blbe, tj. ze to neni nejake pekne cislo,
napr. 1 nebo 2. Mozna byla chyba v zadani zkousky.
Kdyby x bylo 1, pak by T(n)=theta(n*log n).
A kdyby x bylo < 1, tak by T(n)=theta(n).
Napsal: 17. 6. 2007 15:39
od Flamingdog
a co s tim 3n na konci?
to jako že je to jen n na první, tak potom je odůvodnění "protože x > 1"? a že to n je vynásobený trojkou je jedno? dikes
Napsal: 25. 6. 2007 02:03
od nardew
indukcia pre n.log n vyjde, cize podla mna to ma byt Theta(n.log n)