作者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