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

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

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

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

"Подумайте, что означает значение 1/2. Фактическое время для проверки каждого значения сильно зависит от машинной инструкции, что код переводит на и затем скорость, с которой процессор может выполнять инструкции. Поэтому значение 1/2 не означает очень много."

И моя реакция... Huh???. Я в буквальном смысле не знаю, что это говорит или точнее, что это выражение связано с их заключением. Может кто-нибудь изложить это для меня, пожалуйста.

Спасибо за любую помощь.

Ответ 1

Существует различие между "эти константы значимы или актуальны?" и "небезразличная нотация заботится о них?" Ответ на этот второй вопрос - "нет", а ответ на первый вопрос - "абсолютно!".

Нотация Big-O не заботится о константах, потому что нотация Big-O описывает только долгосрочные темпы роста функций, а не их абсолютные величины. Умножение функции на константу влияет только на скорость ее роста на постоянную величину, поэтому линейные функции по-прежнему растут линейно, логарифмические функции по-прежнему логарифмически растут, экспоненциальные функции продолжают расти экспоненциально и т.д. Поскольку эти категории не зависят от констант, это не ' Не имеет значения, что мы отбрасываем константы.

Тем не менее, эти константы абсолютно значимы! Функция с временем выполнения 10 ¹⁰⁰ n будет намного медленнее, чем функция с временем выполнения просто n. Функция с временем выполнения n ^2/2 будет быстрее, чем функция с временем выполнения просто n ². Тот факт, что первые две функции - это O (n), а вторые две - O (n ²), не меняет того факта, что они не выполняются в одно и то же время, поскольку это не то, что обозначение big-O предназначен для. O-запись хороша для определения того, будет ли в долгосрочной перспективе одна функция больше другой. Даже если 10 ¹⁰⁰ п является колоссально огромное значение для любого п> 0, то функция О (п), и поэтому для достаточно больших п в конце концов, он будет бить функцию, во время выполнения равно п ^2/2 потому что функция O (N ²).

Таким образом, поскольку big-O говорит только об относительных классах темпов роста, он игнорирует постоянный фактор. Однако эти константы абсолютно значимы; они просто не имеют отношения к асимптотическому анализу.

Надеюсь это поможет!

Ответ 2

Обозначение 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 для небольших проблемных размеров на многих машинах.

Ответ 3

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

Но даже для разных классов 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.

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

Ответ 4

Для анализа алгоритмов достаточно большого O без константы.

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

Во-вторых, Big O в основном используется для измерения того, как время работы увеличится по мере увеличения проблемы или уменьшения времени выполнения при улучшении производительности аппаратного обеспечения.

В-третьих, для ситуаций с высокой эффективностью оптимизации также будет учитываться постоянная.

Ответ 5

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

Предположим, что мы хотим умножить 2 матрицы размера 10 * 10, у нас не будет проблемы , если мы не хотим делать эту операцию несколько раз, а затем роль асимптотические обозначения становятся преобладающими, и когда значение n становится очень большим, константы на самом деле не имеют никакого отношения к ответу и почти незначительны, поэтому мы склонны оставлять их при вычислении сложность.

Ответ 6

Обозначение Big O чаще всего используется для описания времени выполнения алгоритма. В этом контексте я бы сказал, что конкретные значения констант по сути не имеют смысла. Представьте себе следующий разговор:

Алиса: Каково время работы вашего алгоритма?

Боб: 7n ²

Алиса: Что вы подразумеваете под 7n ²?

Какие подразделения? Микросекунды? Миллисекунды? Наносекунд?
На каком процессоре вы его используете? Intel i9-9900K? Qualcomm Snapdragon 845? (Или вы используете GPU, FPGA или другое оборудование?)
Какой тип оперативной памяти вы используете?
На каком языке программирования вы реализовали алгоритм? Какой исходный код?
Какой компилятор/ВМ вы используете? Какие флаги вы передаете компилятору/ВМ?
Какая операционная система?
и т.п.

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

Теперь можно указать постоянный коэффициент при описании количества операций (соответственно определенных) или инструкций ЦП, которые выполняет алгоритм, количества сравнений, выполняемых алгоритмом сортировки, и так далее. Но, как правило, нас действительно интересует время работы.

Ничто из этого не означает, что реальные характеристики алгоритма не важны. Например, если вам нужен алгоритм для умножения матриц, алгоритм Копперсмита-Винограда не рекомендуется. Это правда, что этот алгоритм занимает O (n ^2,337) времени, тогда как алгоритм Штрассена, его самый сильный конкурент, занимает O (n ^2,808) времени. Однако, согласно Wikipedia, Coppersmith-Winograd работает медленно, и "это дает преимущество только для матриц, настолько больших, что они не могут быть обработаны современным оборудованием". Обычно это объясняется тем, что постоянный коэффициент для Копперсмита-Винограда очень велик. Но, повторюсь, если мы говорим о времени работы Копперсмита-Винограда, не имеет смысла давать конкретное число для постоянного фактора.

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