leetcode 561的时间复杂度

Question

问题是：给定一个2n个整数数组，你的任务是将这些整数分组为n对整数，比如说（a1，b1），（a2，b2），...，（a，bn） min（ai，bi）表示尽可能大的从1到n的所有i。

解决方案提供为：

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不是一个常数因素，可能不应该被删除。

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

希望有所帮助。