|
3 Divide and Conquer 假設多邊形的頂點 ,用 標識n+1邊的圖多邊形分成三角形的個數。 選擇一條邊作為基邊，例如邊 ，從頂點 到 中選擇一個頂點與邊 構成三角形，這樣就把多邊形分為三個區域 ， 為剩余的多邊形部分，那么 區域有k+1條邊， 有n-k+1條邊，根據排列組合的乘法原則，此分法的不同三角形的分法有 ,而三角形頂點的選擇可以從頂點 到 中任意選擇一個，根據排列組合的加法原則 。 已知 ,所以可以根據遞推算出 的結果。 偽代碼如下 Int triangleCount(intedgeCount) { If(edgeCount == 1) Return 1; If(edgeCount == 2) Return 2; Else { sum = 0; For i = 1: n-1 sum = sum + triangleCount(i) * triangleCount(edgeCount -i); return sum; } 時間復雜度分析 主要操作在 ，triangleCount(n),執行n-1次，triangleCount(n-1),執行n-2次，一次類推，所以總的相加次數為(n-1) + (n-2)+…+1,復雜度為o(n2). 6 sorting win7，i3-350，2g 內存下三種排序算法運行20次平均消耗時間如下
|
歸并排序
|
快速排序
|
隨機快速排序
|
時間(ms)
|
26610
|
9036
|
37
|
從上面的數據可以看出隨機快速排序最快，明顯好于其他兩個排序算法，歸并排序最慢，另外對于后兩種排序算法，pivot選用隨機數能夠有效的提高算法的執行速度。 1 非遞歸歸并排序 public class MergeSort { privateint array[] ; publicMergeSort() { LoadDatald = new LoadData(); array= ld.getData(); } publicvoid sort() { intlen = 1; while(len< array.length * 2) { intstart = 0; while(start< array.length) { intend = start + len; if(end>= array.length) end= array.length; for(inti = start;i < end-1; i++) for(int j = i+1;j< end; j++) { if(array[j]< array) { inttemp = array; array= array[j]; array[j]= temp; } } start= end + 1; } len*=2; } } publicstatic void main(String[] args) { //TODO Auto-generated method stub MergeSortsort = new MergeSort(); longstart = System.currentTimeMillis(); sort.sort(); longcost = System.currentTimeMillis() - start; System.out.println(cost); } } 2 快速排序 public class QuickSort { private int array[] = {4,5,3,6,8,1,2,7}; public QuickSort() { LoadData ld = new LoadData(); array = ld.getData(); } public int partition(int start,int finish) { int pivot = -1; int elem = array[start]; while(start < finish) { while(array[finish] > elem && start < finish ) { finish--; } if(start == finish) { pivot = start; break; } int temp = array[finish]; array[finish] = array[start]; array[start] = temp; start++;
while(array[start] < elem && start < finish) { start++ ; } if(start == finish) { pivot = start; break; } temp = array[finish]; array[finish] = array[start]; array[start] = temp; finish--; } if(start!=finish) return pivot; else return start; }
public void sort() { int start = 0; int finish = array.length - 1; int k = partition(0,array.length -1); Stack<Integer> s = new Stack<Integer>(); if(k-1 > start) { s.push(start); s.push(k-1); } if(k+1 < finish) { s.push(k+1); s.push(finish); } while(!s.empty()) { finish = s.pop(); start = s.pop();
k = partition(start, finish); if(k-1 > start) { s.push(start); s.push(k-1); } if(k+1 < finish) { s.push(k+1); s.push(finish); } } } public static void main(String[] args) { // TODO Auto-generatedmethod stub QuickSort sort = new QuickSort(); long start = System.currentTimeMillis(); sort.sort(); long cost = System.currentTimeMillis() - start; System.out.println(cost); } } 3 隨機的快速排序 public class RQuickSort { private int array[] = {4,5,3,6,8,1,2,7}; public int partition(int start,int finish) { int pivot = -1; int random = (int)(Math.random()*(finish - start + 1)); int elem = array[start+random];
int temp = array[start + random]; array[start + random] = array[start]; array[start] = temp;
while(start < finish) { while(array[finish] > elem && start < finish ) { finish--; } if(start == finish) { pivot = start; break; } temp = array[finish]; array[finish] = array[start]; array[start] = temp; start++;
while(array[start] < elem && start < finish) { start++ ; } if(start == finish) { pivot = start; break; } temp = array[finish]; array[finish] = array[start]; array[start] = temp; finish--; } if(start!=finish) return pivot; else return start; } public RQuickSort() { LoadData ld = new LoadData(); array = ld.getData(); } public void sort() { int start = 0; int finish = array.length - 1; int k = partition(0,array.length -1); Stack<Integer> s = new Stack<Integer>(); if(k-1 > start) { s.push(start); s.push(k-1); } if(k+1 < finish) { s.push(k+1); s.push(finish); } while(!s.empty()) { finish = s.pop(); start = s.pop();
k = partition(start, finish); if(k-1 > start) { s.push(start); s.push(k-1); } if(k+1 < finish) { s.push(k+1); s.push(finish); } } } public static void main(String[] args) { // TODO Auto-generatedmethod stub RQuickSort sort = new RQuickSort(); long start = System.currentTimeMillis(); sort.sort(); long cost = System.currentTimeMillis() - start; System.out.println(cost); } } | 
發表于 2012-11-5 19:47
收藏
分享
支持
反對
