Почему сортировка массива с фиксированной длиной (например, массива только с пятью элементами) стоит O (1)?

Question

Насколько я понимаю, когда n фиксировано, стоимость сортировки n элементов равна O (1).

Например, в этом объяснении алгоритма поиска медианы за линейное время говорится:

# Next, we sort each chunk. Each group is a fixed length, so each sort
# takes constant time. Since we have n/5 chunks, this operation
# is also O(n)

https://rcoh.me/posts/linear-time-median-finding/

Я не понимаю, почему.Я должен представить, что есть функция, которая охватывает все 5 возможных!комбинации расположения элементов?

Answer 1

Любое ограниченное время работы по определению считается постоянным.

Например, решение задачи коммивояжера для миллиарда городов занимает постоянное время.

Это потому, что БольшойОбозначение O не относится к единице времени (не задействован реальный компьютер), и любая фиксированная сумма эквивалентна 1.

Answer 2

Хорошей практикой для вас является выяснение того, почему (в качестве альтернативы следованию тому, что вам говорят другие), может быть анализ сложности рутины в обоих направлениях: тот, где вы можете определить сложностьсортировка 5 элементов, а другой, конечно же, происходит заданным образом.Затем примените анализ к нескольким различным длинам ввода и посмотрите, какая из них имеет больше смысла.

Answer 3

Обозначение Big O используется для описания того, как увеличивается время выполнения или пространство по мере увеличения входных данных.Если количество вещей, которые вы сортируете, не увеличивается при увеличении входных данных, то шаг сортировки алгоритма, который вы оцениваете, равен O(1).

Пример. Допустим, ваш ввод представляет собой массив длиныn >= 10, и вы выводите тот же массив, но с первыми 10 элементами в отсортированном порядке, а остальные без изменений.Затем, поскольку время, которое вы тратите на сортировку, не увеличивается по мере увеличения входных данных (при увеличении n) шаг сортировки равен O (1).