algorithm - 算法分析 (N^2)

Question

我需要运行一个最坏情况下运行时Θ（n^2）的算法。之后，我需要运行一个算法 5 次，每次运行时运行时间为 Θ(n^2)。

这些算法的组合最坏情况运行时间是多少？

在我的脑海中，公式看起来像这样：

( N^2 + (N^2 * 5) )

但是当我必须用 theta 表示法分析它时，我的猜测是它在 Θ(n^2) 时间内运行。

我对吗？

Answer 1

两次O(N^2)还是O(N^2)，十次O(N^2)还是O(N^2)，五次O(N^2)还是O(N^2) ，只要 'any' 是一个常数，任何时候 O(N^2) 仍然是 O(N^2)。

相同的答案适用于 \Theta 而不是 O。

Answer 2

O(n^2)无论如何，因为您拥有的基本上是，O(6n^2)这仍然是O(n^2)因为您可以忽略常量。您正在查看的是属于一组功能而不是功能本身的东西。

本质上，6n^2 ∈ O(n^2).

编辑

你也问过Θ。Θ 给你下限和上限，而 O 只给你上限。您只能得到 Ω 的下限。Θ 是这两者的交集。

任何存在的东西Θ(f(n))也是O(f(n))，但反之则不然。