是 O(5n) = 5*O(n) 吗？据我了解，O(5n) == O(n)。因此他们不相等？如果我错了，请纠正我。
问问题
1533 次
6 回答
7
您只关心函数的渐近行为，如果f(x)/g(x)收敛到一个常数，则两个函数被定义为属于同一个 big-O 类。所以5*n / n总是5。所以O(n) = O(5*n)。
至于您的问题：O(f(x))被定义为具有与 f(x) 相同的渐近行为的函数集，因此5*O(N)未定义。哪有这回事。
于 2013-02-27T16:20:42.197 回答
2
你说得对，O(5n)确实等于O(n)。5*O(n) 没有意义，O不返回结果，它是一个符号。所以你不能把它和一个数字相乘。
尽管有一些定义在公式中使用了大 O，例如error terms。但它必须事先像这样定义。
这里的维基百科链接描述O(c*n) = O(n).
于 2013-02-27T16:22:14.313 回答
1
O(5n) = 5*O(n)
如前所述，这没有定义。
我建议您至少（重新）阅读有关该主题的维基百科文章。
“f(x) = O(g(x)) as x -> 无限”意味着（非正式直观定义）：“f 以 g 为界，渐近到一个常数因子”。有关正式定义，请参阅上面的文章。
O(5n) == O(n)。
我认为这是更正确的（“作为 x -> 无限”暗示）： f(x) = O(x) <=> f(x) = O(5x)
干杯!
于 2013-02-27T16:46:48.977 回答
0
变量增长率的重要性。加、减、乘或除以任何常数不会改变它们。
因此，任何常数都是微不足道的，可以在不损失准确性的情况下省略。
关于你的问题——O(5n) = O(n) = 5*O(n)
于 2013-02-27T16:20:50.717 回答
0
是什么5 * { Droider }？
operator *如果没有对集合的特殊定义（或者至少对于大 O 符号），这两个问题（你的和我的）都没有任何意义。
当然你可以定义g(n)*O(f(n)) = O(f(n) * g(n))，然后它就很有意义了，但是你必须先定义它。
AFAIK，此操作没有标准定义。
有了上面的定义，我们得到5*O(n) = O(5*n) = O(n)，你的假设是正确的。
于 2013-02-27T16:26:55.673 回答
0
数学上 O(5N) != O(N) 但是当涉及到算法时，你关心的是效率，或者换句话说，算法的复杂性，所以你更关心变量 N 所以 O(5N) == O(N)就像同样有效（或复杂）一样。
于 2013-02-27T16:29:28.693 回答