算法及其时空复杂度

【算法】

算法是对特定问题求解步骤的描述，是指令的有限序列，每个指令表示一或多个操作，其具有以下特性：

• 有穷性：能在有穷步、有穷时间内执行完毕
• 确定性：相同输入会获得相同输出
• 可行性：算法是可行的
• 输入：具有零到多个输入
• 输出：具有一到多个输出

【时间复杂度】

定义

时间复杂度用于评价算法的时间开销，即在给定数据范围时，通过时间复杂度来判断选用的算法会不会 TLE

通常利用 $T(n)$ 来表示算法中所有语句的频度和，而语句的频度是该语句在算法中重复执行的次数，因此 $T(n)$ 是问题规模 $n$ 的函数；利用 $f(n)$ 来表示基本运算的频度，即最深层循环内的语句频度

由此，算法的时间复杂度被定义为：

$$T(n)=O(f(n))$$

其中，$O$ 为 $T(n)$ 的数量级

运算规则

时间复杂度的运算满足以下规则：

• 加法规则：$T(n)=T_1(n)+T_2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))$
• 乘法规则：$T(n)=T_1(n)*T_2(n)=O(f(n))*O(g(n))=O(f(n)*g(n))$
• 去常规则：当存在常数 $k$ 时，省略掉常数，只关注数量级 $O$，例如：$O(3n^3+8)->O(n^3)$

根据上述规则，可以总结出如下常见时间复杂度关系：

$$O(1)<O(log_2n)<O(n)<O(nlog_2n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)$$

三种时间复杂度

对于某个算法来说，其存在三种时间复杂度：

• 最坏时间复杂度：最坏情况下算法的时间复杂度
• 最优时间复杂度：最好情况下算法的时间复杂度
• 平均时间复杂度：所有可能输入实例等概率情况下，算法的平均时间复杂度

一般来说，考虑最坏时间复杂度，其计算方式如下：

1. 找出执行次数最多的语句（循环层数最多的）
2. 计算语句执行数量级：设 $x$ 来代表执行次数，通过循环条件，化简 $x$ 与条件中 $n$ 的关系
3. 用数量级 $O$ 来表示结果

【空间复杂度】

空间复杂度是评价算法占用空间大小的指标，即在给定数据范围时，通过空间复杂度来判断算法会不会 MLE

在程序执行时，除存放指令、常数、变量、输入数据存储空间外，还要一些对数据进行操作及为实现计算所需的辅助空间 ，空间复杂度是对这些额外空间进行分析的，其被定义为算法耗费的存储空间大小，是问题规模 $n$ 的函数，即：

$$S(n)=O(f(n))$$

其中，$O$ 为 $S(n)$ 的数量级

如果算法所需辅助空间为常量，即 $S(n)=O(1)$ 时，称为算法原地工作，此时所需的辅助空间是固定的

同时，对于递归算法来说，其时间复杂度一般等于递归调用深度