# 4) + 3n  ?

<{ForumPost(poster="kavos", timestamp=2005-07-03 21:29:55)}>


    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.
<{/ForumPost}>

<{ForumPost(poster="univ", timestamp=2007-05-29 12:39:37)}>
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).
<{/ForumPost}>

<{ForumPost(poster="Flamingdog", timestamp=2007-06-17 15:39:31)}>
a co s tim 3n na konci? :roll:  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
<{/ForumPost}>

<{ForumPost(poster="nardew", timestamp=2007-06-25 02:03:25)}>
indukcia pre n.log n vyjde, cize podla mna to ma byt Theta(n.log n)
<{/ForumPost}>