我们已经讨论过渐近分析， 和最坏的情况下,平均那和最佳算法案例。渐近分析的主要思想是衡量不依赖于机器特定常量的算法的效率，并且不需要将算法实现和待比较的程序所花费的时间。渐近符号是数学工具，以表示渐近分析的算法的时间复杂性。以下3个渐近符号主要用于表示算法的时间复杂性。

1）θ表示法：符号从上到下界定了一个函数，所以它定义了确切的渐近行为。
获得表达式的Theta符号的一个简单方法是去掉低阶项并忽略前导常数。例如，考虑下面的表达式。
3N.^3.+ 6n.²+ 6000 =θ（n^3.）
丢弃下顺序总是很好的，因为在其中总是有一个数字（n）（n^3.）具有比θ更高的值（n²）无论涉及的常量如何。
对于给定的函数g（n），我们表示θ（g（n））是遵循一组功能。

θ（g（n））= {f（n）：存在正常数c1，c2和n0，使得所有<= c1 * g（n）<= f（n）<= c2 * g（n）n> = n0}

上述定义意味着，如果f（n）是g（n）的θ，则对于n（n> =的大值），值f（n）始终在C1 * g（n）和c2 * g（n）之间。n0）。Theta的定义还要求F（n）必须为n值的值，对于n0大于n0。

2）大O表示法：大O表示法定义了算法的上限，它仅从上面界定函数。例如，考虑插入排序的情况。在最坏的情况下，它在最佳案例和二次时间中需要线性时间。我们可以安全地说插入排序的时间复杂性是O（n ^ 2）。请注意，O（n ^ 2）也涵盖线性时间。
如果我们使用θ表示法表示插入排序的时间复杂性，我们必须使用两个最佳和最糟糕的案例的语句：
1.插入排序的最坏情况复杂度是θ（n ^ 2）。
插入排序的最佳情况复杂性是θ（n）。

当我们只有算法的时间复杂性的上限时，大的o表示法很有用。很多时候我们只需查看算法即可轻松找到一个上限。

O(g(n)) = {f(n):存在正常数c和n0使0 <= f(n) <= c*g(n)对于所有n >= n0}

3）Ω表示法：正如大O符号提供了一个函数的渐近上界，Ω符号提供了一个渐近下界。
当我们对算法的时间复杂性下降时，Ω表示法很有用。正如前面的帖子所讨论的那样算法的最佳案例性能通常无用，是三种符号中使用最少的。

对于给定的函数g（n），我们表示ω（g（n））该集合。

ω（g（n））= {f（n）：存在正常数c和n0，使得所有n> n0}为0 <= c * g（n）<= f（n）。

让我们考虑同样的插入排序示例。插入排序的时间复杂度可以写成Ω(n)，但这不是关于插入排序的非常有用的信息，因为我们通常对最坏情况感兴趣，有时也对一般情况感兴趣。

渐近符号的性质：
由于我们经历了这三个符号的定义，我们现在讨论这些符号的一些重要属性。

1.一般属性:

如果f（n）是o（g（n）），则a * f（n）也是o（g（n））;其中a是常数。

例子:f(n) = 2n²+5 = O(n²)
那么7*f(n) = 7(2n²+5)= 14n²+35也是O(n²)

类似地，该属性满足θ和Ω表示法。

我们可以说
如果f（n）是θ（g（n）），则a * f（n）也是θ（g（n））;其中a是常数。
如果f（n）是ω（g（n）），则a * f（n）也是ω（g（n））;其中a是常数。

2.传递属性:

如果f（n）是o（g（n）），并且g（n）是o（h（n））那么f（n）= o（h（n））。

示例：如果f（n）= n，g（n）=n²和h（n）=n³
n是o（n²）和n²是o（n³）
然后n是o（nə）

类似地，该属性满足θ和Ω表示法。

我们可以说
如果f（n）是θ（g（n））和g（n）是θ（h（n）），则f（n）=θ（h（n））。
如果f（n）是ω（g（n））和g（n）是ω（h（n）），则f（n）=ω（h（n））

3.反射性的属性：

在传递后，反射性能始终易于理解。

如果f(n)已知，那么f(n) = O(f(n))自F（n）的最大值将是f（n）本身！

因此，x = f（n）和y = o（f（n）始终将自身系在反射关系中。

例子：f（n）=n²;o（n²）i.e（f（n））

类似地，该属性满足θ和Ω表示法。

我们可以这么说：

如果给出f（n），则f（n）是θ（f（n））。

如果给出f（n），则f（n）是ω（f（n））。

4.对称属性：

如果f（n）是θ（g（n）），则g（n）是θ（f（n））。

示例：f（n）=n²和g（n）=n²
然后f（n）=θ（n²）和g（n）=θ（n²）

此属性仅满足θ表示法。

5.转置对称属性：

如果f（n）是o（g（n）），则g（n）是ω（f（n））。

例子：f（n）= n，g（n）=n²
然后n是O（n²），n 2是ω（n）

此属性仅满足O和Ω符号。

6.更多属性:

1.）如果f（n）= o（g（n））和f（n）=ω（g（n））则f（n）=θ（g（n））

2.）如果f（n）= o（g（n））和d（n）= o（e（n））
然后f（n）+ d（n）= o（max（g（n），e（n））））
例子：f（n）= n i.e（n）
d（n）=n²i.e（n²）
然后f（n）+ d（n）= n +n²i.e（n²）

3)。如果f(n)=O(g(n)) and d(n)=O(e(n))
然后f（n）* d（n）= o（g（n）* e（n））
例子：f（n）= n i.e（n）
d（n）=n²i.e（n²）
然后f（n）* d（n）= n *n²= n 1 i.e（nə）

___________________________________________________________________________

锻炼：
下列哪个陈述是有效的?
1.Quicksort的时间复杂性是θ（n ^ 2）
2.快速排序的时间复杂度为O(n^2)
3.对于任意两个功能f（n）和g（n），如果且仅当f（n）= o（g（n））和f（n）=才有，则我们具有f（n）=θ（g（n））ω（g（n））。
4.所有计算机算法的时间复杂性可以写为ω（1）

重要的链接:

• 还有另外两种符号小o和小omega。小o提供严格的上限（从大o删除平等状况），小omega提供严格的下限（从大omega删除平等状况）
• 算法分析|设置4（循环分析）
• 算法分析的最新文章。

参考：
LEC 1 |麻省理工学院（算法简介）

本文是贡献的Abhay Rathi.。如果您发现任何不正确的任何内容，请写出评论，或者您想要共享有关上面讨论主题的更多信息。

注意读者！现在不要停止学习。掌握所有重要的DSA概念DSA自我节奏课程以学生友好188bet2021欧洲杯的价格，成为行业准备。