Rivalry2

HTML Diff

0 added 0 removed

Original 2026-01-01

Modified 2026-02-21

1 <a>#статьи</a>

2 <ul><li>18 янв 2022</li>

3 <li>0</li>

4 </ul>Software Engineer Валерий Жила подробно рассказал, что такое O(n), и показал, как её считать на примере бинарного поиска и других алгоритмов.

5 Кадр: фильм "Мальчишник в Вегасе"

6 Онлайн-журнал для тех, кто влюблён в код и информационные технологии. Пишем для айтишников и об айтишниках.

7 Валерий Жила

8 об эксперте

9 Software Engineer, разрабатывает системы управления городской инфраструктурой для мегаполисов. Основная деятельность: backend, database engineering. Ведёт твиттер<a>@ValeriiZhyla</a>и пишет научные работы по DevOps.

10 Сегодня я расскажу о сложности алгоритмов, или, как её часто называют, Big O Notation. Статья рассчитана на новичков, поэтому постараюсь изложить идеи и концепции просто, не теряя важных деталей.

11 <a>Алгоритмы</a>описывают с помощью двух характеристик -времении памяти.

12 Время - это… время, которое нужно алгоритму для обработки данных. Например, для маленького массива - 10 секунд, а для массива побольше - 100 секунд. Интуитивно понятно, что время выполнения алгоритма зависит от размера массива.

13 Но есть проблема: секунды, минуты и часы - это не очень показательные единицы измерения. Кроме того, время работы алгоритма зависит от железа, на котором он выполняется, и других внешних факторов. Поэтому время считают не в секундах и часах, а в количестве операций, которые алгоритм совершит. Это надёжная и, главное, независимая от железа метрика.

14 Когда говорят о Time Complexityили простоTime, то речь идёт именно о количестве операций. Для простоты расчётов разница в скорости между операциями обычно опускается. Поэтому, несмотря на то, что деление чисел с плавающей точкой требует от процессора больше действий, чем сложение целых чисел, обе операции в теории алгоритмов считаются равными по сложности.

15 Запомните: в О-нотации на операции с одной или двумя переменными вродеi++,a * b,a / 1024,max(a,b)уходит всего одна единица времени.

16 Память, или место, - это объём оперативной памяти, который потребуется алгоритму для работы. Одна переменная - это одна ячейка памяти, а массив с тысячей ячеек - тысяча ячеек памяти.

17 В теории алгоритмов все ячейки считаются равноценными. Например, int a на 4 байта и double b на 8 байт имеют один вес. Потребление памяти обычно называетсяSpace Complexityили простоSpace, редко -Memory.

18 Алгоритмы, которые используют исходный массив как рабочее пространство, называютin-place. Они потребляют мало памяти и создают одиночные переменные - без копий исходного массива и промежуточных структур данных. Алгоритмы, требующие дополнительной памяти, называютout-of-place. Прежде чем использовать алгоритм, надо понять, хватит ли на него памяти, и если нет - поискать менее прожорливые альтернативы.

19 Статья написана на основе<a>треда</a>Валерия в его аккаунте в Twitter. Автор благодарит<a>@usehex</a>за помощь в создании материала.

20 Давайте вспомним 8-й класс и разберёмся: что значит записьO(n)с математической точки зрения. При расчёте Big O Notation используют два правила:

21 Константы откидываются.Нас интересует только часть формулы, которая зависит от размера входных данных. Проще говоря, это само число n, его степени,<a>логарифмы, факториалы и экспоненты</a>, где число находится в степени n.

22 Примеры:

23 O(3n) = O(n)

24 O(10000 n^2) = O(n^2)

25 O(2n * log n) = O(n * log n)

26 Если в O есть сумма, нас интересует самое быстрорастущее слагаемое.Это называется асимптотической оценкой сложности.

27 Примеры:

28 O(n^2 + n) = O(n^2)

29 O(n^3 + 100n * log n) = O(n^3)

30 O(n! + 999) = O(n!)

31 O(1,1^n + n^100) = O(1,1^n)

32 У каждого алгоритма есть худший, средний и лучшийсценарииработы - в зависимости от того, насколько удачно выбраны входные данные. Часто их называютслучаями.

33 Худший случай (worst case) - это когда входные данные требуют максимальных затрат времени и памяти.

34 Например, если мы хотим отсортировать массив по возрастанию (Ascending Order, коротко ASC), то для простых алгоритмов сортировки худшим случаем будет массив, отсортированный по убыванию (Descending Order, коротко DESC).

35 Для алгоритма поиска элемента в неотсортированном массиве worst case - это когда искомый элемент находится в конце массива или если элемента нет вообще.

36 Лучший случай(best case) - полная противоположность worst case, самые удачные входные данные. Правильно отсортированный массив, с которым алгоритму сортировки вообще ничего делать не нужно. В случае поиска - когда алгоритм находит нужный элемент с первого раза.

37 Средний случай(average case) - самый хитрый из тройки. Интуитивно понятно, что он сидит между best case и worst case, но далеко не всегда понятно, где именно. Часто он совпадает с worst case и всегда хуже best case, если best case не совпадает с worst case. Да, иногда они совпадают.

38 Как определяют среднийслучай? Считают статистически усреднённый результат: берут алгоритм, прокручивают его с разными данными, составляют сводку результатов и смотрят, вокруг какой функции распределились результаты. В общем, расчёт average case - дело сложное. А мы приступаем к конкретным алгоритмам.

39 Начнём с самого простого алгоритма -линейного поиска, он жеlinear search. Дальнейшее объяснение подразумевает, что вы знаете, что такое числа и как устроены массивы. Напомню, это всего лишь набор проиндексированных ячеек.

40 Допустим, у нас есть массив целых чиселarr, содержащий n элементов. Вообще, количество элементов, размер строк, массивов, списков и графов в алгоритмах всегда обозначают буквойnилиN. Ещё дано целое числоx. Для удобства обусловимся, чтоarrточно содержитx.

41 Задача:найти, на каком месте в массивеarrнаходится элемент3, и вернуть его индекс.

42 Фото: Валерий Жила для Skillbox MediaМеткий человеческий глаз сразу видит, что искомый элемент содержится в ячейке с индексом 2, то есть в arr[2]. А менее зоркий компьютер будет перебирать ячейки друг за другом:arr[0], arr[1]… и так далее, пока не встретит тройку или конец массива, если тройки в нём нет.

43 Теперь разберём случаи:

44 Worst case.Больше всего шагов потребуется, если искомое число стоит в конце массива. В этом случае придётся перебрать все n ячеек, прочитать их содержимое и сравнить с искомым числом. Получается, worst case равенO(n). В нашем массиве худшему случаю соответствуетx = 2.

45 Best case.Если бы искомое число стояло в самом начале массива, то мы бы получили ответ уже в первой ячейке. Best case линейного поиска -O(1). Именно так обозначается константное время в Big O Notation. В нашем массиве best case наблюдается приx = 7.

46 Average case.В среднем случае результаты будут равномерно распределены по массиву. Средний элемент можно рассчитать по формуле (n + 1) / 2, но так как мы отбрасываем константы, то получаем простоn.Значит, average case равенO(n). Хотя иногда в среднем случае константы оставляют, потому что запись O(n / 2) даёт чуть больше информации.

47 Хорошо, мы уже три минуты обсуждаем linear search, но до сих пор не видели кода. Потерпите, скоро всё будет. Но сперва познакомимся с очень полезным инструментом -псевдокодом.

48 Разработчики пишут на разных языках программирования. Одни похожи друг на друга, а другие - сильно различаются. Часто мы точно знаем, какую операцию хотим выполнить, но не уверены в том, как она выглядит в конкретном языке.

49 Возьмём хотя бы получение длины массива. По историческим причинам практически во всех языках эта операция называется по-разному:.length, length(), len(), size(), .size - попробуй угадай! Как же объяснить свой код коллегам, которые пишут на другом языке? Написать программу на псевдокоде.

50 Псевдокод - достаточно формальный, но не слишком требовательный к мелочам инструмент для изложения мыслей, не связанный с конкретным языком программирования.

51 Прелесть псевдокода в том, что конкретных правил для его написания нет. Я, например, предпочитаю использовать смесь синтаксиса Python и C: обозначаю вложенность с помощью отступов и называю методы в стиле Python.

52 А вот и пример псевдокода для нашей задачи, со всеми допущениями и упрощениями. Метод должен возвращать -1, еслиarrпуст или не содержитx:

53 int linear_search(int[] arr, int x): if arr is empty: return -1 for i in 0..n: if (arr[i] == x): return i return -1 //x was not foundВ псевдокоде часто используют -1 в качестве invalid index, а если алгоритм возвращает объекты - null, nil (то же самое, что и null) или специальный символ "ничего", похожий на перевёрнутую букву "т". Также встречаются конструкции для исключений, вроде throw error ("Very Bad").

54 Уметь писать псевдокод полезно. Например, с его помощью можно решать задачи на доске на технических собеседованиях. Я пишу код на бумаге и доске почти так же, как в компьютере, но ещё явно выделяю отступы - иначе строчки кода разъезжаются куда глаза глядят:

55 Фото: Валерий Жила для Skillbox MediaСледующая остановка -binary search, он жебинарный,илидвоичный, поиск.

56 В чём отличие бинарного поиска от уже знакомого линейного? Чтобы его применить, массивarrдолжен быть отсортирован. В нашем случае - по возрастанию.

57 Часто binary search объясняют на примере с телефонным справочником. Возможно, многие читатели никогда не видели такую приблуду - это большая книга со списками телефонных номеров, отсортированных по фамилиям и именам жителей. Для простоты забудем об именах.

58 Итак, есть огромный справочник на тысячу страниц с десятками тысяч пар "фамилия - номер", отсортированных по фамилиям. Допустим, мы хотим найти номер человека по фамилии Жила. Как бы мы действовали в случае с линейным поиском? Открыли бы книгу и начали её перебирать, строчку за строчкой, страницу за страницей: Астафьев… Безье… Варнава… Ги… До товарища Жилы он дошёл бы за пару часов, а вот господин Янтарный заставил бы алгоритм попотеть ещё дольше.

59 Бинарный поиск мудрее и хитрее. Он открывает книгу ровно посередине и смотрит на фамилию, например Мельник - буква "М". Книга отсортирована по фамилиям, и алгоритм знает, что буква "Ж" идёт перед "М".

60 Алгоритм "разрывает" книгу пополам и выкидывает часть с буквами, которые идут после "М": "Н", "О", "П"… "Я". Затем открывает оставшуюся половинку посередине - на этот раз на фамилии Ежов. Уже близко, но Ежов не Жила, а ещё буква "Ж" идёт после буквы "Е". Разрываем книгу пополам, а левую половину с буквами от "А" до "Е" выбрасываем. Алгоритм продолжает рвать книгу пополам до тех пор, пока не останется единственная измятая страничка с заветной фамилией и номером.

61 Перенесём этот принцип на массивы. У нас есть отсортированный массивarrи число 7, которое нужно найти. Почему поиск называется бинарным? Дело в том, что алгоритм на каждом шаге уменьшает проблему в два раза. Он буквально отрезает на каждом шаге половинуarr, в которой гарантированно нет искомого числа.

62 Фото: Валерий Жила для Skillbox MediaНа каждом шаге мы проверяем только середину. При этом есть три варианта развития событий:

63 <ul><li>попадаем в 7 - тогда проблема решена;</li>

64 <li>нашли число меньше 7 - отрезаем левую половину и ищем в правой половине;</li>

65 <li>нашли число больше 7 - отрезаем правую половину и ищем в левой половине.</li>

66 </ul>Почему это работает? Вспомните про требование к отсортированности массива, и всё встанет на свои места.

67 Итак, смотрим в середину. Карандаш будет служить нам указателем.

68 Фото: Валерий Жила для Skillbox MediaВ середине находится число 5, оно меньше 7. Значит, отрезаем левую половину и проверенное число. Смотрим в середину оставшегося массива:

69 Фото: Валерий Жила для Skillbox MediaВ середине число 8, оно больше 7. Значит, отрезаем правую половинку и проверенное число. Остаётся число 7 - как раз его мы и искали. Поздравляю!

70 Фото: Валерий Жила для Skillbox MediaТеперь давайте попробуем записать это в виде красивого псевдокода. Как обычно, назовём середину mid и будем перемещать "окно наблюдения", ограниченное двумя индексами -low(левая граница) и high(правая граница).

71 int binary_search(int [] arr, int low, int high, int x): if high >= low: mid = round_down((low + high)/2) if arr[mid] == x: // check middle element return mid else if arr[mid] > x: // recursive check left hals return binary_search(arr, low, mid-1, x) else: // recursive check right half return binary_search(arr, mid+1, high, x) else: return -1 // x was not foundАлгоритм организован рекурсивно, то есть вызывает сам себя на строках 7 и 9. Есть итеративный вариант с циклом, без рекурсии, но он кажется мне уродливым. Если не находим искомый элемент, возвращаем -1. В начале работы алгоритма значениеlowсовпадает с началом массива, а high - с его концом. И они бегут навстречу друг другу…

72 Чтобы запускать алгоритм, не задумываясь о начальных значениях индексовlowи high, можно написать такую функцию-обёртку:

73 int binary_search(int [] arr, int x): if arr_is_empty: return -1 lower_bound == 0 upper_bound == arr.length -1 return binary_search(arr, lower_bound, upper_bound, x)Посчитаем сложность бинарного поиска:

74 Best case.Как и у линейного поиска, лучший случай равенO(1), ведь искомое число может находиться в середине массива, и тогда мы найдём его с первой попытки.

75 Worst case.Чтобы найти худший случай, нужно ответить на вопрос: "Сколько раз нужно разделить массив на 2, чтобы в нём остался один элемент?" Или найти минимальное числоk, при котором справедливо2^k ≥ n.

76 Надеюсь, что большинство читателей смогут вычислитьk. Но на всякий случай подскажу решение:k = log nпо основанию 2 (в алгоритмах практически все логарифмы двоичные). Поэтому worst case бинарного поиска - O(log n).

77 Average case.Он тоже равенO(log n). И если для линейного поиска average case в два раза лучше, чем worst case, то тут они обычно отличаются всего на несколько шагов.

78 Часто студенты спрашивают: "Зачем нужен линейный поиск, если бинарный обходит его по всем позициям?" Отвечаю: линейный поиск работает с любыми массивами, а бинарный - только с отсортированными.

79 Мы дошли до важного принципа: чем сложнее структура данных, тем более быстрые алгоритмы к ней можно применять. Отсортированный массив - более сложная структура, чем неотсортированный. Забегу вперёд и скажу, что сортировка в общем случае требует от O(n * log(n))до O(n^2)времени.

80 Создать дополнительные структуры данных несложно, вот только это не бесплатное удовольствие. Они едят много памяти. Как правило,O(n).Отсюда вытекает довольно логичный, но обидный вывод: время и память - "взаимообмениваемые" ресурсы. Алгоритм можно ускорить, пожертвовав памятью, или решать задачу медленно, зато in-place. Кроме того, почти всегда есть промежуточный вариант.

81 Решить одну и ту же проблему зачастую можно тремя способами. Задача разработчика - выбрать самый подходящий.

82 Мы рассмотрели два алгоритма и увидели примеры их сложности. Но так и не поговорили о том, как эту сложность определять. Есть три основных способа.

83 Первый и наиболее часто используемый способ. Именно так мы определяли сложность linear search и binary search. Обобщим эти примеры.

84 Первый случай.Есть алгоритмsome_function, который выполняет действиеА, а после него - действиеВ. На Аи ВнужноKи Jопераций соответственно.

85 int some_function(): action_A() // K operations action_B() // J operationsВ случае последовательного выполнения действий сложность алгоритма будет равнаO(K + J), а значит,O(max (K, J)). Например, еслиАравноn^2, а В -n, то сложность алгоритма будет равнаO(n^2 + n). Но мы уже знаем, что нас интересует только самая быстрорастущая часть. Значит, ответ будетO(n^2).

86 Второй случай.Посчитаем сложность действий или вызова методов в циклах. Размер массива равенn, а над каждым элементом будет выполнено действиеА (n раз).А дальше всё зависит от "содержимого"A.

87 Посчитаем сложность бинарного поиска:

88 int some_function(int [] arr): n = arr.length for i in 0..n: action_A() // K operationsЕсли на каждом шагеAработает с одним элементом, то, независимо от количества операций, получим сложностьO(n). Если жеAобрабатываетarrцеликом, то алгоритм совершит n операций n раз. Тогда получимO(n *n) = O(n^2). По такой же логике можно получить O(n * log n), O(n^3) и так далее.

89 Третий случай - комбо.Для закрепления соединим оба случая. Допустим, действиеАтребуетlog(n)операций, а действиеВ -nопераций. На всякий случай напомню: в алгоритмах всегда идёт речь о двоичных логарифмах.

90 Добавим действиеСс пятью операциями и вот что получим:

91 int some_function(int [] arr): n = arr.length for i in 0..n: for j in 0..n: action_A(arr) // log(n) operations action_B(arr) // n operations action_C() // 5 operationsO(n * (n * log(n) + n) + 5) = O(n^2 * log(n) + n^2 + 5) = O(n^2 * log(n)).

92 Мы видим, что самая дорогая часть алгоритма - действиеА, которое выполняется во вложенном цикле. Поэтому именно оно доминирует в функции.

93 Есть разновидность определения на глаз - амортизационный анализ. Это относительно редкий, но достойный упоминания гость. В двух словах его можно объяснить так: если на X"дешёвых" операций (например, с O(1)) приходится одна "дорогая" (например, с O(n)), то на большом количестве операций суммарная сложность получится неотличимой от O(1).

94 Частый пациент амортизационного анализа -динамический массив. Это массив, который при переполнении создаёт новый, больше оригинального в два раза. При этом элементы старого массива копируются в новый.

95 Практически всегда добавление элементов в такой массив "дёшево" - требует лишь одной операции. Но когда он заполняется, приходится тратить силы: создавать новый массив и копироватьNстарых элементов в новый. Но так как массив каждый раз увеличивается в два раза, переполнения случаются всё реже и реже, поэтому average case добавления элемента равенO(1).

96 Слабое место прикидывания на глаз - рекурсия. С ней и правда приходится тяжко. Поэтому для оценки сложности рекурсивных алгоритмов широко используют<a>мастер-теорему</a>.

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

98 <a>Метод Монте-Карло</a>применяют довольно редко - только если первые два применить невозможно. Особенно часто с его помощью описывают производительность систем, состоящих из множества алгоритмов.

99 Суть метода: берём алгоритм и гоняем его на случайных данных разного размера, замеряем время и память. Полученные измерения выкладываем на отдельные графики для памяти и времени. А затем автоматически вычисляется функция, которая лучше всего описывает полученное облако точек.

100 На протяжении всей статьи мы говорили про Big O Notation. А теперь сюрприз: это только одна из пяти существующих нотаций. Вот они слева направо: Намджун, Чонгук, Чингачгук… простите, не удержался. Сверху вниз:Small o,Big O,Big Theta,Big Omega,Small omega.f - это реальная функция сложности нашего алгоритма, а g - асимптотическая.

101 Пять нотаций в математическом представлении. Фото: Валерий Жила для Skillbox MediaНесколько слов об этой весёлой компании:

102 <ul><li>Big Oобозначает верхнюю границу сложности алгоритма. Это идеальный инструмент для поиска worst case.</li>

103 <li>Big Omega(которая пишется как подкова) обозначает нижнюю границу сложности, и её правильнее использовать для поиска best case.</li>

104 <li>Big Theta(пишется как О с чёрточкой) располагается между О и омегой и показывает точную функцию сложности алгоритма. С её помощью правильнее искать average case.</li>

105 <li>Small oиSmall omegaнаходятся по краям этой иерархии и используются в основном для сравнения алгоритмов между собой.</li>

106 </ul>"Правильнее" в данном контексте означает - с точки зрения математических пейперов по алгоритмам. А в статьях и рабочей документации, как правило, во всех случаях используют "Большое "О“".

107 Если хотите подробнее узнать об остальных нотациях, посмотрите<a>интересный видос</a>на эту тему. Также полезно понимать, как сильно отличаются скорости возрастания различных функций. Вот хороший<a>cheat sheet</a>по сложности алгоритмов и наглядная картинка с графиками оттуда:

108 <a>Сравнение</a>сложности алгоритмов. Скриншот: Валерий Жила для Skillbox MediaХоть картинка и наглядная, она плохо передаёт всю бездну, лежащую между функциями. Поэтому я склепал таблицу со значениями времени для разных функций и N. За время одной операции взял 1 наносекунду:

109 Источник: Валерий Жила. Таблица: Евгений Рыбкин / Skillbox MediaВ последнем разделе поговорим о скрытых константах. Это хитрая штука, там собака зарыта.

110 Возьмём умножение матриц. При размерности матрицы n * n наивный алгоритм, который многие знают с начальных курсов универа, "строчка на столбик" имеет кубическую временную сложностьO(n^3). Кубическая, зато честная. Без констант и O(10000*n^3)под капотом. И памяти не ест - только время.

111 У Валерия есть отдельный<a>тред</a>об умножении матриц.

112 В некоторых алгоритмах умножения матриц степеньnсильно "порезана". Самые "быстрые" из них выдают время околоO(n^2,37). Какой персик, правда? Почему бы нам не забыть про "наивный" алгоритм?

113 Проблема в том, что у таких алгоритмов огромные константы. В пейперах гонятся за более компактной экспонентой, а степени отбрасываются. Я не нашёл внятных значений констант. Даже авторы оригинальных пейперов называют их просто "очень большими".

114 Давайте от балды возьмём не очень большую константу 100 и сравнимn^3c 100 * n^2,37. Правая функция даёт выигрыш по сравнению с левой для n, начинающихся с 1495. А ведь мы взяли довольно скромную константу. Подозреваю, что на практике они не в пример больше…

115 В то же время умножение матриц 1495 × 1495 - очень редкий случай. А матрицы миллиард на миллиард точно нигде не встретишь. Да простит меня Император Душнил с "Хабра" за вольное допущение :)

116 Такие алгоритмы называются галактическими, потому что дают выигрыш только на масштабах, нерелевантных для нас. А в программном умножении матриц, если я правильно помню курс алгоритмов и умею читать "Википедию", очень любят алгоритм Штрассена с егоO(2,807)и маленькими константами. Но и те, к сожалению, жрут слишком много памяти.

117 <a>Бесплатный курс по Python ➞Мини-курс для новичков и для опытных кодеров. 4 крутых проекта в портфолио, живое общение со спикером. Кликните и узнайте, чему можно научиться на курсе. Смотреть программу</a>