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

各位，不管考上的，還在努力的資訊前輩們，大家好。

小弟在研究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)

第二題，
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 次數，然後再回推答案。但是考試時，沒有電腦可以用呀。

每次遇到這種複雜的巢狀迴圈，就是等死，心有不甘。


忙讀書，無法一一回謝。先謝謝參與討論的人，你會更加進步的。
祝金榜題名。



--