算法复杂度分析
2021-05-25 11:52:45 16 举报
AI智能生成
算法复杂度分析是对一个算法在运行过程中所需资源与输入数据规模之间的增长关系进行量化分析的过程。它通常用大O符号表示,包括时间复杂度和空间复杂度两个方面。时间复杂度描述了算法执行的步骤数量随着输入数据规模的增加而增长的速度;而空间复杂度则描述了算法所需的额外存储空间随着输入数据规模的增加而增长的速度。通过算法复杂度分析,我们可以评估算法的效率,为不同规模的应用场景选择合适的算法。
作者其他创作
大纲/内容
衡量不同算法之间的优劣
时间维度:是指执行当前算法所消耗的时间,我们通常用「时间复杂度」来描述。
空间维度:是指执行当前算法需要占用多少内存空间,我们通常用「空间复杂度」来描述。
大O符号表示法
T(n) = O(f(n))
其中 n 表示数据规模 ,O(f(n))表示运行算法所需要执行的指令数,和f(n)成正比。
常见的时间复杂度量级
常数阶O(1)
无论代码执行了多少行,其他区域不会影响到操作,这个代码的时间复杂度都是O(1)
线性阶O(n)
代码会执行 n 遍,因此它消耗的时间是随着 n 的变化而变化的
平方阶O(n²)
双重循环
对数阶O(logn)
一般地,函数y=logaX(a>0,且a≠1)叫做对数函数,也就是说以幂(真数)为自变量,指数为因变量,底数为常量的函数,叫对数函数。
如果ax =N(a>0,且a≠1),那么数x叫做以a为底N的对数,记作x=logaN,读作以a为底N的对数,其中a叫做对数的底数,N叫做真数。
如果ax =N(a>0,且a≠1),那么数x叫做以a为底N的对数,记作x=logaN,读作以a为底N的对数,其中a叫做对数的底数,N叫做真数。
以底数倍数缩减循环次数
线性对数阶O(nlogn)
比较
0 条评论
下一页