阅读约束并选择复杂度

每道题都会列出 n 和数值的限制。这些约束条件会悄悄告诉您出题者期望的复杂度。🔍

在设计任何方案之前，请先找出约束条件中的最大n。n 的规模决定了您需要二次、线性还是对数复杂度。

当 n 不超过 20 时，即使是指数级暴力搜索也能通过。限制较小时，您可以放心尝试每一种组合。

如果 n 达到几百，O(n^3)解法仍然可以通过。在这里，三重循环或针对元素对的基础 DP 都是可行的。

当 n 约为 5000 时，请以 O(n^2) 为目标。对数组使用嵌套循环大约需要 2.5 乘以 10^7 步，仍然符合预算。

当 n 达到 10^5 或 10^6 时，您需要 O(n log n) 或 O(n)。排序、前缀和与双指针会成为您的常用工具。

如果 n 达到十亿，任何遍历 n 次的循环都无法通过。您必须使用 O(log n) 或 O(1)，借助数学方法或对答案进行二分查找。

数值的限制同样重要。较大的数字会提醒您注意其他语言中的溢出，也可能暗示需要使用模运算。

多组测试的题目通常限制的是n 的总和，而不是每组的 n。请仔细阅读这一点，因为它会改变循环可以安全处理的规模。

根据 n 选择目标复杂度，然后选择能够达到该复杂度的算法。让 n指导设计，比凭猜测决定后再重写更好。

请把这张表记在脑中。约束条件到复杂度的对应关系，可以让您在竞赛中快速查看限制后立即制定方案。

让 n 指引您选择正确的复杂度。

现在您可以把限制条件视为目标：n 很小时可以使用暴力搜索，10^5 需要 n log n，而 10^9 则需要对数复杂度或数学方法。让 n 决定方案。🗺️