作者polomoss (小泽)
看板Grad-ProbAsk
标题[理工] [资结]-复杂度计算
时间Mon Dec 14 21:55:40 2009
1. θ(n) + O(n) = θ(n) , why?
2. Ω(n) + O(n) = Ω(n) , why?
94台大资工
3.
(log1)^2 + (log2)^2 + ..... + (logn)^2 = θ(nlog^2n)
4.
k^2(logk)^3 =θ(n^3log^3n) k=1~n 跟第三题一样
想请问: 一、它给的答案是用积分 ∫(从1到n/2) <= 所求 <=∫(从1到n)
为什麽要用这样去夹击~?
之後要算这种题目，只要这样去夹击一定对吗~?
二、我不会积log..............
翻了书没找到怎麽积分，可以教一下吗~?
谢谢，解答是直接用ln来积分，但看不懂~
--
┌这篇文章让您觉得？─────────────────────────────┐
│ │
│ 一"一 \ / >\\\< ╯ ╰ ∩ ∩ ▁ ▁ ＞＿＜ ㄧ ㄧ+ │
│ 皿 ε □ ▽ ▇Δ ▇ ╰╯ ╯ │
│ 北七 乱喔 害羞 莎笅 爽啦 哭爸 ＸＤ 科科 │
└──────────────────────────────────────┘
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 122.116.14.2
1F：推 windysoul:第三跟第四一样 可以用(n/2)log^2(n/2)<=...<=nlog^2n 12/15 00:56
2F：→ windysoul:(n/2)(n/2)^2*log^3(n/2)<=原式<=n*n^2*log^3n 12/15 00:57
3F：→ windysoul:其中的log^2n表示logn的平方 以此类推 12/15 00:58
4F：推 SILBERSCHATZ:1. O(n)是理论上限 Ω(n)是理论下限 12/15 08:38
5F：→ polomoss:还是不懂... 12/15 10:45
6F：→ doom8199:前两题套定义下去证明 12/15 12:45