[理工] [資結]-複雜度計算

[polomoss (小澤)]

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
推 windysoul:第三跟第四一樣  可以用(n/2)log^2(n/2)<=...<=nlog^2n
→ windysoul:(n/2)(n/2)^2*log^3(n/2)<=原式<=n*n^2*log^3n
→ windysoul:其中的log^2n表示logn的平方   以此類推
推 SILBERSCHATZ:1. O(n)是理論上限 Ω(n)是理論下限
→ polomoss:還是不懂...
→ doom8199:前兩題套定義下去證明