«Для малых значений n O (n) можно рассматривать как O (1)»

26

Я слышал несколько раз, что при достаточно малых значениях n O (n) можно рассматривать / обрабатывать так, как будто это O (1).

Пример :

Мотивация для этого основана на неверной идее, что O (1) всегда лучше, чем O (lg n), всегда лучше, чем O (n). Асимптотический порядок операции имеет значение только в том случае, если в реальных условиях размер проблемы действительно становится большим. Если n остается маленьким, то каждая проблема - O (1)!

Что достаточно мало? 10? 100? 1000? В какой момент вы говорите: «мы больше не можем рассматривать это как бесплатную операцию»? Есть ли эмпирическое правило?

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

rianjs
источник
4
Эмпирическое правило зависит от того, какую проблему вы хотите решить. Быть быстрым на встраиваемых системах с N100 ? Опубликовать в теории сложности?
Рафаэль
3
Думая об этом больше, кажется, что в принципе невозможно придумать одно правило, потому что требования к производительности определяются вашим доменом и его бизнес-требованиями. В средах без ограничений n может быть довольно большим. В жестких условиях окружающей среды он может быть довольно маленьким. Это кажется очевидным теперь в ретроспективе.
rianjs
12
@rianjs Вы , кажется, ошибочно принимая O(1)за бесплатно . Причина первых нескольких предложений заключается в том, что O(1)это константа , которая иногда может быть безумно медленной. Расчет, который занимает тысячу миллиардов лет независимо от ввода, является O(1)расчетом.
Mooing Duck
1
Смежный вопрос о том, почему мы используем асимптотику в первую очередь.
Рафаэль
3
@rianjs: будьте в курсе шуток по линии «пятиугольник - это примерно круг, для достаточно больших значений 5». Предложение, о котором вы спрашиваете, имеет смысл, но, поскольку оно вызвало у вас некоторую путаницу, возможно, стоит спросить Эрика Липперта, в какой степени этот точный выбор фраз был для юмористического эффекта. Он мог бы сказать: «если существует какая-либо верхняя граница для то каждая проблема есть O ( 1 ) », и все равно он был математически корректен. «Малый» не является частью математики. NО(1)
Стив Джессоп

Ответы:

21

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

Вот визуальный способ думать об этом.

введите описание изображения здесь

У всех есть постоянная запуска, которая определяет их начальную точку на оси Y. У каждого также есть критическая постоянная определяющая, насколько быстро они будут увеличиваться.С

  • Для , С определяет время.О(1)С
  • действительно C × n , где C определяет угол.О(N)С×NС
  • действительно ( C × n ) 2 , где C определяет резкость кривой.О(N2)(С×N)2С

Чтобы определить, какой алгоритм вы должны использовать, вам нужно оценить место пересечения времени выполнения. Например, решение с высоким временем запуска или высоким C будет проигрывать решению O ( n ) с низким временем запуска и низким C при довольно большом количестве элементов.О(1)СО(N)С

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

Вот пример CS. Допустим, вам нужен список, который всегда сортируется. Вы можете использовать дерево, которое будет держать себя в порядке для . Или вы можете использовать несортированный список и выполнять повторную сортировку после каждой вставки или удаления в O ( n log n ) . Поскольку операции с деревьями сложны (у них высокая константа), а сортировка очень проста (низкая константа), список, скорее всего, выиграет сотни или тысячи элементов.О(журналN)О(NжурналN)

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

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

Schwern
источник
Бессмысленно говорить . То , что вы на самом деле означает, что если время работы составляет T = O ( 1 ) , то (во многих случаях) T C . Если T = O ( n ), то во многих случаях T C n или, более формально, T = C n + o ( n ) . И так далее. Обратите внимание, однако, что в других случаях константа C меняется сO(1)=O(C)T=O(1)TСT=О(N)TСNTзнак равноСN+о(N)С , в определенных пределах. N
Юваль Фильмус
@YuvalFilmus Вот почему мне нравятся графики.
Шверн
На сегодняшний день это лучший ответ, вопрос в том, насколько быстро растет функция.
Рикардо
1
Хороший график, но оси действительно должны быть помечены как «время», а не «скорость». Y
Ильмари Каронен
1
Является ли линия действительно параболой? Это выглядит очень плоским для маленьких n и очень крутым для больших n . О(N2)NN
Дэвид Ричерби
44

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

Показательно, что в этом вопросе обсуждаются «достаточно малые значения n ». Весь смысл Big-O состоит в том, чтобы описать, как обработка растет в зависимости от того, что обрабатывается. Если обрабатываемые данные остаются небольшими, обсуждать Big-O не имеет значения, потому что вас не интересует рост (чего не происходит).

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

Для малых n используйте все, что вам удобно.

Если вы отправляетесь в поездку по пересеченной местности, вам нужно найти способы оптимизировать свое вождение, пробег и т. Д.

Эрик Хьюз
источник
5
«Для маленьких п, используйте все, что вам удобно». - если вы часто выполняете операцию , выберите самый быстрый (для вашего ). Смотрите также здесь . N
Рафаэль
4
Отличная метафора!
Evorlor
1
С чисто математической точки зрения асимптотическая сложность ничего не говорит вам, когда n < infinity.
Гордон Густафсон
15

Цитата довольно расплывчатая и неточная. Есть как минимум три взаимосвязанных способа интерпретации.

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

Более практичное дело, что, когда мы говорим , что время работы алгоритма является , это означает только то , что она асимптотически с п 2  шага, для некоторой константы  C . То есть существует некоторая константа n 0 такая, что для всех n n 0 алгоритм выполняет примерно c n 2 шагов. Но возможноΘ(n2) cn2Cn0nn0cn2N0знак равно100,000,000и вы заинтересованы только в случаях размера гораздо меньше, чем это. Асимптотическая квадратичная граница может даже не относиться к вашим маленьким экземплярам. Вам может повезти, и это может быть быстрее на небольших входах (или вам может не повезти, и это будет медленнее). Например, для малых  , n 2 < 1000 n, поэтому вам лучше запустить квадратичный алгоритм с хорошими константами, чем линейный алгоритм с плохими константами. Реальный пример этого - асимптотически наиболее эффективные алгоритмы умножения матриц (варианты Копперсмита-Винограда , работающие во времени O (NN2<1000N ) редко используются на практике, потомучто O ШтрассенаО(N2,3729) алгоритм работает быстрее, если ваши матрицы не очень большие.О(N2,8074)

Третий момент заключается в том, что, если  мало, n 2 и даже n 3  малы. Например, если вам нужно отсортировать несколько тысяч элементов данных, и вам нужно отсортировать их только один раз, любой алгоритм сортировки достаточно хорош:NN2N3Θ(N2)Алгоритму все еще потребуется несколько десятков миллионов инструкций для сортировки ваших данных, что совсем немного времени на процессоре, который может выполнять миллиарды инструкций в секунду. Хорошо, есть и доступ к памяти, но даже медленный алгоритм займет меньше секунды, поэтому, вероятно, лучше использовать простой, медленный алгоритм и понять его правильно, чем использовать сложный, быстрый алгоритм и обнаружить, что он молниеносный но глючит и не сортирует данные должным образом.

Дэвид Ричерби
источник
4
В то время как совершенно правильные и действительные пункты, я думаю, что вы упустили момент. Кажется, они имели в виду, что иногда алгоритм с работает лучше, чем алгоритм с O ( 1 ) , для достаточно малых n s. Это происходит, например, когда первый имеет время выполнения 10 n + 50 , а второй работает в момент времени 100000 . Тогда для достаточно малых n на самом деле быстрее использовать протокол O ( n ) . О(N)О(1)N10N+50100000NО(N)
Ран Г.
@RanG. Разве это не подпадает под мой второй случай? (Особенно, если я отредактирую это так, чтобы сказать что-то вроде «Линейный алгоритм с хорошими константами мог бы превзойти алгоритм константы / логарифмический с плохими константами»?)
Дэвид Ричерби
1
Было бы хорошо явно упомянуть о важности констант, когда n мало. Это то, что, вероятно, не придет в голову тому, кто не слышал этого раньше.
Роб Уоттс
9

Нотация Big-O действительно только говорит о поведении для произвольного большого n. Например, означает, что существует константа c> 0 и целое число n 0, такое что f ( n ) < c n 2 для каждого n >f(n)=O(n2)n0f(n)<cn2 .n>n0

Во многих случаях вы можете найти константу c и сказать: «Для каждого n> 0 f (n) приблизительно равно ». Какая полезная информация иметь. Но в некоторых случаях это не так. Если f (n) = n 2 + 10 18 , то это полностью вводит в заблуждение. Так что если что-то есть O (n ^ 2), это не значит, что вы можете отключить свой мозг и игнорировать реальную функцию.сN2N2+1018

С другой стороны, если вы когда-либо сталкиваетесь только со значениями n = 1, 2 и 3, то на практике это не имеет значения, что делает f (n) при n ≥ 4, так что вы могли бы также подумать, что f ( n) = O (1), с c = max (f (1), f (2), f (3)). И это то, что достаточно мало означает: если утверждение, что f (n) = O (1) не вводит вас в заблуждение, если единственные значения f (n), с которыми вы сталкиваетесь, «достаточно малы».

gnasher729
источник
5

Если это не растет, это O (1)

Заявление автора несколько аксиоматично.

Порядок роста описывает то, что происходит с объемом работы, которую вы должны выполнять по мере Nувеличения. Если вы знаете, что Nэто не увеличивается, ваша проблема эффективно O(1).

Помните, что O(1)это не значит «быстро». Алгоритм , который всегда требует 1 триллион шагов к полон, O(1). Алгоритм, который занимает от 1 до 200 шагов, но никогда больше O(1). [1]

Если ваш алгоритм выполняет в точности N ^ 3шаги, и вы знаете, что он Nне может быть больше 5, он никогда не может делать более 125 шагов, поэтому он эффективноO(1) .

Но опять же, O(1)не обязательно означает «достаточно быстро». Это отдельный вопрос, который зависит от вашего контекста. Если на завершение чего-то уходит неделя, вам, вероятно, все равно, технически ли это O(1).


[1] Например, поиск в хэше есть O(1), хотя коллизии хэшей означают, что вам, возможно, придется просматривать несколько элементов в одном ведре, если существует жесткое ограничение на количество элементов в этом ведре.

Натан Лонг
источник
1
Все это звучит правильно, за исключением следующего: «Если ваш алгоритм выполняет ровно N ^ 3 шагов, и вы знаете, что N не может быть больше 5, он никогда не может делать больше 125 шагов, поэтому это O (1)». , Опять же, если алгоритм принимает целое число, и моя максимальная целочисленная поддержка равна 32767, это O (1)? Очевидно нет. Big-O не меняется в зависимости от ограничений параметров. Это O (n), даже если вы знаете, что 0 <n <3, потому что n = 2 занимает вдвое больше времени, чем n = 1.
JSobell
3
@JSobell Но это O (1). Если есть ограничение, ограничивающее n для f (n), это означает, что оно не может расти бесконечно. Если ваш n ограничен 2 ^ 15, то ваша замечательная функция n ^ 2 на самом деле g(n) = min(f(2^15), f(n))- что в O (1). При этом константы на практике имеют большое значение, и ясно, что n может стать достаточно большим, чтобы был полезен асимптотический анализ.
Во
2
@JSobell Это похоже на вопрос о том, действительно ли компьютеры «завершены по Тьюрингу», учитывая, что они технически не могут иметь бесконечное пространство для хранения. Технически, математически, компьютер не является «настоящей» машиной Тьюринга. На практике нет такой вещи, как «бесконечная лента», но жесткие диски подходят достаточно близко.
Кайл Стрэнд
Несколько лет назад я написал систему финансового риска, в которой использовалось n ^ 5 матричных манипуляций, поэтому практический предел составлял n = 20, прежде чем ресурсы стали проблемой.
JSobell
Извините, нажал Enter слишком рано. Несколько лет назад я написал систему финансового риска, в которой использовалось n ^ 5 матричных манипуляций, поэтому практический предел составлял n = 20, прежде чем ресурсы стали проблемой. Согласно этой ошибочной логике, созданная функция имеет значение O (1), потому что у меня есть предел 20. Когда клиент говорит: «Хм, возможно, нам следует переместить его до 40 как предел ... Да, алгоритм O (1). ) так что это не проблема "... Вот почему границы на входе не имеют смысла. Функция была O (n ^ 5), а не O (1), и это практический пример того, почему Big-O не зависит от границ.
JSobell
2

Теперь я могу использовать хеш-таблицу и иметь O (1) поисков (оставляя в стороне конкретную реализацию хеш-таблицы), но если бы у меня был, например, список, я бы имел O (n) поисков. Учитывая эту аксиому, эти два одинаковы, если коллекции достаточно малы. Но в какой-то момент они расходятся ... что это за точка?

Практически, это тот момент, когда создание хеш-таблицы занимает больше, чем вы получаете выгоду от улучшенного поиска. Это будет сильно зависеть от того, как часто вы выполняете поиск по сравнению с тем, как часто вы делаете другие вещи. O (1) против O (10) не имеет большого значения, если вы сделаете это один раз. Если вы делаете это тысячи раз в секунду, даже это имеет значение (хотя, по крайней мере, это имеет значение с линейно возрастающей скоростью).

Telastyn
источник
Если вы хотите быть уверены, проведите несколько экспериментов, чтобы увидеть, какая структура данных лучше подходит для ваших параметров.
Юваль Фильмус
@Telastyn Yuval Filmus прав, если вы действительно хотите быть уверены. Я знаю человека по имени Джим, его параметры в порядке. Но он не слушал таких советов, как Юваль. Вы должны действительно слушать Ювала, чтобы быть уверенным и безопасным.
ИнформированоA
2

Хотя цитата верна (но неопределенна), есть и опасности для нее. Имо, вы должны смотреть на сложность на любом этапе вашего приложения.

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

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

(обратите внимание, это все еще небольшой сценарий списка.)

Спустя 3 года я пришел, и мой босс только что сделал большие продажи: наше программное обеспечение будет использоваться крупным национальным ритейлером. Раньше мы обслуживали только небольшие магазины. И теперь мой начальник ругается и ругается, почему программное обеспечение, которое всегда "работало нормально", теперь так ужасно медленно.

Оказывается, этот список был списком клиентов, и у наших клиентов было около 100 клиентов, поэтому никто не заметил. Операция заполнения списка была в основном операцией O (1), потому что она занимала менее миллисекунды. Ну, не так много, когда к нему нужно добавить 10.000 клиентов.

И спустя годы после первоначального плохого решения O (1), компания почти потеряла крупного клиента. Все из-за одной маленькой ошибки дизайна / предположения за годы до этого.

Питер Б
источник
Но это также иллюстрирует важную особенность многих реальных систем: «алгоритмы», которые вы изучаете как студент, на самом деле являются частями, из которых сделаны настоящие «алгоритмы». На это обычно намекают; например, большинству людей известно, что быстрая сортировка часто пишется для возврата к сортировке вставкой, когда разделы становятся достаточно маленькими, и что двоичный поиск часто пишется для возврата к линейному поиску. Но не многие люди понимают, что сортировка слиянием может извлечь пользу из некоторого бинарного поиска.
псевдоним
1

Мотивация для этого основана на неверной идее, что O (1) всегда лучше, чем O (lg n), всегда лучше, чем O (n). Асимптотический порядок операции имеет значение только в том случае, если в реальных условиях размер проблемы действительно становится большим.

Если у меня есть два алгоритма с этими временами:

  • журнал (п) +10000
  • п + 1

Тогда существует некоторая точка, где они пересекаются. При nменьших значениях «линейный» алгоритм работает быстрее, а при nбольших - «логарифмический» алгоритм работает быстрее. Многие люди ошибаются, полагая, что логарифмический алгоритм работает быстрее, но для маленьких nэто не так.

Если n остается маленьким, то каждая проблема - O (1)!

Я предполагаю, что здесь подразумевается, что если nограничено, то каждая проблема - это O (1). Например, если мы сортируем целые числа, мы можем выбрать быструю сортировку. O(n*log(n))очевидно. Но если мы решим, что не может быть больше 2^64=1.8446744e+19целых чисел, то мы знаем, что n*log(n)<= 1.8446744e+19*log(1.8446744e+19)<= 1.1805916e+21. Поэтому алгоритм всегда будет занимать меньше 1.1805916e+21«единиц времени». Поскольку это постоянное время, мы можем сказать, что алгоритм всегда можно выполнить в это постоянное время -> O(1). (Обратите внимание, что даже если эти единицы времени являются наносекундами, это в общей сложности более 37411 лет). Но все же O(1).

Мытье утка
источник
0

Я подозреваю, что во многих из этих ответов отсутствует фундаментальная концепция. O (1): O (n) - это не то же самое, что f (1): f (n), где f - та же самая функция, потому что O не представляет единственную функцию. Даже хороший график Шверна недействителен, потому что он имеет одинаковую ось Y для всех линий. Чтобы все использовать одну и ту же ось, линии должны были быть fn1, fn2 и fn3, где каждая из них была функцией, производительность которой можно было напрямую сравнить с другими.

Я слышал несколько раз, что при достаточно малых значениях n O (n) можно рассматривать / рассматривать так, как будто это O (1)

Хорошо, если n = 1, они точно такие же? Нет. Функция, допускающая переменное число итераций, не имеет ничего общего с той, которая этого не делает, нотации big-O это не важно, и мы не должны.

Нотация Big-O просто предназначена для выражения того, что происходит, когда у нас есть итеративный процесс, и как производительность (время или ресурсы) будет ухудшаться по мере увеличения n.

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

Вот аналогичный вопрос: если я перебираю последовательность символов и знаю, что в общем случае мои строки будут содержать менее 10 символов, могу ли я сказать, что это эквивалент O (1), но если мои строки были длиннее, то я сказал бы, что это был O (n)?

Нет, потому что строка из 10 символов занимает в 10 раз больше строки из 1 символа, но в 100 раз меньше, чем строка из 1000 символов! Это O (n).

JSobell
источник
О(1)е(я)яМаксимум{е(0),...,е(10)}О(1)
Да, и это пример того, как нотация Big-O обычно неправильно понимается. Согласно вашему аргументу, если я знаю, что максимальное значение n равно 1 000 000, то моя функция равна O (1). На самом деле моя функция может быть в лучшем случае O (1), а в худшем - O (n). Эта нотация используется для описания алгоритмической сложности, а не для конкретной реализации, и мы всегда используем самую дорогую для описания сценария, а не лучшую. Фактически, по вашему аргументу, каждая функция, которая допускает n <2, является O (1)! :)
JSobell
N<2О(1)е(N)е(10)NО(1)
Извините, но если вы говорите, что знание верхних границ n делает функцию O (1), то вы говорите, что представление обозначений напрямую связано со значением n, а это не так. Все остальное, что вы упоминаете, является правильным, но предположить, что, поскольку n имеет границы, O (1) неверно. На практике есть места, где то, что вы описываете, может быть наблюдаемым, но мы смотрим здесь на нотацию Big-O, а не на функциональное кодирование. Итак, еще раз, почему вы предлагаете, чтобы n с максимумом 10 сделало бы это O (1)? Почему 10? Почему не 65535 или 2 ^ 64?
JSobell
Сказав это, если вы напишите функцию, которая дополняет строку до 10 символов, то всегда будет
циклически повторять
0

Я считаю, что текст, который вы цитировали, довольно неточен (использование слова «лучше» обычно бессмысленно, если вы не предоставите контекст: с точки зрения времени, пространства и т. Д.) В любом случае, я считаю, что самым простым объяснением было бы:

О(1)О(1)

Теперь давайте возьмем сравнительно небольшой набор из 10 элементов и несколько алгоритмов для его сортировки (просто пример). Давайте предположим, что мы сохраняем элементы в структуре, которая также предоставляет нам алгоритм, способный сортировать элементы за постоянное время. Допустим, наши алгоритмы сортировки могут иметь следующие сложности (с обозначением big-O):

  1. О(1)
  2. О(N)
  3. О(NLог(N))
  4. О(N2)

О(1)

Теперь давайте «раскроем» истинные сложности упомянутых выше алгоритмов сортировки (где «истина» означает не скрывать константу), представленную количеством шагов, необходимых для завершения (и предположим, что все шаги занимают одинаковое количество времени):

  1. 200
  2. 11N
  3. 4NLог(N)
  4. 1N2

Если наш вход имеет размер 10, то это точное количество шагов для каждого алгоритма, упомянутого выше:

  1. 200
  2. 11×10знак равно110
  3. 4×10×3,32134
  4. 1×100знак равно100

О(N2)О(1),О(N)О(NLог(N))О(N2)О(1)О(N2)О(1)

3yakuya
источник