对大 O 表示法感到困惑
Confused on big O notation
根据this book，大O表示：
f(n) = O(g(n)) means c · g(n) is an upper bound on f(n). Thus there exists some constant c such that f(n) is always ≤ c · g(n), for large enough n (i.e. , n ≥ n0 for some constant n0).
我对以下大 O 方程的理解有问题
3n2 − 100n + 6 = O(n2)，因为我选择 c = 3 并且 3n2 > 3n2 − 100n + 6；
3怎么可能是因数？在 3n2 − 100n + 6 中，如果我们去掉低阶项 -100n 和 6，3n2 和 3.n2 不一样吗？这个方程怎么解？
我冒昧地将问题稍微解释为：
Why do 
and 
have the same asymptotic complexity.
要做到这一点，定义应该对两个方向都有效。
第一：
)
让
那么对于
，不等式总是满足的。
反过来：
)
让
%20%5Cgeq%203n%5E2)
我们有一条向上开口的抛物线，因此又存在一些 
之后不等式总是满足的。
y=3n^2（上图）vs y=3n^2 - 100n + 6
考虑上面的草图。根据您的定义，对于足够大的 n（即对于某个常数 n0，n ≥ n0），3n^2 只需要大于 3n^2 - 100n + 6 。在这种情况下让 n0 = 5（它可能会小一些，但很明显哪个图比 n=5 大，所以我们就这样吧）。
从图中可以清楚地看出，3n^2 >= 3n^2 - 100n + 6 在我们绘制的范围内。 3n^2 - 100n + 6 大于 3n^2 的唯一方法是让它增长得更陡。
但是 3n^2 和 3n^2 - 100n + 6 的梯度分别是 6n 和 6n - 100，所以 3n^2 - 100n + 6 不能增长得更陡，因此必须总是在下面。
所以你的定义成立 - 3n^2 - 100n + 6 <= 3n^2 对于所有 n>=5
我不是专家，但这看起来与我们刚刚在真实分析课程中的内容非常相似。
基本上如果你有类似 f(n) = 3n^2 − 100n + 6 的东西，"fastest growing" 术语 "wins" 其他术语，当你有非常大的 n.
所以在这种情况下，当 n 非常大时，3n^2 超过了 100n。
另一个例子是 f(n) = n/n^2 或 f(n) = n! * n^2。
第一个变得更小，因为 n 根本不能 "keep up" 和 n^2。在第二个例子中 n!显然比 n^2 增长得更快，所以我猜答案应该是 f(n) = n!，因为 n^2 在技术上不再与大 n 相关。
像 +6 这样不受 n 影响的项是常数，甚至更不重要，因为即使 n 增长它们也不会增长。
这都是关于当 n 非常大时发生的事情。如果你的 n 是 34934854385754385463543856，那么 n^2 比 100n 大得多，因为 n^2 = n * n = 34934854385754385463543856 * 34934854385754385463543856.
让我们看看您为 f(n) in O(g(n)) 发布的定义：
f(n) = O(g(n)) means c · g(n) is an upper bound on f(n). Thus there
exists some constant c such that f(n) is always ≤ c · g(n), for
large enough n (i.e. , n ≥ n0 for some constant n0).
所以，我们只需要找到一组满足
的常数(c,n0)
f(n) < c · g(n), for all n > n0, (+)
但是这个集合不是唯一的。即，找到使 (+) 成立的常数 (c, n0) 的问题是 degenerate。事实上，如果存在任何这样的常数对，就会存在无数个不同的这样的常数对。
请注意，这里我已切换到严格不等式，这实际上只是个人喜好问题，但我更喜欢后一种约定。现在，我们可以用更容易理解的术语重新陈述 Big-O 的定义：
... we can say that f(n) is O(g(n)) if we can find a constant c such
that f(n) is less than c·g(n) or all n larger than n0, i.e., for all
n>n0.
现在，让我们看看你的函数 f(n)
f(n) = 3n^2 - 100n + 6 (*)
让我们将您的函数描述为最高项与另一个函数的总和
f(n) = 3n^2 + h(n) (**)
h(n) = 6 - 100n (***)
我们现在分别研究 h(n) 和 f(n) 的行为：
h(n) = 6 - 100n
what can we say about this expression?
=> if n > 6/100, then h(n) < 0, since 6 - 100*(6/100) = 0
=> h(n) < 0, given n > 6/100 (i)
f(n) = 3n^2 + h(n)
what can we say about this expression, given (i)?
=> if n > 6/100, the f(n) = 3n^2 + h(n) < 3n^2
=> f(n) < c*n^2, with c=3, given n > 6/100 (ii)
好的！
- 从(ii)我们可以选择常数c=3，假设我们选择另一个常数n0大于6/100。让我们选择满足此要求的第一个整数：n0=1.
因此，我们已经证明常数集 **(c,n0) = (3,1) 的 (+) golds，随后，f(n) 在 O(n ^2).
有关渐近行为的参考，请参阅
根据this book，大O表示：
f(n) = O(g(n)) means c · g(n) is an upper bound on f(n). Thus there exists some constant c such that f(n) is always ≤ c · g(n), for large enough n (i.e. , n ≥ n0 for some constant n0).
我对以下大 O 方程的理解有问题
3n2 − 100n + 6 = O(n2)，因为我选择 c = 3 并且 3n2 > 3n2 − 100n + 6；
3怎么可能是因数？在 3n2 − 100n + 6 中，如果我们去掉低阶项 -100n 和 6，3n2 和 3.n2 不一样吗？这个方程怎么解？
我冒昧地将问题稍微解释为：
Why do
要做到这一点，定义应该对两个方向都有效。
第一：
让
那么对于，不等式总是满足的。
反过来：
让
我们有一条向上开口的抛物线，因此又存在一些 之后不等式总是满足的。
y=3n^2（上图）vs y=3n^2 - 100n + 6
考虑上面的草图。根据您的定义，对于足够大的 n（即对于某个常数 n0，n ≥ n0），3n^2 只需要大于 3n^2 - 100n + 6 。在这种情况下让 n0 = 5（它可能会小一些，但很明显哪个图比 n=5 大，所以我们就这样吧）。
从图中可以清楚地看出，3n^2 >= 3n^2 - 100n + 6 在我们绘制的范围内。 3n^2 - 100n + 6 大于 3n^2 的唯一方法是让它增长得更陡。
但是 3n^2 和 3n^2 - 100n + 6 的梯度分别是 6n 和 6n - 100，所以 3n^2 - 100n + 6 不能增长得更陡，因此必须总是在下面。
所以你的定义成立 - 3n^2 - 100n + 6 <= 3n^2 对于所有 n>=5
我不是专家，但这看起来与我们刚刚在真实分析课程中的内容非常相似。
基本上如果你有类似 f(n) = 3n^2 − 100n + 6 的东西，"fastest growing" 术语 "wins" 其他术语，当你有非常大的 n.
所以在这种情况下，当 n 非常大时，3n^2 超过了 100n。
另一个例子是 f(n) = n/n^2 或 f(n) = n! * n^2。
第一个变得更小，因为 n 根本不能 "keep up" 和 n^2。在第二个例子中 n!显然比 n^2 增长得更快，所以我猜答案应该是 f(n) = n!，因为 n^2 在技术上不再与大 n 相关。
像 +6 这样不受 n 影响的项是常数，甚至更不重要，因为即使 n 增长它们也不会增长。
这都是关于当 n 非常大时发生的事情。如果你的 n 是 34934854385754385463543856，那么 n^2 比 100n 大得多，因为 n^2 = n * n = 34934854385754385463543856 * 34934854385754385463543856.
让我们看看您为 f(n) in O(g(n)) 发布的定义：
f(n) = O(g(n)) means c · g(n) is an upper bound on f(n). Thus there exists some constant c such that f(n) is always ≤ c · g(n), for large enough n (i.e. , n ≥ n0 for some constant n0).
所以，我们只需要找到一组满足
的常数(c,n0)f(n) < c · g(n), for all n > n0, (+)
但是这个集合不是唯一的。即，找到使 (+) 成立的常数 (c, n0) 的问题是 degenerate。事实上，如果存在任何这样的常数对，就会存在无数个不同的这样的常数对。
请注意，这里我已切换到严格不等式，这实际上只是个人喜好问题，但我更喜欢后一种约定。现在，我们可以用更容易理解的术语重新陈述 Big-O 的定义：
... we can say that f(n) is O(g(n)) if we can find a constant c such that f(n) is less than c·g(n) or all n larger than n0, i.e., for all n>n0.
现在，让我们看看你的函数 f(n)
f(n) = 3n^2 - 100n + 6 (*)
让我们将您的函数描述为最高项与另一个函数的总和
f(n) = 3n^2 + h(n) (**)
h(n) = 6 - 100n (***)
我们现在分别研究 h(n) 和 f(n) 的行为：
h(n) = 6 - 100n
what can we say about this expression?
=> if n > 6/100, then h(n) < 0, since 6 - 100*(6/100) = 0
=> h(n) < 0, given n > 6/100 (i)
f(n) = 3n^2 + h(n)
what can we say about this expression, given (i)?
=> if n > 6/100, the f(n) = 3n^2 + h(n) < 3n^2
=> f(n) < c*n^2, with c=3, given n > 6/100 (ii)
好的！
- 从(ii)我们可以选择常数c=3，假设我们选择另一个常数n0大于6/100。让我们选择满足此要求的第一个整数：n0=1.
因此，我们已经证明常数集 **(c,n0) = (3,1) 的 (+) golds，随后，f(n) 在 O(n ^2).
有关渐近行为的参考，请参阅