gpt4 book ai didi

algorithm - 在这种情况下,我对 big o 的解释是否正确?

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:59:11 25 4
gpt4 key购买 nike

我正试图向我的 friend 解释为什么 7n - 2 = O(N)。我想根据大 O 的定义这样做。

根据大O的定义,f(n) = O(g(n))如果:

我们可以找到一个实数值 C 和整数值 n0 >= 1 使得:

  • f(n)<= C 。 g(n) 对于 n >= n0 的所有值。

在这种情况下,下列解释是否正确?

  • 7n - 2 <= C 。 n

  • -2 <= C 。 n - 7n

  • -2 <= n (C - 7)

  • -2/(C - 7) <= n

如果我们考虑 C = 7,在数学上,-2/(C - 7 ) 等于负无穷大,所以

  • n >=(负无穷大)

这意味着对于 n >=(负无穷大) 的所有值,以下成立:

  • 7n - 2 <= 7n

现在我们必须选择 n0,这样对于所有 n >= n0n0 >= 1 满足以下条件:

  • 7n - 2 <= 7n

因为对于 n >=(负无穷大) 的所有值,不等式都成立,我们可以简单地取 n0 = 1

最佳答案

您走在正确的轨道上。但是,从根本上说,您使用的逻辑不起作用。如果你想证明存在一个 n0 和 c 使得 f(n) ≤ cg(n) 对于所有 n ≥ n0,那么你可以'不要从假设 f(n) ≤ cg(n) 开始,因为这最终是您要证明的!

相反,看看您是否可以从初始表达式 (7n - 2) 开始,然后将其推到以 cn 为上限的内容中。这是一种方法:因为 7n - 2 ≤ 7n,我们可以(通过检查)只选择 n0 = 0 和 c = 7 以查看对于所有 n ≥ n 的 7n - 2 ≤ cn 0

对于更有趣的情况,让我们用 7n + 2 来尝试:

7n + 2

≤ 7n + 2n (for all n ≥ 1)

= 9n

所以通过检查我们可以选择 c = 9 和 n0 = 1 并且我们有 7n + 2 ≤ cn 对于所有 n ≥ n0,所以 7n + 2 = O(n)。

请注意,在这个数学中,我们在任何时候都没有假设最终的不平等,这意味着我们永远不必冒被零除错误的风险。

关于algorithm - 在这种情况下,我对 big o 的解释是否正确?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39777924/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com