数据结构和算法 1-3 时间复杂度和空间复杂度
2019-06-23 本文已影响0人
Bc_wh1te_Le1
算法的效率一般指算法的运行时间。
算法效率的度量方法。
- 算法采用的策略、方案
- 编译产生的代码质量
- 问题的输入规模
- 机器执行指令的速度
函数的渐近增长
给定两个函数 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
