简化 Big-O 表达式

Question

说我有这样的表情：

O(10n) * O(4n^2)

我想简化它。如果我们在各项之间进行乘法，我们可以放弃增长较低的一项吗？

例如：

O(10n * 4n^2)
= O(n^2)

或者会是

= O(n * n^2)

我期待它是

O(n * n^2)

，但我不确定。

Answer 1

让我们扩展一下现有的内容，并在应用大 O 之前从多项式开始，这将拉出最高阶多项式作为边界函数：

let's imagine that g(x) = 10n+5     (similar to your example of 10n)
let's imagine that f(x) = 4n^2+n+1  (similar to your example of 4n^2)

big_o(g(x)) = O(n)    *not O(10n)*
big_o(f(x)) = O(n^2)  *not O(4n^2)*

对于提到的二次方程，O(n) 和 O(n^2) 是时间复杂度限制

如果将它们相乘，例如，您执行 g(x) 和 f(x) 次数，则可以执行以下操作之一并获得相同的结果：

a)  just multiply the big O terms

   **O(n) * O(n^2) = O(n^3)**

b)  you can multiply the original quadratics, apply big O and get O(n^3) 

 let h(x) = g(x) * f(x) 
     h(x) = g(x) done f(x) times, and can be thought of as: 
 h(x) = g(x) * f(x) = (10n + 5)*(4n^2 + n +1)
               = 40n^3 + 10n^2 +10n + 20n^2 +5n + 5
          h(x) = 40n^3 + 30n^2 + 15n +5

 if you take the big O of h(x), look at the bounding polynomial 
 (n^3 and remove any mupltiplier), you get: 
         big_O( h(x) ) = O(n^3)
 

您会发现，边界时间复杂度多项式为 O(n^3) 将是答案，因为它受三次函数限制且永远不会克服三次函数。