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)，這點我比較不解。
big oh 是說最壞狀況他要跑幾次
big omaga 是說最好狀況下他可以只跑幾次就完成

big theta 是說當你有一個f(v)的時候
如果f(v)的big oh 、big omaga可以導出一樣的值
則big theta存在

這一題big oh 大概不用解釋
big omaga的部分，如果你可以在x1跟c都存在的狀況下找到

f(x)>=c*g(x)的成立狀況，那就成立

注意，是不管大於或等於都可以。

公式套用的部分你自己算就好，應該不是太難

你會發現它的確存在big o = big omaga的狀況


: 我反問自己，那Ω 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 次數，然後再回推答案。但是考試時，沒有電腦可以用呀。
: 每次遇到這種複雜的巢狀迴圈，就是等死，心有不甘。
: 忙讀書，無法一一回謝。先謝謝參與討論的人，你會更加進步的。
: 祝金榜題名。

第一圈最多是2n
第二圈是n*n
第三圈是n

全部乘起來答案就出來了

第一圈我應該不用解釋
第二圈從零開始，然後每次都到 i*i
你把 第二圈的i 當成 n，那就是每次都從0 到 n 平方減一

第三圈我應該不用解釋了吧？

這不需要用電腦跑一次
基本觀念建立好就好


--