Сортировка вставки / куча Сортировка времени сложность

Question

Предположим, вам нужно отсортировать массив с n = 1,000,000 элементами. Сколько времени потребуется для вставки sort и heapsort, если предположить, что каждый базовый шаг занимает одну миллисекунду?

---

Я знаю, что сортировка вставки в худшем случае занимает n^2 шагов, а в худшем - heapsort n log n.

То есть 1,000,000 ^ 2 для сортировки вставок = 1*10^12 миллисекунд

и 1,000,000 * log(1,000,000) для сортировки кучи? 6,000,000 миллисекунды

это правильно?

Answer 1

Ну ...

Проблема в том, что нотация "порядок" говорит только о пределах и сравнениях, а не об абсолютных временах.Это также исключает константы и члены более низкого порядка.

Например, (это полностью вымышленное) фактическое время выполнения для конкретной реализации сортировки вставки, на которую вы можете смотреть, может быть:

num steps = 45,334 * n^2 + 6,500,000 * n + 2,000,000

Это O(n^2) алгоритм, но он займет намного больше времени, чем вы вычислили.