关于算法复杂性的问题

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（）以微秒为单位返回时间。