Почему постоянная всегда выпадает из большого анализа O?
Я пытаюсь понять конкретный аспект анализа Big O в контексте запуска программ на ПК.
Предположим, что у меня есть алгоритм с производительностью O (n + 2). Здесь, если n становится действительно большим, 2 становится несущественным. В этом случае совершенно ясно, что реальная производительность – O (n).
Однако, скажем, еще один алгоритм имеет среднюю производительность O (n ^ 2/2). Книга, в которой я видел этот пример, говорит, что реальная производительность – O (n ^ 2). Я не уверен, что понимаю почему, я имею в виду, что 2 в этом случае кажется не совсем незначительным. Поэтому я искал хорошее объяснение из книги. Книга объясняет это так:
- Что такое псевдополиномиальное время? Чем он отличается от полиномиального времени?
- Существуют ли случаи, когда вы предпочитаете более высокий алгоритм сложной сложности по сравнению с более низким?
- Что может привести к сложности алгоритма O (log n)?
- Big O, как вы его вычисляете / приближаете?
- Максимальная прибыль от одной продажи
«Подумайте, что означает значение« 1/2 ». Фактическое время проверки каждого значения сильно зависит от машинной команды, которую код переводит, а затем на скорости, с которой процессор может выполнять инструкции, поэтому 1/2 не работает, Это очень важно.
И моя реакция … Хм ???. Я в буквальном смысле не знаю, что это говорит или точнее, что это заявление связано с их заключением. Может кто-нибудь изложить это для меня, пожалуйста.
Спасибо за любую помощь.
Нотация Big-O не заботится о константах, потому что примечание Big-O описывает только долгосрочные темпы роста функций, а не их абсолютные величины. Умножение функции на константу влияет только на ее скорость роста на постоянную величину, поэтому линейные функции все еще растут линейно, логарифмические функции все еще растут логарифмически, экспоненциальные функции все равно растут экспоненциально и т. Д. Так как эти категории не зависят от констант, что мы отбрасываем константы.
Тем не менее, эти константы абсолютно важны! Функция, время выполнения которой составляет 10 100 н, будет медленнее, чем функция, время выполнения которой равно n. Функция с временем выполнения n 2/2 будет быстрее, чем функция, время выполнения которой равно n 2 . Тот факт, что первые две функции являются как O (n), так и вторыми двумя, – O (n 2 ), не изменяет того факта, что они не работают за такое же количество времени, поскольку это не то, что обозначение Big-O предназначен для. O хорошо подходит для определения того, будет ли в долгосрочной перспективе одна функция больше другой. Несмотря на то, что 10 100 n является колоссально огромным значением для любого n> 0, эта функция O (n), и поэтому при достаточно большом n в конечном итоге она будет бить функцию, время выполнения которой равно n 2/2, потому что эта функция O (n 2 ).
Итак, поскольку big-O говорит только об относительных classах темпов роста, он игнорирует постоянный фактор. Однако эти константы абсолютно значительны; они просто не имеют отношения к асимптотическому анализу.
Надеюсь это поможет!
Вы совершенно правы, что константы имеют значение. Сравнивая множество разных алгоритмов для одной и той же проблемы, числа O без констант дают вам обзор того, как они сравниваются друг с другом. Если у вас есть два алгоритма в том же classе O, вы бы сравнили их с использованием констант.
Но даже для разных classов O важны константы. Например, для мультидигитного или большого целочисленного умножения наивный алгоритм равен O (n ^ 2), Карацуба – O (n ^ log_2 (3)), Toom-Cook O (n ^ log_3 (5)) и Schönhage-Strassen O (п * журнал (п) * журнал (журнал (п))). Однако каждый из более быстрых алгоритмов имеет все большие и большие накладные расходы, отраженные в больших константах. Итак, чтобы получить приблизительные точки пересечения, нужны достоверные оценки этих констант. Таким образом, как SWAG, получается, что до n = 16 наивное умножение происходит быстрее всего, до n = 50 Карацуба и переключение из Тоом-Кука в Шенхадж-Штрассен происходит при n = 200.
На самом деле точки пересечения зависят не только от констант, но и от процессорного кэширования и других связанных с аппаратным обеспечением проблем.
Запись Big-O описывает только скорость роста алгоритмов с точки зрения математической функции, а не фактическое время работы алгоритмов на некоторой машине.
Математически Пусть f (x) и g (x) положительны при достаточно больших x. Будем говорить, что f (x) и g (x) растут с той же скоростью, когда x стремится к бесконечности, если
теперь пусть f (x) = x ^ 2 и g (x) = x ^ 2/2, тогда lim (x-> бесконечность) f (x) / g (x) = 2. так что x ^ 2 и x ^ 2/2 имеют одинаковый темп роста. Можно сказать, что O (x ^ 2/2) = O (x ^ 2).
Как подчеркивает templatetypedef, скрытые константы в асимптотических обозначениях абсолютно значительны. В качестве примера: сортировка marge выполняется в O (nlogn) наихудшем случае, а сортировка вставки выполняется в O (n ^ 2) наихудшем случае. Но как скрытые константные факторы в сортировке вставки меньше, чем сортировка marge, на практике сортировка вставки может быть быстрее, чем сортировка marge для небольших проблемных размеров на многих машинах.
Большего O без константы достаточно для анализа алгоритмов.
Во-первых, фактическое время зависит не только от количества инструкций, но и от времени для каждой команды, которая тесно связана с платформой, на которой выполняется код. Это больше, чем теоретический анализ. Поэтому для большинства случаев константа не нужна.
Во-вторых, Big O в основном используется для измерения того, как время работы будет увеличиваться по мере увеличения проблемы или уменьшения времени выполнения при повышении производительности аппаратного обеспечения.
В-третьих, для ситуаций с высокой эффективностью оптимизации также будет учитываться постоянная.
Время, требуемое для выполнения конкретной задачи на компьютерах в настоящее время, не требует большого количества времени, если введенное значение очень велико.
Предположим, что мы хотим умножить 2 матрицы размера 10 * 10, у нас не будет проблем, если мы не хотим делать эту операцию несколько раз, а затем роль асимптотических обозначений становится преобладающей, а когда значение n становится очень большим, то константы не действительно имеет какое-либо значение для ответа и почти ничтожно, поэтому мы склонны оставлять их при вычислении сложности.