渐近分析 "o" 到 "O" 的转换
Asymptotic analysis "o" to "O" conversion
我对"O"和"o"符号的理解是前者是上界，后者是紧界。我的问题是，如果一个函数，f(n) 被某个随机函数紧紧束缚，比如 o(g(n))。是否可以通过乘以某个常数 "c" 使这个界限成为上限，即 (O(g(n))
f ∈ O(g) 表示，本质上是
For at least one choice of a constant k > 0, you can find a constant a
such that the inequality 0 <= f(x) <= k g(x) holds for all x > a.
请注意，O(g) 是满足此条件的所有函数的集合。
f ∈ o(g) 表示，本质上是
For every choice of a constant k > 0, you can find a constant a such
that the inequality 0 <= f(x) < k g(x) holds for all x > a.
再次注意 o(g) 是一个集合。
来自维基百科：
Note the difference between the earlier formal definition for the
big-O notation, and the present definition of little-o: while the
former has to be true for at least one constant M the latter must hold
for every positive constant ε, however small. In this way, little-o
notation makes a stronger statement than the corresponding big-O
notation: every function that is little-o of g is also big-O of g, but
not every function that is big-O of g is also little-o of g (for
instance g itself is not, unless it is identically zero near ∞).
这个link包含很好的解释：
http://www.stat.cmu.edu/~cshalizi/uADA/13/lectures/app-b.pdf
我对"O"和"o"符号的理解是前者是上界，后者是紧界。我的问题是，如果一个函数，f(n) 被某个随机函数紧紧束缚，比如 o(g(n))。是否可以通过乘以某个常数 "c" 使这个界限成为上限，即 (O(g(n))
f ∈ O(g) 表示，本质上是
For at least one choice of a constant k > 0, you can find a constant a such that the inequality 0 <= f(x) <= k g(x) holds for all x > a.
请注意，O(g) 是满足此条件的所有函数的集合。
f ∈ o(g) 表示，本质上是
For every choice of a constant k > 0, you can find a constant a such that the inequality 0 <= f(x) < k g(x) holds for all x > a.
再次注意 o(g) 是一个集合。
来自维基百科：
Note the difference between the earlier formal definition for the big-O notation, and the present definition of little-o: while the former has to be true for at least one constant M the latter must hold for every positive constant ε, however small. In this way, little-o notation makes a stronger statement than the corresponding big-O notation: every function that is little-o of g is also big-O of g, but not every function that is big-O of g is also little-o of g (for instance g itself is not, unless it is identically zero near ∞).
这个link包含很好的解释：
http://www.stat.cmu.edu/~cshalizi/uADA/13/lectures/app-b.pdf