数据结构中的大 o 符号：要知道的一切

数据结构中的大 O 表示法用于确定算法的效率、随着输入的增长运行函数所需的时间量以及函数的可扩展性。 衡量这个效率可以分为两部分，即空间复杂度和时间复杂度。

大 O 表示法是指当参数更倾向于倾向于特定值或无穷大时，充当任何函数的限制因素的数学符号。 它属于 Edmund Landau、Paul Bachmann 等人发明的数学符号类别。 因此，它被统称为 Bachmann-Landau 符号或渐近符号。

根据数学推论，两个函数f(n)和g(n)定义在一组不受约束的正数或实数上。 这里， g(n)对于 n 的每个大值都是严格正的。 它可以用以下方式编写：

f(n) = O(g(n))其中 n 趋于无穷大(n → ∞)

但是，这里没有专门定义 n 到无穷大的假设，因此上述表达式可以写成：

f(n) = O(g(n))

这里，f 和 g 是从正整数到非非负实数的必要函数。

因此，大的 n 值由大 O 渐近线表示。

数据结构中大 O 表示法的属性

数据结构中的大 O算法有很多强制要求的属性。 大 O 表示法的上述基本性质如下：

• 求和函数：
  若 f(n) = f 1 (n) + f 2 (n) + — + f m (n) 且 f i (n)≤ f i +1(n) ∀ i=1, 2,–, m,
  然后 O(f(n)) = O(max(f1(n), f2(n), –, fm(n)))。
• 对数函数：
  如果 f(n) = logan 且 g(n)=logbn，
  那么 O(f(n))=O(g(n))
• 常数乘法：
  如果 f(n) = cg(n)，则 O(f(n)) = O(g(n)) 其中 c 是一个非零常数。
• 多项式函数：
  如果 f(n) = a0 + a1.n + a2.n2 + — + am.nm，
  然后 O(f(n)) = O(nm)。

从世界顶级大学在线学习软件开发课程。 获得行政 PG 课程、高级证书课程或硕士课程，以加快您的职业生涯。

探索我们流行的软件工程课程

在这里，在处理大 O 时，每个日志函数都类似地增加。

大 O 符号在算法运行时分析中的重要性

算法的最坏情况运行时间的复杂度用于进行比较和计算，特别是在分析算法性能的情况下。 O(1) 的顺序，描述为恒定运行时间，是算法的最快运行时间——算法所花费的时间对于不同的输入大小是相同的。 重要的是要注意，算法的理想运行时间是恒定的运行时间，这很少能实现，因为算法的运行时间取决于 n 的输入大小。

例如：

如上所述，算法的运行时性能主要取决于 n 的输入大小。 让我们用几个数学例子来阐明这个事实，以便对不同大小的 n 的算法进行运行时分析：

• n = 20
  日志 (20) = 2.996;
  20 = 20；
  20 对数 (20) = 59.9；
  20 2 = 400；
  2 20 = 1084576；
  20！ = 2.432902 + 18 18 ;
• n = 10
  日志 (10) = 1;
  10 = 10；
  10 对数 (10) = 10；
  10 2 = 100；
  2 10 = 1024；
  10！ = 3628800;

类似地计算算法的运行时性能。

以下是运行时分析的其他一些算法示例——

• 对于线性搜索，运行时复杂度为 O(n)。
• 二分查找的运行时复杂度为 O(log n)。
• 对于选择排序、冒泡排序、桶排序、插入排序，运行时复杂度为 O(n^c)。
• 当涉及指数算法（例如河内塔）时，运行时复杂度为 O(c^n)。
• 对于 Merge SortSort 和 Heap Sort，运行时复杂度为 O(n log n)。

Big O 如何分析空间复杂度？

确定算法的空间复杂度和运行时复杂度是必不可少的步骤。 这是因为通过分析算法的空间复杂度，我们可以通过分析算法的运行时性能和算法占用的内存空间来确定算法所花费的执行时间。 因此，衡量一个算法的空间复杂度，我们必须比较算法在最坏情况下的空间复杂度性能。

为了确定算法的空间复杂度，我们必须遵循以下两个任务——

任务 1：为特定算法实现程序至关重要。

任务 2：必须知道输入 n 的大小以确定每个项目将容纳的内存。

这两个基本任务需要在计算算法的空间复杂度之前完成。

空间复杂度算法的例子

有很多具有空间复杂度的算法示例，为了更好地理解这类算法，下面提到了其中的一些示例：

• 对于冒泡排序、线性搜索、选择排序、插入排序、堆排序和二分搜索，空间复杂度为O(1) 。
• 基数排序的空间复杂度为O(n+k) 。
• 快速排序的空间复杂度为O(n) 。
• 归并排序的空间复杂度为O(log n) 。

C 中的大 O 表示法示例

事实上，Big O 表示法主要用于计算机科学中，用于确定算法的复杂性或性能。 当输入数据的范围变大时，这种表示法使我们能够根据内存空间的增长或执行时间要求对算法的行为进行分类。 它并非旨在预测实际的内存使用或执行时间，而是用于比较算法，然后为作业选择最佳算法。 它不是特定于语言的，但也在 C 中实现。

下面，您将在 C 中找到选择排序算法，其中计算了算法的最坏情况复杂度（大 O 表示法）：-

for(int i=0; i<n; i++)

{

int min = i;

for(int j=i;j<n;j++)

{

如果（数组[j]<数组[分钟]）

最小=j；

}

int temp = 数组[i];

数组[i] = 数组[分钟];

数组[分钟] = 温度；

}

分析算法：

• 已经可以表示 for 外循环的范围是i < n ，这表明循环的阶数是 O(n)。
• 接下来，我们可以确定内部 for 循环的 j < n 也是 O(n)。
• 即使发现常数 c 的平均效率为 n/2，该常数也将被忽略。 所以，顺序是O(n)。
• 将内循环和外循环的顺序相乘后，实现的运行时复杂度为 O(n^2)。

C 中的其他算法可以很容易地实现，其中的复杂性可以很容易地分析和确定。

大 O 表示法的使用

应用大 O 表示法有两个主要领域：-

• 数学：大 O 表示法在数学领域非常常用，用于描述有限级数如何逼近函数，尤其是在涉及渐近展开或截断泰勒级数的情况时。
• 计算机科学：众所周知，Big O 表示法主要用于计算机科学领域，因为它在算法分析中很有用

然而，在这两种应用中，如果省略了低阶项和常数因子，出现在O (·) 中的函数g ( x ) 通常被选择为可能是最简单的。

这个符号还有另外两种形式上接近但相对不同的用法。 他们是：-

• 无限渐近线
• 无穷小渐近线。

然而，这种区别在原则上并不适用，仅适用于“大 O”的正式定义在两种情况下完全相同。 唯一的区别是函数参数的限制。

阅读我们与软件开发相关的热门文章

结论

总之，我们可以说大数据在数据结构中起着不可或缺的作用，对大 O 表示法有深入、全面的了解是一项非常好的技能。 它在工作领域的需求量很大，并且可能是职业道路的绝佳选择。 upGrad 的大数据高级证书课程将为您提供提升职业生涯所需的杠杆作用。 它将向您介绍顶级专业技能，如使用 PySpark 进行数据处理、数据仓库、MapReduce、AWS 云上的大数据处理、实时处理等。