T(n) = T(n/3) + 3T(n/4) + 3n ?

[kavos]

Kód: Vybrat vše

T(n) = T(n/3) + 3T(n/4) + 3n

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.

[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).

[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

[nardew]

indukcia pre n.log n vyjde, cize podla mna to ma byt Theta(n.log n)