时间复杂度

时间复杂度 / Time Complexity

时间复杂度

在计算机科学中，时间复杂度是衡量算法运行效率的重要指标。

In computer science, time complexity is a crucial metric for measuring the efficiency of an algorithm.

时间复杂度通常用大 O 符号表示，例如 $O(n)$、$O(n^2)$ 等，表示算法运行时间与输入数据规模的关系。时间复杂度越低，算法的运行效率越高。

Time complexity is usually expressed using Big O notation, such as $O(n)$, $O(n^2)$, etc., indicating the relationship between the running time of the algorithm and the size of the input data. The lower the time complexity, the more efficient the algorithm.

定义 / Definition

对于一个算法，假设其输入规模为 $n$，运行时间为 $T(n)$，则该算法的时间复杂度为：

For an algorithm, assuming its input size is $n$ and its running time is $T(n)$, the time complexity of the algorithm is:

$$T(n)=O(f(n))$$

其中 $f(n)$ 是一个函数，表示算法运行时间与输入规模 $n$ 的关系。

where $f(n)$ is a function representing the relationship between the running time of the algorithm and the input size $n$.

渐进符号 / Asymptotic Notations

在计算时间复杂度时，通常使用以下三种渐进符号：

When calculating time complexity, the following three asymptotic notations are commonly used:

1. 大 O 符号 / Big O Notation：表示算法的最坏情况运行时间，即算法的上界。 Represents the worst-case running time of the algorithm, i.e., the upper bound of the algorithm.

2. 大 $\Omega$ 符号 / Big $\Omega$ Notation：表示算法的最好情况运行时间，即算法的下界。 Represents the best-case running time of the algorithm, i.e., the lower bound of the algorithm.

3. 大 $\Theta$ 符号 / Big $\Theta$ Notation：表示算法的平均情况运行时间。 Represents the average-case running time of the algorithm.

在实际应用中，我们通常关注算法的最坏情况时间复杂度，因为它能够保证算法在任何情况下都能在规定时间内完成。

In practical applications, we usually focus on the worst-case time complexity of an algorithm because it ensures that the algorithm can complete within a specified time under any circumstances.

数学定义 / Mathematical Definition

对于一个函数 $f(n)$，如果存在常数 $c$ 和 $n_0$，使得对于所有 $n>n_0$，有：

For a function $f(n)$, if there exist constants $c$ and $n_0$ such that for all $n>n_0$:

$$0\le f(n)\le c\cdot g(n)$$

则称 $f(n)$ 是 $O(g(n))$。

then $f(n)$ is said to be $O(g(n))$.

同样的，如果存在常数 $c$ 和 $n_0$，使得对于所有 $n>n_0$，有：

Similarly, if there exist constants $c$ and $n_0$ such that for all $n>n_0$:

$$0\le c\cdot g(n)\le f(n)$$

则称 $f(n)$ 是 $\Omega (g(n))$。

then $f(n)$ is said to be $\Omega (g(n))$.

如果 $f(n)$ 既是 $O(g(n))$ 又是 $\Omega (g(n))$，则称 $f(n)$ 是 $\Theta (g(n))$。

If $f(n)$ is both $O(g(n))$ and $\Omega (g(n))$, then $f(n)$ is said to be $\Theta (g(n))$.

常见的时间复杂度 / Common Time Complexities

1. $O(1)$ - 常数时间复杂度 / Constant Time Complexity

   • 这种复杂度表示算法的运行时间不随输入数据的规模变化。例如，访问数组中的某个元素。 This complexity indicates that the running time of the algorithm does not change with the size of the input data. For example, accessing an element in an array.

2. $O(\log n)$ - 对数时间复杂度 / Logarithmic Time Complexity

   • 这种复杂度通常出现在分治算法中，例如二分查找。 This complexity usually appears in divide-and-conquer algorithms, such as binary search.

3. $O(n)$ - 线性时间复杂度 / Linear Time Complexity

   • 算法的运行时间与输入数据规模成正比。例如，线性搜索。 The running time of the algorithm is proportional to the size of the input data. For example, linear search.

4. $O(n\log n)$ - 线性对数时间复杂度 / Linearithmic Time Complexity

   • 这是高效排序算法（如快速排序、归并排序和堆排序）的典型时间复杂度。 This is the typical time complexity of efficient sorting algorithms, such as quicksort, mergesort, and heapsort.

5. $O(n^2)$ - 二次时间复杂度 / Quadratic Time Complexity

   • 这种复杂度通常出现在简单的排序算法中，如冒泡排序、选择排序和插入排序。 This complexity usually appears in simple sorting algorithms, such as bubble sort, selection sort, and insertion sort.

6. $O(n^3)$ - 三次时间复杂度 / Cubic Time Complexity

   • 例如，朴素的矩阵乘法算法。 For example, the naive matrix multiplication algorithm.

7. $O(2^n)$ - 指数时间复杂度 / Exponential Time Complexity

   • 这种复杂度通常出现在解决某些递归问题的算法中，例如解决 TSP（旅行商问题）的递归方法。 This complexity usually appears in algorithms that solve certain recursive problems, such as the recursive method for solving the TSP (Traveling Salesman Problem).

8. $O(n!)$ - 阶乘时间复杂度 / Factorial Time Complexity

   • 这种复杂度通常出现在组合优化问题中，例如全排列的生成。 This complexity usually appears in combinatorial optimization problems, such as generating all permutations.

常见排序算法及其时间复杂度 / Common Sorting Algorithms and Their Time Complexities

1. 冒泡排序 (Bubble Sort)

   • 时间复杂度 / Time Complexity：$O(n^2)$
   • 简单但效率低，适用于小规模数据。 Simple but inefficient, suitable for small-scale data.

2. 选择排序 (Selection Sort)

   • 时间复杂度 / Time Complexity：$O(n^2)$
   • 通过反复选择剩余元素中的最小值来排序。 Sorts by repeatedly selecting the minimum value from the remaining elements.

3. 插入排序 (Insertion Sort)

   • 时间复杂度 / Time Complexity：$O(n^2)$
   • 对于几乎有序的数据，表现良好。 Performs well for nearly sorted data.

4. 归并排序 (Merge Sort)

   • 时间复杂度 / Time Complexity：$O(n\log n)$
   • 分治算法，稳定排序。 Divide-and-conquer algorithm, stable sorting.

5. 快速排序 (Quick Sort)

   • 时间复杂度 / Time Complexity：平均 $O(n\log n)$，最坏 $O(n^2)$ Average $O(n\log n)$, worst $O(n^2)$
   • 分治算法，不稳定排序。 Divide-and-conquer algorithm, unstable sorting.

6. 堆排序 (Heap Sort)

   • 时间复杂度 / Time Complexity：$O(n\log n)$
   • 基于堆数据结构，不稳定排序。 Based on heap data structure, unstable sorting.

7. 计数排序 (Counting Sort)

   • 时间复杂度 / Time Complexity：$O(n+k)$，其中 $k$ 是数据范围 Where $k$ is the range of the data
   • 适用于数据范围不大的整数排序，稳定排序。 Suitable for sorting integers with a limited range, stable sorting.

8. 基数排序 (Radix Sort)

   • 时间复杂度 / Time Complexity：$O(nk)$，其中 $k$ 是位数 Where $k$ is the number of digits
   • 适用于整数和字符串的排序，稳定排序。 Suitable for sorting integers and strings, stable sorting.

复杂时间复杂度计算方法 / Complex Time Complexity Calculation Methods

递归算法的时间复杂度 / Time Complexity of Recursive Algorithms

对于递归算法，我们通常使用递推关系来表达其时间复杂度。解决递推关系的常用方法包括递归树法、主定理和代入法。

For recursive algorithms, we usually use recurrence relations to express their time complexity. Common methods for solving recurrence relations include the Recursion Tree Method, the Master Theorem, and the Substitution Method.

1. 递归树法 / Recursion Tree Method

   • 通过画出递归树，计算每一层的总时间，然后

   求和得到总时间复杂度。

   By drawing a recursion tree, calculating the total time for each level, and then summing them up to get the total time complexity.

2. 主定理 / Master Theorem

   主定理适用于以下形式的递推关系：

   The Master Theorem applies to the following form of recurrence relations:

$$T(n)=aT\left(\frac{n}{b}\right)+f(n)$$

其中 $a\ge 1$ 且 $b>1$。主定理提供了三种情况来解决递推关系：

Where $a\ge 1$ and $b>1$. The Master Theorem provides three cases to solve the recurrence relation:

• 若 $f(n)=O(n^c)$，且 $c<{\log }_{b}a$，则 $T(n)=\Theta (n^{{\log }_{b}a})$ If $f(n)=O(n^c)$ and $c<{\log }_{b}a$, then $T(n)=\Theta (n^{{\log }_{b}a})$
• 若 $f(n)=\Theta (n^c)$，且 $c={\log }_{b}a$，则 $T(n)=\Theta (n^c\log n)$ If $f(n)=\Theta (n^c)$ and $c={\log }_{b}a$, then $T(n)=\Theta (n^c\log n)$
• 若 $f(n)=\Omega (n^c)$，且 $c>{\log }_{b}a$，则 $T(n)=\Theta (f(n))$ If $f(n)=\Omega (n^c)$ and $c>{\log }_{b}a$, then $T(n)=\Theta (f(n))$

1. 代入法 / Substitution Method

   通过猜测递推关系的解并进行数学归纳法证明。

   By guessing the solution of the recurrence relation and proving it by mathematical induction.

示例：归并排序 / Example: Merge Sort

归并排序的递推关系为：

The recurrence relation for merge sort is:

$$T(n)=2T\left(\frac{n}{2}\right)+O(n)$$

使用主定理：

Using the Master Theorem:

• $a=2$
• $b=2$
• $f(n)=O(n)$
• ${\log }_{b}a={\log }_{2}2=1$

因为 $f(n)=O(n)$ 且 $c=1={\log }_{2}2$，符合主定理的第二种情况，所以：

Since $f(n)=O(n)$ and $c=1={\log }_{2}2$, it fits the second case of the Master Theorem, so:

$$T(n)=\Theta (n\log n)$$

递归树法示例：矩阵链乘法 / Recursion Tree Method Example: Matrix Chain Multiplication

矩阵链乘法的递推关系为：

The recurrence relation for matrix chain multiplication is:

$$T(n)=\underset{1\le k<n}{\min }(T(k)+T(n-k)+P(k,n))$$

其中 $P(k,n)$ 是计算乘法操作的代价。

Where $P(k,n)$ is the cost of the multiplication operation.

通过画递归树并计算每一层的总时间，得出：

By drawing a recursion tree and calculating the total time for each level, we get:

$$T(n)=O(n^3)$$

这些方法可以帮助我们解决递归算法的时间复杂度，从而更好地评估算法的性能。

These methods can help us determine the time complexity of recursive algorithms, thus better evaluating the performance of algorithms.

主定理的证明（Master Theorem Proof）

主定理是解决递归关系的一种重要方法，特别适用于许多分治算法的时间复杂度分析。主定理适用于以下形式的递归关系：

$$T(n)=aT\left(\frac{n}{b}\right)+f(n)$$

其中，$a\ge 1$ 和 $b>1$ 是常数，$f(n)$ 是一个给定的函数。

主定理的三个情形如下：

1. 情形 1: 如果存在常数 $\epsilon >0$ 使得 $f(n)=O(n^{{\log }_{b}a-\epsilon })$，则 $T(n)=\Theta (n^{{\log }_{b}a})$。
2. 情形 2: 如果 $f(n)=\Theta (n^{{\log }_{b}a})$，则 $T(n)=\Theta (n^{{\log }_{b}a}\log n)$。
3. 情形 3: 如果存在常数 $\epsilon >0$ 使得 $f(n)=\Omega (n^{{\log }_{b}a+\epsilon })$，且对于足够大的 $n$，有 $af\left(\frac{n}{b}\right)\le kf(n)$，其中 $0<k<1$ 为常数，则 $T(n)=\Theta (f(n))$。

主定理的证明

证明主定理需要构造递归树并分析其总成本。

递归树分析

考虑递归关系 $T(n)=aT\left(\frac{n}{b}\right)+f(n)$：

1. 递归树的构造:

   • 树的每一层表示一次递归调用
   • 根节点的成本是 $f(n)$
   • 第 $i$ 层有 $a^i$ 个节点，每个节点的成本是 $f\left(\frac{n}{b^i}\right)$

2. 总成本的计算:

   • 树的高度为 ${\log }_{b}n$
   • 每一层的总成本是 $a^{i}f\left(\frac{n}{b^i}\right)$
   • 总成本 $T(n)$ 是所有层成本的总和

情形 1 证明

假设 $f(n)=O(n^{{\log }_{b}a-\epsilon })$。总成本的上界为：

$$T(n)=\sum _{i=0}^{{\log }_{b}n}{a}^{i}f\left(\frac{n}{b^i}\right)$$

由于 $f\left(\frac{n}{b^i}\right)=O\left({\left(\frac{n}{b^i}\right)}^{{\log }_{b}a-\epsilon }\right)$，有：

$$T(n)=\sum _{i=0}^{{\log }_{b}n}{a}^i{\left(\frac{n}{b^i}\right)}^{{\log }_{b}a-\epsilon }=\sum _{i=0}^{{\log }_{b}n}\frac{a^i{n}^{{\log }_{b}a-\epsilon }}{b^{i({\log }_{b}a-\epsilon )}}$$

由于 $a=b^{{\log }_{b}a}$，故有：

$$T(n)=n^{{\log }_{b}a-\epsilon }\sum _{i=0}^{{\log }_{b}n}{b}^{i\epsilon }$$

这是一个几何级数，其和为 $O(1)$，因为 $\epsilon >0$。因此：

$$T(n)=O(n^{{\log }_{b}a})$$

情形 2 证明

假设 $f(n)=\Theta (n^{{\log }_{b}a})$。则总成本为：

$$T(n)=\sum _{i=0}^{{\log }_{b}n}{a}^i{\left(\frac{n}{b^i}\right)}^{{\log }_{b}a}=\sum _{i=0}^{{\log }_{b}n}{n}^{{\log }_{b}a}$$

因为每一项 $n^{{\log }_{b}a}$，有 ${\log }_{b}n$ 项：

$$T(n)=\Theta (n^{{\log }_{b}a}\log n)$$

情形 3 证明

假设 $f(n)=\Omega (n^{{\log }_{b}a+\epsilon })$ 且 $af\left(\frac{n}{b}\right)\le kf(n)$，其中 $0<k<1$。有：

$$T(n)\le f(n)\sum _{i=0}^{{\log }_{b}n}{k}^i$$

这是一个收敛的几何级数，和为 $O(1)$：

$$T(n)=\Theta (f(n))$$

结论

主定理通过递归树的方法，从递归关系中提取出其时间复杂度，帮助我们在分析复杂分治算法时提供了强有力的工具。