$\Theta(n) + \Theta(n) \ne \Theta(n^2)$（蹭个热点）

复杂度

衡量算法的好坏通常使用复杂度。复杂度包括空间复杂度，时间复杂度和理解复杂度（大雾）。

为什么不直接那算法执行时间来衡量算法的好坏呢？

因为烂的电脑执行一个快的算法可以比好的电脑执行一个慢的算法耗时更短。所以靠时间测量这种方法是依赖于硬件的。

当然可以在同一个电脑上执行不同的算法来对比。不过如果有一种不依赖与硬件和执行的方式去衡量算法那就更方便了。

所以聪明的科学家发明了时间复杂度极其相应记号来衡量算法的好坏。

时间复杂度的计算

通常算法的时间复杂度只和他的输入规模有关。比如同样的算法，排序 10000 个数肯定比排序 10 个数慢。如果使用 $n$ 来表示输入的规模（比如排序 10000 个数，那么 $n = 10000$），快速排序的时间复杂度 $T(n)$ 可以表示为关于 $n$ 的多项式 $T(n) = \Theta(n\log(n))$ 。

那么如何计算时间复杂度呢？

一个算法的执行事件等于所有指令耗时的综合。

从高级编程语言的方面上讲，常见的指令有赋值，加减乘除的操作符，循环，函数调用等。

比如赋值指令 x = 1 因为具体时间与硬件平台有关，所以将这个具体时间记为一个单位时间。又因为耗时不会随着问题规模变动，是一个常数，所以表示为 $\Theta(1)$

加减乘除等操作符耗时为 $\Theta(1)$

循环操作本质上是重复一定次数的操作，所以只需要计算一次操作的时间，乘上重复次数就可以算出总的时间。比如求和函数

1
2
3
4
5
var sum = 0
for (var i = 0; i < n; ++i)
{
    sum += i
}

执行了 n 次赋值操作，每次操作时间为 $\Theta(1)$，所以总耗时为 $\Theta(1) \times n = \Theta(n)$ 。

函数是一段代码的集合，所以函数执行时间等于每行代码执行时间的总和。

比如冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function bubble_sort (array) {
    var i, j;
    var n = array.length
    if (n == 0) return;
    
    for(i = 0; i < n - 1; i++) { // n - 1 次
        for(j = 0; j < n - 1- i; j++) { // n - 1 - i 次
            if (array[j] > array[j+1]) { // Θ(1)
                var temp = array[j];	// Θ(1)
                array[j] = array[j+1];	// Θ(1)
                array[j + 1] = temp;	// Θ(1)
            }
        }
    }
    return array;
}

所以冒泡排序的时间复杂度为
$$
T(n) = (n - 1) \times (n - 1 - i) \times \Theta(1) \times 4 = \Theta(2n^2) = \Theta(n^2)
$$
然而不是每个时间复杂度都那么容易求得出来。

比如快速排序的时间复杂度为 $T(n) = 2T(n / 2) + \Theta(n)$ 。

这是一个递推式，要怎么求出递推式的解呢？

聪明的小朋友能马上想到用天下无敌法，但主方法是有使用条件的，如果不能使用该如何求解呢？很简单只要展开递推式，求解每一项的时间求和即可。

比如上面的快速排序递推式，

对于 $ n = 2 $ 时 $T(2) = 2T(1) + \Theta(n) = 2\Theta(n) + \Theta(n) = 3\Theta(n)$

类似的

$T(n) = 2T(n/2) + \Theta(n) = 4T(n/4) + 3\Theta(n) = aT(1) + b\Theta(n)$

其实这是一个等比数列求和的过程。前面的项数$a = 2\log_2{n}$，后面的 $b = a/2 + 1$

因为 $T(1) = \Theta(n)$

所以 $T(n) = 2\log(n)\Theta(n) + \log(n)\Theta(n) = 3\log(n)\Theta(n) = \Theta(n\log(n))$

其他的递推式也可以用类似的方法求解。

后记

本来只想说一个简单的递推式求解，却控制不住自己解释了一堆……