Java演算法筆記: 衡量程式的速度

一個簡單的三層迴圈程式如下:

這個function相當於是找出一個集合中(用int[] a表示) 所有和為零的三個數。
當然以上就是所謂的brute-force方法，地毯式的搜索，我們如果實驗這段程式跑起來的時間，可以發現當N加倍的時候，完成的時間需要2^3倍:

這個圖形的方程式為

這個結果是可以預料到的，因為這相當於一個排列組合問題: C(n,3)，化簡的結果就是:

由於在N很大的時候，最高次方項目遠大於剩下所有較低次方項目的和 (微積分中的limit概念)，由於我們只關心程式所耗時間的在N很大時候的變化趨勢，不關心實際花費的時間 (現實生活中當然會比較關心)，所以可以用一個數學符號 ~ T(N) 來逼近T(N)，方便討論。

所以:

如果把~T(N)再抽出係數化簡的話，就可以得出 order of growth這個更精簡的方程式，主要是因為係數對T(N)圖形不產生改變，只是可能改變斜率或是開口的大小，-而且這個係數是會跟著硬體的增強而變小的，所以不是一個絕對的數字。


所以我們說count這個function的order of growth是N^3。


所以學習演算法的目標就是要努力降低一個程式的order of growth，由下圖中我們可以看到在NLogN (又稱為linearithmic)以上的order of growth已經不適合處理大量的input N:

在估算order of growth的時候，我們其實做了一些假設，但是一旦這些假設不成立的話，我們就無法得出一個order of growth的模型，可能發生的情況如下：

1. 如果program running time的數學方程式的低次項目的係數非常大，那這樣其實不能安心地用~T(N)來省略之，因為低次項目對running time的影響在N很大的時候還是顯著的。

2. 除了inner loop之外的code其實也花了大量的執行時間

3. OS系統運行的狀況會影響預估的執行時間

4. 問題的本質改變了，可能會讓一個可以依照input size N預估的模型變成N dependent，出現worst case/best case不同的情況。