算法的复杂度分为两大类： 时间复杂度、空间复杂度。时间复杂度指的是该算法完成需要执行运算的次数；空间复杂度指执行算法需要消耗的内存空间大小。
对一个算法而言，时间复杂度 和 空间复杂度 都是越小越好。因为优秀算法的核心是通过最短的时间和最小的空间完成指定的目标运算。
这篇文章，将介绍算法的时间复杂度和空间复杂度的计算方式，内容很基础，大神绕了吧。
时间复杂度的计算
通常，我们不会直接将算法执行的总次数作为它的时间复杂度，因为，并不是每一个算法都能算出一个确切的总执行次数，根据不同的计算对象，相同的算法的总执行次数是不固定的，那么计算执行的总次数意义不大。相反，定性的分析同一个算法对规模增加的影响更有意义：我们只想知道，随着规模 N 的增长，算法的执行次数的增长曲线（对数增长？ 常数增长或者是指数增长？）是怎样的，这个增长能够给算法的性能做一个定性的分析，从而判断一个算法的优劣。一般我们会使用大 O 记录。下面介绍几种常见的大 O 记录时间复杂度的例子。
常见的几个时间复杂度算法
O(1)：表示的是该算法的执行次数和规模 N 无关，永远都会执行某个常数次的元素。
比如高斯函数：
// 计算 1 + 2 + 3 + 4 + ...... + 100 + ... + N
// 规模为 N
func addTo(_ n: Int) {
sum = (1 + n) * n/2; /* 执行1次 */
printf("%d", sum); /* 执行1次 */
}
这个高斯函数永远都只会执行2次，不管N有多大。也即是，算法永远执行一个常数次数，这种时间复杂度，用大O表示为O(1)。
O(LogN)：对数递增，表示随着规模的增大，执行次数按照规模N的对数函数递增。
比如： 常见的对分查找。
// 给定一个有序的整型数组 Arr, 从中随机挑选出一个元素 X，在数组中找到 X 的元素的下标值
func findElmentIndex(_ arr: [Int], _ x: Int ) -> Int {
var low = 0, hight = arr.count, index = (low + hight)/2
while x != arr[index] {
if x > arr[index] {
low = index
}else if x < arr[index]{
hight = index
}else{
return index
}
index = (low + hight)/2
}
return index
}
这里并不好算出算法的实际次数（根据X数字的位置会不断改变总执行次数）。但是我们可以给出一个大致的范围，假如 X 刚好在数组的中间，那么一次就可以找到X的位置。如果X在最前面，也就是index = 0的位置,那么需要次数最多，为 logN。这里使用大 O 记录就是 O（logN）。
O(N)：表示算法的执行次数以 N 线性增长。
比如，累加函数。
// 计算 1 + 2 + 3 + 4 + ...... + 100 + ... + N
// 除了使用高斯函数计算，我们也可以使用逐个相加的方法
func addTo(_ n: Int) -> {
var sum = 0
for i in 0..<n+1{
sum += i
}
return sum
}
这个算法的执行次数很明朗，就是N次。因为随着规模 N 线性增长，因此计作 O（N）。
其余常见的还有 O（N^2）、 O（N^3）。以及 O（2^n）、O（N!）、 O（N^N）这些不常用到的，因为越排在后面时间复杂度越大，我们一般很少用到。
计算时间复杂度的大 O 的方法
如何给一个算法定义大 O 呢？其实很简单，只需要遵循一个规律就行。
假若给定一个函数，内部是一个累加算法，我们来想计算它的时间复杂度，可以通过下面的顺序来操作：
- 计算算法执行的总时间
- 用常数1取代运行时间中的所有加法常数。
- 在修改后的运行次数函数中，只保留最髙阶项。
- 如果最高阶项存在且不是1,则去除与这个项相乘的常数。
首先看函数原型：
func addTo(_ n: Int) -> Int {
var sum = 0
for i in 0..<n {
sum += i // 执行n次
}
return sum
}
- 很容易计算得出，总次数为 n
- 没有常数
- 本身只有一项，最高阶即为本身
- 最高阶存在为1， 不需要做其他的处理
这个算法的大 O 记做： O（n），也就是线性执行。这个例子还不够体现上面四个步骤的所有流程。
再来看一个经常用到的：
// 冒泡排序
func sortByBubble<T: Comparable>(_ arr: [T]) -> [T] {
var mutArr = arr; // 1次
for i in 0..<mutArr.count {
// n 次
for j in (i+1)..<mutArr.count {
if mutArr[i] > mutArr[j] {
(mutArr[i],mutArr[j]) = (mutArr[j],mutArr[i]) // n-1 、 n -2 .... 1
}
}
}
return mutArr
}
最快的时间： 在数组本身已经排好序的情况，为n次。
最慢的时间： 完全倒序的情况下，执行 n-1 + n-2 + .... + 1 = n^2/2 + n/2 （注意这里是交换两个元素的值，很多编程语言中应该为3次，也就是这里的值应该乘以3）
我们以最坏的情况计算大 O：
1 + n^2/2 + n/2 ---- > n^2/2 + n/2 + 1
首先去除常数项： ----> n^2/2 + n/2
只保留最高次幂项： ----> n^2/2
去除最高次幂的常数： ----> n^2
所以，冒泡排序的大 O 为：O（n^2）
空间复杂度的计算
一个程序的空间复杂度是指运行完一个程序所需内存的大小。利用程序的空间复杂度，可以对程序的运行所需要的内存多少有个预先估计。一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。程序执行时所需存储空间包括以下两部分。
所以，相对来说，空间复杂度经常不会太大，如果太大，很可能算法会执行不下去。一般的空间复杂度为 O （1），O（n）也很常见，另外像涉及到递归算法中，空间复杂度可能达到O（n^2)。
空间复杂的大 O 计算其实和时间复杂度类似。但是还需要根据实际情况来算，任何脱离实际的算法都毫无意义。
排序算法的稳定性
排序算法的稳定性指的是同一个算法，相同大小的结果在每一次的算法中的顺序都是一样的。我们前面举例的冒泡排序就是如此，就算其中有大小相同的值，但是排序在前面的值，排序后还是在前。
对于不稳定的排序算法，只要举出一个实例，即可说明它的不稳定性；而对于稳定的排序算法，必须对算法进行分析从而得到稳定的特性。需要注意的是，排序算法是否为稳定的是由具体算法决定的，不稳定的算法在某种条件下可以变为稳定的算法，而稳定的算法在某种条件下也可以变为不稳定的算法。
比如还是之前的冒泡排序，改成下面这样就变成了不稳定的排序算法：
// 冒泡排序
func sortByBubble<T: Comparable>(_ arr: [T]) -> [T] {
var mutArr = arr;
for i in 0..<mutArr.count {
for j in (i+1)..<mutArr.count {
if mutArr[i] >= mutArr[j] { // 这里的条件进行了更改
(mutArr[i],mutArr[j]) = (mutArr[j],mutArr[i])
}
}
}
print(mutArr)
return mutArr
}
这个算法最终变成了不稳定的排序算法。
网友评论