電腦科學 ^ IT人生 ^ 公益課程

#12 利用 Hash 來改進 FindSum4()

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



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

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



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

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

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

Share: