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

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

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

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

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

• родственник: можно только сравнить яблоки с яблоками. Вы не можете сравнить алгоритм, чтобы сделать арифметическое умножение к алгоритму, который сортирует список целых чисел. Но сравнение двух алгоритмов, чтобы сделать арифметические операции (одно умножение, одно дополнение) скажут Вам что-то значимое;
• представление: большой-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 добавляет. Для два один миллион чисел цифры мы должны сделать один триллион ⁽¹⁰¹²⁾, умножение и два миллиона добавляет.

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

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

Проницательное, возможно, поняло, что мы могли выразить количество операций как: ⁿ² + 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 ⁽²ⁿ²⁾ и O ^(100n2) тихи оба O ⁽ⁿ²⁾.

Стоит в этой точке объяснить, что Большой 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 ⁽ⁿ²⁾ и т.д. все полиномиальное время. Некоторые проблемы не могут быть решены в полиномиальное время. Определенные вещи используются в мире из-за этого. Шифрование с открытым ключом является главным примером. В вычислительном отношении трудно найти два простых множителя очень большого количества. Если бы это не было, то мы не могли бы использовать системы с открытым ключом, которые мы используем.

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