怎么估算一个算法的时间复杂度

borefo

最近对估算算法的时间复杂度感到力不从心，请教大家是怎么快速的估算时间复杂度的呢？来谈谈心得吧，谢谢

daybreakcx

很多时候是靠经验，套相似的模型，重新开始推导出准确的这样太烦了
举个例子：比如很经典的归并排序的模型，可以套用到很多分治的操作上
这些多分析就有感觉了

borefo

回复 2# daybreakcx

1.     for (i = 1; i < n; i *= 2)
   
2.         for (j = 1; j < i; j++)
   
3.             laugh++;
   

复制代码

这个算法的时间复杂度怎么估算呢？谢谢！

daybreakcx

回复  daybreakcx 这个算法的时间复杂度怎么估算呢？谢谢！
borefo 发表于 2010-08-15 20:27

    按照大的算，n看成是2^k，那么就是外围是for上k=logn下取整次（每次都*2了），每次内部执行是i次，也就是2的指数次，也就是总的是2^0+2^1+...+2^k=2^(k+1)-1左右，2^(k+1)大概是2*n左右，也就是说时间复杂度大概是O(n)，不知道有没有估错……

borefo

回复 4# daybreakcx


    2^0+2^1+...+2^k=2^(k+1)-1

这个表达式没看明白，为什么总的是这样呢？

daybreakcx

回复  daybreakcx


    2^0+2^1+...+2^k=2^(k+1)-1

这个表达式没看明白，为什么总的是这样呢？
borefo 发表于 2010-08-15 21:03

    i是2^t的形式吧，因为从1开始每次都是乘以2，那么累加就是一个等比数列了

sanpiguan

回复  daybreakcx 这个算法的时间复杂度怎么估算呢？谢谢！
borefo 发表于 2010-08-15 20:27

    会不会是nlogn，呵呵，完全不会，瞎蒙的

davelv

外循环是log(n)次，而内循环则依次为1,2,4,8...n-次,用等比数列和公式计算为(1-2^logn)/(1-2)  = n，是O(n)的时间复杂度。
按照时间复杂度最大的内循环计算，整体时间复杂度为O(n).
这是简单的，稍微看下就能明白的，还有比较复杂的递归式，可以用主定理或者递归树的方法去计算。
基本上每个讲算法和数据结构的书籍都回涉及到时间复杂度的计算。在这些书籍用，以《算法导论》为全面和精准，楼主可以去看下这部分，但是要有高等数学的基础，如果没有这样的基础，还是建议找本更基础的算法书籍去仔细阅读和实践下。

ecjtubaowp

估算时间复杂度其实比较麻烦，我们也只是粗略的估计，大概按照如下：O(n),O(logn),O(n^2),O(nlogn),O(n(logn)^2)等等

blackuhlan

时间复杂度就是你的程序运行时间和输入数据集合的元素个数的关系。
例如从n个不同的数中寻找1个数，如果写成
for(...){if(找到)break;} 那么时间复杂度是O(n),因为你找到要经过n/2次循环（概率上说）,所以运行的时间是和n成正比例关系的，如果是是排序的数列中按照二分法查找，那么你找到要经过(log2N)/2次循环，所以时间复杂度是O(log2N),不知道这样解释你明白不?