Обоснование пренебрежения постоянными факторами в Big O

Много раз, если сложности имеют константы, такие как 3n, мы пренебрегаем этой константой и говорим O (n), а не O (3n). Я не могу понять, как мы можем пренебречь такими трехкратными изменениями? Некоторые вещи меняются в 3 раза быстрее, чем другие! Почему мы пренебрегаем этим фактом?

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

Например, мы говорим, что функция, которая выполняет шагов, равна O ( n ) , потому что, грубо говоря, для достаточно больших входных данных удвоение размера входных данных не более чем удвоит количество предпринятых шагов. Точно так же O ( n 2 ) означает, что удвоение входного размера увеличит не более четырехкратного числа шагов, а O ( log n ) означает, что удвоение входного размера увеличит количество шагов не более чем на некоторую постоянную.$3n$$O(n)$$O(n^2)$$O(\log n)$

Это инструмент для определения того, какие алгоритмы лучше масштабируются, а не какие быстрее.

Во-первых, как уже объясняли другие ответы, , или, если выразить это словами, функция есть O ( 3 n ) тогда и только тогда, когда она есть O ( n ) . е = О ( 3 л ) означает , что существует точка Н и фактор С 3 таким образом, что для всех п ≥ N , F ( п ) ≤ C 3 ⋅ $O(3n) = O(n)$$O(3n)$$O(n)$$f = O(3n)$$N$$C_3$$n \ge N$ . Теперь выберите C 1 = 3 C 3 : для всех n ≥ N , f ( n ) ≤ C 1 ⋅ n , поэтому f = O ( n ) . Доказательство обратного аналогично.$f(n) \le C_3 \cdot 3n$$C_1 = 3 C_3$$n \ge N$$f(n) \le C_1 \cdot n$$f = O(n)$

Теперь о причине, почему это правильный инструмент. Заметьте, что когда мы измеряем сложность алгоритма, мы не даем единицу. Мы не считаем секунды или машинные инструкции: мы подсчитываем некоторые неуказанные элементарные шаги, каждый из которых занимает ограниченное время. Мы делаем это потому, что выполнение одного и того же алгоритма на другой машине изменит время, необходимое для каждой инструкции - умножим тактовую частоту на и время выполнения перейдет от f ( n ) к f ( n ) /$3$$f(n)$$f(n)/3$, Если мы реализуем один и тот же алгоритм на другом языке или в другой системе, время, затрачиваемое на каждый элементарный шаг, может быть разным, но опять же, это слишком много деталей: нас вряд ли когда-нибудь будут волновать такие различия.

Когда вы заботитесь о точном времени, асимптотическая сложность не имеет значения: асимптотическая сложность говорит вам, что происходит с очень большими входными размерами, которые могут быть или не быть фактическими входными размерами, с которыми вы имеете дело.

Напомним определение Big-O:

если существует c > 0 такое, что f ( n ) ≤ c g ( n ) для всех n .$f(n)\in O(g(n))$$c>0$$f(n)\le cg(n)$$n$

Согласно этому определению имеем, что для любой константы d . Цель обозначения O состоит именно в том, чтобы упростить выражения таким образом. Действительно, 3 n растет в 3 раза быстрее, чем n , но оба они линейны. Оправдано это или нет - это зависит от контекста. Но если вы согласны использовать обозначение O , то по определению это верно.$dn\in O(n)$$d$$O$$3n$$n$$O$

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

В двух словах: обозначение Big O является относительным типом измерения без единиц измерения (в отличие от абсолютного измерения). Он может измерять только изменение производительности, но не абсолютную производительность, для которой константы имеют большое значение. Преимущество состоит в том, что это делает его в значительной степени независимым от реализации, позволяя более простой анализ, который может игнорировать относительные затраты на элементарные операции, если эти затраты имеют положительные фиксированные верхние и нижние границы. Но следствием этого является то, что постоянные факторы не имеют смысла . Тем не менее, даже по своему прямому назначению анализ асимптотической сложности может быть поставлен под сомнение на других основаниях и должен рассматриваться с осторожностью. Например, необработанный размер ввода может быть неправильным параметром для рассмотрения.

Первое замечание: ваш вопрос не совсем точно сформулирован. Когда вы пренебрегаете константой в 3 n , действительно происходит «трехкратное изменение», но оба изменяются с одинаковой скоростью, и вы не можете утверждать, что «[одна] вещь меняется в 3 раза быстрее, чем другая».$3$$3n$

Хорошая причина игнорировать константу в обозначениях Ландау в том, что у нас нет единицы, на которую мы можем положиться. Когда кто-то заявляет, что А живет вдвое дальше от вас, чем Б, это имеет значение независимо от какой-либо единицы. Мы можем договориться об этом, даже если вы измеряете расстояния в дюймах, а я делаю это в световых годах. Но измерение абсолютного расстояния требует указания единиц измерения, а его числовая формулировка зависит от выбранной единицы измерения.

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

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

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

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

$O(n^6)$алгоритм, используемый для ML, который имеет экспоненциальную сложность в худшем случае. Но это, похоже, не беспокоит пользователей ML и не мешает написанию очень больших программ на ML. Здесь важна не только константа. На самом деле, асимптотический анализ связывает меру стоимости вычислений с некоторой мерой сложности входных данных. Но необработанный размер не может быть правильной мерой.

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

$O(n)=O(3n)$

$n$$3n$

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

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

$f(n)=O(g(n))$$\limsup\limits_{n\to\infty} \frac{f(n)}{g(n)}<+\infty$

$g(n)=n$$g(n)=3n$

$O(n^2)=O(.00005321n^2+1000000000n+10^{46803})$$f$$=$

Позвольте мне объяснить вам просто. Давайте возьмем n = 100000. Теперь, что такое 3n? Это 300000 ( да, это в 3 раза больше n ) Но что такое n ^ 2 ? 10000000000 . ( это 1 lakh сгибов n ) .. Сравните n ^ 2 с n. 3 ничтожно мало, если сравнивать с 1 лакх. Итак, мы можем удалить это.

Подумайте, если n несколько миллиардов или триллионов. В этом случае снова мы собираемся сравнить 3 с несколькими миллиардами или триллионами. Теперь вы знаете, почему мы можем пренебречь 3.