通过矛盾证明 n^2 - 10n 不是 O(n)
Proving n^2 - 10n is not O(n) by contradiction
我有解决方案，但我不明白其中的一部分。
想证明：n^2-10n不是O(n)的元素。
相反假设 n^2 - 10 是 O(n)
的一个元素
必须存在 c > 0 和 n0 > 0 这样对于所有 n >= n0, n^2-10n <= cn
重新排列上面的等式我们得到 n<=c+10
这是我迷路的地方
让k = 1 + max(n0, c+10)
k >= n0然而k <= c+10却不是这样，所以我们得出了一个矛盾。
问题：什么是k，我们为什么要分配它1 + max(n0, c+10)
让我们看看：理解这一点的一部分是直观地看到矛盾存在的原因；理论细节通常是您直觉的结果。
你知道 n^2 - 10n 是 O(n) 如果 n <= c+10 对于每个大于或等于 n0 的 n。请记住 c 是一个常量，所以这意味着 c+10（这也是一个常量）必须大于或等于每个大于或等于 [=14 的 n =].直觉上，您可以立即看出这是不可能的，因为常数不能大于无穷多个数。
这是什么意思？
好吧，你可以为 c 选择任何值，我可以立即告诉你一些 n 大于 c+10 从而违反要求 n <= c+10 .比如你给我c = 1000，我可以说"ok then, I choose n = 1011".
所以，如果你给我c，我给你n = c+10+1，你就输了；每个大于或等于 c+10+1 的 n 都违反了要求 n <= c+10（请记住，要求 必须 对每个 n >= n0).
现在，知道我将始终选择 n = c+10+1，您可能会选择一些大于 c+10 的 n0 来使我的答案无效，从而使事情复杂化。例如，您说 "ok, c is 1000"。我说："fine! n is 1011 - there, I found a value that violates the constraint."。但是你说："No you didn't! Because I choose n0 = 2000"。这使我的回答无效，因为我们早于条件 n <= c+10 必须仅对每个 n >= n0 成立的结论。在这个例子中，1011 不大于等于 2000，所以我的答案是无效的。 2000以下的我都挑不到。
这就是为什么你需要 max(): 来验证任何 n0 的 k。使用 k = max(n0, c+10)+1，您 总是 得到一个违反约束 n <= c+10 的值，无论您选择 c 或 [=14 时多么疯狂=].
所以，有了这个改进，你会告诉我："I choose c = 1000." 而我，为了阻止你的下一步行动，说："Ok, and what value do you choose for n0?" 你选择 -10000，或 5000，或 100000000000000000000。它没关系。如果我回复max(n0, c+10)+1，我总是赢:)
我希望现在说清楚了。
我有解决方案，但我不明白其中的一部分。
想证明：n^2-10n不是O(n)的元素。
相反假设 n^2 - 10 是 O(n)
必须存在 c > 0 和 n0 > 0 这样对于所有 n >= n0, n^2-10n <= cn
重新排列上面的等式我们得到 n<=c+10
这是我迷路的地方
让k = 1 + max(n0, c+10)
k >= n0然而k <= c+10却不是这样，所以我们得出了一个矛盾。
问题：什么是k，我们为什么要分配它1 + max(n0, c+10)
让我们看看：理解这一点的一部分是直观地看到矛盾存在的原因；理论细节通常是您直觉的结果。
你知道 n^2 - 10n 是 O(n) 如果 n <= c+10 对于每个大于或等于 n0 的 n。请记住 c 是一个常量，所以这意味着 c+10（这也是一个常量）必须大于或等于每个大于或等于 [=14 的 n =].直觉上，您可以立即看出这是不可能的，因为常数不能大于无穷多个数。
这是什么意思？
好吧，你可以为 c 选择任何值，我可以立即告诉你一些 n 大于 c+10 从而违反要求 n <= c+10 .比如你给我c = 1000，我可以说"ok then, I choose n = 1011".
所以，如果你给我c，我给你n = c+10+1，你就输了；每个大于或等于 c+10+1 的 n 都违反了要求 n <= c+10（请记住，要求 必须 对每个 n >= n0).
现在，知道我将始终选择 n = c+10+1，您可能会选择一些大于 c+10 的 n0 来使我的答案无效，从而使事情复杂化。例如，您说 "ok, c is 1000"。我说："fine! n is 1011 - there, I found a value that violates the constraint."。但是你说："No you didn't! Because I choose n0 = 2000"。这使我的回答无效，因为我们早于条件 n <= c+10 必须仅对每个 n >= n0 成立的结论。在这个例子中，1011 不大于等于 2000，所以我的答案是无效的。 2000以下的我都挑不到。
这就是为什么你需要 max(): 来验证任何 n0 的 k。使用 k = max(n0, c+10)+1，您 总是 得到一个违反约束 n <= c+10 的值，无论您选择 c 或 [=14 时多么疯狂=].
所以，有了这个改进，你会告诉我："I choose c = 1000." 而我，为了阻止你的下一步行动，说："Ok, and what value do you choose for n0?" 你选择 -10000，或 5000，或 100000000000000000000。它没关系。如果我回复max(n0, c+10)+1，我总是赢:)
我希望现在说清楚了。