Почему временная и пространственная сложность подсчета сортировки равна O (n + k), а не O (max (n, k))?

Question

Здесь 'n' и 'k' - это размер входного массива и максимальный элемент массива соответственно.

Поскольку в массиве имеется один прогон размера 'n' для подсчетачастоты элементов и, отдельный прогон в массиве размера 'k' и для каждого прохода (или итерации) в массиве, есть число [i] итераций, где 'count' является массивом размера 'k'.

То же самое с космической сложностью.

Я ищу хорошее объяснение, объясняющее каждый бит концепции, как вы можете догадаться, я ужасно запутался.

Answer 1

Спасибо всем, кто откликнулся.Но, я думаю, я понял.

Допущения:

• Фактический массив размером N равен A[]
• Максимальный элемент в массиве A[] равенK
• Массив для подсчета частоты элементов с размером K равен count[]
• Вспомогательный массив для хранения отсортированных элементов с размером N равен sorted[]

Я смотрел на это таким образом, в A[] есть один прогон для получения максимального элемента и еще один прогон для сохранения частоты каждого элемента.Это займет O(N).

Теперь в count[] есть один прогон, и для каждой итерации существует цикл в count[i] раз для вставки элементов массива в отсортированном порядке в sorted[].Сумма всех элементов в count[] не может быть больше, чем N.Таким образом, общее время для этих операций составляет O(N + K)

Следовательно, сложность времени наихудшего случая составляет O(N + K).Поправь меня, если я где-то ошибаюсь.

Answer 2

Обратите внимание, что O(n+k) = O(max(n, k)), потому что

       max(n,k) <= n+k <= 2max(n,k)

и big-O не видит константу 2.

Answer 3

На самом деле, в массиве есть два запуска k

k представляет размер массива.'K' в нотации O фактически представляет максимальный элемент.

Если мы напишем O (max (n, k)), это скроет детали алгоритма, который сильно зависит от максимального элемента