Изучение сложности используется, чтобы увидеть, как эффективность вашей программы изменяется с ростом размера проблемы. Это полезно, если ваши входные размеры не имеют определенных границ.
Однако, если размер вашей задачи имеет определенную границу, например, n меньше 60, сложность алгоритма решения выиграет ' Это может быть полезно для вас: алгоритм со сложностью O (1) может быть медленнее, чем алгоритм со сложностью O (n 2 )!
Когда алгоритм A имеет меньшую Временная сложность Big-O (наихудший случай), чем B , , как правило, вы можете подумать , что это подразумевает, что существует N такой, что все размеры проблем больше чем N будет решено быстрее на A .
Вернее , это означает, что для любого n больше N, наихудшая проблема размера n для алгоритма A всегда будет быстрее (с меньшим количеством шагов), чем наихудшая проблема размера n для алгоритма B (обычно это будут совсем другие проблемы!).
В программировании теория сложности big-O полезна л, но только в том, как это помогает нам понять сложность среднего случая (который сложнее анализировать). В вашем примере сортировка слиянием используется вместо сортировки вставкой для больших размеров задач, не из-за сложности Big-O, а потому, что сложность среднего случая (которая в данном случае такая же, как сложность Big-O) .
Пример, когда сложность Big-O на практике не имеет значения (даже если мы заботимся о произвольно больших размерах задач):
- Быстрая сортировка, O (n 2 ), среднее (n log (n))
- Сортировка слиянием, O (n log (n)), среднее (n log (n))
Поскольку средние сложности одинаковы, мы не можем сказать, кто быстрее, без дополнительного анализа. Это похоже на ie -брейкер. Результаты этого анализа известны (не то, чтобы я когда-либо на это смотрел): быстрая сортировка значительно быстрее (имеет более низкую мультипликативную константу, связанную с ее сложностью в среднем случае). Это означает, что если число элементов сортировки произвольно велико, быстрая сортировка всегда является наилучшим вариантом, поскольку в среднем будет быстрее.
Наконец, алгоритм с более высоким значением скрытая мультипликативная константа"иногда очевидна, когда вы смотрите на шаги в алгоритме, но на практике это действительно менее математично и более экспериментально. На практике «шаги» в вашем алгоритме выполняются вашим процессором и зависят от его архитектуры и от того, как вы использовали свой язык программирования для инструктажа, а также от того, как процессор кэширует / выбирает память, процедуру системного вызова вашей операционной системы и т. Д. c. et c.
В итоге: несомненно то, что если алгоритм A имеет лучшую (более низкую) среднюю ситуацию сложность, чем алгоритма B , то существует некоторая N, где A в среднем будет решать проблемы быстрее, чем B для проблемных случаев, больших N. Мы можем измерить производительность, чтобы найти (или приблизительно найти) самую низкую N. Если алгоритм A является явным победителем по сравнению с другим, тогда N может быть 0, но часто алгоритмы с низкой сложностью - по иронии судьбы - более сложны и обычно выполняют больше анализа на каждом этапе, который имеет некоторые накладные расходы, делающие их медленнее для небольших проблемных экземпляров.
Final final комментарий: Если вы можете найти самый низкий N такой, что алгоритм A всегда быстрее, чем алгоритм B для задач с размерами, большими n, тогда это фактически не означает обратное: может не существовать N' > 2, так что любой экземпляр проблемы с размером меньше N' будет решаться быстрее B . Если это N' существует, то часто существует «средний» диапазон размеров, где доминирующая эффективность изменяется между двумя вариантами, что-то вроде этого:
- 1-83, B быстрее
- 84-92, A быстрее
- 93-111, B быстрее
- 112 и далее, A быстрее
Если проблему медленно решить при размерах около 90 (более миллисекунды или около того ), тогда мы могли бы сделать полную проверку, чтобы увидеть, что лучше. В противном случае мы могли бы просто сказать if (n > 111) do A, хотя мы знаем, что есть некоторые случаи, которые будут решены с помощью B , которые были бы быстрее разрешены с помощью A . И если преимущества эффективности B для меньших диапазонов недостаточно значительны, мы всегда можем выбрать A .