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

Question

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

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

То же самое с пространственной сложностью.

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

Answer 1

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

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

а биг-о не видит константу 2,

Answer 2

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

Предположения:

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

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

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

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

Answer 3

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

k представляет размер массива. Буква "k" в обозначении O фактически представляет максимальный элемент.

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