Почему постоянная всегда выпадает из большого анализа O?

Я пытаюсь понять конкретный аспект анализа Big O в контексте запуска программ на ПК.

Предположим, что у меня есть алгоритм с производительностью O (n + 2). Здесь, если n становится действительно большим, 2 становится несущественным. В этом случае совершенно ясно, что реальная производительность – O (n).

Однако, скажем, еще один алгоритм имеет среднюю производительность O (n ^ 2/2). Книга, в которой я видел этот пример, говорит, что реальная производительность – O (n ^ 2). Я не уверен, что понимаю почему, я имею в виду, что 2 в этом случае кажется не совсем незначительным. Поэтому я искал хорошее объяснение из книги. Книга объясняет это так:

«Подумайте, что означает значение« 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 становится очень большим, то константы не действительно имеет какое-либо значение для ответа и почти ничтожно, поэтому мы склонны оставлять их при вычислении сложности.

Interesting Posts

Переименование файлов Linux, которые случайно имеют несколько расширений .mp3

Совместимость материалов дизайна с версиями ниже Android 5.0?

java.sql.SQLException: – ORA-01000: превышены максимальные открытые курсоры

Динамические строки MVC 5 с BeginCollectionItem

C # – статические типы не могут использоваться как аргументы типа

Как установить цвета пули в списки UL / LI html через CSS без использования каких-либо изображений или тегов span

Как я могу исправить ошибку Microsoft Visual Studio: «Пакет неправильно загружен»?

Что нужно разбить в KDE, чтобы отключить прозрачность?

Где я могу разместить папку «assets» в Android Studio?

Кнопки мыши и кнопки браузера браузера отменены

C #: исключение из памяти

Math.random () против Random.nextInt (int)

Оказание другой формы с помощью ajax заставляет его состояние представления потеряться, как мне добавить это обратно?

Что (на самом деле) происходит, когда вызывается функция с предупреждением «control достигает конца не-void функции»?

Excel 2010 Перемещение данных из нескольких столбцов / строк в одну строку

Давайте будем гением компьютера.