算法—算法的时间空间复杂度
1. 事后分析法
缺点:不同的数据规模,不同的机器下算法运行的时间不同,无法做到计算运行时间
2. 事前分析法
2.1 大 O 时间复杂度
渐进时间复杂度 随着 n 的增长,程序运行时间跟随 n 变化的趋势
2.1.1 几个原则
去掉常数项
2(n^2) =n^2
一段代码取时间复杂度最高的
复制代码
这段代码的时间复杂度为 n^3+n^2+n
当 n 足够大时,n^2 和 n 与 n^3 相比太小,可以忽略不计
2.1.2 常见复杂度
o(1)
复制代码
o(n)
复制代码
o(n^2)
复制代码
o(log2n)
PS:如果 ax =N(a>0,且 a≠1),那么数 x 叫做以 a 为底 N 的对数,记作 x=logaN,读作以 a 为底 N 的,其中 a 叫做对数的底数,N 叫做真数。
复制代码
随着循环次数的增加,i 的值变化如下
根据对数函数的公式 2 的 i 次方等于 n,i 等于 log2n
2.2 最好情况时间复杂度
数据比较有序的情况的时间复杂度
2.3 最坏情况时间复杂度
数据完全无序
3. 空间复杂度
与 n 无关的代码空间复杂度可以忽略
空间复杂度 O(n)
复制代码
版权声明: 本文为 InfoQ 作者【思想者杰克】的原创文章。
原文链接:【http://xie.infoq.cn/article/31ef7d263404871c2f4ac3718】。文章转载请联系作者。
评论