演算法的細緻之處…

在 LeetCode 上有個簡單的題目：Two Sum [1]，題目很單純，就是給定一個陣列以及一個目標值，找出能夠滿足相加會等於目標值的兩個數字。

這個問題最容易想到的自然是暴力破解，暴力破解的複雜度是 O(n²)。而另一種想法大概是左右逼近，但這存在一個前提是陣列必須是已排序的陣列，所以考慮排序的話，複雜度會是 O(nlogn)（實際來說複雜度可能是 O(nlogn + 2n) 吧）。然後如果有想到可以用空間換取時間的話，利用 HashMap 就可以達到 O(n)。

接著三種解法都送出的話，想像上效能應該是 O(n) > O(nlogn) > O(n²)，不過實際上呢？（但我沒有嘗試送出 O(nlogn) 的版本，所以時間直接引用 [2]）

1. O(n²) - Your runtime beats 29.85 % of java submissions.
2. O(n) - Your runtime beats 49.89 % of java submissions.
3. O(nlogn) - Your runtime beats 98.85 % of java submissions. [2]

結果實際上是 O(nlogn) 的效能最好。

話說如果稍微有在研究演算法的話，應該很容易可以想像到原因是什麼吧。因為在 1ms 也要追究的情境時，建立物件是很耗時的行為。另外更重要的原因在於，HashMap 的存取並非沒有代價的呀，在 Java 8 中它的實作用到了紅黑樹 [3-4]，每次的存取都是 O(logn) 的效率，因此表面上用 HashMap 的解法複雜度是 O(n)，實際上它依然是 O(nlogn)～。

這裡有感而發的地方是在於…當毫秒必爭的時刻，演算法其實會很吃語言的熟悉度，用什麼語言來實作是會有差的。就像在這個例子中，對於 Java 不熟悉的人會覺得 HashMap 的操作應該要是 O(n) 複雜度，但結果它並不是。此外，這其實也讓我想起在演算法技術手冊 [5] 這本書的開頭看到的一段描述，大意是在說，雖然我們在衡量演算法的時候會用 big O 來表示複雜度，但這其實是一種不怎麼精確的衡量手法。big O 當中假設當 n 無限大的時候，其他常數都可以被忽略，但現實中 n 大多都不是無限大，也就是說在現實環境下，常數有可能是不能被忽略的重要因子。因此在現實上，O(nlogn) 的演算法是有可能跑得比 O(n) 的演算法還快的，例如 O(nlogn) 實際的執行次數是 nlogn + n/2，而 O(n) 的實際執行次數是 10n，當 n=32 的時候，nlogn + n/2 = 32 x 5 + 16 = 176、10n = 10 x 32 = 320，此時 O(nlogn) 的演算法就比 O(n) 的演算法還快將近一倍了。

參考資料

1. Two Sum
2. Java, O(nlogn), beats  98.85%
3. HashMap Java 8 implementation
4. 紅黑樹詳細分析，看了都説好
5. 演算法技術手冊