作者p7pp7 (經驗法則)
看板Prob_Solve
標題[問題] 計算時間複雜度
時間Wed Oct 5 21:25:59 2011
請問
1.f(n) = 10n^2 + 4n + 2
2.Let T(n) = Θ(f(n))
T(n) = 1 + 1/2 + 1/3 + ... + 1/n
想請問這兩題的時間複雜度
第一題我算出來是O(n^2)應該沒錯吧@@
不過第二題真的完全沒頭緒
想請各位幫忙
感謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.47.123.252
1F：推 suhorng:1沒錯 2是Θ(log n), 這個可以從∫1/x dx來看 (上/下界) 10/05 21:31
2F：→ suhorng:或是單純每次取 2, 4, 8, 16, 32, ... 項, 看上下界 10/05 21:31
3F：→ bigbite:harmonic series, 去google一下應該就有了 10/05 22:57