衡量一个算法的优劣-时空复杂度简介

大一大二学习的笔记整合
最新更新于2020/6/22

算法相关

算法特性：

• 有穷：步骤有穷、时间有限
• 确定：语句无二义
• 可行：可运行可实现
• 输入：输入可有可无
• 输出：与输入有确定关系

好算法的标准：

• 正确：能满足问题
• 可读：方便阅读
• 健壮：容错处理
• 通用：对同数据类型的其他数据可用
• 高效率低存储

时间复杂度

算法的控制结构

• 顺序
• 分支
• 循环
• 加减乘除赋值…（原操作）

算法执行时间

（原操作的执行次数乘以原操作的执行时间）的累加

执行时间我们无法计算，但是，执行时间与原操作执行次数之和成正比，所以可用

**频度T（n）**表示算法的执行时间

注意：关于（1）为什么频度是n+1，主要是因为 i自增到n的时候，判定不通过，这步判定算1，而该循环内的语句执行了n次

故第二层循环就执行了n*（n+1），+1代表了一步判定

时间复杂度

保留T（n）的最高阶，忽略低阶项与常系数

一般判断算法也不用算T（n）了，目测出O（n）即可，按照复杂度从小到大排序

• 常数阶O（1） ：无循环语句
• 线性阶O（n）：一重循环
• 对数阶O（log2[n]）：树的结点是2的n次方，这是有关树的时间复杂度 / O（nlog2[n]）典型堆排序
  • 该复杂度本质是二分查找算法的时间复杂度
• 平方阶O（n方）：二重循环
• 立方阶O（n立方）：三重循环
• 指数阶O（2的n次方）

时间复杂度估算

• 常数时间的操作

  • 何为常数时间的操作?

    如果一个操作的执行时间不以具体样本量为转移，每次执行时间都是固定时间。称这样的操作为常数时间的操作。

    常见的常数时间的操作:

    • 常见的算术运算（+、-、*、/、% 等）
    • 常见的位运算（>>、>>>、<<、|、&、^等）
    • 赋值、比较、自增、自减操作等
    • 数组寻址操作

    总之，执行时间固定的操作都是常数时间的操作。
    反之，执行时间不固定的操作，都不是常数时间的操作。****

• 确定算法流程的总操作数量与样本数量之间的表达式关系（算出Tn）

  • 1，想象该算法流程所处理的数据状况，要按照最差情况来。
    2，把整个流程彻底拆分为一个个基本动作，保证每个动作都是常数时间的操作。
    3，如果数据量为N，看看基本动作的数量和N是什么关系。

• 只看表达式最高阶项的部分（算出On）

  • 当完成了表达式的建立，只要把最高阶项留下即可。低阶项都去掉，高阶项的系数也去掉。
    记为：O(忽略掉系数的高阶项)

额外空间复杂度

你要实现一个算法流程，在实现算法流程的过程中，你需要开辟一些空间来支持你的算法流程。

作为输入参数的空间，不算额外空间。
作为输出结果的空间，也不算额外空间。

因为这些都是必要的、和现实目标有关的。所以都不算额外空间

但除此之外，你的流程如果还需要开辟空间才能让你的流程继续下去。这部分空间就是额外空间。

如果你的流程只需要开辟有限几个变量，额外空间复杂度就是O(1)

比如你额外开一个数组，来容纳你n个数据样本，那么该空间复杂度即为O（n）

习题