Зачем игнорировать константы при вычислении сложности времени выполнения алгоритма

Question

Может кто-нибудь объяснить причину игнорирования констант при вычислении сложности алгоритма во время выполнения, пожалуйста?

Спасибо

Answer 1

потому что при сравнении очень больших значений (назовем это n) ... n ^ 2 будет выше, чем k * n для любого k, где n-> бесконечность. это, конечно, верно для любой степени / степени n.

обратите внимание , что в реальных проектах вы делаете эти оптимизации и пытаетесь минимизировать константы, но обычно они менее значимы, чем степень полинома

Answer 2

При анализе констант сложности времени их сложно и неуместно вычислять.

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

Что еще более важно, даже если это верно сейчас, в какой-то момент в будущем или в другой слегка другой архитектуре, эта константа может отличаться, поэтому время выполнения может варьироваться в зависимости от архитектуры. Так что теперь мой алгоритм имеет более одного времени выполнения? Один на данный момент для этой архитектуры, другой для другой архитектуры, и каждый из них может измениться в будущем ... Опять не красиво.

В мире, где возможности вычислений все время меняются, завтра вдвое больше возможностей ЦП, в четыре раза больше памяти за неделю и т. Д., Это не имеет отношения к постоянным факторам. Это не тот случай, если нам нужно количественно оценить реальное время выполнения, но когда мы анализируем сложность алгоритма в целом, а не сложность решения в конкретной среде, это так.

Кроме того, и, вероятно, самое главное, постоянные факторы не являются хорошей мерой сложности проблемы, и в конце дня мы пытаемся измерить сложность. Алгоритм, имеющий определенный класс сложности, ведет себя (или, точнее, ограничен) определенным образом для всех входных данных размера. Поэтому, когда я пытаюсь измерить общую сложность двух решений, я делаю это как можно более общим способом, и поэтому стараюсь учитывать все значения входного размера (т.е. n-> бесконечность).

Наконец, это позволяет теоретикам группировать алгоритмы в один класс, независимо от определенных постоянных факторов, которые могут изменяться или не изменяться, а могут и не улучшаться. Это полезно, помимо прочего, для доказательства оптимальности; обнаружение, что проблема omega(f(n)), полезно только в том случае, если мы рассмотрим алгоритмы в классе сложности O(f(n)), независимо от констант.

Answer 3

Вы игнорируете константы только при грубой оценке. В большинстве случаев это действительно упрощение: при сравнении двух алгоритмов для больших входных измерений, таких как сортировка массива, O (n log n) в конечном итоге будет быстрее или меньше O (n²), несмотря ни на что.

Однако, когда два алгоритма имеют одинаковую сложность или когда ожидаемый набор данных настолько мал, что асимптотическое поведение не является допустимым сценарием реального мира, тогда константа определенно важна. Например, реализация с пузырьковой сортировкой, скорее всего, будет работать быстрее на массиве из 3 или 4 значений, чем быстрая сортировка.

Answer 4

С ростом значения n в уравнении g 6n ^ 2 + 100n + 300 константа становится менее актуальной, и мы склонны игнорировать это .См. Следующее изображение

Снимок сделан из Асимптотическая запись секция в Академии Хана.