【时间复杂度】算法时间复杂度计算

先不上具体的算法，先来理论一下如何去计算一个算法的时间复杂度。

这里给出一个递归关系的表达式，你能够得出具体的复杂度是多少吗？

$f(n)=\begin{cases} 1 & n = 1 \ n + 4f(n/2) & n > 1 \end{cases}$

• a. $f(n) \in \Theta(n^2)$ ✓

• b. $f(n) \in \Theta(n)$

• c. $f(n) \in \Theta(n \log n)$

有三种方法可以去算出来

瞪眼法

你直接猜，别管这个那个的，直接就随便猜一个，然后看答案就完事了

Master theorem

很可惜的是，第一种方法的损失太大了。在一个错一道就扣一个正确的情况下，第一种方法还是太难去成功了。那么这里介绍第二种方法，经典的Master theorem。

Master theorem中定义到，

$T(n)=hT( n/b ) + g(n)$

观察到这个表达式和我的递归表达式差不太多，所以我们也可以将我们的递归表达式套入到这个式子中，

$T(n) = 4T(n/2) + g(n) $

另外我们知道 $g(n) \in \Theta(n^k)$，也就是 $k=1$

我们还知道

$$

T(n) = \begin{cases}

\Theta(n^k) & h < b^k \

\Theta(n\log n) & h = b^k \

\Theta(n^{log_b h}) & h > b^k

\end{cases}

$$

根据上面的式子可以发现，$k= 1$。套入上面公式，也就是 $4 > 2^1 $。这对应了第三种情况，我们把数字替换进去，$\Theta(n^{log_2 4}) $。 计算一下，得出时间复杂度为 $\Theta(n^2) $

不是很难吧。就需要记住公式就好了。

---

当然，还有第三种方法，我们需要把求和公式给推导出来，这也很简单，请看我操作

求和

我们知道当

$ n = 1$ -> $ \Theta(n) = n + 4T(n/2) $

$ n = 2$ -> $ \Theta(n) = n + 4( n + 4T(n/4))$ -> $ n + 4n + 4^2T(n/2^2) $

$ n = 3$ -> $ \Theta(n) = n + 4n + 4^2[(n/2) + 4T(n/2^3)] $ -> $\Theta(n) = n + 4n + 4^2n/2 + 4^3T(n/2^3) $

可以观察到有一个规律，当 $ n = k $ 的时候就是我们需要的结果

$ n = k$ -> $ \Theta(n)$ = $n + \sum_{i=0}^{k}2 ^ i n + 4^{k+1} T(n/2^{k+1}) $

我们公式有了，接下来就是下一个条件了，这个递归条件什么时候才能结束呢？从题目发现当 $ n = 1$ 的时候自然就结束了，那么根据这个条件，我们可以得出 $ n/2^k = 1$ -> $k = log_2 n $

从新替换到求和里，我们最终得出的结果就是 $2^{\log_2 n + 1} $， 结果也还是 $n^2$。

比起第三种方法我还是更加喜欢第二种方法，站在前人的肩膀上去易化困难的题目。

下一次再带来带有代码的例子吧。这次就到这了。