如何判別一個程式寫得好不好,可以用這個程式需要花費的記憶體,或是說要花多少時間才能解出答案,來判斷.因為現在硬體的價格很大眾化.所以我們可以專注在,時間上的討論. 有一個叫做Big-O的概念: 因為會影響時間的因素很多,因此這個概念主要是以討論程式執行的次數多寡來決定要花多少時間.一般我們都是採取比較嚴格的標準檢視程式,所以主要都是討論,在最差的情形下,這程式要花多少時間找出答案.
比如說
for (int i=0; i<n; i++) {
}
假如答案在最後一項,迴圈要跑到n-1,也就是最後一個才找到答案,我們用O(n),來表示這個迴圈要花線性時間來找出答案.
又如
answer=n*2;
因為答案只需要一次就找出來了,我們用O(1)來表示程式只需要常數時間就會找到答案
又若我們可以把數字排序後再來找答案,那麼所需要的時間只有一半而已.
假設1,2,3,4,用Binary Search只需要1~2次即可找出答案,所以可以用O(logN)
來表示只要對數的時間即可找出答案. 我們可以這麼去想, 4=2^2 ,以2為基底的log: log4=2;
所以把線性時間乘以2為基底的log,即為log N.
