如何比较在两种算法的快慢！！！！！

我看过一篇文章，作者的算法的实验数据是以cpu时钟为单位的。我现在自己设计一种算法，在我电脑上运行，我该如何比较两种算法的效率。（作者文章上标明他的电脑是p4－933MHz，我现在用的电脑是赛扬1.8G。请大家指教，解决问题再加分。

13 个解决方案

#1

这种比较的方法不好，可以用数据结构中时间复杂度的计算方法来比较

#2

你可以到数据结构或算法分析与设计的相关书籍中查找时间复杂度的计算方法，算法上时间复杂度一般不是用cpu时钟为单位的（cpu时钟不同，难以比较！），而是执行某一特定简单操作为单位的。

#3

试验数据以cpu时钟为单位？
那么这种算法本身应该不能用普通的算法时间复杂度来衡量了，要精确到CPU时钟单位的算法大概只有从汇编等级考虑效率了。
测试效率需要大量的试验来验证，针对不同的测试数据反馈的结果可能是完全不同的。

#4

如果你只想测试出在你的系统下两种算法的快慢，可以：

1，在算法开始时调用GetTickCount()获取系统运行的时间
2，在算法结束时调用GetTickCount()再获取系统运行的时间
3，把得到的两值相减就是算法耗费时间，可以精确到微秒

#5

icr_mio基本正确，不过GetTickCount只能精确到10ms

#6

谢谢指正

#7

不能只用数据结构时间复杂度分析的，比如
for(i=0;i<m,i++){
    for(j=0;i<n,j++){
    }
}

for(j=0;i<n,j++){
    for(i=0;i<m,i++){
    }
}
当m>>n时第二种消耗的时间要小得多（不信试试），而他们数据结构的时间复杂度都是m*n

#8

比一比

#9

同意 HUNTON()

不信拿个二维数组试试ary[i][j]

遍历数组的二重循环把i放在前和把j放在前是差很大的

#10

需要高精度计时用long t=GetTickCount(); 需要更高精度计时可参考下列程序：

#include <windows.h>
#include <iostream>
#include <iomanip>
using namespace std;
int main()
{
    LARGE_INTEGER t1,t2,feq;
    int b=0;
    QueryPerformanceFrequency(&feq);//每秒跳动次数
    QueryPerformanceCounter(&t1);//测前跳动次数
    for(int i=0;i<100;i++) b++;
    QueryPerformanceCounter(&t2);//测后跳动次数
    double d=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart);//时间差秒
  std::cout<<setprecision(20)<<showpoint<<std::endl;//小数点表示20位
    std::cout<<d<<std::endl;
    return 0;
}

#11

楼上的方法更准确

#12

重复执行1000次不就可以了？而且如果你要看的是算法复杂度的话，就可以1000次、2000次、3000次……，然后划出经验曲线，而不必在乎每次的时间。

#13

谢谢各位的讨论，总的来说，我对作者用cpu时钟作为比较单位还是比较费解。在结贴前，
顺便问两个问题；
1 cpu时钟的定义是什么？
2 两台不同的电脑有什么共性的地方可以比较程序运行的快慢，因为不可能把作者的程序拿到我的电脑上来运行(根本就没有他的源代码)。

#1