算法 复杂度

2 复杂度

2.1 为什么需要复杂度分析？

1. 测试结果非常依赖测试环境；

2. 测试结果受数据规模的影响很大。

2.2 时间复杂度

用来评估算法运行效率的一个式子（单位）

时间复杂度记为O(log2n)或O(logn)

当算法过程中出现循环折半的时候，复杂度式子中会出现log

时间复杂度分析

1. 只关注循环执行次数最多的一段代码

2. 加法法则:总复杂度等于量级最大的那段代码的复杂度

   1. 总的时间复杂度就等于量级最大的那段代码的时间复杂度

3. 乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

2.3 复杂度量级

• 常亮阶 O(1)

• 对数阶 O(logn)

• 线性阶 O(n)

• 线性对数阶 O(nlogn)

• 平方阶 O(n²) O(n³)

• 指数阶 O(2ⁿ)

• 阶乘阶 O(n!)

2.4 时间复杂度—总结

• 时间复杂度是用来估计算法运行时间的一个式子（单位）。

• 一般来说，时间复杂度高的算法比复杂度低的算法慢。

• 常见的时间复杂度（按效率排序）

  • O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n²logn)<O(n³)

• 复杂问题的时间复杂度

• O(n!)O(2ⁿ) O(nⁿ)...

常见时间复杂度关系

2.5 如何简单快速地判断算法复杂度

• 快速判断算法复杂度(适用于绝大多数简单情况)：

  • 确定问题规模n

  • 循环减半过程-→logn

  • k层关于n的循环→n^

• 复杂情况:根据算法执行过程判断.

2.3 空间复杂度

• 空间复杂度:用来评估算法内存占用大小的式子

• 空间复杂度的表示方式与时间复杂度完全一样

  • 算法使用了几个变量: 0(1)

  • 算法使用了长度为n的- -维列表: O(n)

  • 算法使用了m行n列的二维列表: O(mn)

• “空间换时间”