任何线性函数 an + b 都是 O(n^2) CLRS
any linear function an + b is O(n^2) CLRS
在 CLRS 的第 3 版中，特别是第 3.1 节（我书中的第 47 页）他们说
when a > 0, any linear function an + b is in O(n^2), which is easily verified by taking c = a + |b| and n0 = max(1,-b/a).
其中 n0 是这样的值，当 n >= n0 时，我们可以在上述证明中证明 an + b <= cn^2。
- 我试图验证这一点，但我不能走得太远:(
- 他们是如何选择这些 c 和 n0 值的？我知道唯一重要的是存在这样的 c 和 n0 使得上述证明 an + b 是 O(n^2) 但我想知道他们是如何具体选择 c 和 n0 的那些值的？它们看起来并不随意，就好像它们应用了一些我以前从未见过的技术来获得它们一样。
谢谢。
让我们以 a 和 b 均为正数的简单情况为例。作者试图做的是创建一个值，其中二次函数支配 n >= 1 的线性函数。就是这样。他们只是想创建一个通用解决方案来显示正确的抛物线在任何直线上占主导地位。
所以对于 n=1，当 n=1 时，线性函数（即 l(n) = an + b）的值将是 a+b。如果我们选择 c = a + b，则没有任何线性子函数的支配二次函数（即 q(n) = c * n^2）将支配线性函数 l(n) 在 n=1。因此，假设 a 和 b 均为正数，当 n>=1 时 q(n) = (a+b)n^2 支配 l(n) = an + b。您可以自己查看 plotting 30x^2 and 10x + 20 on Densmos.
的示例
当b为负数时有点棘手，但正数情况基本上是重点。
在 CLRS 的第 3 版中，特别是第 3.1 节（我书中的第 47 页）他们说
when a > 0, any linear function an + b is in O(n^2), which is easily verified by taking c = a + |b| and n0 = max(1,-b/a).
其中 n0 是这样的值，当 n >= n0 时，我们可以在上述证明中证明 an + b <= cn^2。
- 我试图验证这一点，但我不能走得太远:(
- 他们是如何选择这些 c 和 n0 值的？我知道唯一重要的是存在这样的 c 和 n0 使得上述证明 an + b 是 O(n^2) 但我想知道他们是如何具体选择 c 和 n0 的那些值的？它们看起来并不随意，就好像它们应用了一些我以前从未见过的技术来获得它们一样。
谢谢。
让我们以 a 和 b 均为正数的简单情况为例。作者试图做的是创建一个值，其中二次函数支配 n >= 1 的线性函数。就是这样。他们只是想创建一个通用解决方案来显示正确的抛物线在任何直线上占主导地位。
所以对于 n=1，当 n=1 时，线性函数（即 l(n) = an + b）的值将是 a+b。如果我们选择 c = a + b，则没有任何线性子函数的支配二次函数（即 q(n) = c * n^2）将支配线性函数 l(n) 在 n=1。因此，假设 a 和 b 均为正数，当 n>=1 时 q(n) = (a+b)n^2 支配 l(n) = an + b。您可以自己查看 plotting 30x^2 and 10x + 20 on Densmos.
当b为负数时有点棘手，但正数情况基本上是重点。