Временная сложность leetcode 561

Question

Вопросы: Учитывая массив из 2n целых чисел, ваша задача состоит в том, чтобы сгруппировать эти целые числа в n пар целых чисел, скажем, (a1, b1), (a2, b2), ..., (an, bn), что составляет сумму min (ai, bi) для всех i от 1 до n как можно большего размера.

Решение предоставляется в виде:

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

Асимптотическая сложность измеряется как функция от n для ALL n. Мы обеспокоены тем, что происходит, когда n становится большим. Действительно, действительно большой.

Может быть, на практике n всегда будет крошечным. Хорошо.

Но когда вы даете меру сложности для алгоритма, вы по определению говорите, что происходит с ростом n. И растет и растет. И когда это произойдет, он будет карликом К.

Значит, 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).

Надеюсь, это поможет.