算法复杂度包括哪些?针对这个问题,这篇文章详细介绍了相对应的分析和解答,希望可以帮助更多想解决这个问题的小伙伴找到更简单易行的方法。
算法复杂度:
在计算机科学中,时间复杂性,又称时间复杂度,算法的时间复杂度是一个函数,它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,亦即考察输入值大小趋近无穷时的情况。
为了计算时间复杂度,我们通常会估计算法的操作单元数量,每个单元运行的时间都是相同的,因此,总运行时间和算法的操作单元数量最多相差一个常量系数。
相同大小的不同输入值仍可能造成算法的运行时间不同,因此我们通常使用算法的最坏情况复杂度,记为T (n),定义为任何大小的输入n所需的最大运行时间。另一种较少使用的方法是平均情况复杂度,通常有特别指定才会使用。时间复杂度可以用函数T (n)的自然特性加以分类,举例来说,有着T (n)=O (n)的算法被称作“线性时间算法”,而T (n)=O (M ^ n)和M=O (T (n)),其中M≥n>1的算法被称作”指数时间算法”。
一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为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 + 3 n + 4与T (n)=4 n2 + 2 n + 1它们的频度不同,但时间复杂度相同,都为O (n2)。
时间频度
一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T (n)。
与时间复杂度类似,空间复杂度是指算法在计算机内执行时所需存储空间的度量。记作:
S O (n)=(f (n))
算法执行期间所需要的存储空间包括3个部分:
- <李>
算法程序所占的空间;
<李>输入的初始数据所占的存储空间;
<李>算法执行过程中所需要的额外空间。
在许多实际问题中,为了减少算法所占的存储空间,通常采用压缩存储技术。
关于算法复杂度包括哪些问题的解答就分享到这里了,希望以上内容可以对大家有一定的帮助,如果你还有很多疑惑没有解开,可以关注行业资讯频道了解更多相关知识。
