理解大 O 复杂度

Question

我很难理解大 O 时间复杂度。

大 O 的正式定义：

f(n) = O(g(n)) 表示存在正常数 c 和 k，使得对于所有的 n ≥ k，都有 0 ≤ f(n) ≤ cg(n)。其中 c 和 k 的值必须固定为函数 f，并且不能依赖于 n。

而插入排序的最坏时间复杂度是 O(n^2)。

我想了解在插入排序中，f(n)、g(n)、c 和 k 分别代表什么意义。

- Ankur Jain

Answer 1

说明

要将算法形式化以便可以正式应用大O，这并不容易，因为它是一个数学概念，不容易转化成算法。通常，您会根据输入的大小来测量执行操作所需的“计算步骤”数量。

• f 是衡量算法执行多少计算步骤的函数。
• n 是输入的大小，例如对于像[4, 2, 9, 8, 2]这样的列表，n为5。
• g 是您要针对进行测量的函数，因此，如果您检查O(n^2)，则g = n^2。
• c 和 k 在很大程度上取决于具体的算法和f的实际样子。

---

示例

正式定义一个算法最大的问题在于您无法准确地告诉程序执行了多少计算步骤。我们假设有以下Java代码：

public static void printAllEven(int n) {
    for (int i = 0; i < n; i++) {
        if (i % 2 == 0) {
            System.out.println(i);
        }
    }
}

它执行了多少步？我们要深入到哪个程度？那么，for (int i = 0; i < count; i++)呢？这是在循环期间执行的多个语句。那么，i % 2呢？我们可以假设这是一个“单个操作”吗？在哪个层次上，一个CPU周期？一条汇编线？println(i)呢？它需要多少计算步骤，1、5或者200？

这是不实际的。我们不知道确切的数量，我们必须抽象并说它是常量A、B和C的步骤数量，这是可以的，因为它以恒定时间运行。

简化分析后，我们可以说我们只关心println(i)被调用的频率。

这导致观察到我们精确地调用它n / 2次（因为在0和n之间有这么多偶数）。

使用上述常量的精确公式将产生类似于以下内容的东西：

n * A + n * B + n/2 * C

但是由于常量在c中并没有真正发挥任何作用（它们会消失），因此我们也可以忽略它并简化问题。

---

现在您需要证明例如n/2在O(n^2)中，通过这样做，您也将得到c和k的具体数字。例如：

n / 2 <= n <= 1 * n^2 // for all n >= 0

选择c = 1和k = 0就证明了这个命题。其他的c和k的值也可以，例如：

n / 2 <= 100 * n <= 5 * n^2 // for all n >= 20

在这里，我们选择了c = 5和k = 20。

---

您也可以使用完整公式玩同样的游戏，得到类似的结果。

n * A + n * B + n/2 * C
    <= n * (A + B + C)
    = D * n
    <= D * n^2 // for all n > 0

当 c = D 且 k = 0 时，如你所见，这些常量并不发挥任何作用，因为这些常量会在 c 中消失。

- Zabuzard

Answer 2

在插入排序的情况下，f(n)是处理排序所需的实际操作次数。g(n)=n²。c和k的最小值将由具体实现定义，但它们并不重要。这个大O符号的主要思想是，如果你将数组的大小加倍，插入排序所需的时间将增长约4倍（2²）。 （对于插入排序，它可能会更小，但大O符号只给出上限）

- Roman Svistunov