O(n^3) 真的比 O(2^n) 更有效率吗？
Is O(n^3) really more efficient than O(2^n)?
我的算法class的作业声称 O(n3) 比 O(2n 更有效).
当我将这些函数放入图形计算器时，f(x)=2x 对于非常大的 n（从 n = 982 左右开始）似乎始终更有效.
考虑到对于函数 f(n) = O(g(n))，对于所有大于某些 n0 的 n，它必须更小，这不是吗意味着从 n = 982 我们可以说 O(2n) 更有效？
你混淆了 O(2n) 和 2n。 O(2n) 实际上是 C*2n，其中 C 是任意选择的正常数。同样，O(n3) 是 D*n3，其中 D 是另一个任意选择的正常数。声明 "O(n3) is more efficient than O(2n)" 意味着，给定任何固定的 C 和 D，总是可以找到这样的 n0 对于任何 n >= n0, D*n3
< C*2n.
2^n 的增长速度比 n^3 快得多。也许您在计算器或类似的东西中输入了错误的值。另请注意，更高效 意味着 更少时间 这意味着 较低的值 y-axis .
让我向您展示这些函数的一些正确图（使用 Wolfram Alpha）：
首先 2^n 更小（但只是一个很小的范围），之后 你可以看到 2^n 如何超越它。
经过这次交集，情况再也没有改变，2^n 仍然远远大于 n^3。这也适用于您分析的范围，因此 > 982，如下图所示（n^3 的图靠近 x-axis）：
另请注意，在 Big-O-Notation 中，我们总是根据函数的增长来比较函数。这就是为什么像 O(n^3) 不包含函数 f : f(x) <= n^3 而是 f : f(x) <= C * n^3 的原因，其中 C 是一个任意常数，它可能很大，也可能很小。这说明了比较中的 增长因子 。另请注意，允许条件在有限数量的 x 中不成立，但在条件成立的地方必须存在一些界限 x'，因此对于每个 x > x'.
将此解释与 Wikipedia 中的完整数学定义进行比较，其中 C 是 k，x 是 n，x' 是n_0:
如果为真，则定义 f(n) 在集合 O(g(n)) 中。
我的算法class的作业声称 O(n3) 比 O(2n 更有效).
当我将这些函数放入图形计算器时，f(x)=2x 对于非常大的 n（从 n = 982 左右开始）似乎始终更有效.
考虑到对于函数 f(n) = O(g(n))，对于所有大于某些 n0 的 n，它必须更小，这不是吗意味着从 n = 982 我们可以说 O(2n) 更有效？
你混淆了 O(2n) 和 2n。 O(2n) 实际上是 C*2n，其中 C 是任意选择的正常数。同样，O(n3) 是 D*n3，其中 D 是另一个任意选择的正常数。声明 "O(n3) is more efficient than O(2n)" 意味着，给定任何固定的 C 和 D，总是可以找到这样的 n0 对于任何 n >= n0, D*n3 < C*2n.
2^n 的增长速度比 n^3 快得多。也许您在计算器或类似的东西中输入了错误的值。另请注意，更高效 意味着 更少时间 这意味着 较低的值 y-axis .
让我向您展示这些函数的一些正确图（使用 Wolfram Alpha）：
首先 2^n 更小（但只是一个很小的范围），之后 你可以看到 2^n 如何超越它。
经过这次交集，情况再也没有改变，2^n 仍然远远大于 n^3。这也适用于您分析的范围，因此 > 982，如下图所示（n^3 的图靠近 x-axis）：
另请注意，在 Big-O-Notation 中，我们总是根据函数的增长来比较函数。这就是为什么像 O(n^3) 不包含函数 f : f(x) <= n^3 而是 f : f(x) <= C * n^3 的原因，其中 C 是一个任意常数，它可能很大，也可能很小。这说明了比较中的 增长因子 。另请注意，允许条件在有限数量的 x 中不成立，但在条件成立的地方必须存在一些界限 x'，因此对于每个 x > x'.
将此解释与 Wikipedia 中的完整数学定义进行比较，其中 C 是 k，x 是 n，x' 是n_0:
如果为真，则定义 f(n) 在集合 O(g(n)) 中。