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