Программисты используют нотацию Big O в качестве сокращения для классификации общих характеристик производительности алгоритма в зависимости от размера входных данных, которые ему даются.
Мы используем Big O отчасти для облегчения проблемы описания того, насколько «хорошим» является алгоритм.
Вместо того, чтобы говорить, что алгоритм A «быстр даже при очень больших входных данных» или «медленный даже при относительно небольших входных данных», мы говорим, что алгоритм A имеет временную сложность O(log n), если он быстрый, или O( n²), если он, например, медленный.
Предполагается, что значение в круглых скобках O() описывает порядок величины, в котором алгоритм работает быстро или медленно по отношению к размеру входных данных. Вот почему это так называемый «Большой О». Подробнее об этом чуть позже.
В широком смысле мы можем использовать нотацию Big O для инкапсуляции характеристик алгоритма:
- Насколько увеличится время выполнения алгоритма по мере увеличения размера входных данных в алгоритм? (временная сложность)
- Сколько дополнительной памяти (т.е. ОЗУ) потребуется алгоритму во время выполнения по мере увеличения размера входных данных в алгоритм? (пространственная сложность)
Для меня умственное удушение указывает на то, что такое Big O:
Я часто ошибочно думаю, что нотация Big O — это способ измерения того, сколько времени и места требуется для запуска алгоритма.
Но это не нотация Big O.
Вместо этого, нотация Big O позволяет приблизительно оценить, сколько больше времени и пространства требуется алгоритму во время выполнения в зависимости от размера входных данных. увеличивается от малого до сколь угодно большого.
С помощью нотации Big O мы пытаемся наметить характеристики производительности алгоритма по отношению к размеру входных данных.
Вот полезный график из очень хорошего stackoverflow post, который показывает все практичные типы Big O и их общие характеристики производительности.
Теперь давайте подкрепим наше понимание упрощенным примером.
var smallArray = [1, 2, 3, 4, … , 96, 97, 98, 99, 100];
var largeArray = [1, 2, 3, 4, … , 9996, 9997, 9998, 9999, 10000];
function iterate(inputArray) {
var total = 0;
for (var i = 0; i < inputArray.length; i++) {
total += inputArray[i];
}
return total;
}
iterate(smallArray);
iterate(largeArray);
Если smallArray содержит 100 элементов, а largeArray имеет 10 000 элементов, и они передаются (в двух отдельных вызовах) в алгоритм, который перебирает каждый элемент в массиве, можно сказать, что этот алгоритм имеет временную сложность O (n) или линейная временная сложность.
Это означает, что мы можем ожидать, что время выполнения этого алгоритма будет увеличиваться линейно с размером входных данных n. Если это поможет, вы можете увидеть O(n) как O(1n), потому что алгоритм перебирает массив размером n ровно один раз.
Это может показаться интуитивным, но я все же выскажу некоторые, казалось бы, очевидные вещи, которые обычно упускаю из виду:
- Временная сложность алгоритма
iterate()на самом деле может быть O(1) или постоянной временной сложностью (Святой Грааль эффективности), если входной массив имеет только 1 элемент. - Но как программистов, нас в основном интересует наихудший сценарий (план на худшее, надежда на лучшее), поэтому такой алгоритм, как
iterate(), будет рассматриваться как O(n), или линейная временная сложность. - Большой O описывает форму и градиент линии на графике (т. е. сложность), а не фактическое время, необходимое для выполнения; поэтому он действительно описывает сложность того, как время зависит от размера входных данных.
Худший вариант
Обычно мы рассматриваем порядок сложности алгоритма, его большое О, как будто Мерфи (и его закон) имеет личную вендетту против нашего алгоритма. То есть мы рассматриваем наихудший сценарий.
Но ранее мы упомянули тот факт, что iterate() может быть выполнено за линейное время, если входной массив содержит только один элемент. Это лучший сценарий. Другими словами, сценарий, о котором нам не следует беспокоиться и который можно спокойно пропустить.
Наконец, иногда программисты также рассматривают ожидаемый сценарий. Это сценарий, который, скорее всего, будет разыгрываться всякий раз, когда мы запускаем алгоритм. В случае нашего алгоритма iterate() это, вероятно, где-то около O(n/2).
Еще немного о последнем пункте. На самом деле люди не говорят O(n/2). Давайте посмотрим, почему дальше.
Константы не имеют большого значения
Что, если мы изменим функцию iterate() так, чтобы входной массив выполнялся дважды, а не один раз? Какова будет его новая временная сложность?
// modified to iterate the array twice instead of just once
function iterate(inputArray) {
var total = 0;
for (var i = 0; i < inputArray.length; i++) {
total += inputArray[i];
}
for (var i = 0; i < inputArray.length; i++) {
total += inputArray[i];
}
return total;
}
Готовый?
Временная сложность новой функции iterate() также O(n) — такая же, как и раньше!
Технически, поскольку этот алгоритм повторяет один и тот же массив дважды, он должен занимать в два раза больше времени по сравнению со старым алгоритмом с одной итерацией. Так что на самом деле было бы точнее сказать, что новая функция iterate() имеет временную сложность O(n+n) или O(2n).
Но учтите следующее: время, необходимое для выполнения операции n раз против 2n раз, имеет один и тот же порядок величины (в отличие от, скажем, n операций против n² операций).
Вот почему мы по-прежнему будем называть этот новый алгоритм временной сложностью O(n) — константы не имеют большого значения в том смысле, что они не заставляют нас сидеть на стульях и беспокоиться о производительности.
Таким образом, при рассмотрении большого О мы опускаем константы.
Самый большой похититель времени
Та же логика, которая применяется к константам, применима и к менее значимым частям алгоритма. Если есть часть алгоритма, которая занимает большую часть времени выполнения, поскольку размер входных данных становится сколь угодно большим, эта часть определяет общую временную сложность алгоритма.
function weirdIterate(inputArray) {
var total = 0;
for (var i = 0; i < inputArray.length; i++) {
total += inputArray[i];
}
for (var i = 0; i < inputArray.length; i++) {
for (var j = 0; j < inputArray.length; j++) {
total += inputArray[i] + inputArray[j];
}
}
return total;
}
Так при чем здесь временная сложность?
Если быть точным, то нам пришлось бы сказать O(n+n²). Но по мере того, как n становится сколь угодно большим, добавление n будет становиться все менее и менее значимым.
Поэтому для практических целей мы должны рассматривать этот алгоритм как имеющий временную сложность O(n²), отбрасывая меньший член величины, n.
Более одного входа
Что произойдет, если наш алгоритм получит два входа вместо одного?
Рассмотрим этот алгоритм, который подсчитывает количество перекрывающихся элементов в двух массивах.
function overlapCount(arrayA, arrayB) {
var count = 0;
for (var i = 0; i < arrayA.length; i++) {
for (var j = 0; j < arrayB.length; j++) {
if (arrayA[i] === arrayB[j]) {
count += 1;
}
}
}
return count;
}
В этом случае временная сложность смешивается с размером двух разных входных данных вместо одного.
Если алгоритм повторяет один и тот же входной массив дважды, мы сможем определить его временную сложность как O(n * n) или O(n²), где n представляет размер одного входного массива.
Но теперь, когда есть два входа вместо одного, мы можем представить их как две отдельные переменные. В то время как это было просто n для одного входа, было бы что-то вроде a для представления размера входа arrayA и b для представления arrayB для двух входов потенциально разных размеров.
Почему это должно быть так, если мы были рады упростить 2n до n в предыдущем пункте о константах?
Причина связана с четким представлением. Когда мы говорим, что алгоритм имеет временную сложность O(n²) вместо O(a * b) или O(ab), мы скрываем тот факт, что сложность действительно зависит от двух входных данных, а не от одного. Это просто понятнее.
Тем не менее, многие люди по-прежнему будут ссылаться на такой алгоритм, как overlapCount(a, b), как имеющий временную сложность O(n²). Они не ошибаются, потому что этот алгоритм в конечном итоге имеет ту же линию и форму на графике. Наверное, это что-то типа картошка, картошка?
Примечание о пространственной сложности
До сих пор мы обсуждали только временную сложность. Как насчет пространственной сложности?
Это точно такая же концепция, только применительно к использованию памяти (то есть ОЗУ) вместо времени.
Мы больше говорим о временной сложности, чем о пространственной. Я думаю, это потому, что наши алгоритмы, как правило, сталкиваются с ограничениями продолжительности выполнения, чем с достижением пределов физической памяти.
Я знаю, что это выглядит так, будто я просматриваю большую тему сам по себе, и это потому, что это так.
Я считаю, что если мы действительно понимаем временную сложность, мы также получаем интуитивное представление о пространственной сложности алгоритма с течением времени. Так что я просто оставлю вас с этим на данный момент ...
Справочные источники, использованные при написании этой статьи:
- Hacker Rank — обозначение Big O (видео)
- Торт-интервью — обозначение Big O
- Ответ Stackoverflow от cletus — обозначение Big O на простом английском языке
В следующем посте я перечислю и обсужу некоторые известные примеры алгоритмов с различной временной сложностью. Подпишитесь на список рассылки, если вы хотите, чтобы будущие сообщения доставлялись прямо в ваш почтовый ящик в момент их публикации. Увидимся со следующей рассылкой!
Чтобы узнать больше о подобных обсуждениях, ознакомьтесь с оставшейся частью раздела Программирование размера укуса.
Первоначально опубликовано на сайте Nick Ang.
