leetcode 561 的时间复杂度

Question

问题是：给定一个2n个整数的数组，你的任务是将这些整数分组为n对整数，比如（a1，b1），（a2，b2），...，（an，bn），这使得从1到n的所有i的min（ai，bi）之和尽可能大。提供的解决方案如下：public class Solution {    public int arrayPairSum(int[] nums) {        int[] arr = new int[20001];        int lim = 10000;        for (int num: nums)            arr[num + lim]++;        int d = 0, sum = 0;        for (int i = -10000; i <= 10000; i++) {            sum += (arr[i + lim] + 1 - d) / 2 * i;            d = (2 + arr[i + lim] - d) % 2;        }        return sum;    }} 我认为说时间复杂度是O（n）是不公平的。虽然 O（n+K） K = 20001 是一个常数，似乎可以省略，但 n 也小于 K。如果是这样，为什么我不能说时间复杂度是O（1）？

Answer 1

对于 ALL n，渐近复杂度测量为 n 的函数。我们关心的是当n变大时会发生什么。真的，真的很大。

也许在实践中，n将永远很小。好。

但是，当你为算法给出一个复杂性度量时，根据定义，你是在说随着n的增长会发生什么。并且不断增长。当它发生时，它将使K相形见绌。

所以O（n）是的。

澄清：

的确，问题规范说：

n 是一个正整数，在 [1， 10000] 的范围内。

数组中的所有整数都将在 [-10000， 10000] 的范围内。

但请记住，这只是针对这个问题！给出硬编码 K 值的解决方案。正如你所注意到的，这里使用的算法确实应该写成O（n + K）。这个K不是一个常数因子，可能不应该被删除。

然而，对于渐近复杂性（Big-O，Big-Theta等），即使使用任意但有限的K，您仍然可以找到常量k和N，使得对于所有n>N，kn>该算法中所需的运算次数，这就是Big-O定义。这就是为什么你会看到很多人说O（n）。

希望有所帮助。