3

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

但是，我一直坚持的事情是算法证明的符号，我不确定在哪里可以找到这部分。我看过的所有书籍都假定这种知识水平。

例如，Skiena's Algorithm Design Manual中的这句话让我很难过：

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

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

这是读者应该完成的推论练习：

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

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

但是我被困在简单的事情上，比如上面的内容是什么？

  • g(n)

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

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

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

4

2 回答 2

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，而 100 根本没有增长。这就是最终n0发挥作用的地方：如果 a 对于有限数量的n ，则 Big-Oh 符号“容忍”它，c*g(n)不大于f(n)，只要它对于无限数量的n都更大。这个有限数用n0给出例如，对于所有n < 1（这是一个有限量：正好是数字 0），f(n)=n+100可以大于c*g(n) = c*n只要对于所有其他n（无限量：所有数字>=1，使n0=1）f(n)更小。

于 2013-01-21T14:58:04.390 回答
0

这里的主要问题是你不习惯数学中使用的习语。

让我们逐句进行：

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

    简单的英语：嘿，写c * g(n) 是 f(n) 的上限对我来说工作量太大，从这里开始我会经常使用它。从现在开始，每次我想说的时候，我都会写f(n) = O(g(n))。此外，f(n)和g(n)只是函数，我不在乎是哪一个，只要它们以整数n作为参数并返回一些实值即可。c只是一些常数，因此我在上面所做的肯定是正确的。请记住，我并没有说任何关于复杂性、关于f或关于g的内容，我只是在创建一个快捷方式来说明c * g(n) 是 f(n) 的上限。

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

    简单的英语：以防万一你不知道，我会回想一下函数的上限是什么。如果你能找到一个常数（我们称之为c）使得 f(n) ≤ c * g(n) 对于足够大的 n ，函数g(n)就是f(n)的上限。你肯定想知道足够大意味着什么，是吗？我们只是说 f(n) ≤ c * g(n) 对于所有大于某个数的n都必须为真。我们不知道它是哪个数字，我们也不想知道，因为对我们来说唯一重要的是那个数字存在！我们将其称为n0以便我们可以说如果n ≥ n0则n足够大.

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

    简单的英语：现在让我们尝试一个例子来展示它是如何工作的。当我写3n^2 - 100n + 6 = O(n^2)时，我们有 f(n) = 3n^2 - 100n + 6 和 g(n) = n^2。看看我在那里做了什么？我之前没有说f(n)和g(n)是什么，这一事实让我可以用任何函数代替。

    正如你所看到的，我在这里的意思是短语 c * n^2 是 3n^2 − 100n + 6 的上限。这是一个可以是真假的肯定。上限的定义将让我们知道如何判断它是否为真。证明这个肯定是真的一种方法是找到一些数字c和一些数字n0使得 3n^2 - 100n + 6 ≤ c * n^2，对于所有 n ≥ n0。如果我们尝试使用 c = 3，我们必须证明 3n^2 − 100n + 6 ≤ 3 * n^2 对于所有 n > n0，这等效于证明 -100n + 6 ≤ 0，对于某些 n > n0。最后我们可以说，要使其为真，我们需要 n0 ≥ 6/100。我们找到了我们的 n0 并且我们证明了整个肯定是真的

在我看来，您的问题是您希望事情变得具体。另一方面，数学试图抽象。这就是为什么它提到函数f和g而没有说明它们实际上是什么。您只需要知道它们是函数，并且作为函数它们具有某些属性。这个想法是你想推理函数的属性而不是一些具体的函数。同样的事情对n0也是有效的，你只关心它的存在，而不是它的价值。如果存在，您可以将其考虑到您的推理中。

希望我的回答对你有所帮助。

于 2014-02-01T17:53:55.823 回答