数据结构中的大O表示法简介

---

介绍

大O表示法是计算机科学中最重要的数学表示法之一，用于确定算法的效率。它可以用来评估算法的效率，包括运行算法所需的时间、内存、其他资源以及输入大小的变化。数据结构中的大O表示法提供了有关算法在各种条件下性能的信息。换句话说，它提供了算法的最坏情况复杂度或上界运行时间。

数据结构中的大O表示法

输入大小的变化会影响算法的性能。在这种情况下，渐近表示法（如大O表示法）很有用。当输入接近某个特定值或极限值时，渐近表示法可用于表示算法的运行时间。

数据结构中使用大O表示法用代数术语表示算法复杂度。它确定在给定输入值下运行算法所需的时间和内存，并表示算法运行时间的上限。

大O是一种数学表示法，其名称来源于“函数阶”，指的是函数的增长。它是渐近表示法家族的一员，也称为兰道符号。

数学解释

考虑函数f(n) & g(n)，其中f和g在正实数集合上具有无界定义。对于g(n)的每个大值n，都有一个严格的正值。

如果函数f (n) CG(n) 对于所有n >= n0 对于一个常数c>0和一个自然数n0，则该函数被称为O(g)（读作g的大O）。

可以写成

其中n趋于无穷大(n )，f(n) = O(g(n))。

上述表达式可以简洁地表示为

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

算法分析

以下是Big-O运行时分析的一般分步过程

• 确定输入以及n代表什么。
• 用n表示算法操作的最高限制。
• 删除除最高阶项以外的所有项。
• 消除所有常数元素。

以下是Big-O表示法分析的一些有益特性

• 如果f(n) = CG(n)，则O(f(n)) = O(g(n))，对于一个常数c > 0，分别对应于常数乘法。

• 如果f(n) = f1(n) + f2(n) + — + FM(n) 并且fi(n) fi+1(n) i=1, 2, --, m，则求和函数为：因此，O(f(n)) = O(max(f1(n), f2(n), -, fm(n))

• 如果f(n) = log an 和g(n) = log bn，则对数函数为O(f(n)) = O(g(n))。

• 如果f(n) = g(n)，则

  如果多项式函数，则f(n) = a0 + a1.n + a2.n2 + — + am.nm，则O(f(n)) = O(nm) (nm)。

为了评估和评估算法的性能，我们必须计算和分析算法的最坏运行时复杂度。算法最快的运行时间为O(1)，也称为常数运行时间，无论输入数量是多少，它都花费相同的时间。尽管它是算法的最佳运行时间，但很少能实现常数运行时间，因为持续时间依赖于n个输入的大小。

具有高运行时复杂度的典型算法示例

• 线性搜索运行时复杂度：O (n)
• 二分搜索运行时复杂度 - O (log n)
• 冒泡排序、插入排序、选择排序和桶排序的运行时复杂度为O(nc)。
• 汉诺塔等指数算法的运行时复杂度为O(cn)。
• 堆排序和归并排序的运行时复杂度为O (n log n)。

分析空间复杂度

确定算法的空间复杂度也很重要。这是因为算法的空间复杂度显示了它需要多少内存。我们对比算法的最坏情况空间复杂度。根据函数增长速度对函数进行分类，使用大O表示法；许多具有相同增长速度的函数可以使用相同的表示法编写。

由于函数的阶也称为其增长速度，因此使用符号O。函数的增长速度通常仅在大O表示法中函数的上限约束。

在使用大O表示法分析空间复杂度之前，必须首先执行以下操作

• 特定算法的程序实现。
• 需要知道输入量n，以确定每个项目将占用多少存储空间。

一些典型算法的空间复杂度

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

让我们探索一些示例

void linearTimeComplex(int a[], int s)
{
   for (int i = 0; i < s; i++)
   {
      printf("%d
", a[i]);
   }
}

此函数在O(n)时间内执行，有时称为“线性时间”，其中n只是数组中项目的数量。如果数组包含10个元素，我们必须打印10次。如果数组包含1000个元素，我们必须打印1000次，得到的复杂度为O(n)。

void quadraTimeComplex(int a[], int s)
{
   for (int i = 0; i < s; i++)
   {
      for (int j = 0; j < s; j++)
      {
         printf("%d = %d
", a[i], a[j]);
      }
   }
}

我们在这里嵌套了两个循环。当我们的数组中有n个元素时，外部循环迭代n次，内部循环对于外部循环的每次迭代都迭代n次，结果是总共打印n2次。如果数组包含10个元素，我们必须打印100次。如果数组包含1000个元素，我们必须打印1000000次。因此，此函数需要O(n2)时间才能完成，得到的复杂度为O(n^2)。

void constTimeComplex(int a[])
{
    printf("First array element = %d",a[0]);
}

相对于其输入，此函数在O(1)时间内执行，有时称为“常数时间”。无论输入数组包含1个元素还是1000个元素，此方法只需要一个步骤。

结论

如果我们处理大数据，大O表示法在理解算法方面特别有用。该工具帮助程序员确定算法的可扩展性或根据程序使用的数据的输出所需步骤的数量。如果用户尝试运行我们的代码以提高其效率，则数据结构中的大O表示法尤其有用。