大 O 复杂度 10n = O(n²)

Question

我正在尝试理解 Big O 符号，但这比我想象的要难一些。我有一个函数 10n 我想证明 10n = O(n² ).

谁能告诉我如何证明这一点？

我可以使用的可能值是：

• c = 0, n0 = 1
• c = 1, n0 = 1
• c = 2, n0 = 5
• c=1,n0=9

Answer 1

大O表示法的思想很简单：

g(n) = O(f(n)) 如果当n足够大时，g(n)的增长率小于或等于f(n)的增长率（等于，我的意思是比率小于无穷大）

所以如果 g(n) = O(f(n)) 那么

k 可以是 0 或小于无穷大的正数。

所以在你的情况下

意味着 10n = O(n^2)

Answer 2

您必须找到 n₀ 和 c 的值，这样对于每个n ≥ n₀ 10n为真≤ c⋅n²

让我们试试您在评论中提出的可能性：

• c=0, n₀=1

  不，那行不通，对于 n=1 我们已经发现 10n > 0 n²

• c=1, n₀=1

  不，那不行，至于n=1，我们发现10n > 1 n²

• c=2, n₀=5

  是的，这行得通：我们必须证明：

  10n ≤ 2n², 所以

  10 ≤ 2n, 所以

  5 ≤ n.

  因为 n₀=5 并且我们必须只检查 n ≥ n₀，我们有一个永远正确的说法。

• c=1, n₀=9

  不，那不行，至于n=9我们发现10n > 1 n²。注意：如果我们选择 n₀=10 会起作用，但这不在您提供的选项中。