Algorithm lecture 2

這一章節主要先以之前所學過的insertion sort當例子。開始解說如何分析一個程式的演算法。

首先，先從分析迴圈開始。initialization, maintenance, termination。三個部分構成一個迴圈。

以一個for迴圈為例：

for(j = 2 to A.length)
key = A[j]
i = j-1

Initialization: j等於2是否小於A這個陣列的長度。是第一次跑這迴圈。

Maintenance:每做一次迴圈，迴圈都會指向下一個陣列。

Termination:當A[j]超過陣列長度時會終止這個迴圈。

分析一個程式分析他的best case, worst case, average case。程式在執行的時候，當然有很多因素在影響。包括電腦的硬體，輸入的值...等等。worst case顧名思義，也就是說一個upper bound on the running time。而average case也往往跟worst case 的結果是一樣的。

設計一個演算法。這章節先大概介紹divide and conque。簡單的概念是把大問題劃分成小問題。解決小問題當然比大問題還簡單。等都解決之後再把結果湊起來，而大問題的解答也因此拼起來了。本章節是以merge sort來做範例說明。

最後用tree的概念。大致分析merge sort。(附在我下面的筆記)

These days

快要過一半的大學生活，我時常問我自己，在大學的日子裡我學到了什麼？

感覺上，我什麼都學了，但我沒有一樣是學的好的。我會寫C/C++，但不是很精通。我學了

Data Structure 但我還是不太會用。念了一點Html但我還是不會寫網站。借了Ruby on rails，但我

還是不會用它。說過要念很多東西的，可是沒有一樣唸起來的。學校成績也只有在中間，沒有達到

我所想像的。

說過要做很多事情的。可是我都沒做到。我覺得我很沒用...。跟別人比起來，我什麼都不會，就指出那一張嘴。我很想成為大大。嘴砲，每個人都做的到。用嘴巴做事情，人人都可以。為什麼每個人每天都是24小時。我卻得到的這麼少。為什麼別人可以學會那麼多課外的知識，但我卻連課內的功課都顧不好。想到這裡...我睡不著。無法好好入眠。

我需要的是改變。改變我的學習態度。改變我的時間規劃。改變才是進步的動力。很謝謝我的好朋友提醒了我。我的時間規劃出了問題，也很感謝他點出我學習上的障礙。我希望我可以成為一個厲害的人。

ps 希望早上起來，大家可以用icelorc.org連上我的部落格