如何理解给定示例中的Big O表示法

Question

Here它说T（n）是O（n ^ 4）。但我想知道为什么它不是O（n ^ 3）？它包含n ^ 3，如果我们省略20n和1，它应该是O（n ^ 3）而不是O（n ^ 4）。为什么会这样？

Answer 1

它在O（n ^ 3）中，但O（n ^ 4），O（n ^ 5）等是O（n ^ 3）的超集，所以如果有东西在O（n ^ 3）那么它可以也在O（n ^ 100）。最好的答案和常规使用的答案是属于的最小的大O，即O（n ^ 3），但它不是唯一的。

Answer 2

我认为你在theta符号和大O符号之间感到困惑。

Theta表示法确定算法运行时间的粗略估计，而Big O表示法确定算法的最坏情况运行时间。

上面提到的方法用于计算theta，而不是大O.上述问题的大O可以是O（n ^ 4），O（n ^ 5），O（n ^ 6）等等......都是正确的价值观。但对于theta，只有theta（n ^ 3）是正确的。