algorithm - 渐近概念 : What is n₀ in formula, 我们如何找到常数

Question

我正在研究 Asymptotic Notations Topic，我发现它的公式很简单，但它什么也没说，有几件事我不明白。
当我们说

f(n) <= c.g(n) where n >= n₀

而且我们不知道c=的值？和 n=?首先，通过对 f(n) 或 g(n) 进行除法，我们得到 c 的值。 (这里是困惑所在)
第一个问题:我们如何决定在方程 f(n) 或 g(n) 中必须除以哪一侧的“n”？< br/>
假设我们要证明:

2n(square) = O(n(cube))

这里 f(n) = 2(n(square)) 和 g(n)=n(cube)
将形成为:

2(n(square)) = c . n(cube)

现在在我读过的笔记中，他们将 2(n(square)) 除以得到 c 的值，这样我们得到 c = 1;
但是如果我们把它除以 n(cube) [我不知道我们是否能做到] 我们得到 c = 2;
我们怎么知道我们必须划分什么值？

第二个问题: n₀ 的任务从哪里来？
好吧，根据公式我们知道 n >= n(0) 这意味着无论我们取 n 什么，我们都应该取 n(0) 的值或者应该比 n 更大。
但我很困惑我们在哪里使用 n₀ ？为什么需要它？
仅通过找到 C 和 N 我们不能得出结论，如果 n(square) = O(n(cube)) 或否。 有人愿意解决这个问题吗？非常感谢。
如果我问任何愚蠢的问题或给 -1，请不要冷落我。请解决它，任何涵盖所有这些内容的有用链接也足够了:3
在发布这个问题之前，我已经浏览了以下链接，这是我的理解，这是这些链接: http://openclassroom.stanford.edu/MainFolder/VideoPage.php?course=IntroToAlgorithms&video=CS161L2P8&speed=
http://faculty.cse.tamu.edu/djimenez/ut/utsa/cs3343/lecture3.html
https://sites.google.com/sites/algorithmss15

Answer 1

来自您问题中的第二个网址:

Let's define big-Oh more formally:

O(g(n)) = { the set of all f such that there exist positive constants c and n0 satisfying 0 <= f(n) <= cg(n) for all n >= n0 }.

这意味着，对于 f(n) = 4*n*n + 135*n*log(n) + 1e8*n大 O 是 O(n*n)。 因为足够大 c和 n0这是真的:
4*n*n + 135*n*log(n) + 1e8*n = f(n) <= O(n*n) = c*n*n

在这种特殊情况下，[c,n0] 可以是例如 [6, 1e8]，因为(这当然不是有效的数学证明，但我希望它是“显而易见的”):
f(1e8) = 4*1e16 + 135*8*1e8 + 1e16 = 5*1e16 + 1080*1e8 <= 6*1e16 = 6*1e8*1e8 =~= O(n*n) .当然还有更多可能的 [c,n0] f(n) <= c*n*n成立，但你只需要找到一对来证明 f(n)有O(f(n))的 O(n*n) .

如您所见，对于 n=1，您需要相当大的 c (如 1e9)，所以乍一看 f(n) 可能看起来比 n*n 大得多，但在渐近概念中你不关心前几个初始值，只要自某个边界以来的行为是想要的。该边界是一些 [c,n0]。如果你能找到这样的边界 ([6, 1e8])，那么 QED:“f(n) 有 n*n 的大 O”。

---

n >= n₀ 意味着对于某些第一个 k(可数)参数 n'，无论您在引理中说什么都可能是假的: n' <n₀，但是因为某些n₀引理对所有 其余的(更大的)整数。

它表示您不关心前几个整数(“前几个” 可以像 1e400 或 1e400000 一样“小”，...等...从理论的角度来看)，你只关心更大的(足够大，大于n₀)n值。

---

最终这意味着，在大 O 表示法中，您通常会编写与所检查的 f(n) 具有相同渐近概念的最简单和最低的函数。

例如，对于多项式类型的任何 f(n)，如 f(n) = ∑a_inⁱ，i=0..k O(f (n)) = O(n^k).
所以我确实放弃了 n 的所有较低的 0..(k-1) 次幂，因为从长远来看它们没有机会对抗 n^k(对于大的 n ). a_k 确实输给了一些更大的 c。

如果你迷失在 i,k,...:
f(n) = 34n⁴ + 23920392n² 有 O(n⁴).

至于足够大的 n，n⁴ 将“掩盖”从 n²。而 34n⁴ 只比 n⁴ 大 34 倍 => 34 是常量(与 有关c) 并且也可以从大 O 符号中省略。