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不同的情況。

Android支援多種螢幕大小和螢幕密度

Android device實在是亂成一團！不搞清楚怎麼正確在各種螢幕大小與螢幕密度的話，真的會一個頭兩個大！

Screen size

是指device真正的物理尺寸，例如對角線長度為五寸的手機，其screen size就是5寸。Android api把物理尺寸分成四個等級: small, normal, large, extra-large。不過在API 13以上，這個等級就已經deprecated，詳見Android文件。

每個等級有定義出最小的虛擬解析度（螢幕上能夠表現出的dp總數）：
xlarge >= 960dp x 720dp
large >= 640dp x 480dp
normal >= 470dp x 320dp
small >= 426dp x 320dp

Screen density

螢幕密度是指螢幕在某個物理尺寸內所能表現的pixel數量，所以是密度的概念，通常稱為dpi (dots per inch)。 Android把螢幕密度分成五個等級：low, medium, high, extra-high, extra-extra-high, extra-extra-extra-high。 （Google工程師真的有比較聰明嗎？看這命名...)

Resolution

解析度通常會跟螢幕密度搞混了，這是指一個螢幕「所有」能表現的pixel數目，是總量的概念，不是密度的概念，通常程式中不會直接面對resolutoin。

Density-independent pixel (dp)

這是一個虛擬的pixel單位，讓我們定義UI的時候，不用去考慮螢幕密度的問題。1dp相當於medium screen density (160dpi)時的一個pixel大小 （白話文就是 當你的螢幕每一英吋能表現160個pixel的時候，這時候一個pixel就可以稱為1dp）。Android runtime會自動做縮放補償，例如一個長度為1dp的image，如果在mdpi的螢幕上，那就剛好用一個pixel表現，但是如果在240dpi的螢幕上，就需要用 (240/160) * 1dp = 1.5個pixel來「補償」放大原本1pixel的區域。


知道了以上的名詞定義，我們可以簡單列出兩個螢幕之間的關係：
如果螢幕A和螢幕B有相同解析度，而且螢幕A的尺寸比螢幕B大的話，那按照定義螢幕A的dpi值一定小於螢幕B的dpi值，這是簡單的數學，也可以說螢幕A的一個pixel的物理尺寸是大於螢幕B的一個pixel的物理尺寸。

如果只用pixel當UI單位的話有什麼問題？

如果用pixel當單位的話，就會在不同的density螢幕中看到依照兩者density的倍數縮放的widget，這會造成widget在較低的dpi螢幕上的物理尺寸變大，而在較高dpi螢幕上物理尺寸較小。舉例來說，一張160 pixel x 160 pixel的影像，在160dpi我們看到的實際尺寸是1 inch x 1 inch，但是在420dpi的螢幕上，1 inch相當於420個pixel的寬度，所以160個pixel的長度會變成 160/420 inch，反之在較低dpi螢幕上（例如80dpi)會變成看到160/80 inch的長度。

有時候這不會不好，如果兩者的解析度一樣的話就只是等比例縮放而已，但是通常解析度不會一樣，這時候dpi的差距常會造成usability的問題，例如按鈕變得太小按不到，或是widget變得太大超出螢幕範圍。

如何達成在各種screen density螢幕中正確表現？

由上可知，在UI中使用dp當作單位的好處就是，在不同的density螢幕中，android runtime會把這個因為單一pixel物理尺寸不同所造成的widget膨脹或縮減作物理尺寸的補償，這會讓使用者看到近似的物理尺寸的widget。

不過這還是會造成一些問題，如果在大螢幕(例如tablet)上的UI用了實際尺寸較大的widget，到小螢幕時還是會一樣大！ 所以如果螢幕大小差距太大時，兩者需要不同的layout file，不能依賴android runtime縮放來保證usability。另外一個問題是android runtime自動放大補償的時候，圖像品質就會下降。

所幸android支援alternative configuration給不同的density不同的bitmaps/layout，也就是我們常會在layout和drawables目錄下看到各種xhdpi, xxhdpi目錄的原因。不過現在已經改成要用sw<N>dp configuration qualifier了，之前講的screen size定義在API level 13以後都deprecated。