【时间复杂度】代码时间复杂度计算
有这么一个少于十行的代码，你知道它的时间复杂度是多少吗？
- a. $T(n) \in \Theta(n^2)$
- b. $T(n) \in \Theta(n)$
- c. $T(n) \in \Theta(log n)$
[poll type=regular results=always public=true chartType=bar]
- a
- b
- c
[/poll]
不管三七二十一，直接随便猜一个。我猜这个的时间复杂度是 $ \Theta(n^2)$ 因为有两个for循环，大家都知道有两个for循环那么时间复杂度也一定是 $ \Theta(n^2)$ 对不对。
很可惜，还真不是 $\Theta(n^2)$， 而是 $\Theta(n)$
为什么呢？且听我慢慢道来。
在外部循环，有一个 i=2，也就是每一次运行都会增长2次，一直到n为止。而在内部循环，是根据外部循环来决定次数的，也就是说，外部运行多少次，内部就会运行多少次。
既然是这样的结果，那为什么不是 $ \Theta(n^2)$ 呢？而是 $\Theta(n)$ 呢？
再来看一个表
| 循环次数 | I | J | Steps |
|---|---|---|---|
| 1 | 1 | 1 | 1 |
| 2 | 2 | 2 | 1 |
| 3 | 4 | 4 | 1 |
| 4 | 8 | 8 | 1 |
| … | … | … | 1 |
| k | $2^{k-1}$ | $2^{k-1}$ | 1 |
观察到，一共会运行 $ 2^{k-1}$ 次在外部循环，外部循环肯定有一个结束条件，不然就是死循环了。在这里，结束条件是 i < n，通过计算，得出外部一共会运行 $ log_2 n + 1 = k$。那么内部呢？
内部的循环次数是有外部决定的，也就是 $ 2^{k-1}$
有了外部和内部的循环次数后，我们就可以开始计算了。哦对了，还有一个steps，这个代表步数，由于只是一个k++操作，可以忽略为常数。
重新写为 $\sum^{log_2 + 1} _1 \sum^{2^k-1} _0 1$
通过计算后，可以得出结果就是 $\Theta (n) $
是什么导致了一开始的错误呢？原因很简单，就是因为有一个i *= 2, 如果只是一个简单的 i++ 那么一开始的答案就是正确的呢。
再来一个经典的quickSort。
有这么一个少于20行的代码，你能一眼看出来最好时间复杂度是多少吗？
- a. $T(n) \in \Omega(n^2)$
- b. $T(n) \in \Omega(n)$
- c. $T(n) \in \Omega(nlog n)$
[poll name=poll2 type=regular results=always public=true chartType=bar]
- a
- b
- c
[/poll]
相信大家都不止一次看到过这个算法，也一定都知道这个算法的最好时间为是 $ \Omega(n logn)$ 最坏是 $ O(n^2)$ ,不过有想过是怎么来的吗？
先来分析最坏的情况，什么情况下会发生最坏的情况呢？
当已经是一个有序数组时就是最坏的情况
由于已经是一个有序数组，quickSort会重新去进行排序，直到排序完成，这样子的时间复杂度就来到了 $O(n^2)$
上数学分析：
当最坏情况发生时，我们可以这么的写
$T(n) \in O(1) \quad \text{if } n \leq 1$
$T(n) \in O(n) + T(n-1) \quad \text{if } n > 1$
其中 T(n - 1) 代表了已经排序好的重新排序 T(n) 为数组大小。
开始计算：
$T(n) = n + T(n-1) \quad \text{Iter. 1}$
$\phantom{T(n)} = n + (n-1) + T(n-2) \quad \text{Iter. 2}$
$\phantom{T(n)} = n + (n-1) + (n-2) + T(n-3) \quad \text{Iter. 3}$
$\phantom{T(n)} = n + (n-1) + (n-2) + \cdots + T(n-i) \quad \text{Iter. } i$
又等于
$= n + (n-1) + (n-2) + \cdots + 3 + 2 + T(1)$
$= \sum_{j=2}^{n} j + 1 = \frac{n(n+1)}{2} \in \Theta(n^2)$
这样子就计算出来了最坏的情况。
那么最好的情况又是什么呢？
那当然时最坏相反啦，一个没有排序的数组就是最好的情况
表达式可以这么的写
$T(n) \in \Omega(1) \quad \text{if } n \leq 1$
$T(n) \in \Omega(n) + T\left(\frac{n}{2}\right) + T\left(\frac{n}{2}\right) \quad \text{if } n > 1$
其中 两次的 T(n/2) 代表两次递归调用。那么问题来了
你知道为什么最坏的情况下只有一次 T(n - 1 ) 吗 这个问题留给你们了。
我们继续计算
$f(n) = n + 2T\left(\frac{n}{2}\right) \quad \text{Iter. 1}$
$= n + 2\left(\frac{n}{2} + 2f\left(\frac{n}{2^2}\right)\right) = 2n + 2^2T\left(\frac{n}{2^2}\right) \quad \text{Iter. 2}$
$= 2n + 2^2\left(\frac{n}{2^2} + 2f\left(\frac{n}{2^3}\right)\right) = 3n + 2^3T\left(\frac{n}{2^3}\right) \quad \text{Iter. 3}$
$= in + 2^iT\left(\frac{n}{2^i}\right) \quad \text{Iter. } i$
跟前面的一样，也是在 $ n/2^i = 1$ 的时候结束，也是 $log_2 n = i$
代入到公式中，$ n\log_2 n + nT(1) = n\log_2 n + n \in n\log_2 n$
至此就计算完了最好和最坏的情况。
那么平均呢？
这个问题留给你们了。
结束