algorithm - 了解大 O 复杂性

Question

我很难理解大 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这里是插入排序的情况。

Answer 1

解释

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

• 所以 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 ？我们可以假设这是一个“单一操作”吗？在哪个级别，一个 CPU 周期？一条流水线？那println(i)呢？ ，它需要多少计算步骤，1 或 5 或可能 200？

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

---

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

这导致了我们称之为 n / 2 的观察结果次(因为我们在 0 和 n 之间有很多偶数。

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 中消失了。 .