算法的渐近符号_渐近符号

素颜马尾好姑娘i 2022-12-07 13:55 312阅读 0赞

算法的渐近符号

Here you will learn about Asymptotic Analysis and Asymptotic Notations in detail.

在这里，您将详细了解渐进分析和渐进符号。

It is common that we write Algorithm before writing code to any problem. There may exist more than one solution for a particular problem. But we need the solution which is better in **time and space complexities**. To compare and analyse algorithms complexities we do some analysis called **Asymptotic Analysis.** That is, we are concerned with the how running time of an algorithm increases with the input. Usually an algorithm asymptotically more efficient will be the best choice.

通常在编写任何问题的代码之前先编写算法。 对于特定问题，可能存在不止一种解决方案。 但是我们需要在**时间和空间复杂度上**更好的解决方案。 为了比较和分析算法的复杂性，我们进行了一些称为“ **渐近分析”的分析。** 也就是说，我们关注算法的运行时间如何随输入而增加。 通常，渐近有效的算法将是最佳选择。

**Also Read: [Analysis of Algorithms][]**

**另请参阅： [算法分析][Analysis of Algorithms]**

## **渐近符号** **(****Asymptotic Notations****)** ##

**Asymptotic Notations** are mathematical tools to represent time complexity of algorithms for asymptotic analysis.

**渐进符号**是代表渐进分析算法时间复杂度的数学工具。

Most commonly used three asymptotic notations are:

最常用的三种渐近符号是：

### 大哦记法(O) **(**Big Oh Notation (O)**)** ###

![Big Oh Notation (O)][Big Oh Notation _O]

It is represented by **O** (capital alphabet O). See the above diagram.

用**O** (大写字母O)表示。 参见上图。

The function f(n) represents that, how running time of the program is increasing when giving larger inputs to the problem.

函数f(n)表示，当为问题提供较大的输入时，程序的运行时间将如何增加。

Now, we try to find what is the worst case or upper bound of the function f(n). So we draw another function g(n) which is always greater than f(n) after some limit n = n0.

现在，我们尝试找出函数f(n)的最坏情况或上限。 因此，我们绘制了另一个函数g(n)，该函数在某个极限n = n 0之后始终大于f(n)。

Therefore we say f(n) = O(g(n)), in the condition that, f(n) <= c g(n), where n >= n0., c > 0, n0 >= 1.

因此我们说f(n)= O(g(n))，条件是f(n)<= cg(n)，其中n> = n 0. ，c> 0，n 0 > = 1。

This says that f(n) is smaller than g(n).** **

这表示f(n)小于g(n)。 ** **

**Example**

**例**

Let f(n) = 3n+2; g(n) = n. To say that f(n) = O g(n),

令f(n)= 3n + 2; g(n)= n。 假设f(n)= O g(n)，

We need to prove that, f(n) <= cg(n); where c > 0, n0 >= 1

我们需要证明，f(n)<= cg(n); 其中c> 0，n 0 > = 1

3n+2 <= cn; If we substitute c = 4, then 3n+2 <= 4n. If we simplify n >= 2.

3n + 2 <= cn; 如果我们用c = 4代替，那么3n + 2 <= 4n。 如果我们简化n> = 2。

Therefore for every n >= 2 and c = 4, f(n) <= c g(n). So f(n) = O g(n).

因此，对于每一个n> = 2和c = 4，f(n)<= cg(n)。 因此f(n)= O g(n)。

Here we proved that, n is bounding given function so definitely greater than “n”, those are n2, n3.. also upper bound this function. But as per Big-O definition, we are interested in **tightest (closest) upper bound.** That is the reason we write 3n+2 = O(n).

在这里，我们证明了，n是给定函数的界，因此绝对大于“ n”，即n 2 ，n 3 ..也是该函数的上限。 但是根据Big-O的定义，我们对**最紧密(最接近)的上限**感兴趣**。** 这就是我们写3n + 2 = O(n)的原因。

### 大欧米符号(Ω) **(**Big Omega Notation (Ω)**)** ###

![Big Omega Notation (Ω)][Big Omega Notation]

It is represented by Greek letter **Ω**.

用希腊字母**Ω**表示。

See the above picture, the actual increasing function of the algorithm is f(n). And we want to give a lower bound for that, it is cg(n).

参见上图，该算法的实际增加函数为f(n)。 我们想为此设置一个下限，即cg(n)。

cg(n) is less than f(n) after some value of n = n0.

在某个值n = n 0之后，cg(n)小于f(n)。

f(n) >= cg(n) , n >= n0, c > 0, n0 >= 1.

f(n)> = cg(n)，n> = n 0 ，c> 0，n 0 > = 1。

If it satisfies above conditions we say, g(n) is smaller than f(n).

如果满足上述条件，我们可以说g(n)小于f(n)。

**Example**

**例**

Let, f(n) = 3n+2. g(n) = n.

设f(n)= 3n + 2。 g(n)= n。

Now check can this f(n) has lower bound as g(n) or not.

现在检查该f(n)是否具有下限g(n)。

f(n) = Ω g(n), this will happen only if f(n) >= c g(n).

f(n)=Ωg(n)，只有在f(n)> = cg(n)时才会发生。

i.e 3n+2 >= cn.  Here c = 1 and n0 >= 1. This is satisfied so f(n) = Ω g(n).

即3n + 2> = cn。 这里c = 1且n 0 > =1。这是满足的，因此f(n)=Ωg(n)。

Therefore, 3n+2 is lower bounded by **n.** Here also since **n** is lower bound of 3n+2, anything less than n also lower bound to 3n+2. That log(n), log log(n), like that. But as per definition we should take **tightest lower bound**, which is n.

因此，3n + 2下限为**n。** 在这里，由于**n**是3n + 2的下界，因此小于n的任何事物也都下界到3n + 2。 那个log(n)，像这样的log log(n)。 但是根据定义，我们应该采用**最严格的下限** n。

### 大Theta符号(Θ **)** **(**Big Theta Notation (Θ**)****)** ###

![Big Theta Notation (Θ)][Big Theta Notation]

This represented by Greek letter **Θ**.

这由希腊字母**Θ**表示。

See the above picture, f(n) is actual growing function. We should find the both the upper bound and lower bound just by varying the constant c, with same function**.** Here that function is g(n).

参见上图，f(n)是实际的增长函数。 我们应该通过改变常数c来找到上限和下限，并且具有相同的函数**。** 这里的函数是g(n)。

If f(n) is bounded by c1 g(n) and c2 g(n) we can say that f(n) = Θ g(n). Constants c1 and c2 could be different.

如果f(n)由c1 g(n)和c2 g(n)界定，我们可以说f(n)=Θg(n)。 常数c1和c2可以不同。

Therefore we say f(n) = Θ g(n) , if f(n) is bounded by g(n) **both in the lower and upper.**

因此，如果f(n) **在上下两边都**受g(n)限制，则说f(n)=Θg(n) **。**

c1 g(n) <= f(n) <= c2 g(n), where c1, c2 > 0, n >= n0, n0 >= 1.

c1 g(n)<= f(n)<= c2 g(n)，其中c1，c2> 0，n> = n 0 ，n 0 > = 1。

**Example**

**例**

F(n) = 3n+2, g(n) = n.

F(n)= 3n + 2，g(n)= n。

F(n) <= c g(n) where c = 4; That is 3n+2 <= 4n. This is valid for all n0 >= 1.

F(n)<= cg(n)其中c = 4; 那就是3n + 2 <= 4n。 这对于所有n 0 > = 1有效。

So we can say g(n) is upper bound for f(n). Now see it is as well as lower bound also.

因此，可以说g(n)是f(n)的上限。 现在看到它以及下界。

F(n) >= c g(n); That is 3n+2 >=  n. where n0 >= 1.

F(n)> = cg(n); 那就是3n + 2> = n。 其中n 0 > = 1。

So both the cases are valid for this.

因此这两种情况都是有效的。

This theta notation also called asymptotically equal.

该theta符号也称为渐近相等。

**Applications of These Notations in Algorithms**

**这些符号在算法中的应用**

*  The Big-O notation says the **worst case** complexity of the algorithm. That means with any large amount of input, that program never exceeds this complexity.
    
    Big-O表示**最坏情况下**算法的复杂性。 这意味着无论输入多少，该程序都不会超过此复杂度。
 *  The Big-Omega notation says that **best case** complexity of the algorithm. That means with any small input, the program never executes less than this complexity.
    
    Big-Omega表示法表示算法的**最佳情况**复杂性。 这意味着在任何小的输入的情况下，程序执行的复杂度都不会低于此。
 *  Theta notation gives the **average case** of complexity.
    
    θ表示法给出了复杂度的**平均值** 。
 *  Most of the cases we are interested in what is the worst case complexity of the program.
    
    在大多数情况下，我们对程序的最坏情况复杂度感兴趣。

For more understanding, see the example below.

要了解更多信息，请参见下面的示例。

Let there is an array of “n” elements. We want to search an element “x” in that array.

假设有一个数组“ n”个元素。 我们要在该数组中搜索元素“ x”。

If we do linear search we may find that element at first index i.e in Ω (1) time. This is the best case of this algorithm.

如果我们进行线性搜索，我们可能会在第一个索引处(即Ω(1)时间)找到该元素。 这是此算法的最佳情况。

In worst case our element “x” many not exists in array. In that case we must check all elements and end up with no result. i.e O (n) time. This is the worst case of this algorithm.

在最坏的情况下，数组中不存在元素“ x”。 在这种情况下，我们必须检查所有元素并最终没有结果。 即O(n)时间。 这是该算法的最坏情况。

Average case is, at some index of array we find that element i.e Θ (n/2) complexity.

平均情况是，在数组的某个索引处，我们发现该元素，即Θ(n / 2)复杂度。

**Some common asymptotic notations are:**

**一些常见的渐近符号是：**

Constant time: O(1)

恒定时间：O(1)

Logarithmic: O(log n)

对数：O(log n)

Linear: O(n)

线性：O(n)

Quadratic: O(n2)

二次方：O(n 2 )

Cubic: O(n3)

立方：O(n 3 )

Polynomial: nO(1)

多项式：n O(1)

Exponential: 2O(n)

指数：2 O(n)

Comment below if you have queries or found any information incorrect in above tutorial for asymptotic notations.

如果您对上面的渐近表示法有疑问或发现任何不正确的信息，请在下面评论。

> 翻译自: [https://www.thecrazyprogrammer.com/2017/06/asymptotic-notations.html][https_www.thecrazyprogrammer.com_2017_06_asymptotic-notations.html]

算法的渐近符号

[Analysis of Algorithms]: https://www.thecrazyprogrammer.com/2017/05/analysis-of-algorithms.html
[Big Oh Notation _O]: /images/20221123/e45d07f686a5436586d944c03f044a8a.png
[Big Omega Notation]: /images/20221123/972784c718a9492da7aa82b17b14c834.png
[Big Theta Notation]: /images/20221123/2ef80eb6e76b4d33851ef55c4cc53e38.png
[https_www.thecrazyprogrammer.com_2017_06_asymptotic-notations.html]: https://www.thecrazyprogrammer.com/2017/06/asymptotic-notations.html