|
|
|
|
|
|
|
|
|
|
考研論壇
標題: (Multimedia Dr)第二次算法作業(yè) [打印本頁]
作者: 598788523 時間: 2012-11-5 19:47
標題: (Multimedia Dr)第二次算法作業(yè)
3 Divide and Conquer
假設多邊形的頂點 ,用 標識n+1邊的圖多邊形分成三角形的個數(shù)。
選擇一條邊作為基邊，例如邊 ，從頂點 到 中選擇一個頂點與邊 構成三角形，這樣就把多邊形分為三個區(qū)域 ， 為剩余的多邊形部分，那么 區(qū)域有k+1條邊， 有n-k+1條邊，根據(jù)排列組合的乘法原則，此分法的不同三角形的分法有 ,而三角形頂點的選擇可以從頂點 到 中任意選擇一個，根據(jù)排列組合的加法原則 。
已知 ,所以可以根據(jù)遞推算出 的結(jié)果。
偽代碼如下
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),執(zhí)行n-1次，triangleCount(n-1),執(zhí)行n-2次，一次類推，所以總的相加次數(shù)為(n-1) + (n-2)+…+1,復雜度為o(n2).
6 sorting
win7，i3-350，2g 內(nèi)存下三種排序算法運行20次平均消耗時間如下
|
歸并排序
|
快速排序
|
隨機快速排序
|
時間(ms)
|
26610
|
9036
|
37
|
從上面的數(shù)據(jù)可以看出隨機快速排序最快，明顯好于其他兩個排序算法，歸并排序最慢，另外對于后兩種排序算法，pivot選用隨機數(shù)能夠有效的提高算法的執(zhí)行速度。
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);
}
}
作者: panda2029 時間: 2013-5-15 17:31
恩呢。。。這個是真的作業(yè)。。。
作者: 真真小帥 時間: 2013-5-15 17:58
膜拜
作者: 可可米露 時間: 2013-5-16 14:33
師父是不是特別聰明哇→ →
作者: 亍彳蟲犭首 時間: 2013-5-16 16:57
[em:42]
作者: 可可米露 時間: 2013-5-17 01:12
我也要膜拜一下。。師父要保佑我學好財管。。里面有一堆公式TT-TT阿米豆腐~~
| 歡迎光臨 考研論壇 (http://www.5522pp.com/) |
Powered by Discuz! X3.2 |