f(n)=O(g(n))这么说和有区别f(n) ∈ O(g(n))吗？
问问题
177 次
3 回答
4
“=”并不意味着在其正常的数学意义上表示“等于”，而是更通俗的“是”，因此第二个表达式在技术上是准确的！
于 2013-02-23T15:44:50.527 回答
1
= 和 ∈ 的符号表示相同的意思，但前者是大多数作者实际使用的符号。
我看了半打手边的书。这些书使用=：
- de Berg 等人，计算几何
- Dasgupta 等人，算法
- Knuth，计算机编程的艺术
- Papadimitriou & Stieglitz，组合优化
在这些书中，我发现没有使用任何一种表示法：我发现的所有 O/o/Θ/Ω 都出现在“算法 A 是 O( n )”这样的上下文中：
- Aho 等人，计算机算法的设计与分析
- Ericson，实时碰撞检测
我没有发现任何 ∈。
于 2013-02-23T19:02:59.117 回答
-1
- 关系“f(n) ∈ O(g(n))”读作“f(x) is little-o of
g(x)”。这意味着 g(x) 比 f(x) 增长得快得多，或者类似地，
f(x) 的增长与 g(x) 的增长相比微不足道。 - 它假设 f 和 g 都是一个变量的函数。形式上， f(n) = o(g(n)) as n → ∞ 意味着对于每个正常数 ε，存在一个常数 N，使得 f(n)<=ɛ(g(n)。
希望你得到你的答案...
于 2013-02-23T16:05:08.583 回答