算法的效率一般指算法的运行时间。

算法效率的度量方法。

• 算法采用的策略、方案
• 编译产生的代码质量
• 问题的输入规模
• 机器执行指令的速度

函数的渐近增长

给定两个函数 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，则去除与这个项相乘的常数

image.png

线性阶
一般含有非嵌套循环涉及线性阶，线性阶就是随着问题规模 n 的扩大，对应计算次数呈直线增长。

平方阶
n^2
对数阶

image.png

image.png

image.png

image.png

image.png

最坏情况与平均情况

image.png

通常除非特别指定，我们提到的运行时间都是最坏情况的运行时间。

算法的控件复杂度

image.png