了解大 O 复杂性

Understanding Big O complexity

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

Big O 的正式定义：

f(n) = O(g(n)) means there are positive constants c and k, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ k. The values of c and k must be fixed for the function f and must not depend on n.

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

我想了解什么是插入排序f(n)、g(n)、c和k。

在插入排序的情况下，f(n) 是您的处理器为执行排序而执行的实际操作数。 g(n)=n2。 c 和 k 的最小值将由实现定义，但它们并不那么重要。这个 Big-O 表示法给出的主要思想是，如果将数组的大小加倍，则插入排序工作所需的时间将增长大约 4 倍（22） . （对于插入排序，它可以更小，但Big-O只给出上限）

说明

将算法形式化到可以正式应用 Big-O 并不容易，它是一个数学概念，不容易转化为算法。通常，您会根据输入的大小测量执行操作所需的 "computation steps" 的数量。

  • 所以 f 是衡量算法执行多少计算步骤的函数。
  • n 是输入的大小，例如 5 对于像 [4, 2, 9, 8, 2].
    • 这样的列表
  • g 是您衡量的函数，因此 g = n^2 如果您检查 O(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 呢？我们可以假设这是一个 "single operation" 吗？在哪一层，一个 CPU 周期？一条流水线？ println(i)，它需要多少计算步骤，1 或 5 或可能 200？

这不实用。我们不知道确切的数量，我们必须抽象并说它是一个常量 A、B 和 C 步数，这没关系，因为它运行在恒定时间内。

简化分析后，我们可以说我们实际上只对调用 println(i) 的频率感兴趣。

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

for f 使用上述常量会产生类似

的结果 
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.

中消失了