algorithm - 用大哦证明小哦

Question

如果我已经知道f(n)是O(g(n))。从little-oh的定义，如何证明f(n)是o(n * g(n))？

Answer 1

给出:f(n) is in O(g(n)) .

使用大 O 符号的定义，我们可以将其写为:

f(n) is in O(g(n))

=> |f(n)| ≤ k*|g(n)|, for some constant k>0                 (+)
                      for n sufficiently large (say, n>N)

如上使用的 big-O 的定义，请参见例如

• https://www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-o-notation

证明:给定(+) , 然后 f(n) is in o(n*g(n)) .

---

让我们首先说明 little-o 表示法的含义:

Formally, f(n) = o(g(n)) (or f(n) ∈ o(g(n))) as n → ∞ means that for every positive constant ε there exists a constant N such that

|f(n)| ≤ ε*|g(n)|, for all n > N                          (++)

来自 https://en.wikipedia.org/wiki/Big_O_notation#Little-o_notation .

现在，使用 (+) , 我们可以写

|f(n)| ≤ k*|g(n)|, som k>0, n sufficiently large 

    <=> { n > 0 } <=> n*|f(n)| ≤ k*n*|g(n)|
                  <=> n*|f(n)| ≤ k*|n*g(n)|
                  <=>   |f(n)| ≤ (k/n)*|n*g(n)|            (+++)

返回little-o的定义，具体(++) ，并让，不失一般性，k固定。现在，每个正常数 ε可以描述为

ε = k/C, for some constant C>0 (with k fixed, k>0)         (*)

现在，不失一般性地假设n比这个大C ，即 n>C .然后，(*)和 (+++)产量

|f(n)| ≤ (k/n)*|n*g(n)| < (k/C)*|n*g(n)| = ε*|n*g(n)|      (**)
                        ^                ^
                        |                |
                    since `n>C`         (*)

由于我们正在研究渐近行为，我们可以选择为 n 分配一个下限任何大于 C 的值(事实上​​，这是 big-O 和 little-o 的定义，“n 足够大”)，因此——根据上面 little-oh 的定义——我们有:

- As shown above, (+) implies (**) 
- By the definition of little-o, (**) shows that f(n) is in o(n*g(n))
- Subsequently, we've shown that, given (+), then: f(n) is in o(n*g(n))

---

结果:如果f(n) is in O(g(n)) , 然后 f(n) is in o(n*g(n)) ，其中这两个关系分别指大 O 和小 O 渐近界。

---

评论:事实上，结果非常微不足道。 big-O 和 little-O 符号仅在用于证明上限的两个常量之一上有所不同，即，我们可以将 big-O 和 little-O 的定义写为:

• f(n)据说在O(g(n))如果我们能找到一组正常数 (k, N) , 这样 f(n) < k*g(n)对所有 n>N 成立.

• f(n)据说在o(g(n))如果我们能找到一个正常数 N , 这样 f(n) < ε*g(n)对所有 n>N 成立，对于每个正常数 ε .

后者显然是一个更严格的约束，但如果我们可以利用 n 的一个额外幂在 f(n) < ε*g(n) 的左侧(即 f(n) < ε*n*g(n) )，那么即使是 ε 的无穷小值, 我们总是可以选择另一个常量 N自由地足够大 ε*n为我们提供任何常数k可以用来表明 f(n)在O(g(n)) (记得，n>N)。