Big-O 表示法中函数 f(n) = n 的上限是多少？为什么？
What is the upper bound of function f(n) = n in Big-O notation and why?
我正在阅读 Karumanchi 的算法一书。在其中一个示例中给出了函数 f(n)= n 的 big-o 表示法是 O(n^2)。但为什么会这样，为什么会这样是不是 O(n) 与 c=2 和 n0=1.
f(n) = O(g(n)) 设置函数 f(n) 的上限。但这个上限不必太紧。
所以对于函数 f(n) = n，我们可以说 f(n) = O(n)，
还有 f(n) = O(n^2)、f(n) = (n^3) 等等。 Big-Oh 的定义并没有说明边界的紧度。
首先要确定我们理解 Karumanchi 所说的内容。首先，在第 61 页，他声明大 O 符号 "gives the tight upper bound of the given function."（他的重点）。所以如果 O(n) 是正确的，那么根据他的定义 O(n^2) 是不正确的。
然后，在第 62 页，我们得到了您引用的示例。他通过声明 n <= n^2 对于所有 n >= 1 来证明 O(n^2) 的合理性。这是真的。
但是对于所有 n >= 1，n <= 2n 也是正确的。（OP 的常量。）这证明了语句 n = O(n) with c = 2 and n0 = 1.
那他为什么说是O(n^2)呢？谁知道？书错了。
我正在阅读 Karumanchi 的算法一书。在其中一个示例中给出了函数 f(n)= n 的 big-o 表示法是 O(n^2)。但为什么会这样，为什么会这样是不是 O(n) 与 c=2 和 n0=1.
f(n) = O(g(n)) 设置函数 f(n) 的上限。但这个上限不必太紧。 所以对于函数 f(n) = n，我们可以说 f(n) = O(n)， 还有 f(n) = O(n^2)、f(n) = (n^3) 等等。 Big-Oh 的定义并没有说明边界的紧度。
首先要确定我们理解 Karumanchi 所说的内容。首先，在第 61 页，他声明大 O 符号 "gives the tight upper bound of the given function."（他的重点）。所以如果 O(n) 是正确的，那么根据他的定义 O(n^2) 是不正确的。
然后，在第 62 页，我们得到了您引用的示例。他通过声明 n <= n^2 对于所有 n >= 1 来证明 O(n^2) 的合理性。这是真的。
但是对于所有 n >= 1，n <= 2n 也是正确的。（OP 的常量。）这证明了语句 n = O(n) with c = 2 and n0 = 1.
那他为什么说是O(n^2)呢？谁知道？书错了。