big-o - 用简单的英语解释算法证明

Question

我是一名从未正式学习过算法的程序员，并且一直想填补我学习中的空白。我目前正在阅读一些书籍和在线资料，我从概念上理解 Big O，即它的用途，以及不同类别的性能，例如常量、线性、二次等。我可以编写问题代码并直观地理解不同方法的性能影响。

但是，我一直被困在算法证明的符号上，我不确定去哪里寻找这部分的答案。我看过的所有书籍都假定了这种知识水平。

例如，Skiena 的算法设计手册中的这句话让我很困惑:

f(n) = O(g(n)) 表示 c * g(n) 是 f(n) 的上限。

因此存在一些常数 c 使得 f(n) 总是 ≤ c * g(n)，对于足够大的 n(即对于某个常数 n ≥ n0 n0).

这是读者应该完成的推论:

3n^2 − 100n + 6 = O(n^2)，因为我选择 c = 3 和 3n^2 > 3n^2− 100n + 6；

我能理解这两种说法，并且可以从逻辑上看出第二种说法成立。我也理解上限的概念，即这是针对最坏情况的。

但我坚持简单的事情，例如，上面的以下内容指的是什么？

• g(n)

• 对于某个常数 n0，n ≥ n0

总的来说，我无法将各个部分放在一起来理解整个证明。

谁能帮我用简单的英语解析上述陈述，并以一种对非技术人员来说有意义的方式展示它们与练习的关系

Answer 1

我希望你仍然对答案有用:)。

g(n) 是您要与 f(n) 进行比较的函数，它是真正的运行时。例如，您会说冒泡排序是 O(n^2)，使得 g(n)=n^2。然而，直觉上，您的算法不会恰好采用 n^2 个时间单位(无论您可能想在此处插入什么时间单位)；但是，它可能需要 3n^2 − 100n + 6(即 f(n))个时间单位。

现在，Big-Oh 符号所做的是比较两个函数的增长速度；请注意，这是一个非常粗略的比较。例如，它不会区分需要 f(n)=n^2 时间单位的算法和需要 f(n)=5n^2 的算法，它也不会区分 f(n)=n^2 和 f(n)=n^2+n。这就是 c 发挥作用的地方——如果您能找到任何可以与 g(n) 相乘的常数 c，那么对于每个 n，结果函数返回一个大于 f(n) 的值，然后 f(n) = O(g(n))。

Big-Oh 符号的作用还在于查看 f(n) 中增长最快的部分。假设您想将 f(n) = n+100 与 g(n) = n 进行比较。直觉上，f(n) = O(g(n))，但是没有 c 可以与 g(n) 相乘，因此它总是大于f(n)；但是，n 的增长速度明显快于根本没有增长的 100。这就是 n0 最后发挥作用的地方:Big-Oh 表示法“容忍”它，如果 finite 个 n' s, c*g(n) 不大于 f(n)，只要它大于 无限 个< strong>n 的。此有限数由 n0 给出 例如，对于所有 n < 1(这是一个有限数:正好是数字 0)，f(n)= n+100 可以大于 c*g(n) = c*n，只要对于所有其他 n(无穷大:所有数>=1，使n0=1) f(n)变小。