您可以使用Big O符号进行加法/乘法吗？

我目前正在参加一个算法课，我们正在讨论大O符号等。上一次，我们谈到了如何您可以使用Big O符号进行加法/乘法吗？

O (n^2 + 3n + 5) = O(n^2)

，我想知道，如果同样的规则适用于本：

O(n^2) + O(3n) + O(5) = O(n^2)

另外，不要下面的符号持有？

O(n^2) + n

或

O(n^2) + Θ (3n+5)

后来n为0之外，所以我不知道它应该意味着。在第二种表示法中，我将O和Θ相加。

来源

2015-05-11 ThunderBalls

我不喜欢使用这种标记没有定义它，因为目前还不清楚是什么应该是这个意思。可能O（x）+ O（y）表示O（x + y），同样O（x）+ y;当你混合像O（n^2）+Θ（3n + 5）这样的渐近类时，它会变得模糊不清。如果您参与了这类练习，请提出澄清。 –

至少在实践中，the Landau O(...) can be viewed as a function（因此其符号的吸引力）。This function has properties for standard operations，例如：

O(f(x)) + O(g(x)) = O(f(x) + g(x)) 
O(f(x)) * O(g(x)) = O(f(x) * g(x)) 
O(k*f(x)) = O(f(x))

井定义的函数f(x)和g(x)，并且一些常数k。

因此，对于你的例子，

是：O(n^2) + O(3n) + O(5) = O(n^2)
和：
O(n^2) + n = O(n^2) + O(n) = O(n^2)，
O(n^2) + Θ(3n+5) = O(n^2) + O(3n+5) = O(n^2)

来源

2015-05-11 14:37:24 DilithiumMatrix

感谢您的回答！但我不完全明白为什么Θ（3n + 5）可以简单地变成O（3n + 5）？如果我是正确的，Θ（3n + 5）应该意味着'增长完全像3n + 5'，所以我可以说它也'增长不超过3n + 5'，从而使得Θ（3n + 5）= O（3n + 5）？ – ThunderBalls

是的，这是完全正确的。 'O（3n + 5）'是一个稍微更一般的，不太具体的语句---你不能**做出反向声明，即'O（3n + 5）=Θ（3n + 5）'，因为在技术上'n^0.5 = O（n^2）'（因为'n^2'仍然是一个上限），但'n^0.5≠Θ（n^2）' – DilithiumMatrix

啊我想我现在明白了。非常感谢你的帮助：） – ThunderBalls

记号：

O(n^2) + O(3n) + O(5) = O(n^2)

以及，例如：

f(n,m) = n^2 + m^3 + O(n+m)

滥用平等符号，因为它违背平等的公理。为了更加正式地正确，你需要将O（g（x））定义为一个集值函数，其值是所有函数的增长速度都不会快于g（x），并且使用集合成员符号来表示特定的功能是该组的成员。

Landau符号（大O）没有定义加法和乘法。

来源

2015-05-11 13:34:58

这些例子如何违反（哪个？）公平的公理？ – DilithiumMatrix

对称公理：“如果a = b，则b = a”。大多数Landau符号的用法是这样的形式：f（x）= O（g（x）），这意味着“存在常数N和C，使得| f（x）| <= C * | g（x）|所有x> N“，并且不表示平等。（与f（x）为O（g（x）））或类似的用法相反） –

而且下面的符号持有

O(n^2) + n = O(n^2)

和

O(n^2) + Θ(3n+5) = O(n^2), Θ(n)

希望这是有道理的......

来源

2015-05-11 13:35:11 Farooque

在复杂性理论，朗道符号用于套的功能。因此O(*)不代表一个单一的功能，而是一整套。的操作者+没有为集定义，然而，在分析功能当下列常用：

O(*) + g(n)

这通常表示一组其中g(n)被添加到每个函数中O(*)功能。结果集可以用大O符号再次表示。

O(*) + O(**)

这与此类似。然而，它表现得像一种笛卡尔产品。来自O(**)的每个功能都被添加到O(*)的每个功能中。

O(*) + Θ(*)

这里适用同样的规则。但是，由于O(*)的松动，结果通常不能表示为Θ(**)。表示为O(**)仍然有可能。

来源

2015-05-11 13:41:17

您可以使用Big O符号进行加法/乘法吗？

回答

相关问题