我现在在上一个算法课,我们要学习大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在o之外,所以我不确定它应该是什么意思。在第二个符号中,我加上O和Θ。
最佳答案
至少出于实际目的,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)
关于algorithm - 您可以使用Big O表示法进行加法/乘法吗?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/57830311/