你如何解决这个问题？你是否先得到 c ，它是两个函数的比率，然后用该比率找到 n 的范围？你怎么知道 ？请解释一下我真的迷路了，谢谢。
示例1:证明运行时间T(n) = n^3 + 20n + 1 为O(n^3) 证明:根据 Big-Oh 定义，
如果 T(n) ≤ c·n^3 对于某些 n ≥ n0 ，则 T(n) 为 O(n^3) 。
让我们检查一下这个条件:
如果 n^3 + 20n + 1 ≤ c·n^3 则 1 + 20/n^2 + 1/n^3 <=c 。
因此， Big-Oh 条件适用于 n ≥ n0 = 1 且 c ≥ 22 (= 1 + 20 + 1)。较大 n0 的值会导致较小的因子 c(例如，对于 n0 = 10 c ≥ 1.201 等)，但 无论如何，上述说法都是有效的。
最佳答案
我认为你看到的技巧是你没有考虑大数字。因此，我们举一个反例:
T(n) = n^4 + n
假设我们认为它是 O(N^3) 而不是 O(N^4)。你可以看到的是
c = n + 1/n^2
这意味着常量c实际上是c(n)，一个依赖于n的函数。将 N 取为一个非常大的数字表明，无论如何，c == c(n) 都是 n 的函数，因此可以不是O(N^3)。
当N趋向无穷大时，你想要的东西是有限的，除了常数之外的一切都保持不变:
c = 1 + 1/n^3
现在你可以轻松地说，它仍然是c(n)!随着 N 变得非常非常大，1/n^3 变为零。因此，在 N 非常大的情况下，在 O(N^4) 时间内声明 T(n) 的情况下，c = = 1 或者它是一个常数!
这有帮助吗？
关于data-structures - 大哦符号运行时间，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21054370/