algorithm - 无法理解 O(f(n))

Question

以下循环的值(value)是什么:

T(n) = T(n/4) + T(n/2) + cn², T(1) = c, T(0) = 0

其中 c 是正常数:

1. T(n) = O(n³)
2. T(n) = O(n²)
3. T(n) = O(n² log n)
4. T(n) = O(n log n)

正确答案是2，但我有疑问。根据 O(f(n)) 的定义，它给了我们一个上限，O(n²) 是最小上限。所以在我看来 O(n³) 和 O(n² log n) 也应该是真的。

让

T(n) = 1/2n² + 3n

以下哪些陈述是正确的(勾选所有适用项。)

1. T(n) = O(n)
2. T(n) = Ω(n)
3. T(n) = θ(n²)
4. T(n) = O(n³)

这里，正确答案是 2、3 和 4。

那么，我是不是理解错了定义，还是犯了一些错误？

Answer 1

让我们尝试证明第一次使用归纳法复发。
我将使用 Big O 的这个定义(来自 CLRS ):

对于一些常量 和 .

基本步骤:

.同样适用于 , 但由于 , 它对重复没有任何贡献，我们可以选择 作为我们的基本案例。

归纳步骤:

假设 , 现在推导出 .自 ，我们的假设意味着 .

我们有

对于一些常量 .

自

持有，设置和 对于所有归纳假设的表达式产生:

_{(如果我在某处搞砸了，请告诉我!)}

So in my opinion O(n³) and O(n² log n) should also be true.

，所以是的，你是完全正确的。你可以像上面那样证明它是正确的。然而，非正式地，人们经常使用 可与紧上限互换。这是不精确的，但习惯了。如果你从高等教育机构那里得到这些问题，那当然是有问题的。

So, am I understanding the definition incorrectly or am I making some mistake?

你基本上是正确的。但是，现实世界与形式的正确性无关，因此请提防非正式主义并了解更多信息。顺便说一句，许多人也对待 Landau 符号 , , 和 相同，即使它们绝对不是。