[問題] 計算時間複雜度

看板Prob_Solve作者 (經驗法則)時間12年前 (2011/10/05 21:26), 編輯推噓1(1推 0噓 2→)
留言3則, 2人參與, 最新討論串1/4 (看更多)
請問 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
推
10/05 21:31, , 1F
1沒錯 2是Θ(log n), 這個可以從∫1/x dx來看 (上/下界)
10/05 21:31, 1F
→
10/05 21:31, , 2F
或是單純每次取 2, 4, 8, 16, 32, ... 項, 看上下界
10/05 21:31, 2F
→
10/05 22:57, , 3F
harmonic series, 去google一下應該就有了
10/05 22:57, 3F
‣ 更多 p7pp7 的文章
文章代碼(AID): #1EZ5hgNh (Prob_Solve)
‣ 更多 p7pp7 的文章
文章代碼(AID): #1EZ5hgNh (Prob_Solve)