算法复杂度分为时间复杂度和空间复杂度。
时间复杂度是度量算法执行的时间长短;而空间复杂度是度量算法所需存储空间的大小。
时间复杂度:
一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。
一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f (n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。
在各种不同算法中,若算法中语句执行次数为一个常数,则时间复杂度为O(1),另外,在时间频度不相同时,时间复杂度有可能相同,如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同,但时间复杂度相同,都为O(n2)。
按数量级递增排列,常见的时间复杂度有:
常数阶O(1),
对数阶O(log2n),
线性阶O(n),
线性对数阶O(nlog2n),
平方阶O(n2),
立方阶O(n3),
...,
k次方阶O(nk),
指数阶O(2n)。
随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低。
分享到:
相关推荐
算法导论大作业:股票买卖最佳时期系列问题 南开大学 算法导论源码算法导论大作业:股票买卖最佳时期系列问题 南开大学 算法导论源码算法导论大作业:股票买卖最佳时期系列问题 南开大学 算法导论源码算法导论大作业...
算法导论讲义\算法导论讲义 算法导论讲义\算法导论讲义 算法导论讲义\算法导论讲义 MIT教师的课堂讲义 很有价值
《算法导论》原书名——《Introduction to Algorithms》,是一本十分经典的计算机算法书籍,与高德纳(Donald E.Knuth)的《计算机程序设计艺术》(《The Art Of Computer Programming》)相媲美。 《算法导论》由...
算法导论第四章答案算法导论第四章答案算法导论第四章答案算法导论第四章答案
第三版、算法导论、全面、详细!可以作为常用书籍、第三版、算法导论、全面、详细!可以作为常用书籍
算法导论
英文版算法导论,算法界的圣经,你能看吗? 在有关算法的书中,有一些叙述非常严谨,但不够全面,另一些涉及了大量的题材,但又缺乏严谨性。《算法导论》将严谨性和全面性 融为一体。 本书深入讨论各类算法,并...
最近在研习算法导论,发现课后习题的精彩程度甚至不亚于正文,对于算法导论的爱好者而言,这是一份不错的参考资料
计算机算法导论计算机算法导论计算机算法导论计算机算法导论计算机算法导论
算法导论 第二十五章 答案 算法导论 第二十五章 答案 算法导论 第二十五章 答案
算法导论第二十四章答案 算法导论第二十四章答案 算法导论第二十四章答案
算法导论 第三版 中文pdf
算法导论中英文合集,经典无需多说。算法导论中英文高清版本
麻省理工--算法导论,书本后答案,考试试卷
算法导论答案,第四版,但是是英文版的。
《算法导论》从一定深度上涵盖了算法的诸多方面,同时其讲授和分析方法又兼顾了各个层次读者的接受能力。这里提供的是该教程第二版的课件,为麻省理工大学制作,英文版,pdf格式,用Abobe Reader全屏查看可以和ppt...
算法导论第三版答案,算是比较全的版本 中文答案
算法导论第五版答案 从第二章开始 大部分是中文的
算法导论教师手册算法导论教师手册算法导论教师手册
算法导论习题解答算法导论习题解答算法导论习题解答算法导论习题解答算法导论习题解答