→ ilcic:n/(2^k)=1 k = lg(n) 01/27 01:12
推 byakuinss:樓上正解 01/27 15:16
忘記還有一題...雖然很基本 但我是硬背的 想知道原因
T(n)= T(n/2) + 1 , T(1)=1
Ans:
T(n)= T(n/2) + 1
= T(n/4) + 2
= T(n/8) + 3
= T(n/16)+ 4
.
.
.
= T(n/n) + logn <= 為何是logn 怎麼來的@@
= 1 + logn
O(logn)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 42.73.214.209