算法的效率
一般指算法的运行时间。
算法效率的度量方法。
- 算法采用的策略、方案
- 编译产生的代码质量
- 问题的输入规模
- 机器执行指令的速度
函数的渐近增长
给定两个函数 f(n) 和 g(n),如果存在一个整数N,使得对于所有的n>N, f(n) 中总是比 g(n) 大,那么,我们说 f(n) 的增长渐近快于 g(n)
image.png image.png
算法可以忽略一些加法常数
image.png image.png
与最高次项相乘的常数并不重要
image.png image.png
最高次项指数大的,函数随着n的增长,结果也会变得增长特别快
image.png
image.png
image.png
判断一个算法的效率时,函数中的常数项和其他次要项常常可以忽略,二更应该关注主项(最高项)的阶数。
空间复杂度 时间复杂度
image.png推导大O阶方法
- 用常数1取代运行次数函数中的所有加法常数
- 在修改后的运行次数函数中,只保留最高阶项
- 如果最高项存在且不是1,则去除与这个项相乘的常数
线性阶
一般含有非嵌套循环涉及线性阶,线性阶就是随着问题规模 n 的扩大,对应计算次数呈直线增长。
平方阶
n^2
对数阶
最坏情况与平均情况
image.png通常除非特别指定,我们提到的运行时间都是最坏情况的运行时间。
网友评论