algorithm - Big O 表示法的预期语法

Question

考虑到您要将它们“提炼”成最重要的部分，是否存在数量有限的基本 O 表示法？

O(n^2):

O(n):

O(1):

O(log n) 对数

O(n!) 阶乘

O(na) 多项式

或者您是否希望计算出诸如 O(n^4) 等的变体……如果是这样，那是唯一的异常(exception)吗？ X one的力量？

Answer 1

通常，您将 Bi​​g-O 符号(以及相关的 Bachman-Landau 符号，如 Big-Theta 和 Big-Omega)提炼为增长最快的 N 项的运算。因此，您删除/简化了较小的项 (N² + N == O(N²)) 和项的非变量系数 (< em>O(4N²) == O(N²))，但不是幂或指数底数 (O(3^4N) == O(3^N)。您也不要去除可变系数； NlogN 是 NlogN，不是 logN 或 N。

因此，如果复杂度是多项式(N 次方)或指数(基数的 N 次方)，您通常只会看到大 O 表示法中的数字。最常见的 Big-Oh 符号与您展示的一样多，加上 NlogN(非常常见)。

但是，如果您要区分一般复杂度相同的两种算法，您可以添加较少的项和/或系数以证明相对差异；与其他 O(N) 算法相比，线性执行但指令是另一个算法的两倍的算法可能被描述为 O(2N)。然而，单独来看，这两种算法都是线性的 (O(N))。

一些 Big-O 符号不是代数的，并且可能涉及多个变量的最简单的一般情况形式。例如，计数排序的复杂度为 O(Max(N,M))，其中 N 是列表中元素的数量，M 是这些元素的范围。在特定情况下，通常可以通过根据 N 定义 M 来减少这种情况，从而减少到单个变量(如果所讨论的列表是前 N 个方 block ，则 M = N²-1 )，但在一般情况下，两个变量都是独立且显着的。 BucketSort 的复杂度正式为 O(N)，但实际上它更像 O(NlogM)，其中 M 是 N 个元素列表的最大值。 M 通常被认为是微不足道的，但这取决于您通常排序的值(对十亿中的每个值排序 5 个值将需要更多循环来比较 10 的每个幂，而不是遍历列表以将它们放入桶中)和使用的基数(RadixSort 是 base-2 BucketSort；同样，对具有更大 log₂ 值的值进行排序将需要比遍历更多的循环)。