利用dev-c 實做”快速排序法的時間複雜度！

Question

int main(void){
int i,num,qty,number;
int array[4000];
srand(time(NULL));
double total,start,end;
//clock_t start,end;
//double total;

cout<<"請輸入最大值: ";
cin>>num;

cout<<"請輸入資料量(小於等於4000): ";
cin>>qty;

for (i=0;i {
number=rand()%num + 1;
array[i]=number;
}


//start = clock();
start=(double)(clock())/(double)CLOCKS_PER_SEC;

Quicksort(array,0,qty-1);

//end = clock();
end=(double)(clock())/(double)CLOCKS_PER_SEC;

total = ((double)(end - start)) / CLOCKS_PER_SEC;
//total=end-start;

printf("\n執行時間 %ld 毫秒",start);
printf("\n執行時間 %ld 毫秒", end);
printf("\n執行時間 %ld 毫秒",total);

while(1);
return 0;
}

以上為我的主程式，我的問題是，我在進入quicksort副程式前後，夾了時間函數，但為什麼出來的數字(total都為0)總都是錯誤的，請幫我解答，謝謝！(註解是我使用的另一方法，副程式的部份都沒有錯誤)

Answer 1

你的 total 是 (end - start) / 準度 (CLOCKS_PER_SEC)
但，你的 end 和 start 都除過 準度了！
而準度極大！！
所以， total = 小小數 / 極大數 / 極大數 只好 = 0 囉！
建議：
用你 // 掉的東東，只改最後的 printf
printf("開始時間： %f 秒\\n", start / (double) CLOCKS_PER_SEC);
printf("結束時間： %f 秒\\n", end / (double) CLOCKS_PER_SEC);
printf("經過時間： %f 秒\\n", total / (double) CLOCKS_PER_SEC);
好處：少誤差、少整數、浮點數轉換；
缺點：慢 零點零零零零零一點點。 ^_^


2006-12-22 02:50:45 補充：
對了，現代電腦極快，加上QuickSort也很快 ( O( n log(n) )。
4000，才 47863 時間單位就做完了！
而一時間單位可能才10萬分之一秒！

總時間可能不到 0.1 秒！！

建議您用大一點的陣列下去測。

2006-12-22 02:53:08 補充：
clock( ) 函數有個問題：不能超過 72 還是 74 分鐘！
（因為CLOCKS_PER_SEC太大，clock_t 撐不住！！）
將來您要是有東東會超過 7x 分鐘，記得，要用別的計時法。

Answer 2

關於時間複雜度這個問題
試著將你的
%ld
改成
%lf
或許就有幫助了!!