时间复杂度

---

---

本章我们将讨论算法的时间复杂度及其影响因素。

时间复杂度

一般来说，算法的时间复杂度是指算法执行代码中每条语句所需的时间。它不是算法的执行时间。这个量会受到多种因素的影响，例如输入大小、使用的方法和过程。当在尽可能短的时间内产生输出时，算法被认为是最有效的。

找到算法时间复杂度的最常用方法是将算法推导为递推关系。让我们进一步了解它。

求解递推关系

递推关系是由自身较小输入定义的方程（或不等式）。这些关系是基于数学归纳法求解的。在这两个过程中，一个条件允许问题被分解成较小的部分，这些部分使用较低值的输入执行相同的方程。

这些递推关系可以使用多种方法求解；它们是：

• 代换法

• 递归树法

• 迭代法

• 主定理

代换法

代换法是一种试错法；其中，我们可能认为可能是关系解的值被代入并检查方程是否有效。如果有效，则找到解。否则，检查另一个值。

步骤

使用代换法求解递推关系的步骤如下：

• 基于试错法猜测解的形式

• 使用数学归纳法证明该解对所有情况都正确。

示例

让我们来看一个使用代换法求解递推关系的例子：

T(n) = 2T(n/2) + n

这里，我们假设该方程的时间复杂度为**O(nlogn)**。因此，根据数学归纳法，T(n/2) 的时间复杂度将为**O(n/2logn/2)**；将该值代入给定方程，我们需要证明T(n)必须大于或等于**nlogn**。

≤ 2n/2Log(n/2) + n
= nLogn - nLog2 + n
= nLogn - n + n
≤ nLogn

递归树法

在递归树方法中，我们绘制一个递归树，直到程序无法进一步细分为更小的部分。然后，我们计算递归树每一层所需的时间。

步骤

• 绘制程序的递归树

• 计算每一层的时间复杂度，并将它们加起来以找到总的时间复杂度。

示例

考虑二分查找算法并为其构建递归树：

由于该算法遵循分治策略，因此递归树绘制到它达到最小输入级别$\mathrm{T\left ( \frac{n}{2^{k}} \right )}$.

$$\mathrm{T\left ( \frac{n}{2^{k}} \right )=T\left ( 1 \right )}$$

$$\mathrm{n=2^{k}}$$

在方程的两边应用对数，

$$\mathrm{log\: n=log\: 2^{k}}$$

$$\mathrm{k=log_{2}\:n}$$

因此，二分查找算法的时间复杂度为**O(log n)**。

主方法

主方法或主定理应用于递减或划分递推关系以查找时间复杂度。它使用一组公式来推导出算法的时间复杂度。

要了解更多关于主定理的信息，请点击这里