Data Structures Algorithms 简明教程

Data Structures - Asymptotic Analysis

Asymptotic Analysis

算法的渐近分析是指对其运行时性能定义数学基础/框架。使用渐近分析，我们能很好地得出算法的最佳情况、平均情况和最差情况。

Asymptotic analysis of an algorithm refers to defining the mathematical foundation/framing of its run-time performance. Using asymptotic analysis, we can very well conclude the best case, average case, and worst case scenario of an algorithm.

渐近分析是输入绑定的，即，如果算法没有输入，则推断算法以常数时间运行。除了“输入”，所有其他因素都被当作常数。

Asymptotic analysis is input bound i.e., if there’s no input to the algorithm, it is concluded to work in a constant time. Other than the "input" all other factors are considered constant.

渐近分析是指用计算的数学单位计算任何操作的运行时间。例如，一个操作的运行时间计算为 f(n)，而另一个操作的运行时间可能计算为 g(n2)。这意味着随着 n 的增加，第一个操作的运行时间将线性增加，而当 n 增加时，第二个操作的运行时间将呈指数增加。类似地，如果 n 很小，则两个操作的运行时间将几乎相同。

Asymptotic analysis refers to computing the running time of any operation in mathematical units of computation. For example, the running time of one operation is computed as f(n) and may be for another operation it is computed as g(n2). This means the first operation running time will increase linearly with the increase in n and the running time of the second operation will increase exponentially when n increases. Similarly, the running time of both operations will be nearly the same if n is significantly small.

通常，算法所需的时间分为以下三种类型−

Usually, the time required by an algorithm falls under three types −

  1. Best Case − Minimum time required for program execution.

  2. Average Case − Average time required for program execution.

  3. Worst Case − Maximum time required for program execution.

Asymptotic Notations

算法的执行时间取决于指令集、处理器速度、磁盘 I/O 速度等。因此，我们渐近估计算法的效率。

Execution time of an algorithm depends on the instruction set, processor speed, disk I/O speed, etc. Hence, we estimate the efficiency of an algorithm asymptotically.

算法的时间函数表示为 T(n) ，其中 n 是输入大小。

Time function of an algorithm is represented by T(n), where n is the input size.

使用不同类型的渐近标记来表示算法的复杂度。以下渐近标记用于计算算法的运行时间复杂度。

Different types of asymptotic notations are used to represent the complexity of an algorithm. Following asymptotic notations are used to calculate the running time complexity of an algorithm.

  1. O − Big Oh Notation

  2. Ω − Big omega Notation

  3. θ − Big theta Notation

  4. o − Little Oh Notation

  5. ω − Little omega Notation

Big Oh, O: Asymptotic Upper Bound

标记 Ο(n) 是表达算法运行时间上界的正式方法。是最常用的标记。它测量算法可能完成的最长时间或 worst case time complexity 。

The notation Ο(n) is the formal way to express the upper bound of an algorithm’s running time. is the most commonly used notation. It measures the worst case time complexity or the longest amount of time an algorithm can possibly take to complete.

一个函数 f(n) 可以表示为 g(n) 的阶，即 O(g(n)) ，如果正整数 n 的一个值存在为 n0 ，正常数 c 满足 −

A function f(n) can be represented is the order of g(n) that is O(g(n)), if there exists a value of positive integer n as n0 and a positive constant c such that −

对于所有情况，当 $n > n0$ 时，$f(n)\leqslant c.g(n)$。

$f(n)\leqslant c.g(n)$ for $n > n_{0}$ in all case

因此，函数 g(n) 是函数 f(n) 的上界，因为 g(n) 比 f(n) 增长得更快。

Hence, function g(n) is an upper bound for function f(n), as g(n) grows faster than f(n).

big oh

Example

我们考虑一个给定函数，$f(n) = 4.n^3 + 10.n^2 + 5.n + 1$

Let us consider a given function, $f(n) = 4.n^3 + 10.n^2 + 5.n + 1$

设 $g(n) = n^3$，

Considering $g(n) = n^3$,

对于所有满足 $n > 2$ 的值，$f(n)\leqslant 5.g(n)$

$f(n)\leqslant 5.g(n)$ for all the values of $n > 2$

因此， f(n) 的复杂度可以表示为 $O(g(n))$，即 $O(n^3)$

Hence, the complexity of f(n) can be represented as $O(g(n))$, i.e. $O(n^3)$

Big Omega, Ω: Asymptotic Lower Bound

符号 Ω(n) 是形式化地表示算法运行时间的下界的形式。它度量算法可能花费的@\( best case time complexity \)或完成操作的最佳时间量。

The notation Ω(n) is the formal way to express the lower bound of an algorithm’s running time. It measures the best case time complexity or the best amount of time an algorithm can possibly take to complete.

当存在常量@\( c \) 时，使对所有足够大的@\( n \)的值都有 $f(n)\geqslant c.g(n)$，则称 $f(n) = \Omega (g(n))$。其中@\( n \) 是正整数。这意味着函数@\( g \)是函数@\( f \)的下界；在大于@\( n, f \)的某些值之后，永不会低于@\( g \)之。

We say that $f(n) = \Omega (g(n))$ when there exists constant c that $f(n)\geqslant c.g(n)$ for all sufficiently large value of n. Here n is a positive integer. It means function g is a lower bound for function f ; after a certain value of n, f will never go below g.

omega

Example

考虑给定函数 $f(n) = 4.n^3 + 10.n^2 + 5.n + 1$。

Let us consider a given function, $f(n) = 4.n^3 + 10.n^2 + 5.n + 1$.

考虑 $g(n) = n^3$，对所有 $n > 0$ 的值，$f(n)\geqslant 4.g(n)$。

Considering $g(n) = n^3$, $f(n)\geqslant 4.g(n)$ for all the values of $n > 0$.

因此，@\( f(n) \) 的复杂度可以表示为 $\Omega (g(n))$，即 $\Omega (n^3)$。

Hence, the complexity of f(n) can be represented as $\Omega (g(n))$, i.e. $\Omega (n^3)$

Theta, θ: Asymptotic Tight Bound

符号 θ(n) 是形式化地表示算法运行时间的下界和上界的形式。一些人可能会混淆 theta 符号与平均情况时间复杂度；尽管大 theta 符号可以几乎精确地用于描述平均情况，但其他符号也可以使用。

The notation θ(n) is the formal way to express both the lower bound and the upper bound of an algorithm’s running time. Some may confuse the theta notation as the average case time complexity; while big theta notation could be almost accurately used to describe the average case, other notations could be used as well.

当存在常量@\( c1 \) 和@\( c2 \) 使对所有足够大的@\( n \)的值都有 $c_{1}.g(n) \leqslant f(n) \leqslant c_{2}.g(n)$，则称 $f(n) = \theta(g(n))$。其中@\( n \) 是正整数。

We say that $f(n) = \theta(g(n))$ when there exist constants c1 and c2 that $c_{1}.g(n) \leqslant f(n) \leqslant c_{2}.g(n)$ for all sufficiently large value of n. Here n is a positive integer.

这意味着函数@\( g \)是函数@\( f \)的紧束缚。

This means function g is a tight bound for function f.

theta

Example

我们考虑一个给定函数，$f(n) = 4.n^3 + 10.n^2 + 5.n + 1$

Let us consider a given function, $f(n) = 4.n^3 + 10.n^2 + 5.n + 1$

考虑 $g(n) = n^3$，对所有@\( n \)的大值，$4.g(n) \leqslant f(n) \leqslant 5.g(n)$。

Considering $g(n) = n^3$, $4.g(n) \leqslant f(n) \leqslant 5.g(n)$ for all the large values of n.

因此，@\( f(n) \) 的复杂度可以表示为 $\theta (g(n))$，即 $\theta (n^3)$。

Hence, the complexity of f(n) can be represented as $\theta (g(n))$, i.e. $\theta (n^3)$.

Little Oh, o

@\( O-notation \) 提供的渐近上界可能是渐近紧的，也可能不是渐近紧。束缚 $2.n^2 = O(n^2)$ 是渐近紧的，但束缚 $2.n = O(n^2)$ 不是。

The asymptotic upper bound provided by O-notation may or may not be asymptotically tight. The bound $2.n^2 = O(n^2)$ is asymptotically tight, but the bound $2.n = O(n^2)$ is not.

我们使用@\( o-notation \) 来表示不是渐近紧的上界。

We use o-notation to denote an upper bound that is not asymptotically tight.

我们正式定义@\( o(g(n)) \)（g(n) 的小 o）为对任何正的常量 $c > 0$，且存在一个值 $n_{0} > 0$，使得 $0 \leqslant f(n) \leqslant c.g(n)$ 的集合@\( f(n) = o(g(n)) \)。

We formally define o(g(n)) (little-oh of g of n) as the set f(n) = o(g(n)) for any positive constant $c > 0$ and there exists a value $n_{0} > 0$, such that $0 \leqslant f(n) \leqslant c.g(n)$.

直观地说，在@\( o-notation \)，随着@\( n \) 接近无穷大，函数@\( f(n) \) 相对于@\( g(n) \) 变得无关紧要；即，

Intuitively, in the o-notation, the function f(n) becomes insignificant relative to g(n) as n approaches infinity; that is,

\lim_{n \rightarrow \infty}\left(\frac{f(n)}{g(n)}\right) = 0

Example

考虑相同的函数 $f(n) = 4.n^3 + 10.n^2 + 5.n + 1$。

Let us consider the same function, $f(n) = 4.n^3 + 10.n^2 + 5.n + 1$

考虑 $g(n) = n^{4}$，

Considering $g(n) = n^{4}$,

\lim_{n \rightarrow \infty}\left(\frac{4.n^3 + 10.n^2 + 5.n + 1}{n^4}\right) = 0

因此，@\( f(n) \) 的复杂度可以表示为 $o(g(n))$，即 $o(n^4)$。

Hence, the complexity of f(n) can be represented as $o(g(n))$, i.e. $o(n^4)$.

Little Omega, ω

我们使用 ω-notation 来表示一个渐近不严格的下界。然而，我们正式定义 ω(g(n)) （g(n) 的小欧米茄）为集合 f(n) = ω(g(n)) ，对于任何正常数 C > 0 和值 $n_{0} > 0$，都有 $0 \leqslant c.g(n) < f(n)$。

We use ω-notation to denote a lower bound that is not asymptotically tight. Formally, however, we define ω(g(n)) (little-omega of g of n) as the set f(n) = ω(g(n)) for any positive constant C > 0 and there exists a value $n_{0} > 0$, such that $0 \leqslant c.g(n) < f(n)$.

例如，$\frac{n^2}{2} = \omega (n)$，但 $\frac{n^2}{2} \neq \omega (n^2)$。关系 $f(n) = \omega (g(n))$ 暗示存在以下极限

For example, $\frac{n^2}{2} = \omega (n)$, but $\frac{n^2}{2} \neq \omega (n^2)$. The relation $f(n) = \omega (g(n))$ implies that the following limit exists

\lim_{n \rightarrow \infty}\left(\frac{f(n)}{g(n)}\right) = \infty

也就是， f(n) 相对于 g(n) 会变得任意大，因为 n 趋近于无穷大。

That is, f(n) becomes arbitrarily large relative to g(n) as n approaches infinity.

Example

让我们考虑同样的函数，$f(n) = 4.n^3 + 10.n^2 + 5.n + 1$

Let us consider same function, $f(n) = 4.n^3 + 10.n^2 + 5.n + 1$

考虑 $g(n) = n^2$，

Considering $g(n) = n^2$,

\lim_{n \rightarrow \infty}\left(\frac{4.n^3 + 10.n^2 + 5.n + 1}{n^2}\right) = \infty

因此， f(n) 的复杂度可以表示为 $o(g(n))$，即 $\omega (n^2)$。

Hence, the complexity of f(n) can be represented as $o(g(n))$, i.e. $\omega (n^2)$.

Common Asymptotic Notations

下面是一些常见渐近符号的列表 −

Following is a list of some common asymptotic notations −

Apriori and Apostiari Analysis

先验分析是指在特定系统上运行之前执行的分析。此分析是一个阶段，在此阶段使用一些理论模型来定义函数。因此，我们通过查看算法而不是在具有不同内存、处理器和编译器的特定系统上运行它来确定算法的时间和空间复杂度。

Apriori analysis means, analysis is performed prior to running it on a specific system. This analysis is a stage where a function is defined using some theoretical model. Hence, we determine the time and space complexity of an algorithm by just looking at the algorithm rather than running it on a particular system with a different memory, processor, and compiler.

后验算法分析是指仅在系统上运行后才执行的算法分析。它直接取决于系统，并且因系统而异。

Apostiari analysis of an algorithm means we perform analysis of an algorithm only after running it on a system. It directly depends on the system and changes from system to system.

在业界，我们无法执行后验分析，因为该软件通常针对匿名用户制作，该用户在与业界不同的系统上运行它。

In an industry, we cannot perform Apostiari analysis as the software is generally made for an anonymous user, which runs it on a system different from those present in the industry.

在先验分析中，这就是我们使用渐近符号来确定时间和空间复杂度的原因，因为它们会因计算机而异；然而，渐近地，它们是相同的。

In Apriori, it is the reason that we use asymptotic notations to determine time and space complexity as they change from computer to computer; however, asymptotically they are the same.