關於算法複雜性的問題

Question

我試過實現兩種方法遞歸和動態方法，都花了0秒這意味着沒有人在我的電腦更好或者代碼中出現錯誤？這裏是這些方法

1 //遞歸

#include <stdio.h> 
#include <time.h> 
#include <iostream> 
using std::cout; 
void print(int n){ 

    if (n<0) return ; 
    cout<<n<<" "; 

    print(n-1); 

} 
int main(){ 
    int n=10; 
    time_t start,end; 
    double dif; 
    time(&start); 
    print(n); 
    time(&end); 
    dif=difftime(end,start); 
    printf("it took you %.21f seconds ",dif); 

    return 0; 
} 

2.second方法

#include <iostream> 
#include <stdio.h> 
#include <time.h> 
using namespace std; 
void print (int n){ 
    if (n<0) return ; 
    while (n>=0){ 
     cout<<n--<<endl; 
    } 



} 
int main(){ 
    int n=10; 
    double dif; 
    time_t start,end; 
    time(&start); 

    print(n); 
    time(&end); 
    dif=difftime(end,start); 
    printf("it took you %.21f seconds",dif); 

return 0; 

} 

Answer 1

第二時鐘分辨率不適合測量這樣的快速操作。

我建議您多次執行您的代碼（類似於100萬次;使用for循環），估計總時間，然後計算平均值。

這樣你會得到更可靠的結果。

只是一個快速提示：我看到你在你的函數中使用了cout。這是一個糟糕的主意：cout並且通常大多數I/O操作是關於其他操作的慢。您的功能可能會花大部分時間來打印價值，而不是計算它。

Answer 2

測試時，你需要將你的函數循環100000次左右，然後測量整個循環時間。然後你將能夠看到一些可靠的結果。

Answer 3

兩個函數所花費的時間都小於計時器分辨率，這就是爲什麼您要測量0秒的原因。

漸近地說，兩個函數的時間複雜度都是O（n）。

Answer 4

要進行全面的性能測量，您必須重複測試的功能，最好使用可重複的隨機輸入，這樣可以實現與您的測量分辨率相匹配的運行時間。然後，重複測量幾次，除去剩餘值中的異常值和平均值。現在你應該有可靠的數字來看待。

Answer 5

另外gettimeofday（）以微秒爲單位返回時間。