这样用大写O()来体现算法时间复杂度的记法,我们称之为大O记法。一般情况下,随着n的增大,T(n)增长最慢的算法为最优算法。
举例,如果一个算法对于任何大小为n的输入,它至多需要5n3+3n的时间运行完毕,那么它的渐近时间复杂度是O(n3) 。
注意:
时间复杂度计算过程中,是最终会去掉这个函数的低阶项和首项系数的。(这也就是为什么5n3+3n 会最终化简为n3)
举例:
一:O(1) 常数阶
Temp=i;i=j;j=temp;
以上三条单个语句的频度均为1,该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶,记作T(n)=O(1)。如果算法的执行时间不随着问题规模n的增加而增长,即使算法中有上千条语句,其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。
二: O(n) 线性阶
通常,如果某个循环结构以线性方式运行n次,并且循环体的时间复杂度都是O(1),那么该循环的复杂度就是O(n).
for(int i = 0; i < n; i++){ //一些列复杂度为O(1)的步骤.... }
即使,该循环跳过某些常数部分,只要跳过的部分是线性的,那么该循环体的时间复杂度仍就是O(n).
比如
int count = 1; while(count < n){ count += 2; //一些列复杂度为O(1)的步骤.... }
时间复杂度还是O(n)
三:O( log2n) 对数级
int count = 1; while(count < n){ count *= 2; //一些列复杂度为O(1)的步骤.... }
该循环2^f(n)<=n; f(n)<=log2n 取最大值f(n)= log2n, T(n)=O(log2n)
四:循环嵌套复杂度分析
for(int count1 = 0; count1 < n; count1++){ for(int count2 = 0; count2 < n; count2++){ //一些列复杂度为O(1)的步骤.... } }
在这种情况下应该 先计算内层循环的时间复杂度,然后用内层的复杂度乘以外层循环的次数。 最内层循环体的时间复杂度都是O(1)所以循环n次也就是O(n) 在乘以最外层for的n次。所以得出结论 2层嵌套循环的时间复杂度 = O(1) * n*n = O(n2)
算法优化:
计算1 + 2 + 3 + 4 + ...... + n =? ,通过程序实现,并标出算法的时间复杂度。
Java解法一:
public int method01(int n){ int sum = 0; for(int i=1;i<=n;i++){ sum += i; } return sum; }
时间复杂度: O(n)
德国数学家高斯曾经在他约9岁的时候就提过自己的解法:
SUM = 1 + 2 + 3 + 4 + ...... + 100
SUM = 100 + 99 + 98 + 97 + ...... + 1
SUM + SUM = 2*SUM = 101 + 101 + 101 + .... + 101 //正好 100 个 101
SUM = (100*101)/2 = 5050
Java解法二:
public int method02(int n){ int sum = 0; sum = (n*(n-1))/2; return sum; }
时间复杂度: O(1)
从时间复杂度上来年,解法二比解法一更高效
常见的算法时间复杂度由小到大依次为:
Ο(1)<Ο(log2n)<Ο(n)<Ο(nlog2n)<Ο(n2)<Ο(n3)<…<{Ο(2n)<Ο(n!)<O(nn)}
最后三项用大括号把他们括起来是想要告诉大家,如果日后大家设计的算法推导出的“大O阶”是大括号中的这几位,那么趁早放弃这个算法,在去研究新的算法出 来吧。因为大括号中的这几位即便是在 n 的规模比较小的情况下仍然要耗费大量的时间,算法的时间复杂度大的离谱,基本上就是“不可用状态”。
参考资料:
http://www.cnblogs.com/sakorn/archive/2007/05/18/751661.html
http://www.douban.com/note/91775206/
http://blog.csdn.net/xingqisan/article/details/3206303
http://www.cnblogs.com/yanng/articles/2178710.html
相关推荐
关于算法时间复杂度的计算 关于算法时间复杂度的计算 关于算法时间复杂度的计算
试完成求有向图的强连同分量的算法,并分析算法的时间复杂度
算法 时间复杂度 空间复杂度 经典算法 时间复杂度 空间复杂度 经典算法 时间复杂度 空间复杂度 经典
数据结构的基本概念和术语,算法的时间复杂度,讲述了数据结构的一些概念点,也就是最基本的一些东西,还有如何计算算法的时间复杂度之类的一些问题及举例
算法时间复杂度
对若干个数据进行操作,实现快速排序、选择排序、直接插入排序、堆排序算法时间复杂度的比较;并在排序数据中快速查找某一数据,给出查找是否成功,以及数据所在的位置信息。
各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶,或大概执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移动次数,以取得直观感受。
算法时间复杂度分析基础算法时间复杂度分析基础算法时间复杂度分析基础
算法的时间复杂度分析 期刊网站都是要现金的哦。
最好情况下, 最坏情况下, 平均情况下的时间复杂度
对算法进行时间复杂度分析是算法分析与研究 的重要内 容, 而对递 归算法分 析其时间 复杂度时 往往比较 困难. 提出了用组合数学中的母函数与递推关系理论来分析一些特 殊的递归算法的 时间复杂度, 并 同时得出三个 ...
算法复杂度分为时间复杂度和空间复杂度。 其作用: 时间复杂度是指执行算法所需要的计算工作量; 而空间复杂度是指执行这个算法所需要的内存空间。 (算法的复杂性体现在运行该算法时的计算机所需资源的多少上,...
这是数据结构算法课程中算复杂度的作业及答案。
关于矩阵乘法的一个改进算法的时间复杂度 两个 n 阶非负整数方阵相乘 常规算法的时间复杂度为 On3
应用马尔科夫链模型证明了遗传禁忌搜索算法是以概率1收敛到全局最优解的,并应用求解随机算法时间复杂度的方法,即求解算法的期望收敛时间,估算了该算法的时间复杂度,结果证明该算法的时间复杂度与所得解的多样性、...
程序员应该掌握的算法复杂度速查表 这个总结非常方便 不仅形象地把各个算法对比开来 也特别利于面试前的复习。
均值滤波很常见 但一般的算法复杂度都和取值窗口w*h有关 算法复杂度太高 本算法优化了基础的均值滤波算法 算法复杂度大大降低
对算法分析与设计课程的实验报告,对算法里面的时间复杂度,和增长率有很好的研究。
根号n段归并排序算法时间复杂度分析过程: 1.合并 根号n向下取整 段子数组使用的是自底向上两两归并的策略 2.根号n段归并排序算法时间复杂度的数学推导