Что такое o большое
Перейти к содержимому

Что такое o большое

  • автор:

Big O

Примечание. Сокращенный перевод, скорее пересказ своими словами.
UPD: как отметили в комментариях, примеры не идеальны. Автор не ищет лучшее решение задачи, его цель объяснить сложность алгоритмов «на пальцах».

Big O нотация нужна для описания сложности алгоритмов. Для этого используется понятие времени. Тема для многих пугающая, программисты избегающие разговоров о «времени порядка N» обычное дело.

Если вы способны оценить код в терминах Big O, скорее всего вас считают «умным парнем». И скорее всего вы пройдете ваше следующее собеседование. Вас не остановит вопрос можно ли уменьшить сложность какого-нибудь куска кода до n log n против n^2.

Структуры данных

Выбор структуры данных зависит от конкретной задачи: от вида данных и алгоритма их обработки. Разнообразные структуры данных (в .NET или Java или Elixir) создавались под определенные типы алгоритмов.

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

Здесь мы будем использовать только массивы чисел (прямо как на собеседовании). Примеры на JavaScript.

Начнем с самого простого: O(1)

Возьмем массив из 5 чисел:

const nums = [1,2,3,4,5];

Допустим надо получить первый элемент. Используем для это индекс:

const nums = [1,2,3,4,5]; const firstNumber = nums[0];

Насколько это сложный алгоритм? Можно сказать: «совсем не сложный — просто берем первый элемент массива». Это верно, но корректнее описывать сложность через количество операций, выполняемых для достижения результата, в зависимости от ввода (операций на ввод).

Другими словами: насколько возрастет кол-во операций при увеличении кол-ва входных параметров.

В нашем примере входных параметров 5, потому что в массиве 5 элементов. Для получения результата нужно выполнить одну операцию (взять элемент по индексу). Сколько операций потребуется если элементов массива будет 100? Или 1000? Или 100 000? Все равно нужна только одна операция.

Т.е.: «одна операция для всех возможных входных данных» — O(1).

O(1) можно прочитать как «сложность порядка 1» (order 1), или «алгоритм выполняется за постоянное/константное время» (constant time).

Вы уже догадались что O(1) алгоритмы самые эффективные.

Итерации и «время порядка n»: O(n)

Теперь давайте найдем сумму элементов массива:

const nums = [1,2,3,4,5]; let sum = 0; for(let num of nums)

Опять зададимся вопросом: сколько операций на ввод нам потребуется? Здесь нужно перебрать все элементы, т.е. операция на каждый элемент. Чем больше массив, тем больше операций.

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

Анализ

Можем ли мы сделать суммирование более эффективным? В общем случае нет. А если мы знаем, что массив гарантированно начинается с 1, отсортирован и не имеет пропусков? Тогда можно применить формулу S = n(n+1)/2 (где n последний элемент массива):

const sumContiguousArray = function(ary) < //get the last item const lastItem = ary[ary.length - 1]; //Gauss's trick return lastItem * (lastItem + 1) / 2; >const nums = [1,2,3,4,5]; const sumOfArray = sumContiguousArray(nums);

Такой алгоритм гораздо эффективнее O(n), более того он выполняется за «постоянное/константное время», т.е. это O(1).

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

Алгоритмы с константным временем это всегда O(1). Тоже и с линейными алгоритмами, фактически операций может быть O(n+5), в Big O нотации это O(n).

Не самые лучшие решения: O(n^2)

Давайте напишем функцию которая проверяет массив на наличие дублей. Решение с вложенным циклом:

const hasDuplicates = function (num) < //loop the list, our O(n) op for (let i = 0; i < nums.length; i++) < const thisNum = nums[i]; //loop the list again, the O(n^2) op for (let j = 0; j < nums.length; j++) < //make sure we're not checking same number if (j !== i) < const otherNum = nums[j]; //if there's an equal value, return if (otherNum === thisNum) return true; >> > //if we're here, no dups return false; > const nums = [1, 2, 3, 4, 5, 5]; hasDuplicates(nums);//true

Мы уже знаем что итерирование массива это O(n). У нас есть вложенный цикл, для каждого элемента мы еще раз итерируем — т.е. O(n^2) или «сложность порядка n квадрат».

Алгоритмы с вложенными циклами по той же коллекции всегда O(n^2).

«Сложность порядка log n»: O(log n)

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

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

Пускай массив будет отсортирован. Тогда мы сможем использовать алгоритм «бинарный поиск»: делим массив на две половины, отбрасываем не нужную, оставшуюся опять делим на две части и так пока не найдем нужное значение. Такой тип алгоритмов называется «разделяй и влавствуй» Divide and Conquer.

бинарный поиск

Этот алгоритм основан на логарифме.

Быстрый обзор логарифмов

Рассмотрим пример, чему будет равен x?

Нужно взять кубический корень от 8 — это будет 2. Теперь посложнее

С использованием логарифма задачу можно записать так

«логарифм по основанию 2 от 512 равен x». Обратите внимание «основание 2», т.е. мы мыслим двойками — сколько раз нужно перемножить 2 что бы получить 512.

В алгоритме «бинарный поиск» на каждом шаге мы делим массив на две части.

Мое дополнение. Т.е. в худшем случае делаем столько операций, сколько раз можем разделить массив на две части. Например, сколько раз мы можем разделить на две части массив из 4 элементов? 2 раза. А массив из 8 элементов? 3 раза. Т.е. кол-во делений/операций = log2(n) (где n кол-во элементов массива).

Получается, что зависимость кол-ва операций от кол-ва элементов ввода описывается как log2(n)

Таким образом, используя нотацию Big O, алгоритм «бинарный поиск» имеет сложность O(log n).

Улучшим O(n^2) до O(n log n)

Вернемся к задачке проверки массива на дубли. Мы перебирали все элементы массива и для каждого элемента еще раз делали перебор. Делали O(n) внутри O(n), т.е. O(n*n) или O(n^2).

Мы можем заменить вложенный цикл на бинарный поиск*. Т.е. у нас остается перебор всех элементов O(n), внутри делаем O(log n). Получается O(n * log n), или O(n log n).

const nums = [1, 2, 3, 4, 5]; const searchFor = function (items, num) < //use binary search! //if found, return the number. Otherwise. //return null. We'll do this in a later chapter. >const hasDuplicates = function (nums) < for (let num of nums) < //let's go through the list again and have a look //at all the other numbers so we can compare if (searchFor(nums, num)) < return true; >> //only arrive here if there are no dups return false; >

* ВНИМАНИЕ, во избежание Импринтинга. Использовать бинарный поиск для проверки массива на дубли — плохое решение. Здесь лишь показывается как в терминах Big O оценить сложность алгоритма показанного в листинге кода выше. Хороший алгоритм или плохой — для данной заметки не важно, важна наглядность.

Мышление в терминах Big O

  • Получение элемента коллекции это O(1). Будь то получение по индексу в массиве, или по ключу в словаре в нотации Big O это будет O(1)
  • Перебор коллекции это O(n)
  • Вложенные циклы по той же коллекции это O(n^2)
  • Разделяй и властвуй (Divide and Conquer) всегда O(log n)
  • Итерации которые используют Divide and Conquer это O(n log n)
  • big-o notation
  • алгоритмы
  • javascript
  • структуры данных
  • сложность алгоритма
  • сложность
  • бинарный поиск
  • JavaScript
  • Программирование
  • Алгоритмы

О большое (Big O) — верхняя оценка сложности алгоритмов

Мы начинаем курс по структурам данных. Чтобы вы сразу представляли о чем пойдет речь приведу примеры таких структур:

  • статический и динамический массивы;
  • стек;
  • очередь;
  • односвязный и двухсвязный списки;
  • множество;
  • хэш-таблица;
  • деревья; бинарные деревья.

Зачем они вообще нужны? Дело в том, что не существует единого, универсального подхода представления и хранения данных в программе и для каждой конкретной задачи следует выбирать свой эффективный способ организации данных в памяти компьютера. Чтобы уметь это делать, как раз и нужно знать основные, наиболее распространенные структуры данных. Но прежде чем мы перейдем непосредственно к рассмотрению этих структур, нам нужно разобраться, как оценивать и сравнивать между собой скорости работы алгоритмов. Опять же единого ответа на этот вопрос нет. На заре вычислительной техники предлагалось сравнивать число элементарных арифметических операций (сложения, умножения, деления), которые совершает алгоритм в процессе своей работы. Однако так можно делать или для очень простых программ или для математических алгоритмов. Еще можно попробовать замерить скорость работы алгоритма в миллисекундах. Однако на разном железе с разной производительностью мы будем получать разные результаты для одной и той же программы. И, кроме того, время работы может нелинейно возрастать с увеличением размерности (объема) входных данных. Например, все медленные алгоритмы сортировки элементов массива имеют квадратическую сложность , где n – число элементов массива. Поэтому такая характеристика тоже не подходит. Например, для n = 3 элементов получим одно значение времени, а для n = 10 заметно больше. И это время будет возрастать нелинейно, а квадратически! Вместо этого было предложено применять приближенную асимптотическую метрику для оценки сложности алгоритмов. В частности метрику «О большое» (от англ. Big O), которая показывает:

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

Чаще всего именно она интересна разработчикам. Например, для тех же медленных алгоритмов сортировки элементов массива длиной n, верхняя граница их вычислительной сложности (т.е. наихудший случай) определяется как . И, глядя на это выражение, мы адекватно можем представить изменение объема вычислений, при изменении величины n. В рамках данного курса я не буду углубляться в фундаментальное математическое определение О большого. Программист чаще всего следует некоторым разумным правилам при оценке сложности алгоритма. И те правила, о которых мы дальше будем говорить, базируются на строгих математических законах.

Сложность выполнения константных операций

Давайте представим, что мы на языке Python выполняем команды, которые не зависят от размера входных данных. Например:

var_a = 10 inf = float('inf') print(inf)

Каждая строчка выполнится за определенное время. Предположим, мы измерили это время, и оно оказалось равным 1 мс. Вопрос. Какова вычислительная сложность каждой команды? Мы с вами прекрасно понимаем, что полученное время t = 1 мс будет разным на разных компьютерах. Поэтому такая характеристика не совсем корректна. По большому счету мы можем здесь сказать только одно: в каждой строчке выполняется одна операция за одно и то же константное время. В нотации О большого это записывается так: O(1) Здесь 1 означает выполнение одной операции. А конкретное время выполнения этой операции, как бы вынесено за скобки и отбрасывается. При качественном сравнении скорости работы алгоритмов подобные константы не имеют большого значения. То есть, с точки зрения О большого любая константа может быть отброшена. Например: O(10) = O(1)
O(C) = O(1) Здесь C – константа. А раз это так, то последовательное выполнение трех константных по времени операций даст с точки зрения О большого, следующее выражение: O(1 + 1 + 1) = O(3) = O(1) То есть, О(1) лишь показывает, что в алгоритме выполняется одна операция за некоторое константное время и при этом не важно, сколько команд входит в эту операцию: одна, две, три. Главное, чтобы все они выполнялись за фиксированный промежуток времени и не зависели от размера входных данных. Вот так следует воспринимать O(1). Линейная сложность выполнения алгоритма Давайте теперь усложним алгоритм и представим, что имеется массив (список) из n элементов. Для простоты это будут произвольные числа:

lst = [1, 4, 10, -5, 0, 2, 3, . , 18, 32] # n элементов

Затем, мы их последовательно в цикле перебираем и выводим на экран:

for x in lst: print(x)

Какова сложность этого алгоритма? Очевидно, что число итераций цикла зависит от размерности массива n. Чем больше n, тем больше итераций нужно сделать в цикле. То есть, цикл зависит от размера входных данных. Так вот, нотация О большое должна показывать динамику этой зависимости, то есть, изменение сложности алгоритма от размера n входных данных. И в данном случае эта величина равна: O(n) Обратите внимание, здесь n – уже переменная, а не константа. Так как в общем случае при работе с массивами и другими упорядоченными коллекциями мы полагаем, что n может бесконечно увеличиваться. Здесь всегда следует помнить, что О большое показывает верхнюю границу, то есть соответствует худшему случаю работы алгоритма (в вычислительном плане). Из записи O(n) хорошо виден линейный характер зависимости сложности работы цикла от размера массива n. Но здесь можно задать резонный вопрос. А что если в цикле будет выполняться сразу несколько команд, например, так:

for x in lst: x += 1 print(x)

Возрастет ли тогда сложность с точки зрения О большого? Будет ли она равна: O(2n) В действительности нет. Всегда следует помнить, что О большое показывает лишь динамику изменения вычислительной сложности алгоритма, ее зависимость от размера входных данных и не более того. Поэтому здесь, как и ранее с тремя командами: O(1) + O(1) + O(1) = O(3) = O(1) отбрасываем константу и получаем: O(2n) = O(n) Помните, что любые константы в нотации О большого отбрасываются, так как О большое характеризует не конкретное время выполнения программы, а характер вычислительной сложности, ее зависимости от входных данных. По сути, все отброшенные константы связаны лишь с временем выполнения алгоритма и не имеют принципиального значения при качественном сравнении сложности алгоритмов.

Правила отбрасывания констант

Итак, будет ли O(n) корректной оценкой сложности всей программы? Здесь перед циклом имеется еще одна команда, которая имеет сложность: O(1) Наверное, ее также следует учесть и записать итоговое выражение в виде: O(1 + n) На самом деле нет. Любая константа, которая добавляется к n, также отбрасывается и результат будет: O(n) Всегда следует помнить, что Big O – это верхняя оценка сложности алгоритма, то есть, при n стремящемся к бесконечности. И добавление к бесконечности какого-либо константного значения дает ту же бесконечность. Поэтому асимптотически верхняя граница для: O(1 + n) = O(n) И, вообще, для любой константы C можно записать: O(n + C) = O(n) Помните, Big O характеризует только скорость (динамику) роста сложности алгоритма, а не его фактическое время выполнения. В результате, получаем следующие правила отбрасывания констант: O(A∙n) = O(n)
O(n + C) = O(n)
O(A∙n + C) = O(n) где A, C – константы; n – размер (число) входных данных. Для лучшего понимания оценки сложности алгоритма приведу еще один пример. Распишем предыдущую программу через два цикла:

lst = [1, 4, 10, -5, 0, 2, 3, . , 18, 32] for i, x in enumerate(lst): lst[i] += 1 for x in lst: print(x)

Какова сложность алгоритма с позиции Big O? Формально, можно записать так: O(1) + O(n) + O(n) = O(1 + n + n) = O(1 + 2n) И, затем, используя правила отбрасывания констант, имеем: O(1 + 2n) = O(n) Мы пришли к тому же результату, что и при оценке предыдущего варианта алгоритма через один цикл. И это логично, т.к. здесь сравнимый объем вычислений. Хотя, реальная скорость работы алгоритмов все же будет несколько отличаться. Но это, как правило, не имеет большого значения. Главное уметь оценивать принципиальные (качественные) отличия объема вычислений тех или иных алгоритмов. Как раз для этого и используется О большое.

Правила сложения и умножения

Но вернемся к нашей программе и посмотрим, что будет, если перебираются два разных списка с длинами n и m:

for x in range(n): print(x) for y in range(m): print(y)

Вычислительная сложность алгоритма с точки зрения Big O будет равна: O(n) + O(m) = O(n + m) И никаких сокращений. Почему так? Дело в том, что теперь обе величины n и m могут принимать произвольные значения, то есть, не являются константами. Мало того, в общем случае, обе величины сравнимы между собой. Поэтому они не могут быть сокращены или отброшены. Далее, если мы один цикл запишем внутри другого:

for x in range(n): for y in range(m): print(x, y)

то объем вычислений в нотации О большого примет вид: O(n ∙ m) потому что обе величины n, m являются переменными и сравнимыми между собой. А умножение появляется в результате перебора m раз значений во внутреннем цикле для каждого значения x внешнего цикла. Поэтому для вложенных циклов получаем умножение, а для последовательных – сложение. Можно заметить, что здесь в частном случае, когда n = m, выходит:

Итоги

Итак, на этом первом занятии по Big O мы с вами увидели, что имеет смысл сравнивать алгоритмы по верхней границе динамики изменения их сложности в зависимости от размера n входных данных. Познакомились со следующими оценками временной сложности:

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

Также мы с вами увидели, что любые константы отбрасываются из нотации О большого: И узнали, в каких случаях следует складывать объемы вычислений, а в каких умножать:

  • — при последовательной записи команд с объемом вычислений n и m;
  • — при вложении одной команды в другую (например, вложенные циклы). На следующем занятии мы продолжим эту тему и рассмотрим примеры алгоритмов, дающих логарифмический и факториальный объем вычислений. Курс по структурам данных: https://stepik.org/a/134212

    «O» большое и «o» малое

    Пусть f(x) и g(x) — две функции, определенные в некоторой проколотой окрестности точки x0, причем в этой окрестности g не обращается в ноль. Говорят, что:

    • f является «O» большим от g при xx0, если существует такая положительная константа C, что для всех x из некоторой окрестности точки x0 имеет место неравенство
    • f является «о» малым от g при xx0, если для любой положительной константы c найдется такая окрестность точки x0, что для всех x из этой окрестности имеет место неравенство

    Иначе говоря, в первом случае отношение |f|/|g| в окрестности точки x0 ограничено сверху, а во втором оно стремится к нулю.

    Обозначение [ ]

    «f является „O“ большим („о“ малым) от g»

    записывается с помощью равенства f(x) = O(g(x)) (соответственно, f(x) = o(g(x))).

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

    «если функция такова, как написано слева от знака равенства, то она и такова, как записано справа»:

    в частности, можно писать

    f(x) = O(g(x))

    f(x) = o(g(x)),

    O(g(x)) = f(x)

    o(g(x)) = f(x)

    бессмысленны. Другой пример: при x → 0 верно, что

    O(x 2 ) = o(x),

    o(x) = O(x 2 ).

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

    x 2 + x 3 ∈ O(x 2 )

    x 2 + x 3 = O(x 2 )

    Однако на практике такая запись встречается крайне редко, в основном в простейших случаях.

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

    Основные свойства [ ]

    Примеры использования [ ]

    Другие подобные обозначения [ ]

    Реже используются обозначения:

    • f = Ω(g) при xx0, если отношение |f(x)/g(x)| ограничено снизу положительной константой в некоторой окрестности точки x0;
    • f = Θ(g) при xx0, если отношение |f(x)/g(x)| ограничено положительными константами и сверху, и снизу, т. е. если одновременно f = O(g) и g = O(f).

    История [ ]

    Обозначение «„O“ большое» введено немецким математиком Paul Gustav Heinrich Bachmann) во втором томе его книги «Analytische Zahlentheorie» (Аналитическая теория чисел), вышедшем в Edmund Georg Hermann Landau) в

    «О» большое — простое объяснение с картинками

    Бью Карнес — разработчик, ведущий YouTube-канал сайта freeCodeCamp.org, — в своей статье «Big O Notation — Simply explained with illustrations and video» попытался простыми словами объяснить нотацию большого «О».

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

    Время работы алгоритмов растет с разной скоростью

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

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

    Выбранный алгоритм должен быть и точным, и быстрым. С одной стороны, двоичный поиск быстрее. А у Иуды зачастую бывает лишь 30 секунд на поиски — пока его другу не станет слишком скучно искать игрушку. С другой стороны, алгоритм простого поиска легче написать, и шансы сделать что-то неверно гораздо меньше. Ведь если друг найдет баги в его коде, это будет очень огорчительно! Чтобы подойти к делу с максимальной точностью, Иуда решает засечь время, за которое каждый из алгоритмов справится со списком из ста игрушек.

    Давайте предположим, что проверка одной игрушки занимает 1мс. Если Иуде придется проверить все 100 игрушек путем простого поиска, это займет 100мс. С другой стороны, применяя двоичный поиск, нужно проверить всего 7 игрушек (log2 100 это примерно 7, мы здесь не будем вдаваться в точную математику), а значит, на это уйдет 7мс.

    Но на самом деле в списке миллиард игрушек. Сколько времени будет работать алгоритм простого поиска, обрабатывая такой список? А сколько времени понадобится алгоритму двоичного поиска?

    Время работы простого и двоичного поиска

    Время работы простого и двоичного поиска со списком из 100 элементов

    Иуда запускает двоичный поиск со списком из 1 млрд. игрушек и на работу этого алгоритма уходит 30мс (log2 1000000000 примерно равен 30). «32мс! — думает он. — Сколько же времени понадобится при простом поиске? Двоичный поиск примерно в 15 раз быстрее простого, ведь алгоритму простого поиска понадобилось 100мс на список из 100 элементов, а алгоритму двоичного поиска — только 7мс. Значит, простой поиск со списком из 1 млрд. элементов займет 30мс*15 = 450мс, верно? Это намного меньше 30 секунд, за которые мой друг успеет устать». И Иуда решает воспользоваться алгоритмом простого поиска. Но был ли это правильный выбор?

    Нет. Оказалось, что Иуда ошибся и, возможно, потерял своего друга навсегда. Время работы алгоритма простого поиска со списком из 1 млрд. элементов это не 450мс, а 1млрд. миллисекунд, т. е., 11 дней! Дело в том, что время работы двоичного и простого поиска возрастает не одинаково.

    Как возрастает время работы алгоритмов

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

    Так что Иуда ошибся, предполагая, что двоичный поиск всегда в 15 раз быстрее простого. Если брать список с 1 миллиардом элементов, двоичный поиск будет уже примерно в 33 миллиона раз быстрее простого.

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

    «О» большое говорит вам, насколько быстр ваш алгоритм. Предположим, у вас есть список с размером n (т. е., у вас n элементов в этом списке). Простому поиску нужно проверить каждый элемент, поэтому ему понадобится произвести n операций. Время работы этого алгоритма, записанное при помощи нотации «О» большого, составляет O(n).

    Где же, собственно, время? Где секунды? Здесь их нет. «О» большое не сообщает вам скорость в секундах. Эта нотация позволяет вам сравнивать количество необходимых операций. Она говорит вам о том, как быстро возрастает скорость работы алгоритма.

    Давайте рассмотрим еще один пример. Двоичному поиску для проверки списка из n элементов нужно осуществить log n операций. Каково время работы алгоритма, записанное в нотации «О» большого? O(log n). В общем, принцип записи следующий:

    Нотация

    Эта запись сообщает вам количество операций, которое осуществит алгоритм. Называется все это нотацией ««О» большое», потому что перед количеством операций ставится заглавная буква «О».

    «О» большое описывает количество операций при наихудшем сценарии

    Поиск пользователей

    Предположим, вы ищете пользователя в своей базе данных и при этом применяете алгоритм простого поиска. Вы знаете, что его скорость — O(n), то есть, в наихудшем случае вашему алгоритму придется проверить каждого пользователя в вашей базе данных. Но допустим, вы ищете пользователя с именем aardvark213, а он стоит первым в списке. Вашему алгоритму не придется проверять каждый элемент списка, потому что он найдет нужного пользователя с первой попытки. Итак, время, которое потребовалось алгоритму, это O(n) или O(1)? Ведь он нашел нужного пользователя с первой же попытки?

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

    Самые распространенные варианты «О» большого

    Вот пять вариантов «О» большого, которые встречаются чаще всего. Они отсортированы от самого быстрого к самому медленному:

    • O(log n) — логарифмическое время. Пример: двоичный поиск.
    • O(n) — линейное время. Пример: простой поиск.
    • O(n * log n). Пример: быстрый алгоритм сортировки, такой как quicksort (быстрая сортировка).
    • O(n2) — квадратичное время. Пример: медленный алгоритм сортировки, такой как сортировка выбором.
    • O(n!) — факториальное время. Пример: очень медленный алгоритм, такой как в задаче коммивояжера.

    Визуализация разного времени в нотации «О» большого

    Сетка из 16 ячеек

    Предположим, вам нужно нарисовать сетку с 16 ячейками и вы можете выбрать для этого 5 разных алгоритмов (из списка выше).

    Первый алгоритм займет O(log n) времени. Вы можете осуществлять 10 операций в секунду. Чтобы нарисовать сетку из 16 ячеек, при времени O(log n) вам понадобится осуществить 4 операции (log 16 с основанием 2 это 4). То есть, у вас на это уйдет 0,4с. Что, если нужно нарисовать 1024 ячеек? На это потребуется log 1024 = 10 операций, т. е., 1с. Это первый алгоритм.

    Второй алгоритм медленнее, его время выполнения O(n). Чтобы нарисовать 16 ячеек, понадобится 16 операций, а чтобы нарисовать 1024 ячейки — 1024 операции. Сколько это в секундах?

    На графиках вы можете увидеть скорость всех алгоритмов, от самого быстрого до самого медленного:

    Графики, иллюстрирующие скорость алгоритмов

    Есть и другие варианты времени выполнения алгоритмов, но эти встречаются чаще всего.

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

    Заключение

    Вот основные вещи, которые нужно усвоить:

    • Скорость алгоритма измеряется не в секундах, а в приросте количества операций.
    • Мы говорим о том, как быстро возрастает время работы алгоритма в зависимости от увеличения объема входящих данных.
    • Время работы алгоритма выражается при помощи нотации большого «О».
    • Алгоритм со скоростью O(log n) быстрее, чем со скоростью O(n), но он становится намного быстрее по мере увеличения списка элементов.
  • Добавить комментарий

    Ваш адрес email не будет опубликован. Обязательные поля помечены *