big-o - 大 O 符号

Question

我正在阅读大 O 符号。在我的书中，有一个例子，其中n ²的复杂度属于 O( n ³ ) 类。这对我来说似乎不合逻辑，因为n ³取决于n并且它不仅仅是我们可以“摆脱”的简单常数乘数。

请向我解释为什么这两个具有相同的复杂性。我在这个论坛或其他任何地方都找不到答案。

Answer 1

大 O 确定较大 n 值的上限。O( n ³ )大于O( n ² )，所以n ²程序仍然是O( n ³ )。它也是 O( n ⁴ ), O(*n ⁵ ), ..., O( n ^infinity )。

然而，反之亦然。n^3 程序不是 O( n ² )。相反，它将是 Omega( n ² )，因为 Omega 确定了一个下限（我们至少需要做多少工作）。

Big O 没有说这个上限是“严格的”，它只需要高于实际复杂度。因此，虽然 n*n 复杂度程序的界限为 O( n ³ )，但这并不是一个非常严格的界限。O( n ² ) 更紧凑，信息更丰富。