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

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

	bool FindSum4(int[] ary, int target) {
	for (int i = 0; i < ary.length ; i++) {
	for ( int j = i + 1 ; j < ary.length ; j++) {
	if ( i != j )
	{
	int sum = ary[i] + ary[j];
	if ( sum == target ) {
	return true;
	}
	}
	}
	}
	return false;
	}

view raw Blog-12-1 hosted with ❤ by GitHub

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

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

	bool FindSum4(int[] ary, int target) {
	Dictionary<int,true> hash = new Dictionary<int,true>();
	for (int i = 0; i < ary.Length; i++) {
	int temp = target - ary[i];
	if (hash.ContainsKey(temp))
	return true;
	else {
	if (!hash.ContainsKey(ary[i]))
	hash.Add(ary[i],true);
	}
	}
	return false;
	}

view raw Blog-12-2 hosted with ❤ by GitHub

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

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

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