Сколько времени потребуется для сортировки 10610610^6 чисел и 10910910^9 чисел для двух алгоритмов, если они занимают одинаковое время для сортировки 100010001000 чисел?

Как говорится, ответ «мы не знаем». Это следует из$O(\cdot)$обозначение — грубо говоря, у вас недостаточно информации, чтобы сделать вывод. Вы знаете только асимптотическое поведение, и даже не константы.

Алгоритм 1 вполне может быть таким же быстрым, как алгоритм 2, если$n$меньше, чем, скажем,$10^{10}$, а потом разорваться.

Хуже того, нотация «большое О» — это только верхняя граница. Насколько нам известно, оба могут иметь одинаковое время работы$O(n\log n)$, так как если бы алгоритм 1 имел время работы$O(n\log n)$, это также тривиально имело бы время работы$O(n^2)$.

Вы видели два ответа, которые иллюстрируют, что оценки времени по принципу «О» мало что говорят о фактическом времени работы, но чтобы проиллюстрировать, насколько велика разница между фактическими заказами, давайте обойдемся без оценок по принципу «О» и предположим, что мы действительно знали что Алгоритм 1 взял именно$c_1n^2$секунд для сортировки$n$чисел, а Алгоритм 2 взял ровно$c_2n\log_{10} n$секунд для сортировки$n$числа (я выбрал логарифм по основанию десять, чтобы упростить расчеты; выбор другого основания только изменил бы константу$c_2$).

Если Алгоритму 2 потребовалась 1 секунда для сортировки$10^3$числа, мы бы

$$1=c_1(10^3)^2=c_1\,10^6$$ так $c_1=1/10^6$. Если алгоритму 2 также потребовалась 1 секунда для сортировки $10^3$числа, мы бы $$1=c_2(10^3\log(10^3))=c_2(3\cdot10^3)$$ так $c_2=1/(3\cdot10^3)$.

Теперь давайте посмотрим, что происходит, когда мы сортируем$10^6$числа. Алгоритм 1 примет

$$\frac{1}{10^6}\cdot(10^6)^2=\frac{10^{12}}{10^6}=10^6\text{ seconds}$$ что получается примерно $11.5$дней. С другой стороны, алгоритм 2 примет $$\frac{1}{3\cdot10^3}\cdot(10^6\log10^6)=\frac{6\cdot10^6}{3\cdot10^3}=2\cdot10^3\text{ seconds}$$ что о $33.3$минут. Хм, 11 дней против получаса. Я знаю, какой алгоритм я бы использовал.

Для больших входных данных разница во времени становится еще более существенной. С$10^9$чисел для сортировки, вы можете понять, что алгоритм 1 займет около 31688 лет , а алгоритм 2 — около 34,7 дней.

Обратите внимание, что алгоритм 1 имел гораздо меньший постоянный множитель, чем алгоритм 2, но в долгосрочной перспективе это не имело такого значения, как асимптотический порядок их времени выполнения. Проще говоря,$n\log n$Алгоритм в конечном итоге забьет$n^2$алгоритм, независимо от того, каков постоянный кратный.

Математически, большой-$O$нотация так не работает.$O(n^2)$обозначает класс эквивалентности функций, основанный на их амиптотике.

Так, например,$f$определяется$f(n)=n^2$принадлежит$O(n^2)$. Так и функция$g$определяется$g(n)=10^{1000}n^2$.

Итак, два разных алгоритма, которые требуют времени$O(n^2)$могут иметь совершенно разную производительность для конкретной задачи. Большой-$O$нотация предназначена для того, чтобы зафиксировать эту масштабируемость этих алгоритмов как$n \rightarrow \infty$.

---

Однако, если вы используете это для практического применения, мультипликативная константа впереди, вероятно, не будет слишком большой. Игнорирование$O(..)$часто может дать разумное представление о том, сколько времени займет алгоритм.

Таким образом, мы можем приблизиться к тому, что$O(n^2)$алгоритм займет время$(10^6)^2=10^{12}$обрабатывать$10^6$предметы и$O(n \log n)$алгоритм займет время$10^9 \log {10^9} \approx 2 \times 10^{10}$обрабатывать$10^9$предметы.

В большинстве реальных случаев сравнение будет неплохим, но, с другой стороны, оно может быть и ужасным.