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


Я бы предпочел как можно меньше формального определения и простую математику.


4489


источник


Ответы:


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


С этим графиком можно визуализировать сложность большого вывода:

Big O Analysis

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

Обозначение Big-O является относительным представлением сложности алгоритма.

В этом предложении есть важные и преднамеренно выбранные слова:

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

Вернитесь и перечитайте выше, когда вы прочтете остальное.

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

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

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

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

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

См. Шаблон? сложность (число операций) прямо пропорционально количеству цифр N в большем количестве. Мы называем это На) или линейная сложность ,

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

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

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

Поскольку алгоритм масштабируется с n- в квадрате , это На 2 ) или квадратичная сложность , Это подходящее время для введения еще одной важной концепции:

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

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

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

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

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

Теперь, если вы поручили компьютеру найти номер телефона для «Джона Смита» в телефонной книге, содержащей 1 000 000 имен, что бы вы сделали? Игнорируя тот факт, что вы могли догадаться, как далеко в начале S (предположим, вы не можете), что бы вы сделали?

Типичная реализация может заключаться в том, чтобы открыть до середины, взять 500 000 го и сравнить его с «Смитом». Если это «Смит, Джон», нам просто повезло. Скорее всего, «Джон Смит» будет до или после этого имени. Если это после того, как мы разделим последнюю половину телефонной книги пополам и повторим. Если до этого мы разделим первую половину телефонной книги пополам и повторим. И так далее.

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

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

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

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

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

В этой связи стоит пояснить, что Big O можно использовать для определения трех случаев с помощью алгоритма:

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

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

Вернемся к телефонной книге.

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

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

Поэтому, чтобы найти имя с указанием номера телефона (обратный поиск):

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

Путешественник

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

Звучит просто? Подумайте еще раз.

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

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

На самом деле это меньше, потому что некоторые из них эквивалентны (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 × 24 × ... × 2 × 1 = 15,511,210,043,330,985,984,000,000
  • ...
  • 50! = 50 × 49 × ... × 2 × 1 = 3.04140932 × 10 64

Таким образом, проблема Big-O от Traveling Salesman На!) или факторная или комбинаторная сложность ,

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

Что-то думать о.

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

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

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

Во всяком случае, это для моего (надеюсь, простого английского) объяснения Big O (пересмотрено).


6037



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

На 2 ) : известный как Квадратичная сложность

  • 1 статья: 1 секунда
  • 10 элементов: 100 секунд
  • 100 предметов: 10000 секунд

Обратите внимание, что количество предметов увеличивается в 10 раз, но время увеличивается в 10 раз 2 , В основном, n = 10 и поэтому O (n 2 ) дает нам масштабный множитель n 2 который составляет 10 2 ,

На) : известный как Линейная сложность

  • 1 статья: 1 секунда
  • 10 элементов: 10 секунд
  • 100 предметов: 100 секунд

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

O (1) : известный как Постоянная сложность

  • 1 статья: 1 секунда
  • 10 наименований: 1 секунда
  • 100 наименований: 1 секунда

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

O (log n) : известный как Логарифмическая сложность

  • 1 статья: 1 секунда
  • 10 наименований: 2 секунды
  • 100 предметов: 3 секунды
  • 1000 наименований: 4 секунды
  • 10000 единиц: 5 секунд

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

В этом суть. Они уменьшают математику, так что это может быть не совсем n 2 или что бы они ни говорили, но это будет доминирующим фактором в масштабировании.


659



Обозначение с обозначением Big-O (также называемое «асимптотическим ростом») какие функции «выглядят», когда вы игнорируете постоянные факторы и вещи рядом с источником , Мы используем его, чтобы говорить о как шкала вещей ,


основы

для «достаточно больших вводов» ...

  • f(x) ∈ O(upperbound)означает f«растет не быстрее, чем» upperbound
  • f(x) ∈ Ɵ(justlikethis)имею в виду f«растет точно так же, как» justlikethis
  • f(x) ∈ Ω(lowerbound)означает f«растет не медленнее, чем» lowerbound

нотация большой О не заботится о постоянных факторах: функция 9x²говорят, что «растут точно так же» 10x², Также большой асимптотический нотация Неасимптотические («материал рядом с источником» или «что происходит, когда размер проблемы мал»): функция 10x²говорят, что «растут точно так же» 10x² - x + 2,

Почему вы хотите игнорировать более мелкие части уравнения? Потому что они становятся полностью затмеванными большими частями уравнения, поскольку вы рассматриваете большие и большие масштабы; их вклад становится затмевающим и несущественным. (См. Раздел примера.)

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

actualAlgorithmTime(N) ∈ O(bound(N))
                                       e.g. "time to mergesort N elements 
                                             is O(N log(N))"

... это значит, что для «достаточно больших» проблемных размеров N (если мы игнорируем материал вблизи начала координат), существует некоторая постоянная (например, 2.5, полностью составленная) такая, что:

actualAlgorithmTime(N)                 e.g. "mergesort_duration(N)       "
────────────────────── < constant            ───────────────────── < 2.5 
       bound(N)                                    N log(N)         

Есть много вариантов постоянных; часто «лучший» выбор известен как «постоянный фактор» алгоритма ... но мы часто игнорируем его, как мы игнорируем не самые большие члены (см. раздел «Постоянные факторы», почему они обычно не имеют значения). Вы можете также думать о вышеупомянутом уравнении как о связи, говоря: В худшем случае время, которое требуется, никогда не будет хуже, чем грубо N*log(N), в 2,5 раза (постоянный фактор, о котором нас не волнует) ».

В целом, O(...)является наиболее полезным, потому что мы часто заботимся о худшем случае поведения. Если f(x)представляет что-то «плохое», как процессор или использование памяти, затем « f(x) ∈ O(upperbound)" означает " upperboundявляется наихудшим сценарием использования процессора / памяти ».


Приложения

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

  • количество возможных рукопожатий среди Nлюди на вечеринке ( Ɵ(N²), в частности N(N-1)/2, но важно то, что оно «масштабируется», )
  • вероятностное ожидаемое число людей, которые видели некоторый вирусный маркетинг как функцию времени
  • как масштабирование латентности веб-сайта с количеством процессоров в процессоре или графическом процессоре или компьютерном кластере
  • как шкала тепловыделения на процессоре умирает в зависимости от количества транзисторов, напряжения и т. д.
  • сколько времени должен выполняться алгоритм, как функция размера ввода
  • сколько пространства должен выполняться алгоритм в зависимости от размера ввода

пример

Для приведенного выше примера рукопожатия все в комнате встряхивают чужую руку. В этом примере, #handshakes ∈ Ɵ(N²), Зачем?

Резервное копирование: количество рукопожатий - это точно n-select-2 или N*(N-1)/2(каждый из N человек встряхивает руки N-1 других людей, но эти двойные счета рукопожатий так делятся на 2):

everyone handshakes everyone else. Image credit and license per wikipedia/wikimedia commons "complete graph" article. adjacency matrix

Однако для очень большого числа людей линейный термин Nзатмевается и эффективно вносит 0 в соотношение (в диаграмме: доля пустых ячеек по диагонали по общим ящикам становится меньше по мере увеличения количества участников). Поэтому поведение масштабирования order N², или количество рукопожатий «растет как N²».

#handshakes(N)
────────────── ≈ 1/2
     N²

Это как если бы пустые поля на диагонали диаграммы (N * (N-1) / 2 галочки) даже не были там (N 2 галочки асимптотически).

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

    N²/2 - N/2         (N²)/2   N/2         1/2
lim ────────── = lim ( ────── - ─── ) = lim ─── = 1/2
N→∞     N²       N→∞     N²     N²      N→∞  1
                               ┕━━━┙
             this is 0 in the limit of N→∞:
             graph it, or plug in a really large number for N

tl; dr: Количество рукопожатий выглядит так «x²» для больших значений, что, если мы должны записать соотношение # handshakes / x², то, что нам не нужно в точку x² рукопожатия даже не появятся в десятичной системе для сколь угодно большого времени.

например для x = 1million, отношение # рукопожатия / x²: 0.499999 ...


Строительная интуиция

Это позволяет нам делать заявления вроде ...

«Для достаточно больших входов = N, независимо от постоянного коэффициента, если I двойной размер ввода


361



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

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

Очевидно, что только использование «размера» в качестве входных данных и «время, взятое» в качестве выходного - та же идея применяется, если вы хотите поговорить об использовании памяти и т. Д.

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

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

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

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

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

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


237



Big O describes an upper limit on the growth behaviour of a function, for example the runtime of a program, when inputs become large.

Examples:

  • O(n): If I double the input size the runtime doubles

  • O(n2): If the input size doubles the runtime quadruples

  • O(log n): If the input size doubles the runtime increases by one

  • O(2n): If the input size increases by one, the runtime doubles

The input size is usually the space in bits needed to represent the input.


121



Big O notation is most commonly used by programmers as an approximate measure of how long a computation (algorithm) will take to complete expressed as a function of the size of the input set.

Big O is useful to compare how well two algorithms will scale up as the number of inputs is increased.

More precisely Big O notation is used to express the asymptotic behavior of a function. That means how the function behaves as it approaches infinity.

In many cases the "O" of an algorithm will fall into one of the following cases:

  • O(1) - Time to complete is the same regardless of the size of input set. An example is accessing an array element by index.
  • O(Log N) - Time to complete increases roughly in line with the log2(n). For example 1024 items takes roughly twice as long as 32 items, because Log2(1024) = 10 and Log2(32) = 5. An example is finding an item in a binary search tree (BST).
  • O(N) - Time to complete that scales linearly with the size of the input set. In other words if you double the number of items in the input set, the algorithm takes roughly twice as long. An example is counting the number of items in a linked list.
  • O(N Log N) - Time to complete increases by the number of items times the result of Log2(N). An example of this is heap sort and quick sort.
  • O(N^2) - Time to complete is roughly equal to the square of the number of items. An example of this is bubble sort.
  • O(N!) - Time to complete is the factorial of the input set. An example of this is the traveling salesman problem brute-force solution.

Big O ignores factors that do not contribute in a meaningful way to the growth curve of a function as the input size increases towards infinity. This means that constants that are added to or multiplied by the function are simply ignored.


98



Big O is just a way to "Express" yourself in a common way, "How much time / space does it take to run my code?".

You may often see O(n), O(n2), O(nlogn) and so forth, all these are just ways to show; How does an algorithm change?

O(n) means Big O is n, and now you might think, "What is n!?" Well "n" is the amount of elements. Imaging you want to search for an Item in an Array. You would have to look on Each element and as "Are you the correct element/item?" in the worst case, the item is at the last index, which means that it took as much time as there are items in the list, so to be generic, we say "oh hey, n is a fair given amount of values!".

So then you might understand what "n2" means, but to be even more specific, play with the thought you have a simple, the simpliest of the sorting algorithms; bubblesort. This algorithm needs to look through the whole list, for each item.

My list

  1. 1
  2. 6
  3. 3

The flow here would be:

  • Compare 1 and 6, which is biggest? Ok 6 is in the right position, moving forward!
  • Compare 6 and 3, oh, 3 is less! Let's move that, Ok the list changed, we need to start from the begining now!

This is O n2 because, you need to look at all items in the list there are "n" items. For each item, you look at all items once more, for comparing, this is also "n", so for every item, you look "n" times meaning n*n = n2

I hope this is as simple as you want it.

But remember, Big O is just a way to experss yourself in the manner of time and space.


78



Big O describes the fundamental scaling nature of an algorithm.

There is a lot of information that Big O does not tell you about a given algorithm. It cuts to the bone and gives only information about the scaling nature of an algorithm, specifically how the resource use (think time or memory) of an algorithm scales in response to the "input size".

Consider the difference between a steam engine and a rocket. They are not merely different varieties of the same thing (as, say, a Prius engine vs. a Lamborghini engine) but they are dramatically different kinds of propulsion systems, at their core. A steam engine may be faster than a toy rocket, but no steam piston engine will be able to achieve the speeds of an orbital launch vehicle. This is because these systems have different scaling characteristics with regards to the relation of fuel required ("resource usage") to reach a given speed ("input size").

Why is this so important? Because software deals with problems that may differ in size by factors up to a trillion. Consider that for a moment. The ratio between the speed necessary to travel to the Moon and human walking speed is less than 10,000:1, and that is absolutely tiny compared to the range in input sizes software may face. And because software may face an astronomical range in input sizes there is the potential for the Big O complexity of an algorithm, it's fundamental scaling nature, to trump any implementation details.

Consider the canonical sorting example. Bubble-sort is O(n2) while merge-sort is O(n log n). Let's say you have two sorting applications, application A which uses bubble-sort and application B which uses merge-sort, and let's say that for input sizes of around 30 elements application A is 1,000x faster than application B at sorting. If you never have to sort much more than 30 elements then it's obvious that you should prefer application A, as it is much faster at these input sizes. However, if you find that you may have to sort ten million items then what you'd expect is that application B actually ends up being thousands of times faster than application A in this case, entirely due to the way each algorithm scales.


53



Here is the plain English bestiary I tend to use when explaining the common varieties of Big-O

In all cases, prefer algorithms higher up on the list to those lower on the list. However, the cost of moving to a more expensive complexity class varies significantly.

O(1):

No growth. Regardless of how big as the problem is, you can solve it in the same amount of time. This is somewhat analogous to broadcasting where it takes the same amount of energy to broadcast over a given distance, regardless of the number of people that lie within the broadcast range.

O(log n):

This complexity is the same as O(1) except that it's just a little bit worse. For all practical purposes, you can consider this as a very large constant scaling. The difference in work between processing 1 thousand and 1 billion items is only a factor six.

O(n):

The cost of solving the problem is proportional to the size of the problem. If your problem doubles in size, then the cost of the solution doubles. Since most problems have to be scanned into the computer in some way, as data entry, disk reads, or network traffic, this is generally an affordable scaling factor.

O(n log n):

This complexity is very similar to O(n). For all practical purposes, the two are equivalent. This level of complexity would generally still be considered scalable. By tweaking assumptions some O(n log n) algorithms can be transformed into O(n) algorithms. For example, bounding the size of keys reduces sorting from O(n log n) to O(n).

O(n2):

Grows as a square, where n is the length of the side of a square. This is the same growth rate as the "network effect", where everyone in a network might know everyone else in the network. Growth is expensive. Most scalable solutions cannot use algorithms with this level of complexity without doing significant gymnastics. This generally applies to all other polynomial complexities - O(nk) - as well.

O(2n):

Does not scale. You have no hope of solving any non-trivially sized problem. Useful for knowing what to avoid, and for experts to find approximate algorithms which are in O(nk).


36



Big O is a measure of how much time/space an algorithm uses relative to the size of its input.

If an algorithm is O(n) then the time/space will increase at the same rate as its input.

If an algorithm is O(n2) then the time/space increase at the rate of its input squared.

and so on.


35



It is very difficult to measure the speed of software programs, and when we try, the answers can be very complex and filled with exceptions and special cases. This is a big problem, because all those exceptions and special cases are distracting and unhelpful when we want to compare two different programs with one another to find out which is "fastest".

As a result of all this unhelpful complexity, people try to describe the speed of software programs using the smallest and least complex (mathematical) expressions possible. These expressions are very very crude approximations: Although, with a bit of luck, they will capture the "essence" of whether a piece of software is fast or slow.

Because they are approximations, we use the letter "O" (Big Oh) in the expression, as a convention to signal to the reader that we are making a gross oversimplification. (And to make sure that nobody mistakenly thinks that the expression is in any way accurate).

If you read the "Oh" as meaning "on the order of" or "approximately" you will not go too far wrong. (I think the choice of the Big-Oh might have been an attempt at humour).

The only thing that these "Big-Oh" expressions try to do is to describe how much the software slows down as we increase the amount of data that the software has to process. If we double the amount of data that needs to be processed, does the software need twice as long to finish it's work? Ten times as long? In practice, there are a very limited number of big-Oh expressions that you will encounter and need to worry about:

The good:

  • O(1) Constant: The program takes the same time to run no matter how big the input is.
  • O(log n) Logarithmic: The program run-time increases only slowly, even with big increases in the size of the input.

The bad:

  • O(n) Linear: The program run-time increases proportionally to the size of the input.
  • O(n^k) Polynomial: - Processing time grows faster and faster - as a polynomial function - as the size of the input increases.

... and the ugly:

  • O(k^n) Exponential The program run-time increases very quickly with even moderate increases in the size of the problem - it is only practical to process small data sets with exponential algorithms.
  • O(n!) Factorial The program run-time will be longer than you can afford to wait for anything but the very smallest and most trivial-seeming datasets.

31



What is a plain English explanation of Big O? With as little formal definition as possible and simple mathematics.

A Plain English Explanation of the Need for Big-O Notation:

When we program, we are trying to solve a problem. What we code is called an algorithm. Big O notation allows us to compare the worse case performance of our algorithms in a standardized way. Hardware specs vary over time and improvements in hardware can reduce the time it takes an algorithms to run. But replacing the hardware does not mean our algorithm is any better or improved over time, as our algorithm is still the same. So in order to allow us to compare different algorithms, to determine if one is better or not, we use Big O notation.

A Plain English Explanation of What Big O Notation is:

Not all algorithms run in the same amount of time, and can vary based on the number of items in the input, which we'll call n. Based on this, we consider the worse case analysis, or an upper-bound of the run-time as n get larger and larger. We must be aware of what n is, because many of the Big O notations reference it.


31