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

首先謝謝 ARCHERDEVIL 解惑，如今我也更確信定義，而不會去懷疑定義。

當然一開始我看您的回答，還是半解，於是我又查了國外幾個大學的投影片，終於懂了。
https://www.youtube.com/watch?v=DhhENikvNik
像這個，我看完後，整個疑惑就解了。

為了回饋與分享，兹將第一小題的作答過程寫出來：
(這是我照定義下去作答，不對也請各位用力鞭)

第一題，
sum=0
for(i=0; i<2*n; i++) .......... 1
for(j=0; j<i; j++) .......... 2
sum++; .......... 3

擬答：

1 --> 2n+1 次
2 --> (2n * 2n) / 2 次
3 --> (2n * (2n-1)) / 2 次

(2n * (2n-1)) / 2
乘開==> (4n^2 - 2n) / 2
化簡==> 2n^2 -n

設 f(n) = 2n^2 -n

第一，求 Big-O notation
取 C=3
得 2n^2 - n <= 3n^2
n^2 >= -n

∀ R 此不等式皆成立，n0 為 R (註：R在數學上指「實數」)
故 O(n^2) .... 找到 Big-O 囉

第二，求 Big-Ω notation
取 C=2
得 2n^2 - n >= 2n^2
n >= 0

只要為正的實數，此不等式皆成立，故 n0 為「正的實數」
(註：正的實數我不會用數學符號來表示，所以用中文)
故Ω(n^2) .... 找到 Big-Ω 囉

∵ f(n)=O(n^2) and f(n)=Ω(n^2)
∴ f(n) = Θ(n^2) 得證

不知道實戰考場，要不要寫這麼大堆? 就請有經驗的講一下吧。


-----------------------第一題作答結束騙p幣分隔線--------------------------


另外，再請教 A 大，您在解第二題時，將「if(j%i == 1)」指令忽略，直接將 k
的那層迴圈也當作 n 來看，這樣在閱卷那關，會給過嗎?

我怕的是這樣「還不夠說服力」，在閱卷就死了。
畢竟，那道 if 指令，有 ignore 的意思。



再謝謝 A 大，也謝謝有參與討論的同學，希望你們也都有收獲。
學問是越辯越明的，我不是要辯贏，而是要辯懂。如有冒犯，請多原諒。


※ 引述《ARCHERDEVIL (開弓)》之銘言：
: ※ 引述《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 平方減一
: 第三圈我應該不用解釋了吧？
: 這不需要用電腦跑一次
: 基本觀念建立好就好

--