时间戳

首页 > 解决方案 > 了解大 O 复杂性

algorithm - 了解大 O 复杂性

问题描述

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

Big 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)ck

标签： algorithmsortingtime-complexitybig-ocomplexity-theory

解决方案

解释

将算法形式化以使您可以正式应用 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和步数，这没关系，因为它在恒定时间内运行。BC

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

这导致我们称之为精确时间的观察结果（因为我们在和n / 2之间有很多偶数。0n

使用上述常量的确切公式将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.

推荐阅读