Что такое простое английское объяснение обозначения «Big O»?

^[0-9]+(\.([0-9]{1,2})?)?$

Будет делать такие вещи, как 12.. Это не то, что принято, но если в случае, если вам нужно быть «гибким», это один из способов. И, конечно, [0-9] можно заменить на \d, но я думаю, что это более читаемо.

4797
задан Steve Chambers 22 July 2016 в 15:40
поделиться

8 ответов

Быстрое примечание, это почти наверняка путает Большую нотацию O (который является верхней границей) с нотацией Теты "Θ" (который, связанный с двумя сторонами). По моему опыту, это на самом деле типично для обсуждений в неакадемических настройках. Извинения за любой беспорядок вызываются.


Большая сложность O может визуализироваться с этим графиком:

Big O Analysis

Самое простое определение, которое я могу дать для Нотации "большого О", является этим:

Нотация "большого О" является относительным представлением сложности алгоритма.

В том предложении существуют некоторые важные и сознательно выбранные слова:

  • родственник: можно только сравнить яблоки с яблоками. Вы не можете сравнить алгоритм, чтобы сделать арифметическое умножение к алгоритму, который сортирует список целых чисел. Но сравнение двух алгоритмов, чтобы сделать арифметические операции (одно умножение, одно дополнение) скажут Вам что-то значимое;
  • представление: большой-O (в его самой простой форме) уменьшает сравнение между алгоритмами к единственной переменной. Та переменная выбрана на основе наблюдений или предположений. Например, сортирующие алгоритмы обычно сравниваются на основе операций сравнения (сравнение двух узлов для определения их родственника, заказывающего). Это предполагает, что сравнение является дорогим. Но что, если сравнение является дешевым, но свопинг является дорогим? Это изменяет сравнение; и
  • сложность: если мне требуется одна секунда для сортировки 10 000 элементов, сколько времени это возьмет меня для сортировки один миллион? Сложность в этом экземпляре является относительной мерой к чему-то еще.

Возвратитесь и перечитайте вышеупомянутое при чтении остальных.

Лучший пример Больших-O, о которых я могу думать, делает арифметику. Возьмите два числа (123456 и 789012). Основные арифметические операции, которые мы изучили в школе, были:

  • дополнение;
  • вычитание;
  • умножение; и
  • подразделение.

Каждый из них является операцией или проблемой. Метод решения их называют алгоритмом.

Дополнение является самым простым. Вы выстраиваете в линию числа (направо) и добавляете цифры в столбце, пишущий последнее количество того дополнения в результате. Часть 'десятков' того числа перенесена на следующий столбец.

Давайте предположим, что добавление этих чисел является самой дорогой операцией в этом алгоритме. Это выдерживает обосновать, что для добавления этих двух чисел вместе мы должны добавить вместе 6 цифр (и возможно нести 7-е). Если мы добавляем два 100 чисел цифры вместе, мы должны сделать 100 дополнений. Если мы добавляем два 10 000 чисел цифры, мы должны сделать 10 000 дополнений.

Видеть шаблон? Сложность (являющийся количеством операций) прямо пропорциональна к количеству цифр n в большем числе. Мы называем этот O (n) или линейная сложность.

Вычитание подобно (кроме Вас, возможно, должен одолжить вместо переноса).

Умножение отличается. Вы выстраиваете в линию числа, берете первую цифру в нижнем числе и умножаете его в свою очередь против каждой цифры в главном числе и так далее через каждую цифру. Таким образом для умножения наш два 6 чисел цифры мы должны сделать 36 умножения. Мы, возможно, должны сделать, целых 10 или 11 столбцов добавляют для получения конечного результата также.

Если у нас есть два 100-разрядных числа, мы должны сделать, 10 000 умножения и 200 добавляет. Для два один миллион чисел цифры мы должны сделать один триллион (1012), умножение и два миллиона добавляет.

Поскольку алгоритм масштабируется с n-squared, это - O (n2) или квадратичная сложность. Это - хорошее время для представления другого важного понятия:

Мы только заботимся о старшей значащей части сложности.

Проницательное, возможно, поняло, что мы могли выразить количество операций как: n2 + 2n. Но поскольку Вы видели от нашего примера с двумя числами миллиона цифр за штуку, второй срок (2n) становится незначительным (составление 0,0002% общих операций тем этапом).

Можно заметить, что мы приняли худший вариант развития событий здесь. В то время как умножение 6 чисел цифры, если у одного из них есть 4 цифры и другая, имеет 6 цифр, то у нас только есть 24 умножения. Однако, мы вычисляем худший вариант развития событий для этого 'n', т.е. когда оба - 6 чисел цифры. Следовательно Нотация "большого О" о Худшем варианте алгоритма.

Телефонная книга

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

Теперь, если Вы давали компьютеру команду искать номер телефона для "John Smith" в телефонной книге, которая содержит 1 000 000 имен, что Вы сделали бы? Игнорирование того, что Вы могли предположить, как далеко в запущенном S (позволяют нам принять Вас, не может), что Вы сделали бы?

Типичная реализация могла бы быть должна открыться до середины, взять 500,000-е и сравнить его с "Smith". Если это, оказывается, "Smith, John", мы просто вернулись к реальности удачливые. Намного более вероятно то, что "John Smith" будет прежде или после того имени. Если это - после того, как мы затем разделим последнюю половину телефонной книги в половине и повторении. Если это к тому времени, мы делим первую половину телефонной книги в половине и повторении. И так далее.

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

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

  • Для телефонной книги 3 имен требуется 2 сравнения (самое большее).
  • Для 7 это берет самое большее 3.
  • Для 15 это берет 4.
  • Для 1,000,000 это берет 20.

Это потрясающе хорошо не так ли?

В Больших-O терминах это - O (зарегистрируйте n), или логарифмическая сложность. Теперь рассматриваемый логарифм мог быть ln (основывайте e), log10, log2 или некоторая другая основа. Не имеет значения, что это все еще O (зарегистрируйте n) точно так же, как O (2n2) и O (100n2) тихи оба O (n2).

Стоит в этой точке объяснить, что Большой O может использоваться для определения трех случаев с алгоритмом:

  • Лучший Случай: В телефонном поиске книги лучший случай - то, что мы находим имя в одном сравнении. Это - O (1) или постоянная сложность;
  • Ожидаемый Случай: Как обсуждено выше этого O (зарегистрируйте n); и
  • Худший Случай: Это также O (зарегистрируйте n).

Обычно мы не заботимся о лучшем случае. Мы интересуемся ожидаемым и худшим случаем. Иногда один или другие из них будет более важным.

Назад к телефонной книге.

Что, если Вы имеете номер телефона и хотите найти имя? У полиции есть обратная телефонная книга, но такие поиски отклонены широкой публике. Или они? Технически можно инвертировать поиск число в книге обычного телефона. Как?

Вы запускаете в имени и сравниваете число. Если это - соответствие, большое, в противном случае Вы идете дальше к следующему. Необходимо сделать это этот путь, потому что телефонная книга не заказана (номером телефона так или иначе).

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

  • Лучший случай: O (1);
  • Ожидаемый случай: O (n) (для 500 000); и
  • Худший случай: O (n) (для 1,000,000).

Коммивояжер

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

Простые звуки? Думайте снова.

Если у Вас есть 3 города A, B и C с дорогами между всеми парами затем, Вы могли пойти:

  • → B → C
  • → C → B
  • B → C → A
  • B → → C
  • C → → B
  • C → B → A

Хорошо на самом деле существуют меньше, чем что, потому что некоторые из них эквивалентны (→ B → C и C → B → A эквивалентен, например, потому что они используют те же дороги, просто наоборот).

В действительности существует 3 возможности.

  • Возьмите это в 4 города, и у Вас есть (iirc) 12 возможностей.
  • С 5 это 60.
  • 6 становится 360.

Это - функция математической операции, названной факториалом. В основном:

  • 5! = 5 × 4 × 3 2 × 1 = 120
  • 6! = 6 × 5 × 4 × 3 2 × 1 = 720
  • 7! = 7 × 6 × 5 × 4 × 3 2 × 1 = 5040
  • 25! = 25 2 × 1 × 24 × … × = 15,511,210,043,330,985,984,000,000
  • 50! = 50 2 × 1 × 49 × … × = 3.04140932 × 1064

Таким образом, Большой-O из проблемы Коммивояжера является O (n!) или факториальная или комбинаторная сложность.

К тому времени, когда Вы добираетесь до 200 городов нет достаточного количества времени, оставленного во вселенной решить проблему с традиционными компьютерами.

Что-то для размышления о.

Полиномиальное время

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

O (n), O (n2) и т.д. все полиномиальное время. Некоторые проблемы не могут быть решены в полиномиальное время. Определенные вещи используются в мире из-за этого. Шифрование с открытым ключом является главным примером. В вычислительном отношении трудно найти два простых множителя очень большого количества. Если бы это не было, то мы не могли бы использовать системы с открытым ключом, которые мы используем.

Так или иначе вот именно для моего (надо надеяться, простой английский язык) объяснение Большого O (пересмотрено).

6483
ответ дан bruno 23 July 2016 в 01:40
поделиться

Это показывает, как алгоритм масштабируется.

O (n <глоток> 2 ) : известный как [1 127] Квадратичная сложность

  • 1 объект: 1 секунда
  • 10 объектов: 100 секунд
  • 100 объектов: 10 000 секунд

Уведомление, которое количество объектов увеличивает фактором 10, но увеличения времени фактором 10 <глоток> 2 . В основном, n=10 и так O (n <глоток> 2 ) дает нам масштабный коэффициент n <глоток> 2 , который является 10 <глоток> 2 .

O (n) : известный как [1 129] Линейная сложность

  • 1 объект: 1 секунда
  • 10 объектов: 10 секунд
  • 100 объектов: 100 секунд

На этот раз количество объектов увеличивается фактором 10 и время - также. n=10 и так O (n) масштабный коэффициент равняется 10.

O (1) : известный как [1 131] сложность Constant

  • 1 объект: 1 секунда
  • 10 объектов: 1 секунда
  • 100 объектов: 1 секунда

количество объектов все еще увеличивается фактором 10, но масштабный коэффициент O (1) всегда равняется 1.

O (регистрируют n) : известный как [1 133] Логарифмическая сложность

  • 1 объект: 1 секунда
  • 10 объектов: 2 секунды
  • 100 объектов: 3 секунды
  • 1 000 объектов: 4 секунды
  • 10 000 объектов: 5 секунд

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

Это - суть его. Они уменьшают математику вниз, таким образом, это не могло бы быть точно n <глоток> 2 или независимо от того, что они говорят, что это, но это будет фактором доминирования в масштабировании.

706
ответ дан chris Frisina 23 July 2016 в 01:40
поделиться

Большой O описывает верхний предел поведения роста функции, например, время выполнения программы, когда исходные данные становятся большими.

Примеры:

  • O (n): Если я удваиваю входной размер, время выполнения удваивается

  • O (n <глоток> 2 ): Если входной размер удваивается, тетрады во время выполнения

  • O (зарегистрируйте n): Если входной размер удваивает увеличения во время выполнения одним

  • O (2 <глоток> n ): Если входные увеличения размера одним, время выполнения удваивается

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

124
ответ дан starblue 23 July 2016 в 01:40
поделиться

Большой O является просто путем к "Экспрессу" самостоятельно в распространенном способе, "Сколько времени / пространство он берет для выполнения моего кода?".

можно часто видеть O (n), O (n <глоток> 2 ), O (nlogn) и т.д, все, что это просто способы показать; Как алгоритм изменяется?

O (n) означает, что Большой O является n, и теперь Вы могли бы думать, "Что является n!?" Хорошо "n" является суммой элементов. Обработка изображений Вас хочет искать Объект в Массиве. Необходимо ли было бы считать Каждый элемент и, "Действительно ли Вы - корректный элемент/объект?" в худшем случае объект в последнем индексе, что означает, что потребовалось столько же времени, сколько существуют объекты в списке, так для дженерика, мы говорим, "о, эй, n является ярмаркой, данной сумму значений!".

Таким образом Вы могли бы понять то, что "n <глоток> 2 " означает, но быть еще более конкретными, игра с мыслью у Вас есть простое, simpliest алгоритмов сортировки; bubblesort. Этот алгоритм должен просмотреть целый список для каждого объекта.

Мой список

  1. 1
  2. 6
  3. 3

поток здесь был бы:

  • Выдерживают сравнение 1 и 6, который является самым большим? Хорошо 6 находится в правильном положении, продвигаясь!
  • Выдерживают сравнение 6 и 3, о, 3 меньше! Давайте переместим это, хорошо измененный список, мы должны запустить с начала теперь!

Это - O n <глоток> 2 , потому что, необходимо посмотреть на все объекты в списке существуют "n" объекты. Для каждого объекта Вы смотрите на все объекты еще раз для сравнения, это также "n", таким образом, для каждого объекта, Вы смотрите "n" времена, означающие n*n = n <глоток> 2

, я надеюсь, что это столь просто, как Вы хотите это.

, Но помнят, Большой O является просто способом выразиться способом времени и пространства.

81
ответ дан ROMANIA_engineer 23 July 2016 в 01:40
поделиться
  • 1
    В то время как эта ссылка может ответить на вопрос, лучше включать основные части ответа здесь и предоставить ссылку для ссылки. Ответы только для ссылки могут стать недопустимыми, если связанная страница изменяется. – dgw 23 August 2012 в 00:30

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

В одном предложении: Когда размер Вашего задания повышается, насколько дольше это берет для завершения его?

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

, Вот пример, где у нас есть футболки N, которые мы хотим высушить. Мы будем принимать , это невероятно быстро для получения их в сохнущем положении (т.е. человеческое взаимодействие незначительно). Это не имеет место в реальной жизни, конечно...

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

  • Используя сушилку для белья: Вы помещаете 10 рубашек в каждую загрузку, и затем они сделаны час спустя. (Проигнорируйте фактические числа здесь — они не важны.) Настолько сохнущие 50 рубашек берет приблизительно в 5 раз более длинные, чем сушка 10 рубашек.

  • Помещение всего в сушилке: Если мы поместим все в одну большую груду и просто позволим общей теплоте сделать это, то будет требоваться много времени для средних рубашек для получения сухим. Я не хотел бы предполагать деталь, но я подозреваю, что это, по крайней мере, O (N^2) — поскольку Вы увеличиваете загрузку промывки, время высыхания увеличивается быстрее.

Один важный аспект "большого O" нотация - то, что это не делает , говорят, какой алгоритм будет быстрее для данного размера. Возьмите хеш-таблицу (строковый ключ, целочисленное значение) по сравнению с массивом пар (строка, целое число). Это быстрее для нахождения ключа в хеш-таблице или элементе в массиве, на основе строки? (т.е. для массива, "находят первый элемент, где строковая часть соответствует данному ключу".) Хеш-таблицы обычно амортизируются (~ = "в среднем") O (1) — после того как они настраиваются, это должно взять в то же время для нахождения записи в 100 таблицах записи как в 1 000 000 таблиц записи. Нахождение элемента в массиве (на основе содержания, а не индекса) линейно, т.е. O (N) — в среднем Вы оказываетесь перед необходимостью смотреть на половину записей.

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

242
ответ дан Jon Skeet 23 July 2016 в 01:40
поделиться
  • 1
    @jobano это максимум. Мне нравится macvim, но энергия от терминала еще больше! – Peter De Winter 1 June 2012 в 22:05

Большой O является мерой того, сколько времени/пространства алгоритм использует относительно размера его входа.

, Если алгоритм является O (n) затем, время/пространство увеличится на том же уровне как его вход.

, Если алгоритм является O (n <глоток> 2 ) затем, увеличение времени/пространства по курсу его входа придало квадратную форму.

и так далее.

36
ответ дан ROMANIA_engineer 23 July 2016 в 01:40
поделиться
  • 1
    Похоже, что наш случай был тем где " никакая временная таблица не является necessary" - но это похоже на наши таблицы, все еще запертые, наши открытые соединения, пронзенные, и у нас было отключение электричества 5 - 10 минут. Если мы уничтожаем запрос, который делает не , создают копию... тогда что? – B T 30 April 2010 в 05:51

Большой O описывает фундаментальную природу масштабирования алгоритма.

существует большая информация, которую Большой O не говорит Вам о данном алгоритме. Это сокращает до крайности и дает только информацию о масштабирующейся природе алгоритма, конкретно как использование ресурса (думают время или память) алгоритма масштабируется в ответ на "входной размер".

Рассматривают различие между паровым двигателем и ракетой. Они не просто различные варианты того же самого (как, скажем, механизм Prius по сравнению с механизмом Ламборгини), но они - существенно различные виды двигательных установок в их ядре. Паровой двигатель может быть быстрее, чем игрушечная ракета, но никакой паровой поршневой механизм не сможет достигнуть скоростей орбитальной ракеты-носителя. Это вызвано тем, что эти системы имеют различные характеристики масштабирования относительно отношения топлива, требуемого ("использование ресурсов") для достижения заданной скорости ("входной размер").

, Почему это настолько важно? Поскольку программное обеспечение имеет дело с проблемами, которые могут отличаться по размеру факторами до триллиона. Рассмотрите это на мгновение. Отношение между скоростью, необходимой для перемещения в Лунную и человеческую скорость обхода, является меньше, чем 10,000:1, и это является абсолютно крошечным по сравнению с диапазоном во входном программном обеспечении размеров, может стоять. И потому что программное обеспечение может стоять перед астрономическим диапазоном во входных размерах существует потенциал для Большой сложности O алгоритма, это - фундаментальная природа масштабирования, для превосхождения любых деталей реализации.

Рассматривают канонический пример сортировки. Пузырьковая сортировка является O (n <глоток> 2 ), в то время как сортировка с объединением является O (n, регистрируют n). Скажем, у Вас есть два приложения сортировки, приложение A, которое использует пузырьковую сортировку и приложение B, которое использует сортировку с объединением, и скажем, который для входных размеров приблизительно 30 приложений A элементов 1,000x быстрее, чем приложение B при сортировке. Если Вы никогда не должны сортировать намного больше чем 30 элементов затем, очевидно, что необходимо предпочесть приложение A, поскольку это намного быстрее в этих входных размерах. Однако, если Вы находите, что Вам, вероятно, придется отсортировать десять миллионов объектов затем, что Вы ожидали бы, то, что приложение B на самом деле заканчивает тем, что было тысячами времен быстрее, чем приложение A в этом случае, совершенно из-за способа, которым масштабируется каждый алгоритм.

54
ответ дан ROMANIA_engineer 23 July 2016 в 01:40
поделиться
  • 1
    Этот isn' t вполне ответ только для ссылки, @Dgw. Это содержит полное предложение, упоминая название связанного - к библиотеке, и в случае этого вопроса, название библиотеки основная часть ответа. Любой может искать его в случае, если ссылка мертва. – Rob Kennedy 11 October 2012 в 02:08

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

Когда мы говорим, что некоторый алгоритм является O(f(n)), мы имеем в виду, что время работы (или пространство, требуемое) этого алгоритма всегда меньше некоторой константы, кратной f(n).

Сказать, что двоичный поиск имеет время работы O(logn), значит сказать, что существует некоторая константа c, на которую можно умножить log(n) и которая всегда будет больше времени работы двоичного поиска. В этом случае у вас всегда будет некоторый постоянный коэффициент сравнения log(n).

Другими словами, когда g(n) - время работы вашего алгоритма, мы говорим, что g(n) = O(f(n)), когда g(n) <= c*f(n) при n > k, где c и k - некоторые константы.

26
ответ дан 22 November 2019 в 19:37
поделиться
Другие вопросы по тегам:

Похожие вопросы: