如何理解给定示例中的大 O 符号
How to understand Big O notation in a given example
Here 它表示 T(n) 是 O(n^4)。但是我想知道为什么不是O(n^3)？它包含 n^3，如果我们省略 20n 和 1，它应该是 O(n^3) 而不是 O(n^4)。为什么会这样？
我认为您对 theta 表示法和大 O 表示法感到困惑。
Theta 表示法确定算法 运行 时间的粗略估计，而 Big O 表示法确定算法的最坏情况 运行 时间。
你上面说的方法是计算theta的，不是big O，上面问题的big O可能是O(n^4), O(n^5), O(n^ 6)等等……都是正确的值。但是对于theta，只有theta(n^3)是正确的。
它在 O(n^3) 中，但是 O(n^4)、O(n^5) 等是 O(n^3) 的超集，所以如果某物在 O(n^) 3) 那么它也可以在 O(n^100) 中。最好的答案和约定俗成的是它所属的最小的大O，也就是O(n^3)，但不是唯一的。
Here 它表示 T(n) 是 O(n^4)。但是我想知道为什么不是O(n^3)？它包含 n^3，如果我们省略 20n 和 1，它应该是 O(n^3) 而不是 O(n^4)。为什么会这样？
我认为您对 theta 表示法和大 O 表示法感到困惑。
Theta 表示法确定算法 运行 时间的粗略估计，而 Big O 表示法确定算法的最坏情况 运行 时间。
你上面说的方法是计算theta的，不是big O，上面问题的big O可能是O(n^4), O(n^5), O(n^ 6)等等……都是正确的值。但是对于theta，只有theta(n^3)是正确的。
它在 O(n^3) 中，但是 O(n^4)、O(n^5) 等是 O(n^3) 的超集，所以如果某物在 O(n^) 3) 那么它也可以在 O(n^100) 中。最好的答案和约定俗成的是它所属的最小的大O，也就是O(n^3)，但不是唯一的。