第4章：渐进符号的介绍

在本章中，我们将学习

4.1什么是渐近符号[AN]？

4.2计算时间的增长顺序表。

4.3将影响运行时间的点列表。

4.4为什么在计算算法复杂度时忽略常量？

4.5渐进符号的类型。

4.1什么是渐近符号[AN]？

AN是用于计算运行时间以及算法增长率的数学函数。

在前面的章节中，我们了解了如何分析时空复杂度。借助先前的学习，我们将看到如何计算渐近符号。

运行时间是指计算机运行算法中所有语句所花费的时间。

增长率指的是当给出大量输入时算法将如何表现。

4.2以下是计算时间增长的一些顺序：

从上表中可以看出，对数算法的增长顺序小于指数算法的增长顺序。因此，如果我们有2种算法解决方案，那么我们应该选择消耗更少时间的解决方案。

logN： 运行时间是对数的。二进制搜索等算法。

N： 运行时间是线性的。线性搜索等算法。

NlogN： 该算法类似于快速排序和合并排序。

N^2: 运行时间是二次的。他们通常会有2个循环。像这样的算法：冒泡排序，选择排序。

2^n: 运行时间是指数的。

我们将在接下来的各章中详细研究它们。

4.3运行程序时，以下是会影响运行时间的要点列表：

1.电脑速度
2.使用的编译器
3.编程语言
4.选择算法
5.输入和输出的类型
6.输入和输出的大小

由于我们无法控制前3分，因此我们将其忽略。我们专注于接下来的3点。

4.4为什么在计算算法复杂度时忽略常量？

这可以通过两个步骤来回答：

1.当我们的时间复杂度为“ O（n ^ 2 + 3）”时，我们忽略常数“ 3”，而发现总的时间复杂度为“ O（n ^ 2）”。这是因为，我们始终想知道该算法在更大的“ n”值下将如何执行。例如，如果“ n”的值为“ 10000”，则常数“ 3”将可忽略不计。因此，我们将其忽略。

2.当我们的时间复杂度为“ O（3n ^ 2）”时，我们忽略常数“ 3”，而最终时间复杂度将为“ O（n ^ 2）”。这是因为不同的计算机体系结构将具有不同的方式来处理常数“ 3”。速度更快的计算机将能够将常量存储在寄存器中，并且能够更快地访问它。较慢的计算机会将其保存在内存中，因此速度较慢。由于我们感兴趣的是，没有算法在硬件性能方面没有表现出来，因此我们忽略了该常数。

4.5渐进符号的类型：

大O： 我们使用这种表示法来计算最坏的情况，称为严格上限。

大欧米茄： 我们使用此符号来计算下限。

位Theta： 我们使用这种表示法来计算平均情况。

让我们借助示例了解最佳，平均和最坏情况：

考虑我们正在搜索10个项目的列表中的键。我们一个接一个地搜索线性搜索。

这里 最佳情况 将是出现在第一项本身上的密钥。

平均情况 是，密钥出现在10个项目的中间位置。

最坏的情况下 是最后一项中出现的关键。

在下一章中，我们将研究 大O 表示法后跟 大欧米茄和大Theta .

AJ的DS和算法指南。单击此处以学习算法和数据结构教程的完整列表。 85多个章节可供学习。

该网站上可用的教程列表：