103年高考資料結構第七題 - 考試

※ 引述《fcouple (皇家典藏20年禮炮)》之銘言：
: 各位，不管考上的，還在努力的資訊前輩們，大家好。
: 小弟在研究103年高考資料結構第七題時，碰到了一些問題，帶上來和大家討論，
: 也期盼能夠拋磚引玉，若有觀念不正確的地方，請前輩用力鞭打。
: 第一題，
: sum=0
: for(i=0; i<2*n; i++)
: for(j=0; j<i; j++)
: sum++;
: 可以計算出 sum 的執行次數為 (2n-1)*2n / 2
: 其 Big-O是 O(n^2)
: 但為何Θ也是Θ(n^2)，這點我比較不解。
: 我反問自己，那Ω notation又是多少呢? 回答不出來，該不會也是 Ω(n^2) 吧?
: 若如此，O、Ω、Θ 差在那? 不是應該要有「上限、下限、相等」的概念在裡面嗎?
: O、Ω、Θ 的定義看了又看，就是無法從定義去推出 Θ(n^2)
設f(n)=O(g(n))且f(n)=Ω(g(n))

by Big-O定義，得
f(n) <= c_1 x g(n)
by Big-Ω定義，得
f(n) >= c_2 x g(n)

可寫成
c_2 x g(n) <= f(n) <= c_1 x g(n)
與Θ定義一樣

f(n)恰好貼在g(n)的緊密上限，又恰好貼在g(n)的緊密下限，所以f(n)與g(n)複雜度相等
: 第二題，
: sum=0
: for(i=0; i<2*n; i++)
: for(j=0; j<i*i; j++)
: for(k=1; k<j; k++)
: if(j%i == 1)
: sum++;
: 考場上，有沒有「一定的程序、方法」去找出這種「非常複雜」的巢狀迴圈執行次數。
有「一定的程序、方法」
就是直接代數字
: 我在想，補習班寫解答的也沒那麼神，應該有先用電腦去跑程式，用 trace 的方式去
補習班寫解答應該也是照程式碼直接代數字求解
: print 次數，然後再回推答案。但是考試時，沒有電腦可以用呀。
: 每次遇到這種複雜的巢狀迴圈，就是等死，心有不甘。
: 忙讀書，無法一一回謝。先謝謝參與討論的人，你會更加進步的。
: 祝金榜題名。
代數字
i j k j%i sum
0 不執行
1 0 不執行
2 0 不執行
2 1 不執行
2 2 1 0不執行
2 3 1 1 1
2 3 2 1 2 i=2時，sum共計執行2次
3 2 1 2不執行
3 3 1 0不執行
3 3 2 0不執行
3 4 1 1 3
3 4 2 1 4
3 4 3 1 5 (.......小計3次)
3 5 1 2不執行
...
3 6 1 0不執行
...
3 7 1 1 6
3 7 2 1 7
3 7 3 1 8
3 7 4 1 9
3 7 5 1 10
3 7 6 1 11 (.......小計6次) i=3時，sum共計執行3+6次
3 8 1 2不執行
...
4 2 1 2不執行
4 3 1 3不執行
...
4 4 1 0不執行
...
4 5 1 1 12
4 5 2 1 13
4 5 3 1 14
4 5 4 1 15 (........小計4次)
4 6 1 2不執行
...
4 7 1 3不執行
...
4 8 1 0不執行
...
4 9 1 1 16
4 9 2 1 17
4 9 3 1 18
4 9 4 1 19
4 9 5 1 20
4 9 6 1 21
4 9 7 1 22
4 9 8 1 23 (........小計8次)
4 10 1 2不執行
...
4 11 1 3不執行
...
4 12 1 0不執行
...
4 13 1 1 24
4 13 2 1 25
...
4 13 12 1 35 (........小計12次) i=4時，sum共計執行4+8+12次
4 14 1 2不執行
...
4 15 1 3不執行
...
歸納可得，每個i，sum共計執行i+2i+3i+...+(i-1)i次
i,2i,3i,...,(i-1)i為等差數列(固定相差i)
代入等差公式，得
[i+(i-1)i] x (i-1) / 2 化簡為
(i^3 - i^2) / 2 ....每個i，sum執行次數
i範圍從0到2n-1，對i加總
2n-1 2n-1 2n-1
Σ (i^3-i^2) /2 = 1/2( Σ i^3 -Σ i^2)
i=0 i=0 i=0

=1/2 { {[0+(2n-1)]2n / 2}^2 - n(n+1)(2n+1)/6 }
...(請自行化簡)
n最大4次方，可得Θ(n^4)

--