09Algorithm

Algorithm 算法

1、定义

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统

的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。

2、算法的衡量

算法复杂度分为时间复杂度和空间复杂度。其作用：时间复杂度是指执行算法所需要的计算工作量；而空

间复杂度是指执行这个算法所需要的内存空间。

时间复杂度

计算的方法：

看看有几重 for 循环，只有一重则时间复杂度为 O(n)，二重则为 O(n2)，依此类推，如果有二分

则为 O(log2n)，二分例如快速幂、二分查找，如果一个 for 循环套一个二分，那么时间复杂度则

为 O(nlog2n)。

按数量级递增排列，常见的时间复杂度有：

随着问题规模 n 的不断增大，上述时间复杂度不断增大，算法的执行效率越低

空间复杂度

一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小，它包括为参数表中形

参变量分配的存储空间和为在函数体中定义的局部变量分配的存储空间两个部分。

1、若一个算法为递归算法，其空间复杂度为递归所使用的堆栈空间的大小，它等于一次调用所分配的临时

存储空间的大小乘以被调用的次数(即为递归调用的次数加 1，这个 1 表示开始进行的一次非递归调用)。

2、算法的空间复杂度一般也以数量级的形式给出。如当一个算法的空间复杂度为一个常量，即不随被处理数

据量 n 的大小而改变时，可表示为 O(1)；当一个算法的空间复杂度与以 2 为底的 n 的对数成正比时，可

表示为 O(log2n)；当一个算法的空间复杂度与 n 成线性比例关系时，可表示为 O(n)。

算法的稳定性

排序算法的稳定性，通俗地讲就是能保证排序前 2 个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下，如果A[i] = A[j], A[i]原来在位置前，排序后 A[i]还是要在 A[j]位置前。