了解大O的复杂性

Question

我在理解Big O的时间复杂性方面遇到了困难。

大O的正式定义。

f(n) = O(g(n)) 是指有正的常数 c 和 k，这样 0 ≤ f(n) ≤ cg(n) 对于所有 n ≥ k. 的值。c 和 k 功能必须固定 f 而不能依靠 n.

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

我想了解什么是 f(n), g(n), c 和 k 在这里插入排序的情况下。

Answer 1

解释

要把算法形式化，使你能正式应用大奥，并不是那么容易，它是一个数学概念，不容易转化为算法。通常情况下，你会测量 "计算步骤" 根据输入的大小来执行操作所需。

• 所以 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.

Answer 2

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