#12 利用 Hash Table 來改進 FindSum4()

在 #2 的文章裡曾寫到 FindSum4() 的 Optimization 寫法，其程式碼再重新呈現如下：

當時我們用了 if ( i != j ) 的方式來做為一種 Optimization 的做法，當 ary 的元素越來越多時，整個程式的時間複雜度還是會往 O(n²) 靠近．理論上，這樣程式的時間複雜度還是 O(n²)．

先前的文章介紹了 Hash function 的好處，我們可以運用 Hash 的概念在這一個程式，

(以上是C#程式碼) 整個程式是 O(n).

從時間複雜度的角度來看，我們利用 hash 將程式的 O(n²) 變成 O(n)，而付出的代價是什麼呢 ? 付出的代價就是我們使用了 hash 在記憶體上的空間，最上面的程式是不需要有特別額外的記憶體空間，但第二個程式使用 hash 付出了 O(n) 的空間複雜度，這種用空間換取時間的情況在軟體的世界是非常常見的，因為在大部份的情況下我們比較在乎程式能在多久的時間內完成．

希望這個用 hash 來改進程式空間複雜度的例子能夠激發出你在日常工作上的想像力．