В программировании используются алгоритмы, которые по-разному решают одну и ту же задачу: например, сортировку массива. При этом алгоритмы работают с разной скоростью и требуют разное количество памяти. При прочих равных условиях мы бы выбрали быстрый или нетребовательный алгоритм.
Чтобы правильно выбирать алгоритмы, нужно научиться сравнивать их, чем мы и займемся в этом уроке. Мы познакомимся с двумя основными способами, разберем их плюсы и минусы. Опираясь на эти способы, мы сравним время работы уже знакомых нам алгоритмов.
Как оценить скорость алгоритма
Скорость алгоритмов можно сравнивать самым очевидным способом — физически измерить время выполнения на одних и тех же данных. Чтобы сравнить сортировку выбором и быструю сортировку, мы можем взять массив из нескольких элементов и измерить время быстрой сортировки:
Алгоритм быстрой сортировки мы уже разбирали. Единственное, что нам пока не встречалось — вызов метода performance.now().
Performance — это объект в глобальной области видимости, который используют для измерения производительности. Метод now() возвращает количество миллисекунд с момента старта браузера. Можно запустить этот метод, сохранить значения до запуска кода и после его завершения, и вычесть одно из другого — и тогда мы узнаем, сколько миллисекунд работал наш код.
Чтобы сравнить два алгоритма, надо упорядочить точно такой же массив с помощью алгоритма выбора:
Оценим скорость кода выше:
- Быстрая сортировка — 0,20 миллисекунд
- Сортировка выбором — 0,09 миллисекунд
Результат выглядит странно. Раз уж быструю сортировку назвали быстрой, то время ее выполнения должно быть меньше, чем у сортировки выбором. Здесь дело в том, что результаты однократного измерения ненадежны. Нужно измерить производительность алгоритмов несколько раз подряд на одних и тех же данных. Можем получить такой результат:
- Быстрая сортировка — 0,21 миллисекунда
- Сортировка выбором — 0,12 миллисекунд
Или даже такой:
- Быстрая сортировка — 0,16 миллисекунд
- Сортировка выбором — 0,17 миллисекунд
Разброс может быть достаточно большим. Дело в том, что на производительность нашей программы влияет множество случайных факторов: другие запущенные программы на компьютере, режим энергосбережения и так далее.
В работе алгоритмов много перечисленных тонкостей, поэтому сравнивать скорости довольно трудно. Чтобы справиться с этой трудностью, используем статистические методы. Будем запускать одну и ту же функцию много раз, а затем разделим общее время выполнения на количество запусков, чтобы вычислить среднее время выполнения:
Возможно вы не знакомы с конструкцией [...items], которая встречается в этом коде. Она позволяет сделать копию массива items. Без копии мы при первом же вызове функции selectionSort упорядочим массив items, и последующие вызовы будут измерять скорость сортировки уже упорядоченного массива.
У функции averagePerformance два параметра:
- Функция, чью производительность мы хотим измерить
- Количество раз, когда мы хотим ее запустить
Мы видим, что среднее время выполнения может заметно отличаться от времени, измеренного один раз — на 30% в нашем случае. Значит ли это, что теперь у нас в руках есть надежный способ сравнения алгоритмов? Кажется, что да. Но мы пока так и не выяснили, почему быстрая сортировка такая медленная по сравнению с сортировкой выбором.
Продолжим искать причину и сравним время выполнения разных сортировок на массиве из ста элементов:
На большом массиве быстрая сортировка оказывается в три раза быстрее, чем сортировка выбором! Как такое может быть? Конечно, у этой странности есть объяснение, мы обсудим его чуть позже. Сейчас обратим внимание, что измерения скорости алгоритма на одних данных ничего не говорит об его скорости на других данных.
Мы можем с большой точностью оценить время работы алгоритма на массиве из десяти элементов и при этом мы совершенно не представляем, какой окажется скорость того же алгоритма на массиве из ста тысяч элементов. Именно поэтому перед программистами встала задача — научиться оценивать скорость алгоритмов в целом.
Оценка скорости алгоритмов «в целом»
Идея оценки «в целом» пришла к нам из математики, где есть похожая задача — нужно оценивать порядок роста функций. Математики могут точно рассчитать скорость возрастания функции в любой точке, но эта информация может оказаться не очень полезной. Сравним графики двух функций:
Кажется, что синяя функция больше, чем, красная. Но если посмотреть на те же графики в другом масштабе, картина изменится:
Красная функция растет гораздо быстрее и почти сразу становится больше синей. С алгоритмами возникает та же проблема: на одном наборе данных первый алгоритм физически будет быстрее второго, на многих других наборах он может оказаться гораздо медленнее. Синяя функция на графике — это прямая линия, а красная — это парабола.
Синие функции в математике принято называть линейными, а красные — квадратичными. Математики знают, что квадратичные функции растут быстрее линейных, а кубические — быстрее квадратичных.
Алгоритмическая сложность тоже бывает линейной, квадратичной и кубической. Для нее характерна та же самая зависимость: алгоритмы с квадратичной сложностью в целом работают медленнее алгоритмов с линейной сложностью. Рассмотрим несколько алгоритмов и разберемся, как определять временную сложность.
Линейная сложность
Чтобы определить временную сложность алгоритма, программисты ставят мысленный эксперимент. Предположим, что мы точно измерили время работы алгоритма на одном массиве, а потом увеличили этот массив в десять раз. Как увеличится время работы алгоритма? Если время работы алгоритма также увеличится в десять раз, то речь идет о линейной сложности — на графике она бы описывалась прямой линией.
Типичный линейный алгоритм — поиск минимального элемента в массиве:
Это простой алгоритм. Мы просматриваем элементы массива по одному и сравниваем с уже найденным. Если новый элемент оказывается меньше минимума, он становится новым минимумом. В самом начале в качестве минимума выбираем самый первый элемент массива с индексом 0. Функция состоит из двух смысловых элементов. Первый элемент — инициализация:
Второй элемент — это цикл:
Если в массиве 10 элементов, цикл выполнится 9 раз, если 100 элементов — 99 раз, если n элементов, цикл выполнится n-1 раз. В итоге, для массива из n элементов функция выполнит n операций — одну операцию инициализации и n-1 операций в цикле. Если увеличить размер массива в 10 раз, то количество элементов будет равно 10*n, и количество операций также будет равно 10*n, то есть тоже вырастет в 10 раз.
Такая линейная временная сложность обозначается O(n). Из-за того, что в записи используется большая буква O, она называется «нотация О-большое». Буква O появилась здесь не случайно. Это первая буква немецкого слова Ordnung, которое означает порядок. В математике, откуда пришло обозначение, оно относится к порядку роста функций.
Какие еще алгоритмы имеют линейную временную сложность? Например, алгоритм вычисления среднего арифметического:
Анализ алгоритма показывает, что для массива из n элементов будет n+1 операция: одна инициализация плюс n операций в цикле. Кажется, что такая временная сложность должна записываться O(n+1). Однако такие варианты, как n-2, n+5 и даже n+1000, всегда записывают как O(n). На первый взгляд это кажется странным, но далее мы разберемся, почему это так. А пока рассмотрим еще один линейный алгоритм — алгоритм определения строк-палиндромов.
Палиндромом называется строка, которая одинаково читается слева направо и справа налево. АНА и ABBA — это палиндромы, а YES и nO — нет:
В этом алгоритме цикл выполняется n/2 раз, где n — длина строки. Казалось бы, сложность работы алгоритма должна быть равна O(n/2). Но, как и в прошлый раз, это не так. Алгоритмы со временем работы 2n, 10n, n/5 и n/32 — все имеют сложность O(n), и снова это кажется странным.
Квадратичная сложность
Квадратичную сложность имеют все простые алгоритмы сортировки. Рассмотрим, например, сортировку выбором. Внутри нее есть вложенный цикл.
Чтобы избавиться от несущественных деталей, в коде выше убрана часть операций — вместо них пустые комментарии. Попробуем оценить количество выполнений цикла. На первом шаге внешнего цикла внутренний выполнится на один раз меньше, чем общее количество элементов, на втором — на два раза меньше, на третьем — на три раза меньше и так далее.
Суммарное количество выполнений цикла можно выразить как сумму чисел от 1 до n-1. Эта сумма равна половине произведения количества элементов на количество элементов минус один. Таким образом, общее количество операций пропорционально квадрату количества элементов.
Для расчетов мы использовали формулу суммы членов арифметической прогрессии. Среди слагаемых есть компонент, который растет как квадрат количества элементов, так что речь идет о квадратичной сложности, которая записывается как O(n^2). И снова встает вопрос: почему мы игнорируем деление на два и вычитаемое? Настало время разобраться.
Как мы уже говорили, алгоритмическая сложность позволяет сравнивать алгоритмы «в целом». Можно утверждать, что все линейные алгоритмы в целом быстрее всех квадратичных, хотя на конкретных данных возможны аномалии. Все квадратичные алгоритмы в целом быстрее всех кубических.
К сожалению, сравнивая два линейных алгоритма, мы не можем сказать, какой из них быстрее. Есть соблазн использовать запись вида O(4n+1) или O(2n-3), но она толкает нас на путь ложных выводов. Определяя алгоритмическую сложность, мы считаем количество операций и предполагаем, что все они выполняются за небольшое постоянное время.
Но как только речь заходит о конкретике, выясняется, что операция сложения может быть очень быстрой, а операция деления — очень медленной по сравнению со сложением. Иногда четыре сложения могут выполниться быстрее, чем два деления. Поэтому нельзя в общем случае утверждать, что O(2n - 3) быстрее, чем O(4n + 1).
Именно поэтому программисты и математики избавляются от деталей в нотации O-большое. Записи вида O(2n-3), O((n^2)/3)+5) и O(20(n^4)-1000) превращаются в O(n), O(n^2) и O(n^4) соответственно.
Какая еще бывает сложность
Теоретически мы можем придумать алгоритмы с любой экзотической сложностью, но на практике чаще встречается всего несколько вариантов.
Константная сложность
Она обозначается O(1). Алгоритмы с константной временной сложностью выполняются за одно и то же время вне зависимости от количества элементов. Например, в упорядоченном массиве минимальный элемент всегда находится в самом начале, поэтому поиск минимума становится тривиальным:
Эта функция всегда выполняется за одно и то же время, независимо от размера массива sortedItems. Формально, константные алгоритмы считаются самыми быстрыми.
Логарифмическая сложность
Обозначается O(logn). За логарифмическое время работает алгоритм бинарного поиска. Эти алгоритмы относятся к быстрым, поскольку логарифмическая функция растет достаточно медленно.
В массиве из тысячи элементов бинарный поиск работает максимум за десять сравнений, а массиве из миллиона — максимум за двадцать. Обычный метод перебора имеет линейную сложность, и поэтому будет работать за тысячу и миллион сравнений соответственно:
Логарифмические алгоритмы считаются очень быстрыми, гораздо быстрее линейных.
Линейно-логарифмическая сложность
Она обозначается как O(nlogn) и описывает сложность алгоритма быстрой сортировки. Сравним количество операций у быстрой сортировки и сортировки выбором — так мы увидим, почему быстрая сортировка так называется:
Быстрая сортировка упорядочивает массив из тысячи элементов приблизительно за десять тысяч операций, в то время как сортировка выбором — за миллион. Время выполнения различается в сто раз, и с ростом n разница только растет! Но важно не забывать, что на очень маленьких массивах (из десяти элементов) сортировка выбором может оказаться быстрее. Так происходит потому, что алгоритм сортировки выбором проще. Быстрая сортировка сложнее, и накладные расходы в реализации оказываются слишком велики для небольшого набора данных.
Линейно-логарифмическая сложность медленнее линейной, но быстрее квадратичной.
Экспоненциальная сложность
Сколько подмассивов можно получить из массива [1, 2, 3, 4]? Попробуем выяснить, но сначала определимся с условиями:
- Подмассивы могут быть любой длины, включая ноль
- Будем считать одним подмассивом все подмассивы, состоящие из одних и тех же элементов в разном порядке (например, [1,2] и [2,1])
Выпишем все варианты и посчитаем их:
Всего 16. Существует общее правило, по которому возможное количество подмассивов у массива длины n составляет 2^n. Формулы вида 2^n, 3^n, 100^n называют экспонентами. Алгоритм, который может построить список всех подмассивов массива длины n, имеет экспоненциальную сложность O(2^n).
Алгоритмы экспоненциальной сложности считаются медленными. Количество подмассивов у массива из тридцати элементов равно 1073741824, то есть превышает миллиард!
Факториальная сложность
Обозначается O(n!). Факториалом числа n называют произведение 1 × 2 × ... × n, то есть всех чисел от 1 до n. Сложность алгоритма, который находит все перестановки массива, равна O(n!). Вот все перестановки массива [1, 2, 3, 4]:
Всего их 4!=24. Факториальная сложность самая медленная из тех, что мы рассмотрели. Если нам потребуется найти все перестановки массива из тридцати элементов, их окажется 265252859812191058636308480000000, то есть 265 миллионов миллионов миллионов миллионов миллионов. Даже на самом быстром современном компьютере поиск всех перестановок займет миллионы миллионов лет.
Сводная таблица временной сложности
Иногда в литературе можно встретить название полиномиальные алгоритмы — к ним относят алгоритмы со сложностью O(n^2), O(n^3) или O(n^100). Условная граница между медленными и быстрыми алгоритмами проходит между полиномиальными и экспоненциальными алгоритмами.
Оценка памяти
В нотации О-большое также оценивается память, которую потребляет алгоритм. На практике здесь редко встречаются большие значения.
Если алгоритму для работы нужно несколько переменных, которые не зависят от размеров данных, сложность по памяти составляет O(1). Такую сложность имеют алгоритмы поиска минимума и вычисления среднего арифметического.
Логарифмическая сложность O(log n) встречается у рекурсивных алгоритмов, которые разбивают массив на два подмассива. Среди рассмотренных нами алгоритмов к этому классу относятся бинарный поиск и быстрая сортировка.
Линейная сложность O(n) означает, что алгоритм во время работы сохраняет дополнительные данные, размер которых соизмерим с входными данными. Например, если мы хотим избавиться от дубликатов в массиве, мы можем хранить просмотренные элементы в структуре множество (Set):
Этих неповторяющихся элементов будет чуть меньше, чем элементов в исходном массиве. Но при этом размер множества будет соизмерим с размером массива, поэтому речь идет о линейной сложности по памяти.
Оптимизация
Одна из задач, которую регулярно решают программисты — оптимизация программы. Пользователи хотят, чтобы программа работала быстрее или занимала меньше памяти.
Неопытные программисты часто пытаются оптимизировать отдельные конструкции в программах, не обращая внимания на производительность в целом. Опытные же программисты оценивают сложность существующего алгоритма. Задача оптимизации сводится к тому, чтобы найти или придумать новый алгоритм с меньшей сложностью.
Разберем пример с определением простоты числа. Простые числа имеют важное значение в криптографии и кодировании, так что программистам время от времени нужен список простых чисел или функция, которая определяет, является ли число простым.
Определение простых чисел и звучит очень просто — простые числа делятся на себя и на единицу. Но проверить число на простоту уже сложнее — попробуйте, например, выяснить — простое ли число 1073676287?
Для определения простоты числа можно использовать один из самых древних, известных человечеству, алгоритмов — Решето Эратосфена. Сначала мы записываем список чисел, начиная с двойки:
Берем первое число — двойку. Выделяем цветом числа, которые делятся на нее. Саму двойку не выделяем:
Следующее неотмеченное число — три. Выделяем цветом числа, которые делятся на три, но не саму тройку:
Четверка зачеркнута — она делится на два, поэтому мы ее пропускаем.
Переходим к пятерке. У нас уже отмечены числа 10, 20 (оба делятся на два) и 15 (делится на три). Единственное неотмеченное число — это 25. Это подсказка, которая помогает понять одну важную мысль — чтобы составить список простых чисел вплоть до n, достаточно повторить эту процедуру только для чисел от 2 до sqrt(n).
Сама процедура выделения чисел на каждой итерации пробегает n чисел. Итого, выходит n чисел на итерацию и sqrt(n) итераций. Сложность алгоритма по времени равна O(n * sqrt(n)) или в более математической записи — O(n^(3/2)). При этом нам приходится выделять память для всех n чисел, поэтому сложность по памяти равна O(n).
Решето Эратосфена — сложный алгоритм, как по времени, так и по памяти.
Чтобы оптимизировать решение, мы должны найти или придумать другой алгоритм. Обратим внимание, что Решето строит список простых чисел от 2 до n, но нам нужно только последнее число n. Мы можем проверить, что число не делится ни на какие целые числа от 2 до n-1:
Этот алгоритм линейный по времени, он работает за O(n). Он константный по памяти, O(1), поскольку количество потребляемой памяти не зависит от n.
Он работает гораздо быстрее Решета, но все еще не самый оптимальный. Как мы помним, для проверки нам не обязательно делить n на все числа меньше себя, достаточно проверить только числа от 2 до sqrt(n), так что алгоритм можно переписать.
Алгоритмическая сложность переписанного алгоритма равна O(sqrt(n)) или O(n^(1/2)).
Выводы
- При общих равных условиях программисты выбирают самые быстрые и самые экономичные алгоритмы
- Выбрать самый быстрый алгоритм оказывается не так просто. Измерения на конкретных данных не позволяют прогнозировать время и память алгоритмов на других данных
- Программисты используют нотацию О-большое, чтобы оценить производительность алгоритмов в целом
- Чаще всего встречаются такие сложности, как константная, логарифмическая, линейная, линейно-логарифмическая, квадратическая, экспоненциальная и факториальная. В этом списке они распределены в порядке от самой быстрой к самой медленной
- Нотация О-большое оценивает не только скорость алгоритма, но и память, которую он использует
<!DOCTYPE html>
<html class="h-100" data-bs-theme="light" data-mantine-color-scheme="light" lang="ru" prefix="og: https://ogp.me/ns#">
<head>
<meta content="width=device-width, initial-scale=1.0" name="viewport">
<meta content="IE=Edge" http-equiv="X-UA-Compatible">
<link crossorigin="true" href="https://cdn.hexlet.io" rel="preconnect">
<link href="https://mc.yandex.ru" rel="preconnect">
<meta content="aa2vrdtq64dub8knuf83lwywit311w" name="facebook-domain-verification">
<link href="/favicon.ico" rel="icon" sizes="any">
<link href="/favicon.svg" rel="icon" type="image/svg+xml">
<link href="/apple-touch-icon.png" rel="apple-touch-icon">
<link href="/manifest.webmanifest" rel="manifest">
<script>
//<![CDATA[
window.gon={};gon.ym_counter="25559621";gon.is_bot=true;gon.applications={};gon.current_user={"id":null,"last_viewed_notification_id":null,"email":null,"state":null,"first_name":"","last_name":"","created_at":"2026-02-26 17:08:58 UTC","current_program":null,"current_team":null,"full_name":"","guest":true,"can_use_paid_features":false,"is_hexlet_employee":false,"sanitized_phone_number":"","can_subscribe":true,"can_renew_education":false};gon.token="LeQUyPLR85YBhCjtiSd1fdqU0h5usD7prJWTQz9fBzvCNd__AK9e9rfHDHWFKIUKGp3_tGaHwEsRdQkXbVjgVQ";gon.locale="ru";gon.language="ru";gon.theme="light";gon.rails_env="production";gon.mobile=false;gon.google={"analytics_key":"UA-1360700-51","optimize_key":"GTM-5QDVFPF"};gon.captcha={"google_v3_site_key":"6LenGbgZAAAAAM7HbrDbn5JlizCSzPcS767c9vaY","yandex_site_key":"ysc1_Vyob5ZPPUdPBsu0ykt8bVFdzsfpoVjQChLGl2b4g19647a89","verification_failed":null};gon.social_signin=false;gon.typoreporter_google_form_id="1FAIpQLSeibfGq-KvWQ2Fyru-zkFFRVTLBuzXAHAoEyN1p49FtDmNoNA";
//]]>
</script>
<meta charset="utf-8">
<title>Алгоритмическая сложность | Основы алгоритмов и структур данных</title>
<meta name="description" content="Алгоритмическая сложность / Основы алгоритмов и структур данных: Учимся анализировать сложность алгоритмов">
<link rel="canonical" href="https://ru.hexlet.io/courses/basic-algorithms/lessons/algorithm-complexity/theory_unit">
<meta name="robots" content="noarchive">
<meta property="og:title" content="Алгоритмическая сложность">
<meta property="og:title" content="Основы алгоритмов и структур данных">
<meta property="og:description" content="Алгоритмическая сложность / Основы алгоритмов и структур данных: Учимся анализировать сложность алгоритмов">
<meta property="og:url" content="https://ru.hexlet.io/courses/basic-algorithms/lessons/algorithm-complexity/theory_unit">
<meta name="csrf-param" content="authenticity_token" />
<meta name="csrf-token" content="Pu6Mvmp5JGffMwjeDMd6tgloBgv_GiR_Gqo66GePIAvRP0eJmAeJB2lwLEYAyIrByWErofct2t2nSqC8NYjHZQ" />
<script src="/vite/assets/inertia-INZxX8jp.js" crossorigin="anonymous" type="module"></script><link rel="modulepreload" href="/vite/assets/chunk-DsPFFUou.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/preload-helper-BJ4cLWpC.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/init-nkZBEvfU.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/ahoy-DrlRQ-1D.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/analytics-6pOtQ3OW.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/ErrorFallbackBlock-naDSYSy9.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/Surface-DL2bpZA-.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/gon-D3e4yh1x.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/mantine-CGMYrt2Y.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/utils-DRqSHbQE.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/routes-CCH8ilKF.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/extends-C-EagtpE.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/inheritsLoose-BBd-DCVI.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/objectWithoutPropertiesLoose-DRHXDhjp.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/index.esm-DAqKOkZ0.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/Button-CGPUux8l.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/CloseButton-D1euiPao.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/Group-BX48WcuU.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/Loader-BQEY8g6v.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/Modal-Cy3HByv7.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/OptionalPortal-1Hza5P2w.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/Stack-CtjJzfw4.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/Textarea-Ck64llAy.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/Box-B5-OOzBf.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/DirectionProvider-Dc9zdUke.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/events-DJQOhap0.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/use-reduced-motion-D2owz4wa.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/use-disclosure-zKtK5W1r.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/use-hotkeys-Cnc_Rwkb.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/random-id-DOQyszCZ.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/notifications.store-C-3AFSMn.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/exports-C_MrNx_T.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/axios-BEvgo0ym.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/dayjs.min-BkKovM-s.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/i18next-BlSq9s7B.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/client-U9M77rxp.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/react-dom-DaLxUz_h.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/useTranslation-Bx1Cdrkz.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/compiler-runtime-6XxiPFnt.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/jsx-runtime-CwjcCKJi.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/react-CkL4ZRHB.js" as="script" crossorigin="anonymous">
<link rel="stylesheet" href="/vite/assets/application-BqhCP46M.js" />
<script src="/vite/assets/application-Df9RExpe.js" crossorigin="anonymous" type="module"></script><link rel="modulepreload" href="/vite/assets/chunk-DsPFFUou.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/autocomplete-VMNbxKGl.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/routes-CCH8ilKF.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/createPopper-C3aM9r1M.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/js.cookie-D1-O8zkX.js" as="script" crossorigin="anonymous"><link rel="stylesheet" href="/vite/assets/application-C8HjmMaq.css" media="screen" />
<script>
window.ym = function(){(ym.a=ym.a||[]).push(arguments)};
window.addEventListener('load', function() {
setTimeout(function() {
ym.l = 1*new Date();
ym(window.gon.ym_counter, "init", {
clickmap: true,
trackLinks: true,
accurateTrackBounce: true,
webvisor: true
});
// Загружаем скрипт
var k = document.createElement('script');
k.async = 1;
k.src = 'https://mc.yandex.ru/metrika/tag.js';
document.head.appendChild(k);
ym(window.gon.ym_counter, 'getClientID', function(clientID) {
window.ymClientId = clientID;
});
}, 1500);
});
</script>
<!-- Google Tag Manager - deferred -->
<script>
// dataLayer stub сразу — пуши работают до загрузки скрипта
window.dataLayer = window.dataLayer || [];
// Сам скрипт — отложенно после load
window.addEventListener('load', function() {
setTimeout(function() {
dataLayer.push({'gtm.start': new Date().getTime(), event: 'gtm.js'});
var j = document.createElement('script');
j.async = true;
j.src = 'https://www.googletagmanager.com/gtm.js?id=GTM-WK88TH';
document.head.appendChild(j);
}, 1500);
});
</script>
<!-- End Google Tag Manager -->
</head>
<body>
<noscript>
<div>
<img alt="" src="https://mc.yandex.ru/watch/25559621" style="position:absolute; left:-9999px;">
</div>
</noscript>
<header class="sticky-top bg-body">
<nav class="navbar navbar-expand-lg">
<div class="container-xxl">
<a class="navbar-brand" href="/"><img alt="Логотип Хекслета" height="24" src="https://ru.hexlet.io/vite/assets/logo_ru_light-BpiEA1LT.svg" width="96">
</a><button aria-controls="collapsable" aria-expanded="false" aria-label="Меню" class="navbar-toggler border-0 mb-0 mt-1" data-bs-target="#collapsable" data-bs-toggle="collapse">
<span class="navbar-toggler-icon"></span>
</button>
<div class="collapse navbar-collapse" id="collapsable">
<ul class="navbar-nav mb-lg-0 mt-lg-1">
<li class="nav-item dropdown">
<button aria-haspopup class="btn nav-link" data-bs-toggle="dropdown" type="button">
Все курсы
<span class="bi bi-chevron-down align-middle ms-1"></span>
</button>
<ul class="dropdown-menu">
<li>
<a class="dropdown-item d-flex py-2" href="/courses"><div class="fw-bold me-auto">Все что есть</div>
<div class="text-muted">117</div>
</a></li>
<li>
<hr class="dropdown-divider">
</li>
<li class="dropdown-item">
<b>Популярные категории</b>
</li>
<li>
<a class="dropdown-item py-2" href="/courses_devops">Курсы по DevOps
</a></li>
<li>
<a class="dropdown-item py-2" href="/courses_data_analytics">Курсы по аналитике данных
</a></li>
<li>
<a class="dropdown-item py-2" href="/courses_programming">Курсы по программированию
</a></li>
<li>
<a class="dropdown-item py-2" href="/courses_testing">Курсы по тестированию
</a></li>
<li>
<hr class="dropdown-divider">
</li>
<li class="dropdown-item">
<b>Популярные курсы</b>
</li>
<li>
<a class="dropdown-item py-2" href="/programs/devops-engineer-from-scratch">DevOps-инженер с нуля
</a></li>
<li>
<a class="dropdown-item py-2" href="/programs/go">Go-разработчик
</a></li>
<li>
<a class="dropdown-item py-2" href="/programs/java">Java-разработчик
</a></li>
<li>
<a class="dropdown-item py-2" href="/programs/python">Python-разработчик
</a></li>
<li>
<a class="dropdown-item py-2" href="/programs/qa-auto-engineer-java">Автоматизатор тестирования на Java
</a></li>
<li>
<a class="dropdown-item py-2" href="/programs/data-analytics">Аналитик данных
</a></li>
<li>
<a class="dropdown-item py-2" href="/programs/frontend">Фронтенд-разработчик
</a></li>
</ul>
</li>
<li class="nav-item dropdown">
<button aria-haspopup class="btn nav-link" data-bs-toggle="dropdown" type="button">
О Хекслете
<span class="bi bi-chevron-down align-middle"></span>
</button>
<ul class="dropdown-menu bg-body">
<li>
<a class="dropdown-item py-2" href="/pages/about">О нас
</a></li>
<li>
<a class="dropdown-item py-2" href="/blog">Блог
</a></li>
<li>
<span class="dropdown-item py-2 external-link" data-href="https://special.hexlet.io/hse-research" role="button">Результаты (Исследование)
</span></li>
<li>
<span class="dropdown-item py-2 external-link" data-href="https://career.hexlet.io" role="button">Хекслет Карьера
</span></li>
<li>
<a class="dropdown-item py-2" href="/testimonials">Отзывы студентов
</a></li>
<li>
<span class="dropdown-item py-2 external-link" data-href="https://t.me/hexlet_help_bot" role="button">Поддержка (В ТГ)
</span></li>
<li>
<span class="dropdown-item py-2 external-link" data-href="https://special.hexlet.io/referal-program/?promo_creative=priglasite-druzei&promo_name=referal-program&promo_position=promo_position&promo_start=010724&promo_type=link" role="button">Реферальная программа
</span></li>
<li>
<span class="dropdown-item py-2 external-link" data-href="https://special.hexlet.io/certificate" role="button">Подарочные сертификаты
</span></li>
<li>
<span class="dropdown-item py-2 external-link" data-href="https://hh.ru/employer/4307094" role="button">Вакансии
</span></li>
<li>
<span class="dropdown-item d-flex external-link" rel="noopener noreferrer nofollow" data-href="https://b2b.hexlet.io" data-target="_blank" role="button">Компаниям
</span></li>
<li>
<span class="dropdown-item d-flex external-link" rel="noopener noreferrer nofollow" data-href="https://hexly.ru/" data-target="_blank" role="button">Колледж
</span></li>
<li>
<span class="dropdown-item d-flex external-link" rel="noopener noreferrer nofollow" data-href="https://hexlyschool.ru/" data-target="_blank" role="button">Частная школа
</span></li>
</ul>
</li>
<li><a class="nav-link" href="/subscription/new">Подписка</a></li>
</ul>
<ul class="navbar-nav flex-lg-row align-items-lg-center gap-2 ms-auto">
<li>
<a class="nav-link" aria-label="Переключить тему" href="/theme/switch?new_theme=dark"><span aria-hidden="true" class="bi bi-moon"></span>
</a></li>
<li>
<span data-target="_self" class="nav-link external-link" data-href="/u/new" role="button"><span>Регистрация</span>
</span></li>
<li>
<span data-target="_self" class="nav-link external-link" data-href="https://ru.hexlet.io/session/new" role="button"><span>Вход</span>
</span></li>
</ul>
</div>
</div>
</nav>
</header>
<div class="x-container-xxxl">
</div>
<main class="mb-6 min-vh-100 h-100">
<link rel="preload" as="image" href="https://hexlet.io/rails/active_storage/representations/proxy/eyJfcmFpbHMiOnsiZGF0YSI6NDAyOCwicHVyIjoiYmxvYl9pZCJ9fQ==--ae9eed98663dd1201759d042a5ba7ca790866156/eyJfcmFpbHMiOnsiZGF0YSI6eyJmb3JtYXQiOiJ3ZWJwIiwicmVzaXplX3RvX2xpbWl0IjpbNDAwLDQwMF0sInNhdmVyIjp7InF1YWxpdHkiOjg1fX0sInB1ciI6InZhcmlhdGlvbiJ9fQ==--5b6f46dacd1af664f27558553a58076185091823/Programming-bro.png"/><link rel="preload" as="image" href="/vite/assets/development-BVihs_d5.png"/><div id="app" data-page="{"component":"web/courses/lessons/theory_unit","props":{"errors":{},"locale":"ru","language":"ru","httpsHost":"https://ru.hexlet.io","host":"ru.hexlet.io","colorScheme":"light","auth":{"user":{"id":null,"last_viewed_notification_id":null,"email":null,"state":null,"first_name":"","last_name":"","created_at":"2026-02-26T17:08:58.327Z","current_program":null,"current_team":null,"full_name":"","guest":true,"can_use_paid_features":false,"is_hexlet_employee":false,"sanitized_phone_number":"","can_subscribe":true,"can_renew_education":false}},"cloudflareTurnstileSiteKey":"0x4AAAAAAA15KmeFXzd2H0Xo","vkIdClientId":"51586979","yandexIdClientId":"88d071f1d3384eb4bd1deb37910235c7","formAuthToken":"H_1167Y0giqWr8ECLrxoY-f-0f6ZObPdz4IuokG7gC7wLL7cREovSiDs5Zois5gUJ_f8VJEOTX9yYrT2E7xnQA","topics":[{"id":60372,"title":"на картинке с кучей графиков, логарифмические подписаны как (long), кажется должно быть (logn)\nВдруг кто-то запутается","plain_title":"на картинке с кучей графиков, логарифмические подписаны как (long), кажется должно быть (logn) Вдруг кто-то запутается ","creator":{"public_name":"Михаил Рогов","id":324392,"is_tutor":false},"comments":[{"creator":{"public_name":"Сергей К.","id":5174,"is_tutor":false},"id":127700,"body":" Верно подметили! Поправил картинку. Спасибо!","topic_id":60372}],"communitable":{"parent_entity_name":null,"parent_entity_url":null,"entity_name":"Алгоритмическая сложность","entity_url":null,"active":true}},{"id":91042,"title":"У вас в задании, в поле для кода написана функция is_prime , а в тексте и тесты пытаются найти функцию solution. Немного путает, или это так и задумано?)","plain_title":"У вас в задании, в поле для кода написана функция is_prime , а в тексте и тесты пытаются найти функцию solution. Немного путает, или это так и задумано?) ","creator":{"public_name":"","id":394430,"is_tutor":false},"comments":[{"creator":{"public_name":"Maksim Litvinov","id":198906,"is_tutor":true},"id":180332,"body":"Добрый день! Спасибо, поправил описание. Нужно будет нажать Сброс, чтобы получить новую версию упражнения","topic_id":91042}],"communitable":{"parent_entity_name":null,"parent_entity_url":null,"entity_name":"Алгоритмическая сложность","entity_url":null,"active":true}},{"id":81973,"title":"Как кажется, здесь подразумевается time, а не line\n\n","plain_title":"Как кажется, здесь подразумевается time, а не line image https://i.ibb.co/yN3jtmt/Screenshot-2023-01-09-at-11-36-52.png ","creator":{"public_name":"Юрий Кормин","id":412035,"is_tutor":false},"comments":[{"creator":{"public_name":"Aleksandr Litvinov","id":117182,"is_tutor":true},"id":167376,"body":"Спасибо! Поправим :)","topic_id":81973}],"communitable":{"parent_entity_name":null,"parent_entity_url":null,"entity_name":"Алгоритмическая сложность","entity_url":null,"active":true}},{"id":57537,"title":"В тесте есть 2 вопроса - Какова сложность быстрого поиска? и Какова сложность бинарного поиска? Согласно вики это одно и тоже, наверно имелась ввиду быстрая сортировка","plain_title":"В тесте есть 2 вопроса - Какова сложность быстрого поиска? и Какова сложность бинарного поиска? Согласно вики это одно и тоже, наверно имелась ввиду быстрая сортировка ","creator":{"public_name":"Павел","id":13568,"is_tutor":false},"comments":[{"creator":{"public_name":"Vasiliy Chapaev ...","id":233479,"is_tutor":false},"id":122311,"body":"Верно, поправили. Спасибо!","topic_id":57537}],"communitable":{"parent_entity_name":null,"parent_entity_url":null,"entity_name":"Алгоритмическая сложность","entity_url":null,"active":true}},{"id":57473,"title":"> Добавление элементов в массив. Вне зависимости от длины массива скорость будет одинаковой f(1)\n\nЯ так понимаю здесь пропущено уточнение - добавление в конец массива.\nПри добавлении в начало массива сложность будет линейной.","plain_title":"Добавление элементов в массив. Вне зависимости от длины массива скорость будет одинаковой f(1) Я так понимаю здесь пропущено уточнение - добавление в конец массива. При добавлении в начало массива сложность будет линейной. ","creator":{"public_name":"Victor Kushnir","id":51391,"is_tutor":false},"comments":[{"creator":{"public_name":"Vasiliy Chapaev ...","id":233479,"is_tutor":false},"id":122312,"body":"Добрый вечер! Все верно, не стоит считать что добавление в массив f(1), даже при добавлении в конец сложность может быть другой, в зависимости от реализации динамического массива в самом ЯП. Поправим, спасибо! ","topic_id":57473}],"communitable":{"parent_entity_name":null,"parent_entity_url":null,"entity_name":"Алгоритмическая сложность","entity_url":null,"active":true}},{"id":95502,"title":"Не требуется ли в решении упражнения к конечной границе генератора range() прибавлять 1?\nМы же должны проверить все числа до корня из N включительно, а генератор range не включает конечную границу.\n\n`for i in range(2, int(sqrt) + 1):` \n`....`","plain_title":"Не требуется ли в решении упражнения к конечной границе генератора range() прибавлять 1? Мы же должны проверить все числа до корня из N включительно, а генератор range не включает конечную границу. for i in range(2, int(sqrt) + 1): .... ","creator":{"public_name":"Петр Малафеев","id":446598,"is_tutor":false},"comments":[{"creator":{"public_name":"Ivan Mamtsev","id":294764,"is_tutor":true},"id":186435,"body":"Да, вы правы, поправлю решение.","topic_id":95502}],"communitable":{"parent_entity_name":null,"parent_entity_url":null,"entity_name":"Алгоритмическая сложность","entity_url":null,"active":true}},{"id":98499,"title":"В примере, где оценка скорости работы сортировки выбором, для Python\n\n`average_performance(selection_sort(items[:]), 1) # 0.1000000238418\naverage_performance(selection_sort(items[:]), 10) # 0.0699999988079`\n\nВ данном примере в Цикл в место функции залетает None.\nДля себя я поправил\n\n\ndef average_performance(f, args, count):\n start = datetime.now()\n\n for i in range(count):\n f(*args)\n\n end = datetime.now()\n\n return (end - start) / count\n\nitems = [86, 66, 44, 77, 56, 64, 76, 39, 32, 93, 33, 54, 63, 96, 5, 41, 20, 58, 55, 28]\naverage_performance(selection_sort, (items[:],), 1)\naverage_performance(selection_sort, (items[:],), 10)","plain_title":"В примере, где оценка скорости работы сортировки выбором, для Python average_performance(selection_sort(items[:]), 1) # 0.1000000238418 average_performance(selection_sort(items[:]), 10) # 0.0699999988079 В данном примере в Цикл в место функции залетает None. Для себя я поправил def average_performance(f, args, count): start = datetime.now() for i in range(count): f(*args) end = datetime.now() return (end - start) / count items = [86, 66, 44, 77, 56, 64, 76, 39, 32, 93, 33, 54, 63, 96, 5, 41, 20, 58, 55, 28] averageperformance(selectionsort, (items[:],), 1) averageperformance(selectionsort, (items[:],), 10) ","creator":{"public_name":"Иван Колташев","id":652598,"is_tutor":false},"comments":[{"creator":{"public_name":"Ivan Mamtsev","id":294764,"is_tutor":true},"id":189832,"body":"Спасибо, поправил пример","topic_id":98499}],"communitable":{"parent_entity_name":null,"parent_entity_url":null,"entity_name":"Алгоритмическая сложность","entity_url":null,"active":true}},{"id":102934,"title":"В теории сначала идет пример кода \n\n```\n...\nconst items = [86, 66, 44, 77, 56, 64, 76, 39, 32, 93, 33, 54, 63, 96, 5, 41, 20, 58, 55, 28];\naveragePerformance(() => selectionSort, items, 1); // 0.1000000238418\naveragePerformance(() => selectionSort, items, 10); // 0.0699999988079\n```\nпотом текст \n\n> Возможно вы не знакомы с конструкцией […items], которая встречается в этом коде. \n\nи ниже \n\n> У функции averagePerformance два параметра:\n\nхотя это не так, у функции averagePerformance три параметра и только через пару абзацев уже подходящий код:\n\n```\naveragePerformance(() => selectionSort([...items]), 10); // 0.60\naveragePerformance(() => quickSort([...items]), 10); // 0.19\n```","plain_title":"В теории сначала идет пример кода ... const items = [86, 66, 44, 77, 56, 64, 76, 39, 32, 93, 33, 54, 63, 96, 5, 41, 20, 58, 55, 28]; averagePerformance(() => selectionSort, items, 1); // 0.1000000238418 averagePerformance(() => selectionSort, items, 10); // 0.0699999988079 потом текст Возможно вы не знакомы с конструкцией […items], которая встречается в этом коде. и ниже У функции averagePerformance два параметра: хотя это не так, у функции averagePerformance три параметра и только через пару абзацев уже подходящий код: averagePerformance(() => selectionSort([...items]), 10); // 0.60 averagePerformance(() => quickSort([...items]), 10); // 0.19 ","creator":{"public_name":"Ася Бахнарь","id":104075,"is_tutor":false},"comments":[{"creator":{"public_name":"Maksim Litvinov","id":198906,"is_tutor":true},"id":195322,"body":"Поправил пример, спасибо","topic_id":102934}],"communitable":{"parent_entity_name":null,"parent_entity_url":null,"entity_name":"Алгоритмическая сложность","entity_url":null,"active":true}},{"id":102533,"title":"ужасный урок. Ничего не объясняется и если ты математически не подкован, то ничего не поймешь. Про сложность - просто приведены примеры и говорится какой алгоритм какая сложность, но не объясняется почему. Тот случай, когда проще пойти на ютуб и найти материал получше","plain_title":"ужасный урок. Ничего не объясняется и если ты математически не подкован, то ничего не поймешь. Про сложность - просто приведены примеры и говорится какой алгоритм какая сложность, но не объясняется почему. Тот случай, когда проще пойти на ютуб и найти материал получше ","creator":{"public_name":"","id":372079,"is_tutor":false},"comments":[{"creator":{"public_name":"Maksim Litvinov","id":198906,"is_tutor":true},"id":194752,"body":"Добрый день! Да, с алгоритмами есть некторые проблемы. Оформил ваш фидбек в тикет, передам авторам курса","topic_id":102533}],"communitable":{"parent_entity_name":null,"parent_entity_url":null,"entity_name":"Алгоритмическая сложность","entity_url":null,"active":true}},{"id":102955,"title":"Поясните, пожалуйста, как получилось выражение: [(n - 1) * (n - 2)] / 2, \nпосле применения формулы суммы членов арифметической прогрессии\n","plain_title":"Поясните, пожалуйста, как получилось выражение: [(n - 1) * (n - 2)] / 2, после применения формулы суммы членов арифметической прогрессии ","creator":{"public_name":"Александр","id":867718,"is_tutor":false},"comments":[{"creator":{"public_name":"Maksim Litvinov","id":198906,"is_tutor":true},"id":195329,"body":"Приветствую, Александр! Там небольшая ошибка в формуле была. Сейчас поправил, спасибо","topic_id":102955}],"communitable":{"parent_entity_name":null,"parent_entity_url":null,"entity_name":"Алгоритмическая сложность","entity_url":null,"active":true}}],"lesson":{"exercise":{"id":2005,"slug":"js_basic_algorithms_complexity_exercise","name":null,"state":"active","kind":"exercise","language":"javascript","locale":"ru","has_web_view":false,"has_test_view":false,"reviewable":true,"readme":"Реализуйте функцию, которая проверяет является ли число простым или нет.\n\nОптимизируйте алгоритм так, чтобы он выполнялся за наименьшее количество итераций.\n\n## solutions/solution.js\n\nРеализуйте и экспортируйте функцию по умолчанию\n\n```javascript\nimport isPrime from './solution.js';\n\nisPrime(2147483648) // false\nisPrime(87178291199) // true\n```\n\n## solutions/solution.php\n\nРеализуйте функцию `solution`.\n\n```php\n<?php\n\nsolution(2147483648) # False\nsolution(87178291199) # True\n```\n\n## solutions/solution.py\n\nРеализуйте функцию `solution`.\n\n```python\nfrom solution import solution\n\nsolution(2147483648) # False\nsolution(87178291199) # True\n```\n\n## solutions/Solution.java\n\nВ файле определите пакет `solutions`. Создайте в нем публичный класс `Solution` и реализуйте в нем публичный статический метод `run()`. Метод принимает в качестве параметра целое число типа `long` и проверяет, является ли оно простым или нет\n\n```java\nSolution.run(2147483648); // false\nSolution.run(87178291199); // true\n```\n\nОптимизируйте алгоритм так, чтобы он выполнялся за наименьшее количество итераций\n\n### Подсказки\n\n* Оптимальным алгоритмом можно считать алгоритм со сложностью `O(sqrt(n))`\n","prepared_readme":"Реализуйте функцию, которая проверяет является ли число простым или нет.\n\nОптимизируйте алгоритм так, чтобы он выполнялся за наименьшее количество итераций.\n\n## solutions/solution.js\n\nРеализуйте и экспортируйте функцию по умолчанию\n\n```javascript\nimport isPrime from './solution.js';\n\nisPrime(2147483648) // false\nisPrime(87178291199) // true\n```\n\n## solutions/solution.php\n\nРеализуйте функцию `solution`.\n\n```php\n<?php\n\nsolution(2147483648) # False\nsolution(87178291199) # True\n```\n\n## solutions/solution.py\n\nРеализуйте функцию `solution`.\n\n```python\nfrom solution import solution\n\nsolution(2147483648) # False\nsolution(87178291199) # True\n```\n\n## solutions/Solution.java\n\nВ файле определите пакет `solutions`. Создайте в нем публичный класс `Solution` и реализуйте в нем публичный статический метод `run()`. Метод принимает в качестве параметра целое число типа `long` и проверяет, является ли оно простым или нет\n\n```java\nSolution.run(2147483648); // false\nSolution.run(87178291199); // true\n```\n\nОптимизируйте алгоритм так, чтобы он выполнялся за наименьшее количество итераций\n\n### Подсказки\n\n* Оптимальным алгоритмом можно считать алгоритм со сложностью `O(sqrt(n))`\n","has_solution":true,"entity_name":"Алгоритмическая сложность"},"units":[{"id":4576,"name":"theory","url":"/courses/basic-algorithms/lessons/algorithm-complexity/theory_unit"},{"id":4577,"name":"quiz","url":"/courses/basic-algorithms/lessons/algorithm-complexity/quiz_unit"},{"id":6495,"name":"exercise","url":"/courses/basic-algorithms/lessons/algorithm-complexity/exercise_unit"}],"links":[{"id":427702,"name":"Сервис, на котором можно сравнить производительность двух фрагментов кода","url":"https://jsben.ch/\n"}],"ordered_units":[{"id":4576,"name":"theory","url":"/courses/basic-algorithms/lessons/algorithm-complexity/theory_unit"},{"id":4577,"name":"quiz","url":"/courses/basic-algorithms/lessons/algorithm-complexity/quiz_unit"},{"id":6495,"name":"exercise","url":"/courses/basic-algorithms/lessons/algorithm-complexity/exercise_unit"}],"id":2041,"slug":"algorithm-complexity","state":"approved","name":"Алгоритмическая сложность","course_order":400,"goal":"Учимся анализировать сложность алгоритмов","self_study":null,"theory_video_provider":null,"theory_video_uid":null,"theory":"В программировании используются алгоритмы, которые по-разному решают одну и ту же задачу: например, сортировку массива. При этом алгоритмы работают с разной скоростью и требуют разное количество памяти. При прочих равных условиях мы бы выбрали быстрый или нетребовательный алгоритм.\n\nЧтобы правильно выбирать алгоритмы, нужно научиться сравнивать их, чем мы и займемся в этом уроке. Мы познакомимся с двумя основными способами, разберем их плюсы и минусы. Опираясь на эти способы, мы сравним время работы уже знакомых нам алгоритмов.\n\n## Как оценить скорость алгоритма\n\nСкорость алгоритмов можно сравнивать самым очевидным способом — физически измерить время выполнения на одних и тех же данных. Чтобы сравнить сортировку выбором и быструю сортировку, мы можем взять массив из нескольких элементов и измерить время быстрой сортировки:\n\n```javascript\nconst quickSort = (items) => {\n const partition = (items, left, right, pivot) => {\n while (true) {\n while (items[left] < pivot) {\n left++\n }\n\n while (items[right] > pivot) {\n right--\n }\n\n if (left >= right) {\n return right + 1\n }\n\n const t = items[left]\n items[left] = items[right]\n items[right] = t\n\n left++\n right--\n }\n }\n\n const quickSort = (items, left, right) => {\n const length = right - left + 1\n\n if (length < 2) {\n return\n }\n\n const pivot = items[left]\n\n const split_index = partition(items, left, right, pivot)\n\n quickSort(items, left, split_index - 1)\n quickSort(items, split_index, right)\n }\n\n quickSort(items, 0, items.length - 1)\n}; const items = [86, 66, 44, 77, 56, 64, 76, 39, 32, 93, 33, 54, 63, 96, 5, 41, 20, 58, 55, 28]\nconst start = performance.now()\nquickSort(items)\nconst end = performance.now()\nconsole.log(end - start) // => 0.20 миллисекунд\n```\n\n```python\nfrom datetime import datetime\n\ndef quick_sort(items):\n def partition(items, left, right, pivot):\n while True:\n while items[left] < pivot:\n left += 1\n\n while items[right] > pivot:\n right -= 1\n\n if left >= right:\n return right + 1\n\n items[left], items[right] = items[right], items[left]\n left += 1\n right -= 1\n\n def quick_sort(items, left, right):\n length = right - left + 1\n\n if length < 2:\n return\n\n pivot = items[left]\n split_index = partition(items, left, right, pivot)\n quick_sort(items, left, split_index - 1)\n quick_sort(items, split_index, right)\n\n quick_sort(items, 0, len(items) - 1)\n\nitems = [86, 66, 44, 77, 56, 64, 76, 39, 32, 93, 33, 54, 63, 96, 5, 41, 20, 58, 55, 28];\nstart = datetime.now();\nquick_sort(items);\nend = datetime.now();\nprint(end - start); # => 0.20 миллисекунд\n```\n\n```php\n<?php\n\nfunction quickSort($items)\n{\n $partition = function ($items, $left, $right, $pivot) {\n while (true) {\n while ($items[$left] < $pivot) {\n $left += 1;\n }\n\n while ($items[$right] > $pivot) {\n $right -= 1;\n }\n\n if ($left >= $right) {\n return $right + 1;\n }\n\n $t = $items[$left];\n $items[$left] = $items[$right];\n $items[$right] = $t;\n\n $left += 1;\n $right -= 1;\n }\n };\n\n $quickSort = function ($items, $left, $right) use ($partition, &$quickSort) {\n $length = $right - $left + 1;\n if ($length < 2) {\n return;\n }\n\n $pivot = $items[$left];\n\n $splitIndex = $partition($items, $left, $right, $pivot);\n\n $quickSort($items, $left, $splitIndex - 1);\n $quickSort($items, $splitIndex, $right);\n };\n\n $quickSort($items, 0, count($items) - 1);\n};\n\n$items = [86, 66, 44, 77, 56, 64, 76, 39, 32, 93, 33, 54, 63, 96, 5, 41, 20, 58, 55, 28];\n$start = microtime(true);\nquickSort($items);\n$end = microtime(true);\nprint_r($end - $start); // => 0.20 миллисекунд\n```\n\n```java\nclass App {\n public static int partition(int[] items, int left, int right, int pivot) {\n while (true) {\n while (items[left] < pivot) {\n left++;\n }\n\n while (items[right] > pivot) {\n right--;\n }\n\n if (left >= right) {\n return right + 1;\n }\n\n var temporary = items[left];\n items[left] = items[right];\n items[right] = temporary;\n\n left++;\n right--;\n }\n }\n\n public static void sort(int[] items, int left, int right) {\n var length = right - left + 1;\n\n if (length < 2) {\n return;\n }\n\n var pivot = items[left];\n\n var splitIndex = partition(items, left, right, pivot);\n sort(items, left, splitIndex - 1);\n sort(items, splitIndex, right);\n }\n\n public static void quicksort(int[] items) {\n sort(items, 0, items.length - 1);\n }\n}\n\nint[] items = {86, 66, 44, 77, 56, 64, 76, 39, 32, 93, 33, 54, 63, 96, 5, 41, 20, 58, 55, 28};\n\nvar start = System.nanoTime();\nApp.quicksort(items);\nvar end = System.nanoTime();\nSystem.out.println(end - start); // 0.2 миллисекунд\n```\n\nАлгоритм быстрой сортировки мы уже разбирали. Единственное, что нам пока не встречалось — вызов метода `performance.now()`.\n\n_Performance_ — это объект в глобальной области видимости, который используют для измерения производительности. Метод `now()` возвращает количество миллисекунд с момента старта браузера. Можно запустить этот метод, сохранить значения до запуска кода и после его завершения, и вычесть одно из другого — и тогда мы узнаем, сколько миллисекунд работал наш код.\n\nЧтобы сравнить два алгоритма, надо упорядочить точно такой же массив с помощью алгоритма выбора:\n\n```javascript\nconst selectionSort = (items) => {\n for (i = 0; i < items.length - 1; i++) {\n let indexMin = i\n for (j = i + 1; j < items.length; j++) {\n if (items[j] < items[indexMin])\n indexMin = j\n }\n\n const t = items[i]\n items[i] = items[indexMin]\n items[indexMin] = t\n }\n}\n\nconst items = [86, 66, 44, 77, 56, 64, 76, 39, 32, 93, 33, 54, 63, 96, 5, 41, 20, 58, 55, 28]\nconst start = performance.now()\nselectionSort(items)\nconst end = performance.now()\nconsole.log(end - start) // <= 0.09 миллисекунды\n```\n\n```python\nfrom datetime import datetime\n\ndef selection_sort(items):\n for i in range(len(items) - 1):\n index_min = i\n for j in range(i + 1, len(items) - 1):\n if items[j] < items[index_min]:\n index_min = j\n items[i], items[index_min] = items[index_min], items[i]\n\nitems = [86, 66, 44, 77, 56, 64, 76, 39, 32, 93, 33, 54, 63, 96, 5, 41, 20, 58, 55, 28]\nstart = datetime.now()\nselection_sort(items)\nend = datetime.now()\nprint(end - start) # <= 0.09 миллисекунды\n```\n\n```php\n<?php\n\nfunction selectionSort(&$items)\n{\n for ($i = 0; $i < count($items) - 1; $i++) {\n $indexMin = $i;\n for ($j = $i + 1; $j < count($items); $j++) {\n if ($items[$j] < $items[$indexMin]) {\n $indexMin = $j;\n }\n }\n\n $t = $items[$i];\n $items[$i] = $items[$indexMin];\n $items[$indexMin] = $t;\n }\n}\n\n$items = [86, 66, 44, 77, 56, 64, 76, 39, 32, 93, 33, 54, 63, 96, 5, 41, 20, 58, 55, 28];\n$start = microtime(true);\nselectionSort($items);\n$end = microtime(true);\nprint_r($end - $start); // <= 0.09 миллисекунды\n```\n\n```java\nclass App {\n public static void selectionSort(int[] items) {\n for (var i = 0; i < items.length - 1; i++) {\n var indexMin = i;\n for (var j = i + 1; j < items.length; j++) {\n if (items[j] < items[indexMin]) {\n indexMin = j;\n }\n }\n\n var temporary = items[i];\n items[i] = items[indexMin];\n items[indexMin] = temporary;\n }\n }\n}\n\nint[] items = {86, 66, 44, 77, 56, 64, 76, 39, 32, 93, 33, 54, 63, 96, 5, 41, 20, 58, 55, 28};\n\nvar start = System.nanoTime();\nApp.selectionSort(items);\nvar end = System.nanoTime();\nSystem.out.println(end - start); // 0.09 миллисекунд\n```\n\nОценим скорость кода выше:\n\n* Быстрая сортировка — 0,20 миллисекунд\n* Сортировка выбором — 0,09 миллисекунд\n\nРезультат выглядит странно. Раз уж быструю сортировку назвали быстрой, то время ее выполнения должно быть меньше, чем у сортировки выбором. Здесь дело в том, что результаты однократного измерения ненадежны. Нужно измерить производительность алгоритмов несколько раз подряд на одних и тех же данных. Можем получить такой результат:\n\n* Быстрая сортировка — 0,21 миллисекунда\n* Сортировка выбором — 0,12 миллисекунд\n\nИли даже такой:\n\n* Быстрая сортировка — 0,16 миллисекунд\n* Сортировка выбором — 0,17 миллисекунд\n\nРазброс может быть достаточно большим. Дело в том, что на производительность нашей программы влияет множество случайных факторов: другие запущенные программы на компьютере, режим энергосбережения и так далее.\n\nВ работе алгоритмов много перечисленных тонкостей, поэтому сравнивать скорости довольно трудно. Чтобы справиться с этой трудностью, используем статистические методы. Будем запускать одну и ту же функцию много раз, а затем разделим общее время выполнения на количество запусков, чтобы вычислить среднее время выполнения:\n\n```javascript\nconst averagePerformance = (f, count) => {\n const start = window.performance.now()\n\n for (let i = 0; i < count; i++) {\n f()\n }\n\n const end = window.performance.now()\n return (end - start) / count\n}\n\nconst items = [86, 66, 44, 77, 56, 64, 76, 39, 32, 93, 33, 54, 63, 96, 5, 41, 20, 58, 55, 28]\naveragePerformance(() => selectionSort([...items]), 1) // 0.1000000238418\naveragePerformance(() => selectionSort([...items]), 10) // 0.0699999988079\n```\n\n```python\nfrom datetime import datetime\n\ndef average_performance(f, args, count):\n start = datetime.now()\n\n for i in range(count):\n f(*args)\n\n end = datetime.now()\n\n return (end - start) / count\n\nitems = [86, 66, 44, 77, 56, 64, 76, 39, 32, 93, 33, 54, 63, 96, 5, 41, 20, 58, 55, 28]\naverage_performance(selection_sort, (items[:],), 1) # 0.1000000238418\naverage_performance(selection_sort, (items[:],), 10) # 0.0699999988079\n```\n\n```php\n<?php\n\nfunction averagePerformance($f, $args, $count)\n{\n $start = microtime(true);\n\n for ($i = 0; $i < $count; $i++) {\n $f(...$args);\n }\n\n $end = microtime(true);\n return ($end - $start) / $count;\n}\n\n$items = [86, 66, 44, 77, 56, 64, 76, 39, 32, 93, 33, 54, 63, 96, 5, 41, 20, 58, 55, 28];\naveragePerformance(fn() => selectionSort, $items, 1); // 34\naveragePerformance(fn() => selectionSort, $items, 10); // 9.7\n```\n\n```java\npublic class App {\n\n public static double averagePerformance (Runnable f, int count) {\n var start = System.nanoTime();\n\n for (var i = 0; i < count; i++) {\n f.run();\n }\n\n var end = System.nanoTime();\n System.out.println((end - start) / count);\n return (end - start) / count;\n }\n}\n\nint[] items = {86, 66, 44, 77, 56, 64, 76, 39, 32, 93, 33, 54, 63, 96, 5, 41, 20, 58, 55, 28};\n\nApp.averagePerformance(() -> selectionSort(Arrays.copyOf(items, items.length)), 1); // 0.1\nApp.averagePerformance(() -> selectionSort(Arrays.copyOf(items, items.length)), 10);// 0.069\n```\n\nВозможно вы не знакомы с конструкцией `[...items]`, которая встречается в этом коде. Она позволяет сделать копию массива `items`. Без копии мы при первом же вызове функции `selectionSort` упорядочим массив `items`, и последующие вызовы будут измерять скорость сортировки уже упорядоченного массива.\n\nУ функции `averagePerformance` два параметра:\n\n* Функция, чью производительность мы хотим измерить\n* Количество раз, когда мы хотим ее запустить\n\nМы видим, что среднее время выполнения может заметно отличаться от времени, измеренного один раз — на 30% в нашем случае. Значит ли это, что теперь у нас в руках есть надежный способ сравнения алгоритмов? Кажется, что да. Но мы пока так и не выяснили, почему быстрая сортировка такая медленная по сравнению с сортировкой выбором.\n\nПродолжим искать причину и сравним время выполнения разных сортировок на массиве из ста элементов:\n\n```javascript\nconst items = [86, 66, 44, 77, 56, 64, 76, 39, 32, 93, 33, 54, 63, 96, 5, 41, 20, 58, 55, 28, 91, 81, 97, 24, 96, 33, 11, 47, 18, 44, 95, 34, 52, 65, 18, 5, 30, 54, 67, 24, 13, 70, 62, 88, 18, 78, 72, 40, 10, 73, 27, 44, 46, 8, 1, 49, 45, 98, 91, 70, 30, 48, 44, 52, 24, 39, 91, 22, 93, 30, 2, 85, 30, 34, 7, 82, 18, 87, 91, 37, 11, 93, 74, 27, 15, 44, 81, 15, 74, 17, 53, 3, 67, 84, 78, 98, 6, 8, 90, 50]\naveragePerformance(() => selectionSort([...items]), 10) // 0.60\naveragePerformance(() => quickSort([...items]), 10) // 0.19\n```\n\n```python\nitems = [86, 66, 44, 77, 56, 64, 76, 39, 32, 93, 33, 54, 63, 96, 5, 41, 20, 58, 55, 28, 91, 81, 97, 24, 96, 33, 11, 47, 18, 44, 95, 34, 52, 65, 18, 5, 30, 54, 67, 24, 13, 70, 62, 88, 18, 78, 72, 40, 10, 73, 27, 44, 46, 8, 1, 49, 45, 98, 91, 70, 30, 48, 44, 52, 24, 39, 91, 22, 93, 30, 2, 85, 30, 34, 7, 82, 18, 87, 91, 37, 11, 93, 74, 27, 15, 44, 81, 15, 74, 17, 53, 3, 67, 84, 78, 98, 6, 8, 90, 50]\naverage_performance(selection_sort(items[:]), 10) # 0.60\naverage_performance(quick_sort(items[:]), 10) # 0.19\n```\n\n```php\n<?php\n\n$items = [86, 66, 44, 77, 56, 64, 76, 39, 32, 93, 33, 54, 63, 96, 5, 41, 20, 58, 55, 28, 91, 81, 97, 24, 96, 33, 11, 47, 18, 44, 95, 34, 52, 65, 18, 5, 30, 54, 67, 24, 13, 70, 62, 88, 18, 78, 72, 40, 10, 73, 27, 44, 46, 8, 1, 49, 45, 98, 91, 70, 30, 48, 44, 52, 24, 39, 91, 22, 93, 30, 2, 85, 30, 34, 7, 82, 18, 87, 91, 37, 11, 93, 74, 27, 15, 44, 81, 15, 74, 17, 53, 3, 67, 84, 78, 98, 6, 8, 90, 50];\n\nprint_r(averagePerformance(fn() => $selectionSort, [...$items], 10)); // 34\nprint_r(averagePerformance(fn() => $quickSort, [...$items], 10)); // 9.7\n```\n\n```java\nint[] items = {6, 66, 44, 77, 56, 64, 76, 39, 32, 93, 33, 54, 63, 96, 5, 41, 20, 58, 55, 28, 91, 81, 97, 24, 96, 33, 11, 47, 18, 44, 95, 34, 52, 65, 18, 5, 30, 54, 67, 24, 13, 70, 62, 88, 18, 78, 72, 40, 10, 73, 27, 44, 46, 8, 1, 49, 45, 98, 91, 70, 30, 48, 44, 52, 24, 39, 91, 22, 93, 30, 2, 85, 30, 34, 7, 82, 18, 87, 91, 37, 11, 93, 74, 27, 15, 44, 81, 15, 74, 17, 53, 3, 67, 84, 78, 98, 6, 8, 90, 50};\n\nApp.averagePerformance(() -> selectionSort(Arrays.copyOf(items, items.length)), 10); // 0.6\nApp.averagePerformance(() -> quickSort(Arrays.copyOf(items, items.length)), 10);// 0.19\n```\n\nНа большом массиве быстрая сортировка оказывается в три раза быстрее, чем сортировка выбором! Как такое может быть? Конечно, у этой странности есть объяснение, мы обсудим его чуть позже. Сейчас обратим внимание, что измерения скорости алгоритма на одних данных ничего не говорит об его скорости на других данных.\n\nМы можем с большой точностью оценить время работы алгоритма на массиве из десяти элементов и при этом мы совершенно не представляем, какой окажется скорость того же алгоритма на массиве из ста тысяч элементов. Именно поэтому перед программистами встала задача — научиться оценивать скорость алгоритмов в целом.\n\n## Оценка скорости алгоритмов «в целом»\n\nИдея оценки «в целом» пришла к нам из математики, где есть похожая задача — нужно оценивать порядок роста функций. Математики могут точно рассчитать скорость возрастания функции в любой точке, но эта информация может оказаться не очень полезной. Сравним графики двух функций:\n\n\n\nКажется, что синяя функция больше, чем, красная. Но если посмотреть на те же графики в другом масштабе, картина изменится:\n\n\n\nКрасная функция растет гораздо быстрее и почти сразу становится больше синей. С алгоритмами возникает та же проблема: на одном наборе данных первый алгоритм физически будет быстрее второго, на многих других наборах он может оказаться гораздо медленнее. Синяя функция на графике — это прямая линия, а красная — это парабола.\n\nСиние функции в математике принято называть линейными, а красные — квадратичными. Математики знают, что квадратичные функции растут быстрее линейных, а кубические — быстрее квадратичных.\n\nАлгоритмическая сложность тоже бывает линейной, квадратичной и кубической. Для нее характерна та же самая зависимость: алгоритмы с квадратичной сложностью в целом работают медленнее алгоритмов с линейной сложностью. Рассмотрим несколько алгоритмов и разберемся, как определять временную сложность.\n\n## Линейная сложность\n\nЧтобы определить временную сложность алгоритма, программисты ставят мысленный эксперимент. Предположим, что мы точно измерили время работы алгоритма на одном массиве, а потом увеличили этот массив в десять раз. Как увеличится время работы алгоритма? Если время работы алгоритма также увеличится в десять раз, то речь идет **о линейной сложности** — на графике она бы описывалась прямой линией.\n\nТипичный линейный алгоритм — поиск минимального элемента в массиве:\n\n```javascript\nconst getMinimum = (items) => {\n let minimum = items[0]\n\n for (let i = 1; i < items.length; i++) {\n if (minimum > items[i]) {\n minimum = items[i]\n }\n }\n\n return minimum\n}\n```\n\n```python\ndef get_minimum(items):\n minimum = items[0]\n\n for i in range(1, len(items)):\n if minimum > items[i]:\n minimum = items[i]\n\n return minimum\n```\n\n```php\n<?php\n\nfunction getMinimum($items)\n{\n $minimum = $items[0];\n\n for ($i = 1; i < count($items); $i++) {\n if ($minimum > $items[i]) {\n $minimum = $items[i];\n }\n }\n\n return $minimum;\n};\n```\n\n```java\npublic class App {\n public static int getMinimum(int[] items) {\n var minimum = items[0];\n\n for (var i = 1; i < items.length; i++) {\n if (minimum > items[i]) {\n minimum = items[i];\n }\n }\n\n return minimum;\n }\n}\n```\n\nЭто простой алгоритм. Мы просматриваем элементы массива по одному и сравниваем с уже найденным. Если новый элемент оказывается меньше минимума, он становится новым минимумом. В самом начале в качестве минимума выбираем самый первый элемент массива с индексом 0. Функция состоит из двух смысловых элементов. Первый элемент — инициализация:\n\n```javascript\nlet minimum = items[0]\n```\n\n```python\nminimum = items[0]\n```\n\n```php\n<?php\n\n$minimum = $items[0];\n```\n\n```java\nvar minimum = items[0];\n```\n\nВторой элемент — это цикл:\n\n```javascript\nfor (let i = 1; i < items.length; i++) {\n if (minimum > items[i]) {\n minimum = items[i]\n }\n}\n```\n\n```python\nfor i in range(1, len(items)):\n if minimum > items[i]:\n minimum = items[i]\n```\n\n```php\n<?php\n\nfor ($i = 1; $i < count($items); $i++) {\n if ($minimum > $items[$i]) {\n $minimum = $items[$i];\n }\n}\n```\n\n```java\n\nfor (var i = 1; i < items.length; i++) {\n if (minimum > items[i]) {\n minimum = items[i];\n }\n}\n```\n\nЕсли в массиве 10 элементов, цикл выполнится 9 раз, если 100 элементов — 99 раз, если n элементов, цикл выполнится n-1 раз. В итоге, для массива из n элементов функция выполнит n операций — одну операцию инициализации и n-1 операций в цикле. Если увеличить размер массива в 10 раз, то количество элементов будет равно 10\\*n, и количество операций также будет равно 10\\*n, то есть тоже вырастет в 10 раз.\n\nТакая линейная временная сложность обозначается **O(n)**. Из-за того, что в записи используется большая буква O, она называется «н**отация О-большое**». Буква O появилась здесь не случайно. Это первая буква немецкого слова _Ordnung_, которое означает порядок. В математике, откуда пришло обозначение, оно относится к порядку роста функций.\n\nКакие еще алгоритмы имеют линейную временную сложность? Например, алгоритм вычисления среднего арифметического:\n\n```javascript\nconst average = (items) => {\n let sum = 0\n\n for (let i = 0; i < items.length; i++) {\n sum = sum + items[i]\n }\n\n return sum / items.length\n}\n```\n\n```python\ndef get_average(items):\n sum = 0\n\n for i in range(len(items)):\n sum = sum + items[i]\n\n return sum / len(items)\n```\n\n```php\n<?php\n\nfunction average($items)\n{\n $sum = 0;\n\n for ($i = 0; $i < count($items); $i++) {\n $sum = $sum + $items[$i];\n }\n\n return $sum / count($items);\n}\n```\n\n```java\npublic class App {\n public static double average(int[] items) {\n double sum = 0;\n\n for (var i = 0; i < items.length; i++) {\n sum = sum + items[i];\n }\n\n return sum / items.length;\n }\n}\n```\n\nАнализ алгоритма показывает, что для массива из n элементов будет n+1 операция: одна инициализация плюс n операций в цикле. Кажется, что такая временная сложность должна записываться O(n+1). Однако такие варианты, как n-2, n+5 и даже n+1000, всегда записывают как O(n). На первый взгляд это кажется странным, но далее мы разберемся, почему это так. А пока рассмотрим еще один линейный алгоритм — алгоритм определения строк-палиндромов.\n\nПалиндромом называется строка, которая одинаково читается слева направо и справа налево. АНА и ABBA — это палиндромы, а YES и nO — нет:\n\n```javascript\nconst palindrome = (string) => {\n for (let i = 0; i < string.length / 2; i++) {\n if (string[i] != string[string.length - 1 - i]) {\n return false\n }\n }\n\n return true\n}\n\npalindrome('') // true\npalindrome('a') // true\npalindrome('ab') // false\npalindrome('aha') // true\npalindrome('abba') // true\n```\n\n```python\ndef palindrome(string):\n for i in range(len(string) // 2):\n if string[i] != string[len(string) - 1 - i]:\n return False\n return True\n\npalindrome('') // true\npalindrome('a') // true\npalindrome('ab') // false\npalindrome('aha') // true\npalindrome('abba') // true\n```\n\n```php\n<?php\n\nfunction palindrome($string) => {\n for ($i = 0; $i < strlen($string) / 2; i++) {\n if ($string[$i] != $string[strlen($string) - 1 - $i]) {\n return false;\n }\n }\n\n return true;\n}\n\npalindrome('') // true\npalindrome('a') // true\npalindrome('ab') // false\npalindrome('aha') // true\npalindrome('abba') // true\n```\n\n```java\npublic class App {\n public static boolean palindrome(String word) {\n for (var i = 0; i < word.length() / 2; i++) {\n if (word.charAt(i) != word.charAt(word.length() - 1 - i)) {\n return false;\n }\n }\n\n return true;\n }\n}\n\nApp.palindrome(\"\") // true\nApp.palindrome(\"a\") // true\nApp.palindrome(\"ab\") // false\nApp.palindrome(\"aha\") // true\nApp.palindrome(\"abba\") // true\n```\n\nВ этом алгоритме цикл выполняется n/2 раз, где n — длина строки. Казалось бы, сложность работы алгоритма должна быть равна O(n/2). Но, как и в прошлый раз, это не так. Алгоритмы со временем работы 2n, 10n, n/5 и n/32 — все имеют сложность O(n), и снова это кажется странным.\n\n## Квадратичная сложность\n\nКвадратичную сложность имеют все простые алгоритмы сортировки. Рассмотрим, например, сортировку выбором. Внутри нее есть вложенный цикл.\n\n```javascript\nfor (i = 0; i < items.length - 1; i++) {\n for (j = i + 1; j < items.length; j++) {\n // …\n }\n\n // …\n}\n```\n\n```python\nfor i in range(len(items) - 1):\n for j in range(i + 1, len(items):\n # ...\n # ...\n```\n\n```php\n<?php\n\nfor ($i = 0; $i < count($items) - 1; $i++) {\n for ($j = $i + 1; $j < count($items); $j++) {\n // …\n }\n\n // …\n}\n```\n\n```java\nfor (var i = 0; i < items.length - 1; i++) {\n for (var j = i + 1; j < items.length; j++) {\n // …\n }\n\n // …\n}\n```\n\nЧтобы избавиться от несущественных деталей, в коде выше убрана часть операций — вместо них пустые комментарии. Попробуем оценить количество выполнений цикла. На первом шаге внешнего цикла внутренний выполнится на один раз меньше, чем общее количество элементов, на втором — на два раза меньше, на третьем — на три раза меньше и так далее.\n\nСуммарное количество выполнений цикла можно выразить как сумму чисел от 1 до n-1. Эта сумма равна половине произведения количества элементов на количество элементов минус один. Таким образом, общее количество операций пропорционально квадрату количества элементов.\n\n```text\n(n-1) + (n-2) + (n-3) + ... + 1 = (n * (n - 1)) / 2 = (n^2 - n) / 2\n```\n\nДля расчетов мы использовали формулу суммы членов арифметической прогрессии. Среди слагаемых есть компонент, который растет как квадрат количества элементов, так что речь идет о квадратичной сложности, которая записывается как **O(n\\^2)**. И снова встает вопрос: почему мы игнорируем деление на два и вычитаемое? Настало время разобраться.\n\nКак мы уже говорили, алгоритмическая сложность позволяет сравнивать алгоритмы «в целом». Можно утверждать, что все линейные алгоритмы в целом быстрее всех квадратичных, хотя на конкретных данных возможны аномалии. Все квадратичные алгоритмы в целом быстрее всех кубических.\n\nК сожалению, сравнивая два линейных алгоритма, мы не можем сказать, какой из них быстрее. Есть соблазн использовать запись вида O(4n+1) или O(2n-3), но она толкает нас на путь ложных выводов. Определяя алгоритмическую сложность, мы считаем количество операций и предполагаем, что все они выполняются за небольшое постоянное время.\n\nНо как только речь заходит о конкретике, выясняется, что операция сложения может быть очень быстрой, а операция деления — очень медленной по сравнению со сложением. Иногда четыре сложения могут выполниться быстрее, чем два деления. Поэтому нельзя в общем случае утверждать, что O(2n - 3) быстрее, чем O(4n + 1).\n\nИменно поэтому программисты и математики избавляются от деталей в нотации O-большое. Записи вида O(2n-3), O((n\\^2)/3)+5) и O(20(n\\^4)-1000) превращаются в **O(n)**, **O(n\\^2)** и **O(n\\^4)** соответственно.\n\n## Какая еще бывает сложность\n\nТеоретически мы можем придумать алгоритмы с любой экзотической сложностью, но на практике чаще встречается всего несколько вариантов.\n\n### Константная сложность\n\nОна обозначается **O(1)**. Алгоритмы с константной временной сложностью выполняются за одно и то же время вне зависимости от количества элементов. Например, в упорядоченном массиве минимальный элемент всегда находится в самом начале, поэтому поиск минимума становится тривиальным:\n\n```javascript\nconst sortedMinimum = (sortedItems) => {\n return sortedItems[0]\n}\n```\n\n```python\ndef sorted_minimum(sorted_items):\n return sorted_items[0]\n```\n\n```php\n<?php\n\nfunction sortedMinimum($sortedItems)\n{\n return $sortedItems[0];\n}\n```\n\n```java\npublic class App {\n public static int sortedMinimum(int[] sortedItems) {\n return sortedItems[0];\n }\n}\n```\n\nЭта функция всегда выполняется за одно и то же время, независимо от размера массива `sortedItems`. Формально, константные алгоритмы считаются самыми быстрыми.\n\n### Логарифмическая сложность\n\nОбозначается **O(logn)**. За логарифмическое время работает алгоритм бинарного поиска. Эти алгоритмы относятся к быстрым, поскольку логарифмическая функция растет достаточно медленно.\n\n\n\nВ массиве из тысячи элементов бинарный поиск работает максимум за десять сравнений, а массиве из миллиона — максимум за двадцать. Обычный метод перебора имеет линейную сложность, и поэтому будет работать за тысячу и миллион сравнений соответственно:\n\n| n | O(log n) | O(n) |\n|---------|----------|---------|\n| 1000 | 10 | 1000 |\n| 1000000 | 20 | 1000000 |\n\nЛогарифмические алгоритмы считаются очень быстрыми, гораздо быстрее линейных.\n\n### Линейно-логарифмическая сложность\n\nОна обозначается как **O(nlogn)** и описывает сложность алгоритма быстрой сортировки. Сравним количество операций у быстрой сортировки и сортировки выбором — так мы увидим, почему быстрая сортировка так называется:\n\n| n | Быстрая O(nlogn) | Выбор O(n\\^2) |\n|---------|------------------|---------------|\n| 1000 | 10000 | 1000000 |\n| 1000000 | 20000000 | 1000000000000 |\n\nБыстрая сортировка упорядочивает массив из тысячи элементов приблизительно за десять тысяч операций, в то время как сортировка выбором — за миллион. Время выполнения различается в сто раз, и с ростом n разница только растет! Но важно не забывать, что на очень маленьких массивах (из десяти элементов) сортировка выбором может оказаться быстрее. Так происходит потому, что алгоритм сортировки выбором проще. Быстрая сортировка сложнее, и накладные расходы в реализации оказываются слишком велики для небольшого набора данных.\n\nЛинейно-логарифмическая сложность медленнее линейной, но быстрее квадратичной.\n\n### Экспоненциальная сложность\n\nСколько подмассивов можно получить из массива `[1, 2, 3, 4]`? Попробуем выяснить, но сначала определимся с условиями:\n\n* Подмассивы могут быть любой длины, включая ноль\n* Будем считать одним подмассивом все подмассивы, состоящие из одних и тех же элементов в разном порядке (например, `[1,2]` и `[2,1]`)\n\nВыпишем все варианты и посчитаем их:\n\n| | | | |\n|-----|-------|---------|-----------|\n| [] | [4] | [2,3] | [1,2,4] |\n| [1] | [1,2] | [2,4] | [1,3,4] |\n| [2] | [1,3] | [3,4] | [2,3,4] |\n| [3] | [1,4] | [1,2,3] | [1,2,3,4] |\n\nВсего 16. Существует общее правило, по которому возможное количество подмассивов у массива длины n составляет 2\\^n. Формулы вида 2\\^n, 3\\^n, 100\\^n называют **экспонентами**. Алгоритм, который может построить список всех подмассивов массива длины n, имеет экспоненциальную сложность O(2\\^n).\n\nАлгоритмы экспоненциальной сложности считаются медленными. Количество подмассивов у массива из тридцати элементов равно 1073741824, то есть превышает миллиард!\n\n### Факториальная сложность\nОбозначается **O(n!)**. Факториалом числа n называют произведение 1 × 2 × ... × n, то есть всех чисел от 1 до n. Сложность алгоритма, который находит все перестановки массива, равна O(n!). Вот все перестановки массива [1, 2, 3, 4]:\n\n| |\n|--------------|\n| [1, 2, 3, 4] |\n| [2, 1, 3, 4] |\n| [3, 2, 1, 4] |\n| [4, 2, 3, 1] |\n| [1, 2, 4, 3] |\n| [2, 1, 3, 3] |\n| [3, 2, 4, 1] |\n| [4, 2, 1, 3] |\n| [1, 3, 2, 4] |\n| [2, 3, 1, 4] |\n| [3, 1, 2, 4] |\n| [4, 3, 2, 1] |\n| [1, 3, 4, 2] |\n| [2, 3, 4, 1] |\n| [3, 1, 4, 2] |\n| [4, 3, 1, 2] |\n| [1, 4, 2, 3] |\n| [2, 4, 1, 3] |\n| [3, 4, 2, 1] |\n| [4, 1, 2, 3] |\n| [1, 4, 3, 2] |\n| [2, 4, 3, 1] |\n| [3, 4, 1, 3] |\n| [4, 1, 3, 2] |\n\nВсего их 4!\\=24. Факториальная сложность самая медленная из тех, что мы рассмотрели. Если нам потребуется найти все перестановки массива из тридцати элементов, их окажется 265252859812191058636308480000000, то есть 265 миллионов миллионов миллионов миллионов миллионов. Даже на самом быстром современном компьютере поиск всех перестановок займет миллионы миллионов лет.\n\n## Сводная таблица временной сложности\n\n| Название | Формула | Примеры алгоритмов |\n|-------------------------|------------|--------------------------------------------|\n| Константная | O(1) | Длина массива |\n| Логарифмическая | O(log n) | Бинарный поиск |\n| Линейная | O(n) | Поиск методом перебора |\n| Линейно-логарифмическая | O(n log n) | Быстрая сортировка |\n| Квадратичная | O(n\\^2) | Сортировка выбором, пузырьковая сортировка |\n| Экспоненциальная | O(2\\^n) | Список подмассивов |\n| Факториальная | O(n!) | Список перестановок |\n\nИногда в литературе можно встретить название **полиномиальные алгоритмы** — к ним относят алгоритмы со сложностью O(n\\^2), O(n\\^3) или O(n\\^100). Условная граница между медленными и быстрыми алгоритмами проходит между **полиномиальными** и **экспоненциальными алгоритмами**.\n\n### Оценка памяти\n\nВ нотации О-большое также оценивается память, которую потребляет алгоритм. На практике здесь редко встречаются большие значения.\n\nЕсли алгоритму для работы нужно несколько переменных, которые не зависят от размеров данных, сложность по памяти составляет O(1). Такую сложность имеют алгоритмы поиска минимума и вычисления среднего арифметического.\nЛогарифмическая сложность O(log n) встречается у рекурсивных алгоритмов, которые разбивают массив на два подмассива. Среди рассмотренных нами алгоритмов к этому классу относятся бинарный поиск и быстрая сортировка.\n\nЛинейная сложность O(n) означает, что алгоритм во время работы сохраняет дополнительные данные, размер которых соизмерим с входными данными. Например, если мы хотим избавиться от дубликатов в массиве, мы можем хранить просмотренные элементы в структуре множество `(Set)`:\n\n```javascript\nconst removeDuplicates = (items) => {\n const visited = new Set()\n for (let i = 0; i < items.length; i++) {\n if (visited.has(items[i])) {\n items.splice(i, 1)\n i--\n }\n else {\n visited.add(items[i])\n }\n }\n}\n```\n\n```python\ndef remove_duplicates(items):\n visited = set()\n i = 0\n while i < len(items):\n if items[i] in visited:\n items.pop(i)\n i -= 1\n else:\n visited.add(items[i])\n i += 1\n```\n\n```php\n<?php\n\nfunction removeDuplicates($items)\n{\n $visited = new \\DS\\Set();\n for ($i = 0; $i < count($items); $i++) {\n if ($visited->contains($items[$i])) {\n array_splice($items, $i, 1);\n $i--;\n } else {\n $visited->add($items[$i]);\n }\n }\n\n return $items;\n}\n```\n\n```java\npublic static void removeDuplicates(List<Integer> items) {\n Set<Integer> visited = new HashSet<>();\n\n for (var i = 0; i < items.size(); i++) {\n if(visited.contains(items.get(i))) {\n items.remove(i);\n i--;\n } else {\n visited.add(items.get(i));\n }\n }\n }\n```\n\nЭтих неповторяющихся элементов будет чуть меньше, чем элементов в исходном массиве. Но при этом размер множества будет соизмерим с размером массива, поэтому речь идет о линейной сложности по памяти.\n\n## Оптимизация\n\nОдна из задач, которую регулярно решают программисты — оптимизация программы. Пользователи хотят, чтобы программа работала быстрее или занимала меньше памяти.\n\nНеопытные программисты часто пытаются оптимизировать отдельные конструкции в программах, не обращая внимания на производительность в целом. Опытные же программисты оценивают сложность существующего алгоритма. Задача оптимизации сводится к тому, чтобы найти или придумать новый алгоритм с меньшей сложностью.\n\nРазберем пример с определением простоты числа. Простые числа имеют важное значение в криптографии и кодировании, так что программистам время от времени нужен список простых чисел или функция, которая определяет, является ли число простым.\n\nОпределение простых чисел и звучит очень просто — простые числа делятся на себя и на единицу. Но проверить число на простоту уже сложнее — попробуйте, например, выяснить — простое ли число 1073676287?\n\nДля определения простоты числа можно использовать один из самых древних, известных человечеству, алгоритмов — **Решето Эратосфена**. Сначала мы записываем список чисел, начиная с двойки:\n\n| | | | | |\n|:--:|:--:|:--:|:--:|:--:|\n| 2 | 3 | 4 | 5 | 6 |\n| 7 | 8 | 9 | 10 | 11 |\n| 12 | 13 | 14 | 15 | 16 |\n| 17 | 18 | 19 | 20 | 21 |\n| 22 | 23 | 24 | 25 | 26 |\n\nБерем первое число — двойку. Выделяем цветом числа, которые делятся на нее. Саму двойку не выделяем:\n\n| | | | | |\n|:--------:|:--------:|:--------:|:--------:|:--------:|\n| 2 | 3 | ***4*** | 5 | ***6*** |\n| 7 | ***8*** | 9 | ***10*** | 11 |\n| ***12*** | 13 | 14 | 15 | 16 |\n| 17 | ***18*** | 19 | ***20*** | 21 |\n| ***22*** | 23 | ***24*** | 25 | ***26*** |\n\nСледующее неотмеченное число — три. Выделяем цветом числа, которые делятся на три, но не саму тройку:\n\n| | | | | |\n|:--------:|:--------:|:--------:|:--------:|:--------:|\n| 2 | 3 | ***4*** | 5 | ***6*** |\n| 7 | ***8*** | ***9*** | ***10*** | 11 |\n| ***12*** | 13 | ***14*** | ***15*** | ***16*** |\n| 17 | ***18*** | 19 | ***20*** | ***21*** |\n| ***22*** | 23 | ***24*** | 25 | ***26*** |\n\nЧетверка зачеркнута — она делится на два, поэтому мы ее пропускаем.\n\nПереходим к пятерке. У нас уже отмечены числа 10, 20 (оба делятся на два) и 15 (делится на три). Единственное неотмеченное число — это 25. Это подсказка, которая помогает понять одну важную мысль — чтобы составить список простых чисел вплоть до n, достаточно повторить эту процедуру только для чисел от 2 до sqrt(n).\n\nСама процедура выделения чисел на каждой итерации пробегает n чисел. Итого, выходит n чисел на итерацию и sqrt(n) итераций. Сложность алгоритма по времени равна O(n * sqrt(n)) или в более математической записи — O(n\\^(3/2)). При этом нам приходится выделять память для всех n чисел, поэтому сложность по памяти равна **O(n)**.\n\nРешето Эратосфена — сложный алгоритм, как по времени, так и по памяти.\n\nЧтобы оптимизировать решение, мы должны найти или придумать другой алгоритм. Обратим внимание, что Решето строит список простых чисел от 2 до n, но нам нужно только последнее число n. Мы можем проверить, что число не делится ни на какие целые числа от 2 до n-1:\n\n```javascript\nconst isPrime = (n) => {\n for (let i = 2; i < n; i++) {\n if (n % i == 0) {\n return false\n }\n }\n\n return true\n}\n```\n\n```python\ndef is_prime(n):\n for i in range(2, n):\n if n % i == 0:\n return False\n return True\n```\n\n```php\nfunction isPrime(int $n): bool\n{\n if ($n < 2) {\n return false;\n }\n\n for ($i = 2; $i < $n; $i++) {\n if ($n % $i == 0) {\n return false;\n }\n }\n\n return true;\n}\n```\n\n```java\npublic class App {\n public static boolean isPrime(int n) {\n for (var i = 2; i < n; i++) {\n if (n % i == 0) {\n return false;\n }\n }\n\n return true;\n }\n}\n```\n\nЭтот алгоритм линейный по времени, он работает за O(n). Он константный по памяти, O(1), поскольку количество потребляемой памяти не зависит от n.\n\nОн работает гораздо быстрее Решета, но все еще не самый оптимальный. Как мы помним, для проверки нам не обязательно делить n на все числа меньше себя, достаточно проверить только числа от 2 до sqrt(n), так что алгоритм можно переписать.\n\nАлгоритмическая сложность переписанного алгоритма равна O(sqrt(n)) или O(n\\^(1/2)).\n\n## Выводы\n\n1. При общих равных условиях программисты выбирают самые быстрые и самые экономичные алгоритмы\n2. Выбрать самый быстрый алгоритм оказывается не так просто. Измерения на конкретных данных не позволяют прогнозировать время и память алгоритмов на других данных\n3. Программисты используют нотацию О-большое, чтобы оценить производительность алгоритмов в целом\n4. Чаще всего встречаются такие сложности, как константная, логарифмическая, линейная, линейно-логарифмическая, квадратическая, экспоненциальная и факториальная. В этом списке они распределены в порядке от самой быстрой к самой медленной\n5. Нотация О-большое оценивает не только скорость алгоритма, но и память, которую он использует\n"},"lessonMember":null,"courseMember":null,"course":{"start_lesson":{"exercise":null,"units":[{"id":4581,"name":"theory","url":"/courses/basic-algorithms/lessons/intro/theory_unit"}],"links":[],"ordered_units":[{"id":4581,"name":"theory","url":"/courses/basic-algorithms/lessons/intro/theory_unit"}],"id":2044,"slug":"intro","state":"approved","name":"Введение","course_order":100,"goal":"Знакомимся с темой курса","self_study":null,"theory_video_provider":null,"theory_video_uid":null,"theory":"> «Плохие программисты думают о коде. Хорошие программисты думают о структурах данных и их взаимосвязях», — Линус Торвальдс, создатель Linux.\n\nАлгоритмы и структуры данных — основа Computer Science. Даже если вы не собираетесь писать алгоритмы или реализовывать структуры, их знание потребуется вам для понимания почему, как, и где использовать уже имеющиеся инструменты (библиотеки, фреймворки, базы данных). А хорошее владение этой темой открывает путь в мир сложных задач (поисковые системы, карты, компиляторы, нейронные сети, UI-фреймворки), и именно поэтому она должна входить в базовый набор знаний программиста.\n\nВ этом курсе рассмотрим следующие темы:\n\n- Алгоритмы поиска и сортировки.\n- Оценка сложности алгоритмов (сколько нужно сделать шагов и сколько памяти потребуется для решения задачи).\n- Реализация структур данных, стека, очереди, связного списка.\n- Жадные алгоритмы.\n- Динамическое программирование.\n\n## Зачем это нужно?\n\n- Получить необходимые знания перед изучением графов, деревьев, машинного обучения.\n- Для развития в качестве профессионального разработчика.\n- Для развития алгоритмического мышления.\n- Для подготовки к собеседованию.\n"},"id":222,"slug":"basic-algorithms","challenges_count":5,"name":"Основы алгоритмов и структур данных","allow_indexing":true,"state":"approved","course_state":"finished","pricing_type":"paid","description":"Курс посвящен знакомству со структурами данных, алгоритмами поиска и сортировки. Здесь мы на практике разберем, в каких ситуациях подходит тот или иной алгоритм. Вы научитесь оценивать сложность алгоритмов с помощью нотации «О-большое» — узнавать их сложность, скорость и затраты памяти. За время курса вы напишете свою реализацию структур данных.","kind":"basic","updated_at":"2026-02-12T14:03:31.332Z","language":"javascript","duration_cache":38520,"skills":["Определять эффективность алгоритмов","Выбирать подходящую структуру данных в зависимости от ситуации","Определять NP-полные задачи и находить приближенное решение"],"keywords":["Алгоритмы сортировки","Структуры данных","Бинарный поиск","Жадные алгоритмы","Асимптотический анализ"],"lessons_count":9,"cover":"https://hexlet.io/rails/active_storage/representations/proxy/eyJfcmFpbHMiOnsiZGF0YSI6MTQzMDksInB1ciI6ImJsb2JfaWQifX0=--7159d348a0cee778c91291e2f50f87b02ac3dcc6/eyJfcmFpbHMiOnsiZGF0YSI6eyJmb3JtYXQiOiJwbmciLCJyZXNpemVfdG9fZmlsbCI6WzYwMCw0MDBdfSwicHVyIjoidmFyaWF0aW9uIn19--6067466c2912ca31a17eddee04b8cf2a38c6ad17/image.png"},"recommendedLandings":[{"stack":{"id":34,"slug":"algorithms","title":"Алгоритмы и структуры данных","audience":"for_programmers","start_type":"anytime","pricing_model":"subscription","priority":"medium","kind":"track","state":"published","stack_state":"finished","order":4000,"duration_in_months":2},"id":56,"slug":"algorithms","title":"Алгоритмы и структуры данных","subtitle":"Навык, который увеличит ваши шансы пройти алгоритмическое интервью в международные компании на 80%","subtitle_for_lists":"Алгоритмы для собеседований","locale":"ru","current":true,"duration_in_months_text":"2 месяца","stack_slug":"algorithms","price_text":"от 3 900 ₽","duration_text":"2 месяца","cover_list_variant":"https://hexlet.io/rails/active_storage/representations/proxy/eyJfcmFpbHMiOnsiZGF0YSI6NDAyOCwicHVyIjoiYmxvYl9pZCJ9fQ==--ae9eed98663dd1201759d042a5ba7ca790866156/eyJfcmFpbHMiOnsiZGF0YSI6eyJmb3JtYXQiOiJ3ZWJwIiwicmVzaXplX3RvX2xpbWl0IjpbNDAwLDQwMF0sInNhdmVyIjp7InF1YWxpdHkiOjg1fX0sInB1ciI6InZhcmlhdGlvbiJ9fQ==--5b6f46dacd1af664f27558553a58076185091823/Programming-bro.png"}],"lessonMemberUnit":null,"accessToLearnUnitExists":false,"accessToCourseExists":false},"url":"/courses/basic-algorithms/lessons/algorithm-complexity/theory_unit","version":"0b0c6d4ebbd40fd58630a0dd89cc25544ccdf24e","encryptHistory":false,"clearHistory":false}"><style data-mantine-styles="true">:root, :host{--mantine-font-family: Arial, sans-serif;--mantine-font-family-headings: Arial, sans-serif;--mantine-heading-font-weight: normal;--mantine-radius-default: 0rem;--mantine-primary-color-filled: var(--mantine-color-indigo-filled);--mantine-primary-color-filled-hover: var(--mantine-color-indigo-filled-hover);--mantine-primary-color-light: var(--mantine-color-indigo-light);--mantine-primary-color-light-hover: var(--mantine-color-indigo-light-hover);--mantine-primary-color-light-color: var(--mantine-color-indigo-light-color);--mantine-spacing-xxl: calc(4rem * var(--mantine-scale));--mantine-font-size-xs: 12px;--mantine-font-size-sm: 14px;--mantine-font-size-md: 16px;--mantine-font-size-lg: clamp(16.0000px, calc(15.2727px + 0.2273vw), 18.0000px);--mantine-font-size-xl: clamp(16.0000px, calc(14.5455px + 0.4545vw), 20.0000px);--mantine-font-size-display-3: clamp(32.0000px, calc(26.1818px + 1.8182vw), 48.0000px);--mantine-font-size-display-2: clamp(36.0000px, calc(25.8182px + 3.1818vw), 64.0000px);--mantine-font-size-display-1: clamp(40.0000px, calc(25.4545px + 4.5455vw), 80.0000px);--mantine-font-size-h1: clamp(28.0000px, calc(23.6364px + 1.3636vw), 40.0000px);--mantine-font-size-h2: clamp(24.0000px, calc(21.0909px + 0.9091vw), 32.0000px);--mantine-font-size-h3: clamp(20.0000px, calc(17.0909px + 0.9091vw), 28.0000px);--mantine-font-size-h4: clamp(16.0000px, calc(13.0909px + 0.9091vw), 24.0000px);--mantine-font-size-h5: clamp(16.0000px, calc(14.5455px + 0.4545vw), 20.0000px);--mantine-font-size-h6: 1rem;--mantine-primary-color-0: var(--mantine-color-indigo-0);--mantine-primary-color-1: var(--mantine-color-indigo-1);--mantine-primary-color-2: var(--mantine-color-indigo-2);--mantine-primary-color-3: var(--mantine-color-indigo-3);--mantine-primary-color-4: var(--mantine-color-indigo-4);--mantine-primary-color-5: var(--mantine-color-indigo-5);--mantine-primary-color-6: var(--mantine-color-indigo-6);--mantine-primary-color-7: var(--mantine-color-indigo-7);--mantine-primary-color-8: var(--mantine-color-indigo-8);--mantine-primary-color-9: var(--mantine-color-indigo-9);--mantine-color-red-0: #ffeaea;--mantine-color-red-1: #fed4d4;--mantine-color-red-2: #f4a7a8;--mantine-color-red-3: #ec7878;--mantine-color-red-4: #e55050;--mantine-color-red-5: #e03131;--mantine-color-red-6: #e02829;--mantine-color-red-7: #c71a1c;--mantine-color-red-8: #b21218;--mantine-color-red-9: #9c0411;--mantine-color-violet-0: #fce9ff;--mantine-color-violet-1: #f1cfff;--mantine-color-violet-2: #e09bff;--mantine-color-violet-3: #d16fff;--mantine-color-violet-4: #be37fe;--mantine-color-violet-5: #b51afe;--mantine-color-violet-6: #b009ff;--mantine-color-violet-7: #9b00e4;--mantine-color-violet-8: #8a00cc;--mantine-color-violet-9: #7800b3;--mantine-color-indigo-0: #edecff;--mantine-color-indigo-1: #d6d5fe;--mantine-color-indigo-2: #aaa9f4;--mantine-color-indigo-3: #7b79eb;--mantine-color-indigo-4: #5451e4;--mantine-color-indigo-5: #3b37e0;--mantine-color-indigo-6: #2d2adf;--mantine-color-indigo-7: #1f1ec7;--mantine-color-indigo-8: #1819b2;--mantine-color-indigo-9: #0c149e;--mantine-color-cyan-0: #dffdff;--mantine-color-cyan-1: #caf5ff;--mantine-color-cyan-2: #99e8ff;--mantine-color-cyan-3: #64daff;--mantine-color-cyan-4: #3ccffe;--mantine-color-cyan-5: #24c8fe;--mantine-color-cyan-6: #00c2ff;--mantine-color-cyan-7: #00ade4;--mantine-color-cyan-8: #009acd;--mantine-color-cyan-9: #0085b5;--mantine-color-green-0: #e9fdec;--mantine-color-green-1: #d7f6dc;--mantine-color-green-2: #b0eab9;--mantine-color-green-3: #86df94;--mantine-color-green-4: #62d574;--mantine-color-green-5: #4ccf5f;--mantine-color-green-6: #3fcc54;--mantine-color-green-7: #2fb344;--mantine-color-green-8: #25a03b;--mantine-color-green-9: #138a2e;--mantine-color-yellow-0: #fff7e2;--mantine-color-yellow-1: #ffeecd;--mantine-color-yellow-2: #ffdc9c;--mantine-color-yellow-3: #ffc966;--mantine-color-yellow-4: #feb93a;--mantine-color-yellow-5: #feae1e;--mantine-color-yellow-6: #ffa90f;--mantine-color-yellow-8: #ca8200;--mantine-color-yellow-9: #af7000;--mantine-h1-font-size: clamp(28.0000px, calc(23.6364px + 1.3636vw), 40.0000px);--mantine-h1-font-weight: normal;--mantine-h2-font-size: clamp(24.0000px, calc(21.0909px + 0.9091vw), 32.0000px);--mantine-h2-font-weight: normal;--mantine-h3-font-size: clamp(20.0000px, calc(17.0909px + 0.9091vw), 28.0000px);--mantine-h3-font-weight: normal;--mantine-h4-font-size: clamp(16.0000px, calc(13.0909px + 0.9091vw), 24.0000px);--mantine-h4-font-weight: normal;--mantine-h5-font-size: clamp(16.0000px, calc(14.5455px + 0.4545vw), 20.0000px);--mantine-h5-font-weight: normal;--mantine-h6-font-size: 1rem;--mantine-h6-font-weight: normal;}
:root[data-mantine-color-scheme="dark"], :host([data-mantine-color-scheme="dark"]){--mantine-color-anchor: var(--mantine-color-text);--mantine-color-dimmed: #495057;--mantine-color-dark-filled: var(--mantine-color-dark-5);--mantine-color-dark-filled-hover: var(--mantine-color-dark-6);--mantine-color-dark-light: rgba(105, 105, 105, 0.15);--mantine-color-dark-light-hover: rgba(105, 105, 105, 0.2);--mantine-color-dark-light-color: var(--mantine-color-dark-0);--mantine-color-dark-outline: var(--mantine-color-dark-1);--mantine-color-dark-outline-hover: rgba(184, 184, 184, 0.05);--mantine-color-gray-filled: var(--mantine-color-gray-5);--mantine-color-gray-filled-hover: var(--mantine-color-gray-6);--mantine-color-gray-light: rgba(222, 226, 230, 0.15);--mantine-color-gray-light-hover: rgba(222, 226, 230, 0.2);--mantine-color-gray-light-color: var(--mantine-color-gray-0);--mantine-color-gray-outline: var(--mantine-color-gray-1);--mantine-color-gray-outline-hover: rgba(241, 243, 245, 0.05);--mantine-color-red-filled: var(--mantine-color-red-5);--mantine-color-red-filled-hover: var(--mantine-color-red-6);--mantine-color-red-light: rgba(236, 120, 120, 0.15);--mantine-color-red-light-hover: rgba(236, 120, 120, 0.2);--mantine-color-red-light-color: var(--mantine-color-red-0);--mantine-color-red-outline: var(--mantine-color-red-1);--mantine-color-red-outline-hover: rgba(254, 212, 212, 0.05);--mantine-color-pink-filled: var(--mantine-color-pink-5);--mantine-color-pink-filled-hover: var(--mantine-color-pink-6);--mantine-color-pink-light: rgba(250, 162, 193, 0.15);--mantine-color-pink-light-hover: rgba(250, 162, 193, 0.2);--mantine-color-pink-light-color: var(--mantine-color-pink-0);--mantine-color-pink-outline: var(--mantine-color-pink-1);--mantine-color-pink-outline-hover: rgba(255, 222, 235, 0.05);--mantine-color-grape-filled: var(--mantine-color-grape-5);--mantine-color-grape-filled-hover: var(--mantine-color-grape-6);--mantine-color-grape-light: rgba(229, 153, 247, 0.15);--mantine-color-grape-light-hover: rgba(229, 153, 247, 0.2);--mantine-color-grape-light-color: var(--mantine-color-grape-0);--mantine-color-grape-outline: var(--mantine-color-grape-1);--mantine-color-grape-outline-hover: rgba(243, 217, 250, 0.05);--mantine-color-violet-filled: var(--mantine-color-violet-5);--mantine-color-violet-filled-hover: var(--mantine-color-violet-6);--mantine-color-violet-light: rgba(209, 111, 255, 0.15);--mantine-color-violet-light-hover: rgba(209, 111, 255, 0.2);--mantine-color-violet-light-color: var(--mantine-color-violet-0);--mantine-color-violet-outline: var(--mantine-color-violet-1);--mantine-color-violet-outline-hover: rgba(241, 207, 255, 0.05);--mantine-color-indigo-filled: var(--mantine-color-indigo-5);--mantine-color-indigo-filled-hover: var(--mantine-color-indigo-6);--mantine-color-indigo-light: rgba(123, 121, 235, 0.15);--mantine-color-indigo-light-hover: rgba(123, 121, 235, 0.2);--mantine-color-indigo-light-color: var(--mantine-color-indigo-0);--mantine-color-indigo-outline: var(--mantine-color-indigo-1);--mantine-color-indigo-outline-hover: rgba(214, 213, 254, 0.05);--mantine-color-blue-filled: var(--mantine-color-blue-5);--mantine-color-blue-filled-hover: var(--mantine-color-blue-6);--mantine-color-blue-light: rgba(116, 192, 252, 0.15);--mantine-color-blue-light-hover: rgba(116, 192, 252, 0.2);--mantine-color-blue-light-color: var(--mantine-color-blue-0);--mantine-color-blue-outline: var(--mantine-color-blue-1);--mantine-color-blue-outline-hover: rgba(208, 235, 255, 0.05);--mantine-color-cyan-filled: var(--mantine-color-cyan-5);--mantine-color-cyan-filled-hover: var(--mantine-color-cyan-6);--mantine-color-cyan-light: rgba(100, 218, 255, 0.15);--mantine-color-cyan-light-hover: rgba(100, 218, 255, 0.2);--mantine-color-cyan-light-color: var(--mantine-color-cyan-0);--mantine-color-cyan-outline: var(--mantine-color-cyan-1);--mantine-color-cyan-outline-hover: rgba(202, 245, 255, 0.05);--mantine-color-teal-filled: var(--mantine-color-teal-5);--mantine-color-teal-filled-hover: var(--mantine-color-teal-6);--mantine-color-teal-light: rgba(99, 230, 190, 0.15);--mantine-color-teal-light-hover: rgba(99, 230, 190, 0.2);--mantine-color-teal-light-color: var(--mantine-color-teal-0);--mantine-color-teal-outline: var(--mantine-color-teal-1);--mantine-color-teal-outline-hover: rgba(195, 250, 232, 0.05);--mantine-color-green-filled: var(--mantine-color-green-5);--mantine-color-green-filled-hover: var(--mantine-color-green-6);--mantine-color-green-light: rgba(134, 223, 148, 0.15);--mantine-color-green-light-hover: rgba(134, 223, 148, 0.2);--mantine-color-green-light-color: var(--mantine-color-green-0);--mantine-color-green-outline: var(--mantine-color-green-1);--mantine-color-green-outline-hover: rgba(215, 246, 220, 0.05);--mantine-color-lime-filled: var(--mantine-color-lime-5);--mantine-color-lime-filled-hover: var(--mantine-color-lime-6);--mantine-color-lime-light: rgba(192, 235, 117, 0.15);--mantine-color-lime-light-hover: rgba(192, 235, 117, 0.2);--mantine-color-lime-light-color: var(--mantine-color-lime-0);--mantine-color-lime-outline: var(--mantine-color-lime-1);--mantine-color-lime-outline-hover: rgba(233, 250, 200, 0.05);--mantine-color-yellow-filled: var(--mantine-color-yellow-5);--mantine-color-yellow-filled-hover: var(--mantine-color-yellow-6);--mantine-color-yellow-light: rgba(255, 201, 102, 0.15);--mantine-color-yellow-light-hover: rgba(255, 201, 102, 0.2);--mantine-color-yellow-light-color: var(--mantine-color-yellow-0);--mantine-color-yellow-outline: var(--mantine-color-yellow-1);--mantine-color-yellow-outline-hover: rgba(255, 238, 205, 0.05);--mantine-color-orange-filled: var(--mantine-color-orange-5);--mantine-color-orange-filled-hover: var(--mantine-color-orange-6);--mantine-color-orange-light: rgba(255, 192, 120, 0.15);--mantine-color-orange-light-hover: rgba(255, 192, 120, 0.2);--mantine-color-orange-light-color: var(--mantine-color-orange-0);--mantine-color-orange-outline: var(--mantine-color-orange-1);--mantine-color-orange-outline-hover: rgba(255, 232, 204, 0.05);--app-cta-gradient: linear-gradient(90deg, var(--mantine-color-blue-9) 0%, var(--mantine-color-cyan-7) 100%);--app-color-surface: #2e2e2e;}
:root[data-mantine-color-scheme="light"], :host([data-mantine-color-scheme="light"]){--mantine-color-anchor: var(--mantine-color-text);--mantine-color-dimmed: #495057;--mantine-color-red-light: rgba(224, 40, 41, 0.1);--mantine-color-red-light-hover: rgba(224, 40, 41, 0.12);--mantine-color-red-outline-hover: rgba(224, 40, 41, 0.05);--mantine-color-violet-light: rgba(176, 9, 255, 0.1);--mantine-color-violet-light-hover: rgba(176, 9, 255, 0.12);--mantine-color-violet-outline-hover: rgba(176, 9, 255, 0.05);--mantine-color-indigo-light: rgba(45, 42, 223, 0.1);--mantine-color-indigo-light-hover: rgba(45, 42, 223, 0.12);--mantine-color-indigo-outline-hover: rgba(45, 42, 223, 0.05);--mantine-color-cyan-light: rgba(0, 194, 255, 0.1);--mantine-color-cyan-light-hover: rgba(0, 194, 255, 0.12);--mantine-color-cyan-outline-hover: rgba(0, 194, 255, 0.05);--mantine-color-green-light: rgba(63, 204, 84, 0.1);--mantine-color-green-light-hover: rgba(63, 204, 84, 0.12);--mantine-color-green-outline-hover: rgba(63, 204, 84, 0.05);--mantine-color-yellow-light: rgba(255, 169, 15, 0.1);--mantine-color-yellow-light-hover: rgba(255, 169, 15, 0.12);--mantine-color-yellow-outline-hover: rgba(255, 169, 15, 0.05);--app-color-surface: #f1f3f5;--app-cta-gradient: linear-gradient(90deg, var(--mantine-color-blue-filled) 0%, var(--mantine-color-cyan-5) 100%);}</style><style data-mantine-styles="classes">@media (max-width: 35.99375em) {.mantine-visible-from-xs {display: none !important;}}@media (min-width: 36em) {.mantine-hidden-from-xs {display: none !important;}}@media (max-width: 47.99375em) {.mantine-visible-from-sm {display: none !important;}}@media (min-width: 48em) {.mantine-hidden-from-sm {display: none !important;}}@media (max-width: 61.99375em) {.mantine-visible-from-md {display: none !important;}}@media (min-width: 62em) {.mantine-hidden-from-md {display: none !important;}}@media (max-width: 74.99375em) {.mantine-visible-from-lg {display: none !important;}}@media (min-width: 75em) {.mantine-hidden-from-lg {display: none !important;}}@media (max-width: 87.99375em) {.mantine-visible-from-xl {display: none !important;}}@media (min-width: 88em) {.mantine-hidden-from-xl {display: none !important;}}</style><div style="position:absolute;top:0rem" class=""></div><div style="max-width:var(--container-size-xl);height:100%;min-height:0rem" class=""><style data-mantine-styles="inline">.__m__-_R_5ub_{--grid-gutter:0rem;}</style><div style="height:100%;min-height:0rem" class="m_410352e9 mantine-Grid-root __m__-_R_5ub_"><div class="m_dee7bd2f mantine-Grid-inner" style="height:100%"><style data-mantine-styles="inline">.__m__-_R_rdub_{--col-flex-grow:auto;--col-flex-basis:91.66666666666667%;--col-max-width:91.66666666666667%;}@media(min-width: 48em){.__m__-_R_rdub_{--col-flex-grow:auto;--col-flex-basis:83.33333333333334%;--col-max-width:83.33333333333334%;}}</style><div style="min-width:0rem;height:100%;min-height:0rem;display:flex" class="m_96bdd299 mantine-Grid-col __m__-_R_rdub_"><style data-mantine-styles="inline">.__m__-_R_6qrdub_{margin-top:0rem;padding-inline:var(--mantine-spacing-xs);width:100%;}@media(min-width: 48em){.__m__-_R_6qrdub_{margin-top:var(--mantine-spacing-xl);width:80%;}}@media(min-width: 62em){.__m__-_R_6qrdub_{padding-inline:var(--mantine-spacing-xl);}}</style><div style="margin-inline:auto;max-width:var(--mantine-breakpoint-xl)" class="__m__-_R_6qrdub_"><div style="color:var(--mantine-color-dimmed)" class="m_4451eb3a mantine-Center-root" data-inline="true"><div style="--ti-size:var(--ti-size-xs);--ti-bg:transparent;--ti-color:var(--mantine-color-indigo-light-color);--ti-bd:calc(0.0625rem * var(--mantine-scale)) solid transparent;margin-inline-end:calc(0.125rem * var(--mantine-scale));color:inherit" class="m_7341320d mantine-ThemeIcon-root" data-variant="transparent" data-size="xs"><svg xmlns="http://www.w3.org/2000/svg" width="24" height="24" viewBox="0 0 24 24" fill="none" stroke="currentColor" stroke-width="2" stroke-linecap="round" stroke-linejoin="round" class="tabler-icon tabler-icon-lock "><path d="M5 13a2 2 0 0 1 2 -2h10a2 2 0 0 1 2 2v6a2 2 0 0 1 -2 2h-10a2 2 0 0 1 -2 -2v-6"></path><path d="M11 16a1 1 0 1 0 2 0a1 1 0 0 0 -2 0"></path><path d="M8 11v-4a4 4 0 1 1 8 0v4"></path></svg></div><p style="font-size:var(--mantine-font-size-sm)" class="mantine-focus-auto m_b6d8b162 mantine-Text-root">Основы алгоритмов и структур данных</p></div><h1 style="--title-fw:var(--mantine-h1-font-weight);--title-lh:var(--mantine-h1-line-height);--title-fz:var(--mantine-h1-font-size);margin-bottom:var(--mantine-spacing-xl)" class="m_8a5d1357 mantine-Title-root" data-order="1">Теория: Алгоритмическая сложность</h1><script type="application/ld+json">{"@context":"https://schema.org","@type":"LearningResource","name":"Алгоритмическая сложность","inLanguage":"ru","isPartOf":{"@type":"LearningResource","name":"Основы алгоритмов и структур данных"},"isAccessibleForFree":"False","hasPart":{"@type":"WebPageElement","isAccessibleForFree":"False","cssSelector":".paywalled"}}</script><div class=""><div style="--alert-color:var(--mantine-color-indigo-light-color);margin-bottom:var(--mantine-spacing-lg);font-size:var(--mantine-font-size-lg)" class="m_66836ed3 mantine-Alert-root" id="mantine-_R_remqrdub_" role="alert" aria-describedby="mantine-_R_remqrdub_-body" aria-labelledby="mantine-_R_remqrdub_-title"><div class="m_a5d60502 mantine-Alert-wrapper"><div class="m_667f2a6a mantine-Alert-icon"><svg xmlns="http://www.w3.org/2000/svg" width="24" height="24" viewBox="0 0 24 24" fill="none" stroke="currentColor" stroke-width="2" stroke-linecap="round" stroke-linejoin="round" class="tabler-icon tabler-icon-rocket "><path d="M4 13a8 8 0 0 1 7 7a6 6 0 0 0 3 -5a9 9 0 0 0 6 -8a3 3 0 0 0 -3 -3a9 9 0 0 0 -8 6a6 6 0 0 0 -5 3"></path><path d="M7 14a6 6 0 0 0 -3 6a6 6 0 0 0 6 -3"></path><path d="M14 9a1 1 0 1 0 2 0a1 1 0 1 0 -2 0"></path></svg></div><div class="m_667c2793 mantine-Alert-body"><div class="m_6a03f287 mantine-Alert-title"><span id="mantine-_R_remqrdub_-title" class="m_698f4f23 mantine-Alert-label">Полный доступ к материалам</span></div><div id="mantine-_R_remqrdub_-body" class="m_7fa78076 mantine-Alert-message"><div style="--group-gap:var(--mantine-spacing-md);--group-align:center;--group-justify:space-between;--group-wrap:wrap" class="m_4081bf90 mantine-Group-root"><p class="mantine-focus-auto m_b6d8b162 mantine-Text-root">Зарегистрируйтесь и получите доступ к этому и десяткам других курсов</p><a style="--button-height:var(--button-height-xs);--button-padding-x:var(--button-padding-x-xs);--button-fz:var(--mantine-font-size-xs);--button-bg:linear-gradient(45deg, var(--mantine-color-blue-filled) 0%, var(--mantine-color-cyan-filled) 100%);--button-hover:linear-gradient(45deg, var(--mantine-color-blue-filled) 0%, var(--mantine-color-cyan-filled) 100%);--button-color:var(--mantine-color-white);--button-bd:none" class="mantine-focus-auto mantine-active m_77c9d27d mantine-Button-root m_87cf2631 mantine-UnstyledButton-root" data-variant="gradient" data-size="xs" href="/u/new"><span class="m_80f1301b mantine-Button-inner"><span class="m_811560b9 mantine-Button-label">Зарегистрироваться</span></span></a></div></div></div></div></div><div class="paywalled m_d08caa0 mantine-Typography-root"><p>В программировании используются алгоритмы, которые по-разному решают одну и ту же задачу: например, сортировку массива. При этом алгоритмы работают с разной скоростью и требуют разное количество памяти. При прочих равных условиях мы бы выбрали быстрый или нетребовательный алгоритм.</p>
<p>Чтобы правильно выбирать алгоритмы, нужно научиться сравнивать их, чем мы и займемся в этом уроке. Мы познакомимся с двумя основными способами, разберем их плюсы и минусы. Опираясь на эти способы, мы сравним время работы уже знакомых нам алгоритмов.</p>
<h2 id="heading-2-1">Как оценить скорость алгоритма</h2>
<p>Скорость алгоритмов можно сравнивать самым очевидным способом — физически измерить время выполнения на одних и тех же данных. Чтобы сравнить сортировку выбором и быструю сортировку, мы можем взять массив из нескольких элементов и измерить время быстрой сортировки:</p>
<div class="m_5cb1b9c8 mantine-CodeHighlightTabs-root"><div style="--sa-corner-width:0px;--sa-corner-height:0px" class="m_7b14120b mantine-CodeHighlightTabs-filesScrollarea m_d57069b5 mantine-ScrollArea-root" dir="ltr"><div style="overflow-x:hidden;overflow-y:hidden" class="m_c0783ff9 mantine-ScrollArea-viewport" data-scrollbars="xy"><div class="m_b1336c6 mantine-ScrollArea-content"><div class="m_38d99e51 mantine-CodeHighlightTabs-files"><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" data-active="true" type="button"><span>javascript</span></button><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" type="button"><span>python</span></button><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" type="button"><span>php</span></button><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" type="button"><span>java</span></button></div></div></div><div data-orientation="horizontal" class="m_c44ba933 mantine-ScrollArea-scrollbar" data-hidden="true" style="position:absolute;--sa-thumb-width:18px" data-mantine-scrollbar="true"></div><div class="m_c44ba933 mantine-ScrollArea-scrollbar" data-hidden="true" data-orientation="vertical" style="position:absolute;--sa-thumb-height:18px" data-mantine-scrollbar="true"></div></div><div style="margin-bottom:var(--mantine-spacing-lg)" class="m_e597c321 mantine-CodeHighlightTabs-codeHighlight" dir="ltr"><div class="m_be7e9c9c mantine-CodeHighlightTabs-controls" data-with-offset="true"><button style="--ai-bg:transparent;--ai-hover:transparent;--ai-color:inherit;--ai-bd:none" class="mantine-focus-auto mantine-active m_d498bab7 mantine-CodeHighlightTabs-control m_8d3f4000 mantine-ActionIcon-root m_87cf2631 mantine-UnstyledButton-root" data-variant="none" type="button" aria-label="Copy code"><span class="m_8d3afb97 mantine-ActionIcon-icon"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round"><path stroke="none" d="M0 0h24v24H0z" fill="none"></path><path d="M8 8m0 2a2 2 0 0 1 2 -2h8a2 2 0 0 1 2 2v8a2 2 0 0 1 -2 2h-8a2 2 0 0 1 -2 -2z"></path><path d="M16 8v-2a2 2 0 0 0 -2 -2h-8a2 2 0 0 0 -2 2v8a2 2 0 0 0 2 2h2"></path></svg></span></button></div><div style="--scrollarea-scrollbar-size:calc(0.25rem * var(--mantine-scale));--sa-corner-width:0px;--sa-corner-height:0px" class="m_f744fd40 mantine-CodeHighlightTabs-scrollarea m_d57069b5 mantine-ScrollArea-root" dir="ltr"><div style="overflow-x:hidden;overflow-y:hidden;overscroll-behavior-inline:none" class="m_c0783ff9 mantine-ScrollArea-viewport" data-scrollbars="xy"><div class="m_b1336c6 mantine-ScrollArea-content"><pre class="m_2c47c4fd mantine-CodeHighlightTabs-pre" data-with-offset="true"><code class="m_5caae6d3 mantine-CodeHighlightTabs-code">const quickSort = (items) => {
const partition = (items, left, right, pivot) => {
while (true) {
while (items[left] < pivot) {
left++
}
while (items[right] > pivot) {
right--
}
if (left >= right) {
return right + 1
}
const t = items[left]
items[left] = items[right]
items[right] = t
left++
right--
}
}
const quickSort = (items, left, right) => {
const length = right - left + 1
if (length < 2) {
return
}
const pivot = items[left]
const split_index = partition(items, left, right, pivot)
quickSort(items, left, split_index - 1)
quickSort(items, split_index, right)
}
quickSort(items, 0, items.length - 1)
}; const items = [86, 66, 44, 77, 56, 64, 76, 39, 32, 93, 33, 54, 63, 96, 5, 41, 20, 58, 55, 28]
const start = performance.now()
quickSort(items)
const end = performance.now()
console.log(end - start) // => 0.20 миллисекунд</code></pre></div></div></div><button class="mantine-focus-auto m_c9378bc2 mantine-CodeHighlightTabs-showCodeButton m_87cf2631 mantine-UnstyledButton-root" data-hidden="true" type="button">Expand code</button></div></div><p>Алгоритм быстрой сортировки мы уже разбирали. Единственное, что нам пока не встречалось — вызов метода <code style="margin-bottom:var(--mantine-spacing-lg)" class="m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight m_e597c321 mantine-CodeHighlight-codeHighlight m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight">performance.now()</code>.</p>
<p><em>Performance</em> — это объект в глобальной области видимости, который используют для измерения производительности. Метод <code style="margin-bottom:var(--mantine-spacing-lg)" class="m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight m_e597c321 mantine-CodeHighlight-codeHighlight m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight">now()</code> возвращает количество миллисекунд с момента старта браузера. Можно запустить этот метод, сохранить значения до запуска кода и после его завершения, и вычесть одно из другого — и тогда мы узнаем, сколько миллисекунд работал наш код.</p>
<p>Чтобы сравнить два алгоритма, надо упорядочить точно такой же массив с помощью алгоритма выбора:</p>
<div class="m_5cb1b9c8 mantine-CodeHighlightTabs-root"><div style="--sa-corner-width:0px;--sa-corner-height:0px" class="m_7b14120b mantine-CodeHighlightTabs-filesScrollarea m_d57069b5 mantine-ScrollArea-root" dir="ltr"><div style="overflow-x:hidden;overflow-y:hidden" class="m_c0783ff9 mantine-ScrollArea-viewport" data-scrollbars="xy"><div class="m_b1336c6 mantine-ScrollArea-content"><div class="m_38d99e51 mantine-CodeHighlightTabs-files"><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" data-active="true" type="button"><span>javascript</span></button><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" type="button"><span>python</span></button><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" type="button"><span>php</span></button><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" type="button"><span>java</span></button></div></div></div><div data-orientation="horizontal" class="m_c44ba933 mantine-ScrollArea-scrollbar" data-hidden="true" style="position:absolute;--sa-thumb-width:18px" data-mantine-scrollbar="true"></div><div class="m_c44ba933 mantine-ScrollArea-scrollbar" data-hidden="true" data-orientation="vertical" style="position:absolute;--sa-thumb-height:18px" data-mantine-scrollbar="true"></div></div><div style="margin-bottom:var(--mantine-spacing-lg)" class="m_e597c321 mantine-CodeHighlightTabs-codeHighlight" dir="ltr"><div class="m_be7e9c9c mantine-CodeHighlightTabs-controls" data-with-offset="true"><button style="--ai-bg:transparent;--ai-hover:transparent;--ai-color:inherit;--ai-bd:none" class="mantine-focus-auto mantine-active m_d498bab7 mantine-CodeHighlightTabs-control m_8d3f4000 mantine-ActionIcon-root m_87cf2631 mantine-UnstyledButton-root" data-variant="none" type="button" aria-label="Copy code"><span class="m_8d3afb97 mantine-ActionIcon-icon"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round"><path stroke="none" d="M0 0h24v24H0z" fill="none"></path><path d="M8 8m0 2a2 2 0 0 1 2 -2h8a2 2 0 0 1 2 2v8a2 2 0 0 1 -2 2h-8a2 2 0 0 1 -2 -2z"></path><path d="M16 8v-2a2 2 0 0 0 -2 -2h-8a2 2 0 0 0 -2 2v8a2 2 0 0 0 2 2h2"></path></svg></span></button></div><div style="--scrollarea-scrollbar-size:calc(0.25rem * var(--mantine-scale));--sa-corner-width:0px;--sa-corner-height:0px" class="m_f744fd40 mantine-CodeHighlightTabs-scrollarea m_d57069b5 mantine-ScrollArea-root" dir="ltr"><div style="overflow-x:hidden;overflow-y:hidden;overscroll-behavior-inline:none" class="m_c0783ff9 mantine-ScrollArea-viewport" data-scrollbars="xy"><div class="m_b1336c6 mantine-ScrollArea-content"><pre class="m_2c47c4fd mantine-CodeHighlightTabs-pre" data-with-offset="true"><code class="m_5caae6d3 mantine-CodeHighlightTabs-code">const selectionSort = (items) => {
for (i = 0; i < items.length - 1; i++) {
let indexMin = i
for (j = i + 1; j < items.length; j++) {
if (items[j] < items[indexMin])
indexMin = j
}
const t = items[i]
items[i] = items[indexMin]
items[indexMin] = t
}
}
const items = [86, 66, 44, 77, 56, 64, 76, 39, 32, 93, 33, 54, 63, 96, 5, 41, 20, 58, 55, 28]
const start = performance.now()
selectionSort(items)
const end = performance.now()
console.log(end - start) // <= 0.09 миллисекунды</code></pre></div></div></div><button class="mantine-focus-auto m_c9378bc2 mantine-CodeHighlightTabs-showCodeButton m_87cf2631 mantine-UnstyledButton-root" data-hidden="true" type="button">Expand code</button></div></div><p>Оценим скорость кода выше:</p>
<ul>
<li>Быстрая сортировка — 0,20 миллисекунд</li>
<li>Сортировка выбором — 0,09 миллисекунд</li>
</ul>
<p>Результат выглядит странно. Раз уж быструю сортировку назвали быстрой, то время ее выполнения должно быть меньше, чем у сортировки выбором. Здесь дело в том, что результаты однократного измерения ненадежны. Нужно измерить производительность алгоритмов несколько раз подряд на одних и тех же данных. Можем получить такой результат:</p>
<ul>
<li>Быстрая сортировка — 0,21 миллисекунда</li>
<li>Сортировка выбором — 0,12 миллисекунд</li>
</ul>
<p>Или даже такой:</p>
<ul>
<li>Быстрая сортировка — 0,16 миллисекунд</li>
<li>Сортировка выбором — 0,17 миллисекунд</li>
</ul>
<p>Разброс может быть достаточно большим. Дело в том, что на производительность нашей программы влияет множество случайных факторов: другие запущенные программы на компьютере, режим энергосбережения и так далее.</p>
<p>В работе алгоритмов много перечисленных тонкостей, поэтому сравнивать скорости довольно трудно. Чтобы справиться с этой трудностью, используем статистические методы. Будем запускать одну и ту же функцию много раз, а затем разделим общее время выполнения на количество запусков, чтобы вычислить среднее время выполнения:</p>
<div class="m_5cb1b9c8 mantine-CodeHighlightTabs-root"><div style="--sa-corner-width:0px;--sa-corner-height:0px" class="m_7b14120b mantine-CodeHighlightTabs-filesScrollarea m_d57069b5 mantine-ScrollArea-root" dir="ltr"><div style="overflow-x:hidden;overflow-y:hidden" class="m_c0783ff9 mantine-ScrollArea-viewport" data-scrollbars="xy"><div class="m_b1336c6 mantine-ScrollArea-content"><div class="m_38d99e51 mantine-CodeHighlightTabs-files"><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" data-active="true" type="button"><span>javascript</span></button><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" type="button"><span>python</span></button><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" type="button"><span>php</span></button><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" type="button"><span>java</span></button></div></div></div><div data-orientation="horizontal" class="m_c44ba933 mantine-ScrollArea-scrollbar" data-hidden="true" style="position:absolute;--sa-thumb-width:18px" data-mantine-scrollbar="true"></div><div class="m_c44ba933 mantine-ScrollArea-scrollbar" data-hidden="true" data-orientation="vertical" style="position:absolute;--sa-thumb-height:18px" data-mantine-scrollbar="true"></div></div><div style="margin-bottom:var(--mantine-spacing-lg)" class="m_e597c321 mantine-CodeHighlightTabs-codeHighlight" dir="ltr"><div class="m_be7e9c9c mantine-CodeHighlightTabs-controls" data-with-offset="true"><button style="--ai-bg:transparent;--ai-hover:transparent;--ai-color:inherit;--ai-bd:none" class="mantine-focus-auto mantine-active m_d498bab7 mantine-CodeHighlightTabs-control m_8d3f4000 mantine-ActionIcon-root m_87cf2631 mantine-UnstyledButton-root" data-variant="none" type="button" aria-label="Copy code"><span class="m_8d3afb97 mantine-ActionIcon-icon"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round"><path stroke="none" d="M0 0h24v24H0z" fill="none"></path><path d="M8 8m0 2a2 2 0 0 1 2 -2h8a2 2 0 0 1 2 2v8a2 2 0 0 1 -2 2h-8a2 2 0 0 1 -2 -2z"></path><path d="M16 8v-2a2 2 0 0 0 -2 -2h-8a2 2 0 0 0 -2 2v8a2 2 0 0 0 2 2h2"></path></svg></span></button></div><div style="--scrollarea-scrollbar-size:calc(0.25rem * var(--mantine-scale));--sa-corner-width:0px;--sa-corner-height:0px" class="m_f744fd40 mantine-CodeHighlightTabs-scrollarea m_d57069b5 mantine-ScrollArea-root" dir="ltr"><div style="overflow-x:hidden;overflow-y:hidden;overscroll-behavior-inline:none" class="m_c0783ff9 mantine-ScrollArea-viewport" data-scrollbars="xy"><div class="m_b1336c6 mantine-ScrollArea-content"><pre class="m_2c47c4fd mantine-CodeHighlightTabs-pre" data-with-offset="true"><code class="m_5caae6d3 mantine-CodeHighlightTabs-code">const averagePerformance = (f, count) => {
const start = window.performance.now()
for (let i = 0; i < count; i++) {
f()
}
const end = window.performance.now()
return (end - start) / count
}
const items = [86, 66, 44, 77, 56, 64, 76, 39, 32, 93, 33, 54, 63, 96, 5, 41, 20, 58, 55, 28]
averagePerformance(() => selectionSort([...items]), 1) // 0.1000000238418
averagePerformance(() => selectionSort([...items]), 10) // 0.0699999988079</code></pre></div></div></div><button class="mantine-focus-auto m_c9378bc2 mantine-CodeHighlightTabs-showCodeButton m_87cf2631 mantine-UnstyledButton-root" data-hidden="true" type="button">Expand code</button></div></div><p>Возможно вы не знакомы с конструкцией <code style="margin-bottom:var(--mantine-spacing-lg)" class="m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight m_e597c321 mantine-CodeHighlight-codeHighlight m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight">[...items]</code>, которая встречается в этом коде. Она позволяет сделать копию массива <code style="margin-bottom:var(--mantine-spacing-lg)" class="m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight m_e597c321 mantine-CodeHighlight-codeHighlight m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight">items</code>. Без копии мы при первом же вызове функции <code style="margin-bottom:var(--mantine-spacing-lg)" class="m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight m_e597c321 mantine-CodeHighlight-codeHighlight m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight">selectionSort</code> упорядочим массив <code style="margin-bottom:var(--mantine-spacing-lg)" class="m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight m_e597c321 mantine-CodeHighlight-codeHighlight m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight">items</code>, и последующие вызовы будут измерять скорость сортировки уже упорядоченного массива.</p>
<p>У функции <code style="margin-bottom:var(--mantine-spacing-lg)" class="m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight m_e597c321 mantine-CodeHighlight-codeHighlight m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight">averagePerformance</code> два параметра:</p>
<ul>
<li>Функция, чью производительность мы хотим измерить</li>
<li>Количество раз, когда мы хотим ее запустить</li>
</ul>
<p>Мы видим, что среднее время выполнения может заметно отличаться от времени, измеренного один раз — на 30% в нашем случае. Значит ли это, что теперь у нас в руках есть надежный способ сравнения алгоритмов? Кажется, что да. Но мы пока так и не выяснили, почему быстрая сортировка такая медленная по сравнению с сортировкой выбором.</p>
<p>Продолжим искать причину и сравним время выполнения разных сортировок на массиве из ста элементов:</p>
<div class="m_5cb1b9c8 mantine-CodeHighlightTabs-root"><div style="--sa-corner-width:0px;--sa-corner-height:0px" class="m_7b14120b mantine-CodeHighlightTabs-filesScrollarea m_d57069b5 mantine-ScrollArea-root" dir="ltr"><div style="overflow-x:hidden;overflow-y:hidden" class="m_c0783ff9 mantine-ScrollArea-viewport" data-scrollbars="xy"><div class="m_b1336c6 mantine-ScrollArea-content"><div class="m_38d99e51 mantine-CodeHighlightTabs-files"><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" data-active="true" type="button"><span>javascript</span></button><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" type="button"><span>python</span></button><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" type="button"><span>php</span></button><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" type="button"><span>java</span></button></div></div></div><div data-orientation="horizontal" class="m_c44ba933 mantine-ScrollArea-scrollbar" data-hidden="true" style="position:absolute;--sa-thumb-width:18px" data-mantine-scrollbar="true"></div><div class="m_c44ba933 mantine-ScrollArea-scrollbar" data-hidden="true" data-orientation="vertical" style="position:absolute;--sa-thumb-height:18px" data-mantine-scrollbar="true"></div></div><div style="margin-bottom:var(--mantine-spacing-lg)" class="m_e597c321 mantine-CodeHighlightTabs-codeHighlight" dir="ltr"><div class="m_be7e9c9c mantine-CodeHighlightTabs-controls" data-with-offset="true"><button style="--ai-bg:transparent;--ai-hover:transparent;--ai-color:inherit;--ai-bd:none" class="mantine-focus-auto mantine-active m_d498bab7 mantine-CodeHighlightTabs-control m_8d3f4000 mantine-ActionIcon-root m_87cf2631 mantine-UnstyledButton-root" data-variant="none" type="button" aria-label="Copy code"><span class="m_8d3afb97 mantine-ActionIcon-icon"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round"><path stroke="none" d="M0 0h24v24H0z" fill="none"></path><path d="M8 8m0 2a2 2 0 0 1 2 -2h8a2 2 0 0 1 2 2v8a2 2 0 0 1 -2 2h-8a2 2 0 0 1 -2 -2z"></path><path d="M16 8v-2a2 2 0 0 0 -2 -2h-8a2 2 0 0 0 -2 2v8a2 2 0 0 0 2 2h2"></path></svg></span></button></div><div style="--scrollarea-scrollbar-size:calc(0.25rem * var(--mantine-scale));--sa-corner-width:0px;--sa-corner-height:0px" class="m_f744fd40 mantine-CodeHighlightTabs-scrollarea m_d57069b5 mantine-ScrollArea-root" dir="ltr"><div style="overflow-x:hidden;overflow-y:hidden;overscroll-behavior-inline:none" class="m_c0783ff9 mantine-ScrollArea-viewport" data-scrollbars="xy"><div class="m_b1336c6 mantine-ScrollArea-content"><pre class="m_2c47c4fd mantine-CodeHighlightTabs-pre" data-with-offset="true"><code class="m_5caae6d3 mantine-CodeHighlightTabs-code">const items = [86, 66, 44, 77, 56, 64, 76, 39, 32, 93, 33, 54, 63, 96, 5, 41, 20, 58, 55, 28, 91, 81, 97, 24, 96, 33, 11, 47, 18, 44, 95, 34, 52, 65, 18, 5, 30, 54, 67, 24, 13, 70, 62, 88, 18, 78, 72, 40, 10, 73, 27, 44, 46, 8, 1, 49, 45, 98, 91, 70, 30, 48, 44, 52, 24, 39, 91, 22, 93, 30, 2, 85, 30, 34, 7, 82, 18, 87, 91, 37, 11, 93, 74, 27, 15, 44, 81, 15, 74, 17, 53, 3, 67, 84, 78, 98, 6, 8, 90, 50]
averagePerformance(() => selectionSort([...items]), 10) // 0.60
averagePerformance(() => quickSort([...items]), 10) // 0.19</code></pre></div></div></div><button class="mantine-focus-auto m_c9378bc2 mantine-CodeHighlightTabs-showCodeButton m_87cf2631 mantine-UnstyledButton-root" data-hidden="true" type="button">Expand code</button></div></div><p>На большом массиве быстрая сортировка оказывается в три раза быстрее, чем сортировка выбором! Как такое может быть? Конечно, у этой странности есть объяснение, мы обсудим его чуть позже. Сейчас обратим внимание, что измерения скорости алгоритма на одних данных ничего не говорит об его скорости на других данных.</p>
<p>Мы можем с большой точностью оценить время работы алгоритма на массиве из десяти элементов и при этом мы совершенно не представляем, какой окажется скорость того же алгоритма на массиве из ста тысяч элементов. Именно поэтому перед программистами встала задача — научиться оценивать скорость алгоритмов в целом.</p>
<h2 id="heading-2-2">Оценка скорости алгоритмов «в целом»</h2>
<p>Идея оценки «в целом» пришла к нам из математики, где есть похожая задача — нужно оценивать порядок роста функций. Математики могут точно рассчитать скорость возрастания функции в любой точке, но эта информация может оказаться не очень полезной. Сравним графики двух функций:</p>
<p><img style="--image-object-fit:contain;width:auto" class="m_9e117634 mantine-Image-root" src="/rails/active_storage/blobs/proxy/eyJfcmFpbHMiOnsiZGF0YSI6MTQzNTQsInB1ciI6ImJsb2JfaWQifX0=--d4bc839c728375c0321dc1af69924247199c0b78/complexity01.png" alt="complexity01" loading="lazy"/></p>
<p>Кажется, что синяя функция больше, чем, красная. Но если посмотреть на те же графики в другом масштабе, картина изменится:</p>
<p><img style="--image-object-fit:contain;width:auto" class="m_9e117634 mantine-Image-root" src="/rails/active_storage/blobs/proxy/eyJfcmFpbHMiOnsiZGF0YSI6MTQzNTUsInB1ciI6ImJsb2JfaWQifX0=--4a5c905fae9f74f780dd31a9be61903f3303cbe7/complexity02.png" alt="complexity02" loading="lazy"/></p>
<p>Красная функция растет гораздо быстрее и почти сразу становится больше синей. С алгоритмами возникает та же проблема: на одном наборе данных первый алгоритм физически будет быстрее второго, на многих других наборах он может оказаться гораздо медленнее. Синяя функция на графике — это прямая линия, а красная — это парабола.</p>
<p>Синие функции в математике принято называть линейными, а красные — квадратичными. Математики знают, что квадратичные функции растут быстрее линейных, а кубические — быстрее квадратичных.</p>
<p>Алгоритмическая сложность тоже бывает линейной, квадратичной и кубической. Для нее характерна та же самая зависимость: алгоритмы с квадратичной сложностью в целом работают медленнее алгоритмов с линейной сложностью. Рассмотрим несколько алгоритмов и разберемся, как определять временную сложность.</p>
<h2 id="heading-2-3">Линейная сложность</h2>
<p>Чтобы определить временную сложность алгоритма, программисты ставят мысленный эксперимент. Предположим, что мы точно измерили время работы алгоритма на одном массиве, а потом увеличили этот массив в десять раз. Как увеличится время работы алгоритма? Если время работы алгоритма также увеличится в десять раз, то речь идет <strong>о линейной сложности</strong> — на графике она бы описывалась прямой линией.</p>
<p>Типичный линейный алгоритм — поиск минимального элемента в массиве:</p>
<div class="m_5cb1b9c8 mantine-CodeHighlightTabs-root"><div style="--sa-corner-width:0px;--sa-corner-height:0px" class="m_7b14120b mantine-CodeHighlightTabs-filesScrollarea m_d57069b5 mantine-ScrollArea-root" dir="ltr"><div style="overflow-x:hidden;overflow-y:hidden" class="m_c0783ff9 mantine-ScrollArea-viewport" data-scrollbars="xy"><div class="m_b1336c6 mantine-ScrollArea-content"><div class="m_38d99e51 mantine-CodeHighlightTabs-files"><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" data-active="true" type="button"><span>javascript</span></button><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" type="button"><span>python</span></button><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" type="button"><span>php</span></button><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" type="button"><span>java</span></button></div></div></div><div data-orientation="horizontal" class="m_c44ba933 mantine-ScrollArea-scrollbar" data-hidden="true" style="position:absolute;--sa-thumb-width:18px" data-mantine-scrollbar="true"></div><div class="m_c44ba933 mantine-ScrollArea-scrollbar" data-hidden="true" data-orientation="vertical" style="position:absolute;--sa-thumb-height:18px" data-mantine-scrollbar="true"></div></div><div style="margin-bottom:var(--mantine-spacing-lg)" class="m_e597c321 mantine-CodeHighlightTabs-codeHighlight" dir="ltr"><div class="m_be7e9c9c mantine-CodeHighlightTabs-controls" data-with-offset="true"><button style="--ai-bg:transparent;--ai-hover:transparent;--ai-color:inherit;--ai-bd:none" class="mantine-focus-auto mantine-active m_d498bab7 mantine-CodeHighlightTabs-control m_8d3f4000 mantine-ActionIcon-root m_87cf2631 mantine-UnstyledButton-root" data-variant="none" type="button" aria-label="Copy code"><span class="m_8d3afb97 mantine-ActionIcon-icon"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round"><path stroke="none" d="M0 0h24v24H0z" fill="none"></path><path d="M8 8m0 2a2 2 0 0 1 2 -2h8a2 2 0 0 1 2 2v8a2 2 0 0 1 -2 2h-8a2 2 0 0 1 -2 -2z"></path><path d="M16 8v-2a2 2 0 0 0 -2 -2h-8a2 2 0 0 0 -2 2v8a2 2 0 0 0 2 2h2"></path></svg></span></button></div><div style="--scrollarea-scrollbar-size:calc(0.25rem * var(--mantine-scale));--sa-corner-width:0px;--sa-corner-height:0px" class="m_f744fd40 mantine-CodeHighlightTabs-scrollarea m_d57069b5 mantine-ScrollArea-root" dir="ltr"><div style="overflow-x:hidden;overflow-y:hidden;overscroll-behavior-inline:none" class="m_c0783ff9 mantine-ScrollArea-viewport" data-scrollbars="xy"><div class="m_b1336c6 mantine-ScrollArea-content"><pre class="m_2c47c4fd mantine-CodeHighlightTabs-pre" data-with-offset="true"><code class="m_5caae6d3 mantine-CodeHighlightTabs-code">const getMinimum = (items) => {
let minimum = items[0]
for (let i = 1; i < items.length; i++) {
if (minimum > items[i]) {
minimum = items[i]
}
}
return minimum
}</code></pre></div></div></div><button class="mantine-focus-auto m_c9378bc2 mantine-CodeHighlightTabs-showCodeButton m_87cf2631 mantine-UnstyledButton-root" data-hidden="true" type="button">Expand code</button></div></div><p>Это простой алгоритм. Мы просматриваем элементы массива по одному и сравниваем с уже найденным. Если новый элемент оказывается меньше минимума, он становится новым минимумом. В самом начале в качестве минимума выбираем самый первый элемент массива с индексом 0. Функция состоит из двух смысловых элементов. Первый элемент — инициализация:</p>
<div class="m_5cb1b9c8 mantine-CodeHighlightTabs-root"><div style="--sa-corner-width:0px;--sa-corner-height:0px" class="m_7b14120b mantine-CodeHighlightTabs-filesScrollarea m_d57069b5 mantine-ScrollArea-root" dir="ltr"><div style="overflow-x:hidden;overflow-y:hidden" class="m_c0783ff9 mantine-ScrollArea-viewport" data-scrollbars="xy"><div class="m_b1336c6 mantine-ScrollArea-content"><div class="m_38d99e51 mantine-CodeHighlightTabs-files"><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" data-active="true" type="button"><span>javascript</span></button><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" type="button"><span>python</span></button><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" type="button"><span>php</span></button><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" type="button"><span>java</span></button></div></div></div><div data-orientation="horizontal" class="m_c44ba933 mantine-ScrollArea-scrollbar" data-hidden="true" style="position:absolute;--sa-thumb-width:18px" data-mantine-scrollbar="true"></div><div class="m_c44ba933 mantine-ScrollArea-scrollbar" data-hidden="true" data-orientation="vertical" style="position:absolute;--sa-thumb-height:18px" data-mantine-scrollbar="true"></div></div><div style="margin-bottom:var(--mantine-spacing-lg)" class="m_e597c321 mantine-CodeHighlightTabs-codeHighlight" dir="ltr"><div class="m_be7e9c9c mantine-CodeHighlightTabs-controls" data-with-offset="true"><button style="--ai-bg:transparent;--ai-hover:transparent;--ai-color:inherit;--ai-bd:none" class="mantine-focus-auto mantine-active m_d498bab7 mantine-CodeHighlightTabs-control m_8d3f4000 mantine-ActionIcon-root m_87cf2631 mantine-UnstyledButton-root" data-variant="none" type="button" aria-label="Copy code"><span class="m_8d3afb97 mantine-ActionIcon-icon"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round"><path stroke="none" d="M0 0h24v24H0z" fill="none"></path><path d="M8 8m0 2a2 2 0 0 1 2 -2h8a2 2 0 0 1 2 2v8a2 2 0 0 1 -2 2h-8a2 2 0 0 1 -2 -2z"></path><path d="M16 8v-2a2 2 0 0 0 -2 -2h-8a2 2 0 0 0 -2 2v8a2 2 0 0 0 2 2h2"></path></svg></span></button></div><div style="--scrollarea-scrollbar-size:calc(0.25rem * var(--mantine-scale));--sa-corner-width:0px;--sa-corner-height:0px" class="m_f744fd40 mantine-CodeHighlightTabs-scrollarea m_d57069b5 mantine-ScrollArea-root" dir="ltr"><div style="overflow-x:hidden;overflow-y:hidden;overscroll-behavior-inline:none" class="m_c0783ff9 mantine-ScrollArea-viewport" data-scrollbars="xy"><div class="m_b1336c6 mantine-ScrollArea-content"><pre class="m_2c47c4fd mantine-CodeHighlightTabs-pre" data-with-offset="true"><code class="m_5caae6d3 mantine-CodeHighlightTabs-code">let minimum = items[0]</code></pre></div></div></div><button class="mantine-focus-auto m_c9378bc2 mantine-CodeHighlightTabs-showCodeButton m_87cf2631 mantine-UnstyledButton-root" data-hidden="true" type="button">Expand code</button></div></div><p>Второй элемент — это цикл:</p>
<div class="m_5cb1b9c8 mantine-CodeHighlightTabs-root"><div style="--sa-corner-width:0px;--sa-corner-height:0px" class="m_7b14120b mantine-CodeHighlightTabs-filesScrollarea m_d57069b5 mantine-ScrollArea-root" dir="ltr"><div style="overflow-x:hidden;overflow-y:hidden" class="m_c0783ff9 mantine-ScrollArea-viewport" data-scrollbars="xy"><div class="m_b1336c6 mantine-ScrollArea-content"><div class="m_38d99e51 mantine-CodeHighlightTabs-files"><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" data-active="true" type="button"><span>javascript</span></button><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" type="button"><span>python</span></button><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" type="button"><span>php</span></button><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" type="button"><span>java</span></button></div></div></div><div data-orientation="horizontal" class="m_c44ba933 mantine-ScrollArea-scrollbar" data-hidden="true" style="position:absolute;--sa-thumb-width:18px" data-mantine-scrollbar="true"></div><div class="m_c44ba933 mantine-ScrollArea-scrollbar" data-hidden="true" data-orientation="vertical" style="position:absolute;--sa-thumb-height:18px" data-mantine-scrollbar="true"></div></div><div style="margin-bottom:var(--mantine-spacing-lg)" class="m_e597c321 mantine-CodeHighlightTabs-codeHighlight" dir="ltr"><div class="m_be7e9c9c mantine-CodeHighlightTabs-controls" data-with-offset="true"><button style="--ai-bg:transparent;--ai-hover:transparent;--ai-color:inherit;--ai-bd:none" class="mantine-focus-auto mantine-active m_d498bab7 mantine-CodeHighlightTabs-control m_8d3f4000 mantine-ActionIcon-root m_87cf2631 mantine-UnstyledButton-root" data-variant="none" type="button" aria-label="Copy code"><span class="m_8d3afb97 mantine-ActionIcon-icon"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round"><path stroke="none" d="M0 0h24v24H0z" fill="none"></path><path d="M8 8m0 2a2 2 0 0 1 2 -2h8a2 2 0 0 1 2 2v8a2 2 0 0 1 -2 2h-8a2 2 0 0 1 -2 -2z"></path><path d="M16 8v-2a2 2 0 0 0 -2 -2h-8a2 2 0 0 0 -2 2v8a2 2 0 0 0 2 2h2"></path></svg></span></button></div><div style="--scrollarea-scrollbar-size:calc(0.25rem * var(--mantine-scale));--sa-corner-width:0px;--sa-corner-height:0px" class="m_f744fd40 mantine-CodeHighlightTabs-scrollarea m_d57069b5 mantine-ScrollArea-root" dir="ltr"><div style="overflow-x:hidden;overflow-y:hidden;overscroll-behavior-inline:none" class="m_c0783ff9 mantine-ScrollArea-viewport" data-scrollbars="xy"><div class="m_b1336c6 mantine-ScrollArea-content"><pre class="m_2c47c4fd mantine-CodeHighlightTabs-pre" data-with-offset="true"><code class="m_5caae6d3 mantine-CodeHighlightTabs-code">for (let i = 1; i < items.length; i++) {
if (minimum > items[i]) {
minimum = items[i]
}
}</code></pre></div></div></div><button class="mantine-focus-auto m_c9378bc2 mantine-CodeHighlightTabs-showCodeButton m_87cf2631 mantine-UnstyledButton-root" data-hidden="true" type="button">Expand code</button></div></div><p>Если в массиве 10 элементов, цикл выполнится 9 раз, если 100 элементов — 99 раз, если n элементов, цикл выполнится n-1 раз. В итоге, для массива из n элементов функция выполнит n операций — одну операцию инициализации и n-1 операций в цикле. Если увеличить размер массива в 10 раз, то количество элементов будет равно 10*n, и количество операций также будет равно 10*n, то есть тоже вырастет в 10 раз.</p>
<p>Такая линейная временная сложность обозначается <strong>O(n)</strong>. Из-за того, что в записи используется большая буква O, она называется «н<strong>отация О-большое</strong>». Буква O появилась здесь не случайно. Это первая буква немецкого слова <em>Ordnung</em>, которое означает порядок. В математике, откуда пришло обозначение, оно относится к порядку роста функций.</p>
<p>Какие еще алгоритмы имеют линейную временную сложность? Например, алгоритм вычисления среднего арифметического:</p>
<div class="m_5cb1b9c8 mantine-CodeHighlightTabs-root"><div style="--sa-corner-width:0px;--sa-corner-height:0px" class="m_7b14120b mantine-CodeHighlightTabs-filesScrollarea m_d57069b5 mantine-ScrollArea-root" dir="ltr"><div style="overflow-x:hidden;overflow-y:hidden" class="m_c0783ff9 mantine-ScrollArea-viewport" data-scrollbars="xy"><div class="m_b1336c6 mantine-ScrollArea-content"><div class="m_38d99e51 mantine-CodeHighlightTabs-files"><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" data-active="true" type="button"><span>javascript</span></button><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" type="button"><span>python</span></button><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" type="button"><span>php</span></button><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" type="button"><span>java</span></button></div></div></div><div data-orientation="horizontal" class="m_c44ba933 mantine-ScrollArea-scrollbar" data-hidden="true" style="position:absolute;--sa-thumb-width:18px" data-mantine-scrollbar="true"></div><div class="m_c44ba933 mantine-ScrollArea-scrollbar" data-hidden="true" data-orientation="vertical" style="position:absolute;--sa-thumb-height:18px" data-mantine-scrollbar="true"></div></div><div style="margin-bottom:var(--mantine-spacing-lg)" class="m_e597c321 mantine-CodeHighlightTabs-codeHighlight" dir="ltr"><div class="m_be7e9c9c mantine-CodeHighlightTabs-controls" data-with-offset="true"><button style="--ai-bg:transparent;--ai-hover:transparent;--ai-color:inherit;--ai-bd:none" class="mantine-focus-auto mantine-active m_d498bab7 mantine-CodeHighlightTabs-control m_8d3f4000 mantine-ActionIcon-root m_87cf2631 mantine-UnstyledButton-root" data-variant="none" type="button" aria-label="Copy code"><span class="m_8d3afb97 mantine-ActionIcon-icon"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round"><path stroke="none" d="M0 0h24v24H0z" fill="none"></path><path d="M8 8m0 2a2 2 0 0 1 2 -2h8a2 2 0 0 1 2 2v8a2 2 0 0 1 -2 2h-8a2 2 0 0 1 -2 -2z"></path><path d="M16 8v-2a2 2 0 0 0 -2 -2h-8a2 2 0 0 0 -2 2v8a2 2 0 0 0 2 2h2"></path></svg></span></button></div><div style="--scrollarea-scrollbar-size:calc(0.25rem * var(--mantine-scale));--sa-corner-width:0px;--sa-corner-height:0px" class="m_f744fd40 mantine-CodeHighlightTabs-scrollarea m_d57069b5 mantine-ScrollArea-root" dir="ltr"><div style="overflow-x:hidden;overflow-y:hidden;overscroll-behavior-inline:none" class="m_c0783ff9 mantine-ScrollArea-viewport" data-scrollbars="xy"><div class="m_b1336c6 mantine-ScrollArea-content"><pre class="m_2c47c4fd mantine-CodeHighlightTabs-pre" data-with-offset="true"><code class="m_5caae6d3 mantine-CodeHighlightTabs-code">const average = (items) => {
let sum = 0
for (let i = 0; i < items.length; i++) {
sum = sum + items[i]
}
return sum / items.length
}</code></pre></div></div></div><button class="mantine-focus-auto m_c9378bc2 mantine-CodeHighlightTabs-showCodeButton m_87cf2631 mantine-UnstyledButton-root" data-hidden="true" type="button">Expand code</button></div></div><p>Анализ алгоритма показывает, что для массива из n элементов будет n+1 операция: одна инициализация плюс n операций в цикле. Кажется, что такая временная сложность должна записываться O(n+1). Однако такие варианты, как n-2, n+5 и даже n+1000, всегда записывают как O(n). На первый взгляд это кажется странным, но далее мы разберемся, почему это так. А пока рассмотрим еще один линейный алгоритм — алгоритм определения строк-палиндромов.</p>
<p>Палиндромом называется строка, которая одинаково читается слева направо и справа налево. АНА и ABBA — это палиндромы, а YES и nO — нет:</p>
<div class="m_5cb1b9c8 mantine-CodeHighlightTabs-root"><div style="--sa-corner-width:0px;--sa-corner-height:0px" class="m_7b14120b mantine-CodeHighlightTabs-filesScrollarea m_d57069b5 mantine-ScrollArea-root" dir="ltr"><div style="overflow-x:hidden;overflow-y:hidden" class="m_c0783ff9 mantine-ScrollArea-viewport" data-scrollbars="xy"><div class="m_b1336c6 mantine-ScrollArea-content"><div class="m_38d99e51 mantine-CodeHighlightTabs-files"><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" data-active="true" type="button"><span>javascript</span></button><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" type="button"><span>python</span></button><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" type="button"><span>php</span></button><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" type="button"><span>java</span></button></div></div></div><div data-orientation="horizontal" class="m_c44ba933 mantine-ScrollArea-scrollbar" data-hidden="true" style="position:absolute;--sa-thumb-width:18px" data-mantine-scrollbar="true"></div><div class="m_c44ba933 mantine-ScrollArea-scrollbar" data-hidden="true" data-orientation="vertical" style="position:absolute;--sa-thumb-height:18px" data-mantine-scrollbar="true"></div></div><div style="margin-bottom:var(--mantine-spacing-lg)" class="m_e597c321 mantine-CodeHighlightTabs-codeHighlight" dir="ltr"><div class="m_be7e9c9c mantine-CodeHighlightTabs-controls" data-with-offset="true"><button style="--ai-bg:transparent;--ai-hover:transparent;--ai-color:inherit;--ai-bd:none" class="mantine-focus-auto mantine-active m_d498bab7 mantine-CodeHighlightTabs-control m_8d3f4000 mantine-ActionIcon-root m_87cf2631 mantine-UnstyledButton-root" data-variant="none" type="button" aria-label="Copy code"><span class="m_8d3afb97 mantine-ActionIcon-icon"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round"><path stroke="none" d="M0 0h24v24H0z" fill="none"></path><path d="M8 8m0 2a2 2 0 0 1 2 -2h8a2 2 0 0 1 2 2v8a2 2 0 0 1 -2 2h-8a2 2 0 0 1 -2 -2z"></path><path d="M16 8v-2a2 2 0 0 0 -2 -2h-8a2 2 0 0 0 -2 2v8a2 2 0 0 0 2 2h2"></path></svg></span></button></div><div style="--scrollarea-scrollbar-size:calc(0.25rem * var(--mantine-scale));--sa-corner-width:0px;--sa-corner-height:0px" class="m_f744fd40 mantine-CodeHighlightTabs-scrollarea m_d57069b5 mantine-ScrollArea-root" dir="ltr"><div style="overflow-x:hidden;overflow-y:hidden;overscroll-behavior-inline:none" class="m_c0783ff9 mantine-ScrollArea-viewport" data-scrollbars="xy"><div class="m_b1336c6 mantine-ScrollArea-content"><pre class="m_2c47c4fd mantine-CodeHighlightTabs-pre" data-with-offset="true"><code class="m_5caae6d3 mantine-CodeHighlightTabs-code">const palindrome = (string) => {
for (let i = 0; i < string.length / 2; i++) {
if (string[i] != string[string.length - 1 - i]) {
return false
}
}
return true
}
palindrome('') // true
palindrome('a') // true
palindrome('ab') // false
palindrome('aha') // true
palindrome('abba') // true</code></pre></div></div></div><button class="mantine-focus-auto m_c9378bc2 mantine-CodeHighlightTabs-showCodeButton m_87cf2631 mantine-UnstyledButton-root" data-hidden="true" type="button">Expand code</button></div></div><p>В этом алгоритме цикл выполняется n/2 раз, где n — длина строки. Казалось бы, сложность работы алгоритма должна быть равна O(n/2). Но, как и в прошлый раз, это не так. Алгоритмы со временем работы 2n, 10n, n/5 и n/32 — все имеют сложность O(n), и снова это кажется странным.</p>
<h2 id="heading-2-4">Квадратичная сложность</h2>
<p>Квадратичную сложность имеют все простые алгоритмы сортировки. Рассмотрим, например, сортировку выбором. Внутри нее есть вложенный цикл.</p>
<div class="m_5cb1b9c8 mantine-CodeHighlightTabs-root"><div style="--sa-corner-width:0px;--sa-corner-height:0px" class="m_7b14120b mantine-CodeHighlightTabs-filesScrollarea m_d57069b5 mantine-ScrollArea-root" dir="ltr"><div style="overflow-x:hidden;overflow-y:hidden" class="m_c0783ff9 mantine-ScrollArea-viewport" data-scrollbars="xy"><div class="m_b1336c6 mantine-ScrollArea-content"><div class="m_38d99e51 mantine-CodeHighlightTabs-files"><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" data-active="true" type="button"><span>javascript</span></button><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" type="button"><span>python</span></button><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" type="button"><span>php</span></button><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" type="button"><span>java</span></button></div></div></div><div data-orientation="horizontal" class="m_c44ba933 mantine-ScrollArea-scrollbar" data-hidden="true" style="position:absolute;--sa-thumb-width:18px" data-mantine-scrollbar="true"></div><div class="m_c44ba933 mantine-ScrollArea-scrollbar" data-hidden="true" data-orientation="vertical" style="position:absolute;--sa-thumb-height:18px" data-mantine-scrollbar="true"></div></div><div style="margin-bottom:var(--mantine-spacing-lg)" class="m_e597c321 mantine-CodeHighlightTabs-codeHighlight" dir="ltr"><div class="m_be7e9c9c mantine-CodeHighlightTabs-controls" data-with-offset="true"><button style="--ai-bg:transparent;--ai-hover:transparent;--ai-color:inherit;--ai-bd:none" class="mantine-focus-auto mantine-active m_d498bab7 mantine-CodeHighlightTabs-control m_8d3f4000 mantine-ActionIcon-root m_87cf2631 mantine-UnstyledButton-root" data-variant="none" type="button" aria-label="Copy code"><span class="m_8d3afb97 mantine-ActionIcon-icon"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round"><path stroke="none" d="M0 0h24v24H0z" fill="none"></path><path d="M8 8m0 2a2 2 0 0 1 2 -2h8a2 2 0 0 1 2 2v8a2 2 0 0 1 -2 2h-8a2 2 0 0 1 -2 -2z"></path><path d="M16 8v-2a2 2 0 0 0 -2 -2h-8a2 2 0 0 0 -2 2v8a2 2 0 0 0 2 2h2"></path></svg></span></button></div><div style="--scrollarea-scrollbar-size:calc(0.25rem * var(--mantine-scale));--sa-corner-width:0px;--sa-corner-height:0px" class="m_f744fd40 mantine-CodeHighlightTabs-scrollarea m_d57069b5 mantine-ScrollArea-root" dir="ltr"><div style="overflow-x:hidden;overflow-y:hidden;overscroll-behavior-inline:none" class="m_c0783ff9 mantine-ScrollArea-viewport" data-scrollbars="xy"><div class="m_b1336c6 mantine-ScrollArea-content"><pre class="m_2c47c4fd mantine-CodeHighlightTabs-pre" data-with-offset="true"><code class="m_5caae6d3 mantine-CodeHighlightTabs-code">for (i = 0; i < items.length - 1; i++) {
for (j = i + 1; j < items.length; j++) {
// …
}
// …
}</code></pre></div></div></div><button class="mantine-focus-auto m_c9378bc2 mantine-CodeHighlightTabs-showCodeButton m_87cf2631 mantine-UnstyledButton-root" data-hidden="true" type="button">Expand code</button></div></div><p>Чтобы избавиться от несущественных деталей, в коде выше убрана часть операций — вместо них пустые комментарии. Попробуем оценить количество выполнений цикла. На первом шаге внешнего цикла внутренний выполнится на один раз меньше, чем общее количество элементов, на втором — на два раза меньше, на третьем — на три раза меньше и так далее.</p>
<p>Суммарное количество выполнений цикла можно выразить как сумму чисел от 1 до n-1. Эта сумма равна половине произведения количества элементов на количество элементов минус один. Таким образом, общее количество операций пропорционально квадрату количества элементов.</p>
<div style="margin-bottom:var(--mantine-spacing-lg)" class="m_e597c321 mantine-CodeHighlight-codeHighlight" dir="ltr"><div class="m_be7e9c9c mantine-CodeHighlight-controls"><button style="--ai-bg:transparent;--ai-hover:transparent;--ai-color:inherit;--ai-bd:none" class="mantine-focus-auto mantine-active m_d498bab7 mantine-CodeHighlight-control m_8d3f4000 mantine-ActionIcon-root m_87cf2631 mantine-UnstyledButton-root" data-variant="none" type="button" aria-label="Copy code"><span class="m_8d3afb97 mantine-ActionIcon-icon"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round"><path stroke="none" d="M0 0h24v24H0z" fill="none"></path><path d="M8 8m0 2a2 2 0 0 1 2 -2h8a2 2 0 0 1 2 2v8a2 2 0 0 1 -2 2h-8a2 2 0 0 1 -2 -2z"></path><path d="M16 8v-2a2 2 0 0 0 -2 -2h-8a2 2 0 0 0 -2 2v8a2 2 0 0 0 2 2h2"></path></svg></span></button></div><div style="--scrollarea-scrollbar-size:calc(0.25rem * var(--mantine-scale));--sa-corner-width:0px;--sa-corner-height:0px" class="m_f744fd40 mantine-CodeHighlight-scrollarea m_d57069b5 mantine-ScrollArea-root" dir="ltr"><div style="overflow-x:hidden;overflow-y:hidden;overscroll-behavior-inline:none" class="m_c0783ff9 mantine-ScrollArea-viewport" data-scrollbars="xy"><div class="m_b1336c6 mantine-ScrollArea-content"><pre class="m_2c47c4fd mantine-CodeHighlight-pre" style="padding:0"><code class="m_5caae6d3 mantine-CodeHighlight-code">(n-1) + (n-2) + (n-3) + ... + 1 = (n * (n - 1)) / 2 = (n^2 - n) / 2</code></pre></div></div></div><button class="mantine-focus-auto m_c9378bc2 mantine-CodeHighlight-showCodeButton m_87cf2631 mantine-UnstyledButton-root" data-hidden="true" type="button">Expand code</button></div>
<p>Для расчетов мы использовали формулу суммы членов арифметической прогрессии. Среди слагаемых есть компонент, который растет как квадрат количества элементов, так что речь идет о квадратичной сложности, которая записывается как <strong>O(n^2)</strong>. И снова встает вопрос: почему мы игнорируем деление на два и вычитаемое? Настало время разобраться.</p>
<p>Как мы уже говорили, алгоритмическая сложность позволяет сравнивать алгоритмы «в целом». Можно утверждать, что все линейные алгоритмы в целом быстрее всех квадратичных, хотя на конкретных данных возможны аномалии. Все квадратичные алгоритмы в целом быстрее всех кубических.</p>
<p>К сожалению, сравнивая два линейных алгоритма, мы не можем сказать, какой из них быстрее. Есть соблазн использовать запись вида O(4n+1) или O(2n-3), но она толкает нас на путь ложных выводов. Определяя алгоритмическую сложность, мы считаем количество операций и предполагаем, что все они выполняются за небольшое постоянное время.</p>
<p>Но как только речь заходит о конкретике, выясняется, что операция сложения может быть очень быстрой, а операция деления — очень медленной по сравнению со сложением. Иногда четыре сложения могут выполниться быстрее, чем два деления. Поэтому нельзя в общем случае утверждать, что O(2n - 3) быстрее, чем O(4n + 1).</p>
<p>Именно поэтому программисты и математики избавляются от деталей в нотации O-большое. Записи вида O(2n-3), O((n^2)/3)+5) и O(20(n^4)-1000) превращаются в <strong>O(n)</strong>, <strong>O(n^2)</strong> и <strong>O(n^4)</strong> соответственно.</p>
<h2 id="heading-2-5">Какая еще бывает сложность</h2>
<p>Теоретически мы можем придумать алгоритмы с любой экзотической сложностью, но на практике чаще встречается всего несколько вариантов.</p>
<h3 id="heading-3-6">Константная сложность</h3>
<p>Она обозначается <strong>O(1)</strong>. Алгоритмы с константной временной сложностью выполняются за одно и то же время вне зависимости от количества элементов. Например, в упорядоченном массиве минимальный элемент всегда находится в самом начале, поэтому поиск минимума становится тривиальным:</p>
<div class="m_5cb1b9c8 mantine-CodeHighlightTabs-root"><div style="--sa-corner-width:0px;--sa-corner-height:0px" class="m_7b14120b mantine-CodeHighlightTabs-filesScrollarea m_d57069b5 mantine-ScrollArea-root" dir="ltr"><div style="overflow-x:hidden;overflow-y:hidden" class="m_c0783ff9 mantine-ScrollArea-viewport" data-scrollbars="xy"><div class="m_b1336c6 mantine-ScrollArea-content"><div class="m_38d99e51 mantine-CodeHighlightTabs-files"><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" data-active="true" type="button"><span>javascript</span></button><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" type="button"><span>python</span></button><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" type="button"><span>php</span></button><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" type="button"><span>java</span></button></div></div></div><div data-orientation="horizontal" class="m_c44ba933 mantine-ScrollArea-scrollbar" data-hidden="true" style="position:absolute;--sa-thumb-width:18px" data-mantine-scrollbar="true"></div><div class="m_c44ba933 mantine-ScrollArea-scrollbar" data-hidden="true" data-orientation="vertical" style="position:absolute;--sa-thumb-height:18px" data-mantine-scrollbar="true"></div></div><div style="margin-bottom:var(--mantine-spacing-lg)" class="m_e597c321 mantine-CodeHighlightTabs-codeHighlight" dir="ltr"><div class="m_be7e9c9c mantine-CodeHighlightTabs-controls" data-with-offset="true"><button style="--ai-bg:transparent;--ai-hover:transparent;--ai-color:inherit;--ai-bd:none" class="mantine-focus-auto mantine-active m_d498bab7 mantine-CodeHighlightTabs-control m_8d3f4000 mantine-ActionIcon-root m_87cf2631 mantine-UnstyledButton-root" data-variant="none" type="button" aria-label="Copy code"><span class="m_8d3afb97 mantine-ActionIcon-icon"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round"><path stroke="none" d="M0 0h24v24H0z" fill="none"></path><path d="M8 8m0 2a2 2 0 0 1 2 -2h8a2 2 0 0 1 2 2v8a2 2 0 0 1 -2 2h-8a2 2 0 0 1 -2 -2z"></path><path d="M16 8v-2a2 2 0 0 0 -2 -2h-8a2 2 0 0 0 -2 2v8a2 2 0 0 0 2 2h2"></path></svg></span></button></div><div style="--scrollarea-scrollbar-size:calc(0.25rem * var(--mantine-scale));--sa-corner-width:0px;--sa-corner-height:0px" class="m_f744fd40 mantine-CodeHighlightTabs-scrollarea m_d57069b5 mantine-ScrollArea-root" dir="ltr"><div style="overflow-x:hidden;overflow-y:hidden;overscroll-behavior-inline:none" class="m_c0783ff9 mantine-ScrollArea-viewport" data-scrollbars="xy"><div class="m_b1336c6 mantine-ScrollArea-content"><pre class="m_2c47c4fd mantine-CodeHighlightTabs-pre" data-with-offset="true"><code class="m_5caae6d3 mantine-CodeHighlightTabs-code">const sortedMinimum = (sortedItems) => {
return sortedItems[0]
}</code></pre></div></div></div><button class="mantine-focus-auto m_c9378bc2 mantine-CodeHighlightTabs-showCodeButton m_87cf2631 mantine-UnstyledButton-root" data-hidden="true" type="button">Expand code</button></div></div><p>Эта функция всегда выполняется за одно и то же время, независимо от размера массива <code style="margin-bottom:var(--mantine-spacing-lg)" class="m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight m_e597c321 mantine-CodeHighlight-codeHighlight m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight">sortedItems</code>. Формально, константные алгоритмы считаются самыми быстрыми.</p>
<h3 id="heading-3-7">Логарифмическая сложность</h3>
<p>Обозначается <strong>O(logn)</strong>. За логарифмическое время работает алгоритм бинарного поиска. Эти алгоритмы относятся к быстрым, поскольку логарифмическая функция растет достаточно медленно.</p>
<p><img style="--image-object-fit:contain;width:auto" class="m_9e117634 mantine-Image-root" src="/rails/active_storage/blobs/proxy/eyJfcmFpbHMiOnsiZGF0YSI6MTQzNTYsInB1ciI6ImJsb2JfaWQifX0=--4925ae83cd2b0149e32fca224de07302fe012e0b/complexity03.png" alt="complexity03" loading="lazy"/></p>
<p>В массиве из тысячи элементов бинарный поиск работает максимум за десять сравнений, а массиве из миллиона — максимум за двадцать. Обычный метод перебора имеет линейную сложность, и поэтому будет работать за тысячу и миллион сравнений соответственно:</p>
<div style="--table-min-width:calc(50rem * var(--mantine-scale));--sa-corner-width:0px;--sa-corner-height:0px" class="m_a100c15 mantine-TableScrollContainer-scrollContainer m_d57069b5 mantine-ScrollArea-root"><div style="overflow-x:hidden;overflow-y:hidden" class="m_c0783ff9 mantine-ScrollArea-viewport" data-offset-scrollbars="x" data-scrollbars="xy"><div class="m_b1336c6 mantine-ScrollArea-content"><div class="m_62259741 mantine-TableScrollContainer-scrollContainerInner"><table><thead><tr><th>n</th><th>O(log n)</th><th>O(n)</th></tr></thead><tbody><tr><td>1000</td><td>10</td><td>1000</td></tr><tr><td>1000000</td><td>20</td><td>1000000</td></tr></tbody></table></div></div></div></div>
<p>Логарифмические алгоритмы считаются очень быстрыми, гораздо быстрее линейных.</p>
<h3 id="heading-3-8">Линейно-логарифмическая сложность</h3>
<p>Она обозначается как <strong>O(nlogn)</strong> и описывает сложность алгоритма быстрой сортировки. Сравним количество операций у быстрой сортировки и сортировки выбором — так мы увидим, почему быстрая сортировка так называется:</p>
<div style="--table-min-width:calc(50rem * var(--mantine-scale));--sa-corner-width:0px;--sa-corner-height:0px" class="m_a100c15 mantine-TableScrollContainer-scrollContainer m_d57069b5 mantine-ScrollArea-root"><div style="overflow-x:hidden;overflow-y:hidden" class="m_c0783ff9 mantine-ScrollArea-viewport" data-offset-scrollbars="x" data-scrollbars="xy"><div class="m_b1336c6 mantine-ScrollArea-content"><div class="m_62259741 mantine-TableScrollContainer-scrollContainerInner"><table><thead><tr><th>n</th><th>Быстрая O(nlogn)</th><th>Выбор O(n^2)</th></tr></thead><tbody><tr><td>1000</td><td>10000</td><td>1000000</td></tr><tr><td>1000000</td><td>20000000</td><td>1000000000000</td></tr></tbody></table></div></div></div></div>
<p>Быстрая сортировка упорядочивает массив из тысячи элементов приблизительно за десять тысяч операций, в то время как сортировка выбором — за миллион. Время выполнения различается в сто раз, и с ростом n разница только растет! Но важно не забывать, что на очень маленьких массивах (из десяти элементов) сортировка выбором может оказаться быстрее. Так происходит потому, что алгоритм сортировки выбором проще. Быстрая сортировка сложнее, и накладные расходы в реализации оказываются слишком велики для небольшого набора данных.</p>
<p>Линейно-логарифмическая сложность медленнее линейной, но быстрее квадратичной.</p>
<h3 id="heading-3-9">Экспоненциальная сложность</h3>
<p>Сколько подмассивов можно получить из массива <code style="margin-bottom:var(--mantine-spacing-lg)" class="m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight m_e597c321 mantine-CodeHighlight-codeHighlight m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight">[1, 2, 3, 4]</code>? Попробуем выяснить, но сначала определимся с условиями:</p>
<ul>
<li>Подмассивы могут быть любой длины, включая ноль</li>
<li>Будем считать одним подмассивом все подмассивы, состоящие из одних и тех же элементов в разном порядке (например, <code style="margin-bottom:var(--mantine-spacing-lg)" class="m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight m_e597c321 mantine-CodeHighlight-codeHighlight m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight">[1,2]</code> и <code style="margin-bottom:var(--mantine-spacing-lg)" class="m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight m_e597c321 mantine-CodeHighlight-codeHighlight m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight">[2,1]</code>)</li>
</ul>
<p>Выпишем все варианты и посчитаем их:</p>
<div style="--table-min-width:calc(50rem * var(--mantine-scale));--sa-corner-width:0px;--sa-corner-height:0px" class="m_a100c15 mantine-TableScrollContainer-scrollContainer m_d57069b5 mantine-ScrollArea-root"><div style="overflow-x:hidden;overflow-y:hidden" class="m_c0783ff9 mantine-ScrollArea-viewport" data-offset-scrollbars="x" data-scrollbars="xy"><div class="m_b1336c6 mantine-ScrollArea-content"><div class="m_62259741 mantine-TableScrollContainer-scrollContainerInner"><table><thead><tr><th></th><th></th><th></th><th></th></tr></thead><tbody><tr><td>[]</td><td>[4]</td><td>[2,3]</td><td>[1,2,4]</td></tr><tr><td>[1]</td><td>[1,2]</td><td>[2,4]</td><td>[1,3,4]</td></tr><tr><td>[2]</td><td>[1,3]</td><td>[3,4]</td><td>[2,3,4]</td></tr><tr><td>[3]</td><td>[1,4]</td><td>[1,2,3]</td><td>[1,2,3,4]</td></tr></tbody></table></div></div></div></div>
<p>Всего 16. Существует общее правило, по которому возможное количество подмассивов у массива длины n составляет 2^n. Формулы вида 2^n, 3^n, 100^n называют <strong>экспонентами</strong>. Алгоритм, который может построить список всех подмассивов массива длины n, имеет экспоненциальную сложность O(2^n).</p>
<p>Алгоритмы экспоненциальной сложности считаются медленными. Количество подмассивов у массива из тридцати элементов равно 1073741824, то есть превышает миллиард!</p>
<h3 id="heading-3-10">Факториальная сложность</h3>
<p>Обозначается <strong>O(n!)</strong>. Факториалом числа n называют произведение 1 × 2 × ... × n, то есть всех чисел от 1 до n. Сложность алгоритма, который находит все перестановки массива, равна O(n!). Вот все перестановки массива [1, 2, 3, 4]:</p>
<div style="--table-min-width:calc(50rem * var(--mantine-scale));--sa-corner-width:0px;--sa-corner-height:0px" class="m_a100c15 mantine-TableScrollContainer-scrollContainer m_d57069b5 mantine-ScrollArea-root"><div style="overflow-x:hidden;overflow-y:hidden" class="m_c0783ff9 mantine-ScrollArea-viewport" data-offset-scrollbars="x" data-scrollbars="xy"><div class="m_b1336c6 mantine-ScrollArea-content"><div class="m_62259741 mantine-TableScrollContainer-scrollContainerInner"><table><thead><tr><th></th></tr></thead><tbody><tr><td>[1, 2, 3, 4]</td></tr><tr><td>[2, 1, 3, 4]</td></tr><tr><td>[3, 2, 1, 4]</td></tr><tr><td>[4, 2, 3, 1]</td></tr><tr><td>[1, 2, 4, 3]</td></tr><tr><td>[2, 1, 3, 3]</td></tr><tr><td>[3, 2, 4, 1]</td></tr><tr><td>[4, 2, 1, 3]</td></tr><tr><td>[1, 3, 2, 4]</td></tr><tr><td>[2, 3, 1, 4]</td></tr><tr><td>[3, 1, 2, 4]</td></tr><tr><td>[4, 3, 2, 1]</td></tr><tr><td>[1, 3, 4, 2]</td></tr><tr><td>[2, 3, 4, 1]</td></tr><tr><td>[3, 1, 4, 2]</td></tr><tr><td>[4, 3, 1, 2]</td></tr><tr><td>[1, 4, 2, 3]</td></tr><tr><td>[2, 4, 1, 3]</td></tr><tr><td>[3, 4, 2, 1]</td></tr><tr><td>[4, 1, 2, 3]</td></tr><tr><td>[1, 4, 3, 2]</td></tr><tr><td>[2, 4, 3, 1]</td></tr><tr><td>[3, 4, 1, 3]</td></tr><tr><td>[4, 1, 3, 2]</td></tr></tbody></table></div></div></div></div>
<p>Всего их 4!=24. Факториальная сложность самая медленная из тех, что мы рассмотрели. Если нам потребуется найти все перестановки массива из тридцати элементов, их окажется 265252859812191058636308480000000, то есть 265 миллионов миллионов миллионов миллионов миллионов. Даже на самом быстром современном компьютере поиск всех перестановок займет миллионы миллионов лет.</p>
<h2 id="heading-2-11">Сводная таблица временной сложности</h2>
<div style="--table-min-width:calc(50rem * var(--mantine-scale));--sa-corner-width:0px;--sa-corner-height:0px" class="m_a100c15 mantine-TableScrollContainer-scrollContainer m_d57069b5 mantine-ScrollArea-root"><div style="overflow-x:hidden;overflow-y:hidden" class="m_c0783ff9 mantine-ScrollArea-viewport" data-offset-scrollbars="x" data-scrollbars="xy"><div class="m_b1336c6 mantine-ScrollArea-content"><div class="m_62259741 mantine-TableScrollContainer-scrollContainerInner"><table><thead><tr><th>Название</th><th>Формула</th><th>Примеры алгоритмов</th></tr></thead><tbody><tr><td>Константная</td><td>O(1)</td><td>Длина массива</td></tr><tr><td>Логарифмическая</td><td>O(log n)</td><td>Бинарный поиск</td></tr><tr><td>Линейная</td><td>O(n)</td><td>Поиск методом перебора</td></tr><tr><td>Линейно-логарифмическая</td><td>O(n log n)</td><td>Быстрая сортировка</td></tr><tr><td>Квадратичная</td><td>O(n^2)</td><td>Сортировка выбором, пузырьковая сортировка</td></tr><tr><td>Экспоненциальная</td><td>O(2^n)</td><td>Список подмассивов</td></tr><tr><td>Факториальная</td><td>O(n!)</td><td>Список перестановок</td></tr></tbody></table></div></div></div></div>
<p>Иногда в литературе можно встретить название <strong>полиномиальные алгоритмы</strong> — к ним относят алгоритмы со сложностью O(n^2), O(n^3) или O(n^100). Условная граница между медленными и быстрыми алгоритмами проходит между <strong>полиномиальными</strong> и <strong>экспоненциальными алгоритмами</strong>.</p>
<h3 id="heading-3-12">Оценка памяти</h3>
<p>В нотации О-большое также оценивается память, которую потребляет алгоритм. На практике здесь редко встречаются большие значения.</p>
<p>Если алгоритму для работы нужно несколько переменных, которые не зависят от размеров данных, сложность по памяти составляет O(1). Такую сложность имеют алгоритмы поиска минимума и вычисления среднего арифметического.
Логарифмическая сложность O(log n) встречается у рекурсивных алгоритмов, которые разбивают массив на два подмассива. Среди рассмотренных нами алгоритмов к этому классу относятся бинарный поиск и быстрая сортировка.</p>
<p>Линейная сложность O(n) означает, что алгоритм во время работы сохраняет дополнительные данные, размер которых соизмерим с входными данными. Например, если мы хотим избавиться от дубликатов в массиве, мы можем хранить просмотренные элементы в структуре множество <code style="margin-bottom:var(--mantine-spacing-lg)" class="m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight m_e597c321 mantine-CodeHighlight-codeHighlight m_dfe9c588 mantine-InlineCodeHighlight-inlineCodeHighlight">(Set)</code>:</p>
<div class="m_5cb1b9c8 mantine-CodeHighlightTabs-root"><div style="--sa-corner-width:0px;--sa-corner-height:0px" class="m_7b14120b mantine-CodeHighlightTabs-filesScrollarea m_d57069b5 mantine-ScrollArea-root" dir="ltr"><div style="overflow-x:hidden;overflow-y:hidden" class="m_c0783ff9 mantine-ScrollArea-viewport" data-scrollbars="xy"><div class="m_b1336c6 mantine-ScrollArea-content"><div class="m_38d99e51 mantine-CodeHighlightTabs-files"><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" data-active="true" type="button"><span>javascript</span></button><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" type="button"><span>python</span></button><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" type="button"><span>php</span></button><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" type="button"><span>java</span></button></div></div></div><div data-orientation="horizontal" class="m_c44ba933 mantine-ScrollArea-scrollbar" data-hidden="true" style="position:absolute;--sa-thumb-width:18px" data-mantine-scrollbar="true"></div><div class="m_c44ba933 mantine-ScrollArea-scrollbar" data-hidden="true" data-orientation="vertical" style="position:absolute;--sa-thumb-height:18px" data-mantine-scrollbar="true"></div></div><div style="margin-bottom:var(--mantine-spacing-lg)" class="m_e597c321 mantine-CodeHighlightTabs-codeHighlight" dir="ltr"><div class="m_be7e9c9c mantine-CodeHighlightTabs-controls" data-with-offset="true"><button style="--ai-bg:transparent;--ai-hover:transparent;--ai-color:inherit;--ai-bd:none" class="mantine-focus-auto mantine-active m_d498bab7 mantine-CodeHighlightTabs-control m_8d3f4000 mantine-ActionIcon-root m_87cf2631 mantine-UnstyledButton-root" data-variant="none" type="button" aria-label="Copy code"><span class="m_8d3afb97 mantine-ActionIcon-icon"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round"><path stroke="none" d="M0 0h24v24H0z" fill="none"></path><path d="M8 8m0 2a2 2 0 0 1 2 -2h8a2 2 0 0 1 2 2v8a2 2 0 0 1 -2 2h-8a2 2 0 0 1 -2 -2z"></path><path d="M16 8v-2a2 2 0 0 0 -2 -2h-8a2 2 0 0 0 -2 2v8a2 2 0 0 0 2 2h2"></path></svg></span></button></div><div style="--scrollarea-scrollbar-size:calc(0.25rem * var(--mantine-scale));--sa-corner-width:0px;--sa-corner-height:0px" class="m_f744fd40 mantine-CodeHighlightTabs-scrollarea m_d57069b5 mantine-ScrollArea-root" dir="ltr"><div style="overflow-x:hidden;overflow-y:hidden;overscroll-behavior-inline:none" class="m_c0783ff9 mantine-ScrollArea-viewport" data-scrollbars="xy"><div class="m_b1336c6 mantine-ScrollArea-content"><pre class="m_2c47c4fd mantine-CodeHighlightTabs-pre" data-with-offset="true"><code class="m_5caae6d3 mantine-CodeHighlightTabs-code">const removeDuplicates = (items) => {
const visited = new Set()
for (let i = 0; i < items.length; i++) {
if (visited.has(items[i])) {
items.splice(i, 1)
i--
}
else {
visited.add(items[i])
}
}
}</code></pre></div></div></div><button class="mantine-focus-auto m_c9378bc2 mantine-CodeHighlightTabs-showCodeButton m_87cf2631 mantine-UnstyledButton-root" data-hidden="true" type="button">Expand code</button></div></div><p>Этих неповторяющихся элементов будет чуть меньше, чем элементов в исходном массиве. Но при этом размер множества будет соизмерим с размером массива, поэтому речь идет о линейной сложности по памяти.</p>
<h2 id="heading-2-13">Оптимизация</h2>
<p>Одна из задач, которую регулярно решают программисты — оптимизация программы. Пользователи хотят, чтобы программа работала быстрее или занимала меньше памяти.</p>
<p>Неопытные программисты часто пытаются оптимизировать отдельные конструкции в программах, не обращая внимания на производительность в целом. Опытные же программисты оценивают сложность существующего алгоритма. Задача оптимизации сводится к тому, чтобы найти или придумать новый алгоритм с меньшей сложностью.</p>
<p>Разберем пример с определением простоты числа. Простые числа имеют важное значение в криптографии и кодировании, так что программистам время от времени нужен список простых чисел или функция, которая определяет, является ли число простым.</p>
<p>Определение простых чисел и звучит очень просто — простые числа делятся на себя и на единицу. Но проверить число на простоту уже сложнее — попробуйте, например, выяснить — простое ли число 1073676287?</p>
<p>Для определения простоты числа можно использовать один из самых древних, известных человечеству, алгоритмов — <strong>Решето Эратосфена</strong>. Сначала мы записываем список чисел, начиная с двойки:</p>
<div style="--table-min-width:calc(50rem * var(--mantine-scale));--sa-corner-width:0px;--sa-corner-height:0px" class="m_a100c15 mantine-TableScrollContainer-scrollContainer m_d57069b5 mantine-ScrollArea-root"><div style="overflow-x:hidden;overflow-y:hidden" class="m_c0783ff9 mantine-ScrollArea-viewport" data-offset-scrollbars="x" data-scrollbars="xy"><div class="m_b1336c6 mantine-ScrollArea-content"><div class="m_62259741 mantine-TableScrollContainer-scrollContainerInner"><table><thead><tr><th style="text-align:center"></th><th style="text-align:center"></th><th style="text-align:center"></th><th style="text-align:center"></th><th style="text-align:center"></th></tr></thead><tbody><tr><td style="text-align:center">2</td><td style="text-align:center">3</td><td style="text-align:center">4</td><td style="text-align:center">5</td><td style="text-align:center">6</td></tr><tr><td style="text-align:center">7</td><td style="text-align:center">8</td><td style="text-align:center">9</td><td style="text-align:center">10</td><td style="text-align:center">11</td></tr><tr><td style="text-align:center">12</td><td style="text-align:center">13</td><td style="text-align:center">14</td><td style="text-align:center">15</td><td style="text-align:center">16</td></tr><tr><td style="text-align:center">17</td><td style="text-align:center">18</td><td style="text-align:center">19</td><td style="text-align:center">20</td><td style="text-align:center">21</td></tr><tr><td style="text-align:center">22</td><td style="text-align:center">23</td><td style="text-align:center">24</td><td style="text-align:center">25</td><td style="text-align:center">26</td></tr></tbody></table></div></div></div></div>
<p>Берем первое число — двойку. Выделяем цветом числа, которые делятся на нее. Саму двойку не выделяем:</p>
<div style="--table-min-width:calc(50rem * var(--mantine-scale));--sa-corner-width:0px;--sa-corner-height:0px" class="m_a100c15 mantine-TableScrollContainer-scrollContainer m_d57069b5 mantine-ScrollArea-root"><div style="overflow-x:hidden;overflow-y:hidden" class="m_c0783ff9 mantine-ScrollArea-viewport" data-offset-scrollbars="x" data-scrollbars="xy"><div class="m_b1336c6 mantine-ScrollArea-content"><div class="m_62259741 mantine-TableScrollContainer-scrollContainerInner"><table><thead><tr><th style="text-align:center"></th><th style="text-align:center"></th><th style="text-align:center"></th><th style="text-align:center"></th><th style="text-align:center"></th></tr></thead><tbody><tr><td style="text-align:center">2</td><td style="text-align:center">3</td><td style="text-align:center"><em><strong>4</strong></em></td><td style="text-align:center">5</td><td style="text-align:center"><em><strong>6</strong></em></td></tr><tr><td style="text-align:center">7</td><td style="text-align:center"><em><strong>8</strong></em></td><td style="text-align:center">9</td><td style="text-align:center"><em><strong>10</strong></em></td><td style="text-align:center">11</td></tr><tr><td style="text-align:center"><em><strong>12</strong></em></td><td style="text-align:center">13</td><td style="text-align:center">14</td><td style="text-align:center">15</td><td style="text-align:center">16</td></tr><tr><td style="text-align:center">17</td><td style="text-align:center"><em><strong>18</strong></em></td><td style="text-align:center">19</td><td style="text-align:center"><em><strong>20</strong></em></td><td style="text-align:center">21</td></tr><tr><td style="text-align:center"><em><strong>22</strong></em></td><td style="text-align:center">23</td><td style="text-align:center"><em><strong>24</strong></em></td><td style="text-align:center">25</td><td style="text-align:center"><em><strong>26</strong></em></td></tr></tbody></table></div></div></div></div>
<p>Следующее неотмеченное число — три. Выделяем цветом числа, которые делятся на три, но не саму тройку:</p>
<div style="--table-min-width:calc(50rem * var(--mantine-scale));--sa-corner-width:0px;--sa-corner-height:0px" class="m_a100c15 mantine-TableScrollContainer-scrollContainer m_d57069b5 mantine-ScrollArea-root"><div style="overflow-x:hidden;overflow-y:hidden" class="m_c0783ff9 mantine-ScrollArea-viewport" data-offset-scrollbars="x" data-scrollbars="xy"><div class="m_b1336c6 mantine-ScrollArea-content"><div class="m_62259741 mantine-TableScrollContainer-scrollContainerInner"><table><thead><tr><th style="text-align:center"></th><th style="text-align:center"></th><th style="text-align:center"></th><th style="text-align:center"></th><th style="text-align:center"></th></tr></thead><tbody><tr><td style="text-align:center">2</td><td style="text-align:center">3</td><td style="text-align:center"><em><strong>4</strong></em></td><td style="text-align:center">5</td><td style="text-align:center"><em><strong>6</strong></em></td></tr><tr><td style="text-align:center">7</td><td style="text-align:center"><em><strong>8</strong></em></td><td style="text-align:center"><em><strong>9</strong></em></td><td style="text-align:center"><em><strong>10</strong></em></td><td style="text-align:center">11</td></tr><tr><td style="text-align:center"><em><strong>12</strong></em></td><td style="text-align:center">13</td><td style="text-align:center"><em><strong>14</strong></em></td><td style="text-align:center"><em><strong>15</strong></em></td><td style="text-align:center"><em><strong>16</strong></em></td></tr><tr><td style="text-align:center">17</td><td style="text-align:center"><em><strong>18</strong></em></td><td style="text-align:center">19</td><td style="text-align:center"><em><strong>20</strong></em></td><td style="text-align:center"><em><strong>21</strong></em></td></tr><tr><td style="text-align:center"><em><strong>22</strong></em></td><td style="text-align:center">23</td><td style="text-align:center"><em><strong>24</strong></em></td><td style="text-align:center">25</td><td style="text-align:center"><em><strong>26</strong></em></td></tr></tbody></table></div></div></div></div>
<p>Четверка зачеркнута — она делится на два, поэтому мы ее пропускаем.</p>
<p>Переходим к пятерке. У нас уже отмечены числа 10, 20 (оба делятся на два) и 15 (делится на три). Единственное неотмеченное число — это 25. Это подсказка, которая помогает понять одну важную мысль — чтобы составить список простых чисел вплоть до n, достаточно повторить эту процедуру только для чисел от 2 до sqrt(n).</p>
<p>Сама процедура выделения чисел на каждой итерации пробегает n чисел. Итого, выходит n чисел на итерацию и sqrt(n) итераций. Сложность алгоритма по времени равна O(n * sqrt(n)) или в более математической записи — O(n^(3/2)). При этом нам приходится выделять память для всех n чисел, поэтому сложность по памяти равна <strong>O(n)</strong>.</p>
<p>Решето Эратосфена — сложный алгоритм, как по времени, так и по памяти.</p>
<p>Чтобы оптимизировать решение, мы должны найти или придумать другой алгоритм. Обратим внимание, что Решето строит список простых чисел от 2 до n, но нам нужно только последнее число n. Мы можем проверить, что число не делится ни на какие целые числа от 2 до n-1:</p>
<div class="m_5cb1b9c8 mantine-CodeHighlightTabs-root"><div style="--sa-corner-width:0px;--sa-corner-height:0px" class="m_7b14120b mantine-CodeHighlightTabs-filesScrollarea m_d57069b5 mantine-ScrollArea-root" dir="ltr"><div style="overflow-x:hidden;overflow-y:hidden" class="m_c0783ff9 mantine-ScrollArea-viewport" data-scrollbars="xy"><div class="m_b1336c6 mantine-ScrollArea-content"><div class="m_38d99e51 mantine-CodeHighlightTabs-files"><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" data-active="true" type="button"><span>javascript</span></button><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" type="button"><span>python</span></button><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" type="button"><span>php</span></button><button class="mantine-focus-auto m_5cac2e62 mantine-CodeHighlightTabs-file m_87cf2631 mantine-UnstyledButton-root" type="button"><span>java</span></button></div></div></div><div data-orientation="horizontal" class="m_c44ba933 mantine-ScrollArea-scrollbar" data-hidden="true" style="position:absolute;--sa-thumb-width:18px" data-mantine-scrollbar="true"></div><div class="m_c44ba933 mantine-ScrollArea-scrollbar" data-hidden="true" data-orientation="vertical" style="position:absolute;--sa-thumb-height:18px" data-mantine-scrollbar="true"></div></div><div style="margin-bottom:var(--mantine-spacing-lg)" class="m_e597c321 mantine-CodeHighlightTabs-codeHighlight" dir="ltr"><div class="m_be7e9c9c mantine-CodeHighlightTabs-controls" data-with-offset="true"><button style="--ai-bg:transparent;--ai-hover:transparent;--ai-color:inherit;--ai-bd:none" class="mantine-focus-auto mantine-active m_d498bab7 mantine-CodeHighlightTabs-control m_8d3f4000 mantine-ActionIcon-root m_87cf2631 mantine-UnstyledButton-root" data-variant="none" type="button" aria-label="Copy code"><span class="m_8d3afb97 mantine-ActionIcon-icon"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round"><path stroke="none" d="M0 0h24v24H0z" fill="none"></path><path d="M8 8m0 2a2 2 0 0 1 2 -2h8a2 2 0 0 1 2 2v8a2 2 0 0 1 -2 2h-8a2 2 0 0 1 -2 -2z"></path><path d="M16 8v-2a2 2 0 0 0 -2 -2h-8a2 2 0 0 0 -2 2v8a2 2 0 0 0 2 2h2"></path></svg></span></button></div><div style="--scrollarea-scrollbar-size:calc(0.25rem * var(--mantine-scale));--sa-corner-width:0px;--sa-corner-height:0px" class="m_f744fd40 mantine-CodeHighlightTabs-scrollarea m_d57069b5 mantine-ScrollArea-root" dir="ltr"><div style="overflow-x:hidden;overflow-y:hidden;overscroll-behavior-inline:none" class="m_c0783ff9 mantine-ScrollArea-viewport" data-scrollbars="xy"><div class="m_b1336c6 mantine-ScrollArea-content"><pre class="m_2c47c4fd mantine-CodeHighlightTabs-pre" data-with-offset="true"><code class="m_5caae6d3 mantine-CodeHighlightTabs-code">const isPrime = (n) => {
for (let i = 2; i < n; i++) {
if (n % i == 0) {
return false
}
}
return true
}</code></pre></div></div></div><button class="mantine-focus-auto m_c9378bc2 mantine-CodeHighlightTabs-showCodeButton m_87cf2631 mantine-UnstyledButton-root" data-hidden="true" type="button">Expand code</button></div></div><p>Этот алгоритм линейный по времени, он работает за O(n). Он константный по памяти, O(1), поскольку количество потребляемой памяти не зависит от n.</p>
<p>Он работает гораздо быстрее Решета, но все еще не самый оптимальный. Как мы помним, для проверки нам не обязательно делить n на все числа меньше себя, достаточно проверить только числа от 2 до sqrt(n), так что алгоритм можно переписать.</p>
<p>Алгоритмическая сложность переписанного алгоритма равна O(sqrt(n)) или O(n^(1/2)).</p>
<h2 id="heading-2-14">Выводы</h2>
<ol>
<li>При общих равных условиях программисты выбирают самые быстрые и самые экономичные алгоритмы</li>
<li>Выбрать самый быстрый алгоритм оказывается не так просто. Измерения на конкретных данных не позволяют прогнозировать время и память алгоритмов на других данных</li>
<li>Программисты используют нотацию О-большое, чтобы оценить производительность алгоритмов в целом</li>
<li>Чаще всего встречаются такие сложности, как константная, логарифмическая, линейная, линейно-логарифмическая, квадратическая, экспоненциальная и факториальная. В этом списке они распределены в порядке от самой быстрой к самой медленной</li>
<li>Нотация О-большое оценивает не только скорость алгоритма, но и память, которую он использует</li>
</ol></div><div style="margin-block:var(--mantine-spacing-xl)" class=""><h2 style="--title-fw:var(--mantine-h2-font-weight);--title-lh:var(--mantine-h2-line-height);--title-fz:var(--mantine-h2-font-size);margin-bottom:var(--mantine-spacing-md)" class="m_8a5d1357 mantine-Title-root" data-order="2">Рекомендуемые программы</h2><style data-mantine-styles="inline">.__m__-_R_2mremqrdub_{--carousel-slide-gap:var(--mantine-spacing-xs);--carousel-slide-size:70%;}@media(min-width: 36em){.__m__-_R_2mremqrdub_{--carousel-slide-gap:var(--mantine-spacing-xl);--carousel-slide-size:50%;}}</style><div style="--carousel-control-size:calc(2.5rem * var(--mantine-scale));--carousel-controls-offset:var(--mantine-spacing-sm);margin-bottom:var(--mantine-spacing-lg);padding-block:var(--mantine-spacing-sm);background:var(--app-color-surface)" class="m_17884d0f mantine-Carousel-root responsiveClassName" data-orientation="horizontal" data-include-gap-in-size="true"><div class="m_39bc3463 mantine-Carousel-controls" data-orientation="horizontal"><button class="mantine-focus-auto m_64f58e10 mantine-Carousel-control m_87cf2631 mantine-UnstyledButton-root" type="button" data-inactive="true" data-type="previous" tabindex="-1"><svg viewBox="0 0 15 15" fill="none" xmlns="http://www.w3.org/2000/svg" style="transform:rotate(90deg);width:calc(1rem * var(--mantine-scale));height:calc(1rem * var(--mantine-scale));display:block"><path d="M3.13523 6.15803C3.3241 5.95657 3.64052 5.94637 3.84197 6.13523L7.5 9.56464L11.158 6.13523C11.3595 5.94637 11.6759 5.95657 11.8648 6.15803C12.0536 6.35949 12.0434 6.67591 11.842 6.86477L7.84197 10.6148C7.64964 10.7951 7.35036 10.7951 7.15803 10.6148L3.15803 6.86477C2.95657 6.67591 2.94637 6.35949 3.13523 6.15803Z" fill="currentColor" fill-rule="evenodd" clip-rule="evenodd"></path></svg></button><button class="mantine-focus-auto m_64f58e10 mantine-Carousel-control m_87cf2631 mantine-UnstyledButton-root" type="button" data-inactive="true" data-type="next" tabindex="-1"><svg viewBox="0 0 15 15" fill="none" xmlns="http://www.w3.org/2000/svg" style="transform:rotate(-90deg);width:calc(1rem * var(--mantine-scale));height:calc(1rem * var(--mantine-scale));display:block"><path d="M3.13523 6.15803C3.3241 5.95657 3.64052 5.94637 3.84197 6.13523L7.5 9.56464L11.158 6.13523C11.3595 5.94637 11.6759 5.95657 11.8648 6.15803C12.0536 6.35949 12.0434 6.67591 11.842 6.86477L7.84197 10.6148C7.64964 10.7951 7.35036 10.7951 7.15803 10.6148L3.15803 6.86477C2.95657 6.67591 2.94637 6.35949 3.13523 6.15803Z" fill="currentColor" fill-rule="evenodd" clip-rule="evenodd"></path></svg></button></div><div class="m_a2dae653 mantine-Carousel-viewport" data-type="media"><div class="m_fcd81474 mantine-Carousel-container __m__-_R_2mremqrdub_" data-orientation="horizontal"><div class="m_d98df724 mantine-Carousel-slide" data-orientation="horizontal"><div tabindex="0" style="cursor:pointer;height:100%"><a style="text-decoration:none" class="mantine-focus-auto m_849cf0da m_b6d8b162 mantine-Text-root mantine-Anchor-root" data-underline="hover" href="/programs/algorithms?promo_name=programs_list&promo_position=course&promo_creative=catalog_card&promo_type=card" target="_blank"><div style="height:100%" class="m_e615b15f mantine-Card-root m_1b7284a3 mantine-Paper-root" data-with-border="true"><div style="--group-gap:calc(0.25rem * var(--mantine-scale));--group-align:center;--group-justify:flex-start;--group-wrap:nowrap" class="m_4081bf90 mantine-Group-root"><span style="font-size:var(--mantine-font-size-sm)" class="mantine-focus-auto m_b6d8b162 mantine-Text-root">2 месяца</span><span class="mantine-focus-auto m_b6d8b162 mantine-Text-root">·</span><span style="font-size:var(--mantine-font-size-sm)" class="mantine-focus-auto m_b6d8b162 mantine-Text-root">Для продвинутых</span></div><p style="margin-bottom:var(--mantine-spacing-sm);font-size:var(--mantine-font-size-h5);font-weight:bold" class="mantine-focus-auto m_b6d8b162 mantine-Text-root">Алгоритмы и структуры данных</p><p class="mantine-focus-auto m_b6d8b162 mantine-Text-root">Алгоритмы для собеседований</p><div style="margin-top:auto" class=""><div class="m_4451eb3a mantine-Center-root"><img style="opacity:0.8;width:70%" class="m_9e117634 mantine-Image-root mantine-visible-from-xs" src="https://hexlet.io/rails/active_storage/representations/proxy/eyJfcmFpbHMiOnsiZGF0YSI6NDAyOCwicHVyIjoiYmxvYl9pZCJ9fQ==--ae9eed98663dd1201759d042a5ba7ca790866156/eyJfcmFpbHMiOnsiZGF0YSI6eyJmb3JtYXQiOiJ3ZWJwIiwicmVzaXplX3RvX2xpbWl0IjpbNDAwLDQwMF0sInNhdmVyIjp7InF1YWxpdHkiOjg1fX0sInB1ciI6InZhcmlhdGlvbiJ9fQ==--5b6f46dacd1af664f27558553a58076185091823/Programming-bro.png" alt="Алгоритмы и структуры данных" loading="eager"/></div><div style="--group-gap:var(--mantine-spacing-md);--group-align:end;--group-justify:space-between;--group-wrap:wrap;margin-top:var(--mantine-spacing-xs)" class="m_4081bf90 mantine-Group-root"><p style="font-size:var(--mantine-font-size-xl)" class="mantine-focus-auto m_b6d8b162 mantine-Text-root">от 3 900 ₽</p><p style="font-size:var(--mantine-font-size-sm)" class="mantine-focus-auto m_b6d8b162 mantine-Text-root">Посмотреть →</p></div></div></div></a></div></div><div class="m_d98df724 mantine-Carousel-slide" data-orientation="horizontal"><div tabindex="0" style="cursor:pointer;height:100%"><a style="text-decoration:none" class="mantine-focus-auto m_849cf0da m_b6d8b162 mantine-Text-root mantine-Anchor-root" data-underline="hover" href="/courses?promo_name=programs_list&promo_position=course&promo_creative=catalog_card&promo_type=card"><div style="height:100%" class="m_e615b15f mantine-Card-root m_1b7284a3 mantine-Paper-root" data-with-border="true"><h2 style="--title-fw:var(--mantine-h2-font-weight);--title-lh:var(--mantine-h2-line-height);--title-fz:var(--mantine-h2-font-size);margin-bottom:var(--mantine-spacing-md);font-size:var(--mantine-font-size-h3)" class="m_8a5d1357 mantine-Title-root" data-order="2" data-responsive="true">Каталог</h2><p style="margin-bottom:auto" class="mantine-focus-auto m_b6d8b162 mantine-Text-root">Полный список доступных курсов по разным направлениям</p><div style="margin-top:auto" class=""><div class="m_4451eb3a mantine-Center-root"><img style="opacity:0.8;width:70%" class="m_9e117634 mantine-Image-root mantine-visible-from-xs" src="/vite/assets/development-BVihs_d5.png" alt="Orientation"/></div></div></div></a></div></div></div></div></div></div></div></div></div><style data-mantine-styles="inline">.__m__-_R_1bdub_{--col-flex-grow:auto;--col-flex-basis:8.333333333333334%;--col-max-width:8.333333333333334%;}@media(min-width: 48em){.__m__-_R_1bdub_{--col-flex-grow:auto;--col-flex-basis:16.666666666666668%;--col-max-width:16.666666666666668%;}}</style><div style="min-width:0rem;height:100%;min-height:0rem" class="m_96bdd299 mantine-Grid-col __m__-_R_1bdub_"><div style="margin-inline:var(--mantine-spacing-xs)" class="mantine-visible-from-sm"><a style="--button-color:var(--mantine-color-white);margin-bottom:var(--mantine-spacing-lg);text-decoration:none" class="mantine-focus-auto m_849cf0da mantine-focus-auto m_77c9d27d mantine-Button-root m_87cf2631 mantine-UnstyledButton-root m_b6d8b162 mantine-Text-root mantine-Anchor-root" data-underline="hover" href="/courses/basic-algorithms/lessons/algorithm-complexity/finish_unit?unit=theory" data-disabled="true" data-block="true" disabled=""><span class="m_80f1301b mantine-Button-inner"><span class="m_811560b9 mantine-Button-label"><span style="margin-inline-end:var(--mantine-spacing-xs)" class="mantine-focus-auto m_b6d8b162 mantine-Text-root">Дальше</span>→</span></span></a><a style="padding-inline:0rem" class="mantine-focus-auto m_f0824112 mantine-NavLink-root m_87cf2631 mantine-UnstyledButton-root"><span class="m_690090b5 mantine-NavLink-section" data-position="left"><div style="--ti-size:var(--ti-size-sm);--ti-bg:transparent;--ti-color:var(--mantine-color-indigo-light-color);--ti-bd:calc(0.0625rem * var(--mantine-scale)) solid transparent;color:inherit" class="m_7341320d mantine-ThemeIcon-root" data-variant="transparent" data-size="sm"><svg xmlns="http://www.w3.org/2000/svg" width="24" height="24" viewBox="0 0 24 24" fill="none" stroke="currentColor" stroke-width="1.2" stroke-linecap="round" stroke-linejoin="round" class="tabler-icon tabler-icon-list-numbers "><path d="M11 6h9"></path><path d="M11 12h9"></path><path d="M12 18h8"></path><path d="M4 16a2 2 0 1 1 4 0c0 .591 -.5 1 -1 1.5l-3 2.5h4"></path><path d="M6 10v-6l-2 2"></path></svg></div></span><div class="m_f07af9d2 mantine-NavLink-body"><span class="m_1f6ac4c4 mantine-NavLink-label">Навигация по теме</span><span class="m_57492dcc mantine-NavLink-description">Теория</span></div><span class="m_690090b5 mantine-NavLink-section" data-position="right"></span></a><div style="margin-block:var(--mantine-spacing-lg)" class="m_3eebeb36 mantine-Divider-root" data-orientation="horizontal" role="separator"></div><div style="margin-block:var(--mantine-spacing-lg)" class=""><div style="justify-content:space-between;margin-bottom:calc(0.1875rem * var(--mantine-scale));color:var(--mantine-color-dimmed);font-size:var(--mantine-font-size-xs)" class="m_8bffd616 mantine-Flex-root __m__-_R_qimrbdub_"><p style="font-size:var(--mantine-font-size-xs)" class="mantine-focus-auto m_b6d8b162 mantine-Text-root">Завершено</p><p style="font-size:var(--mantine-font-size-xs)" class="mantine-focus-auto m_b6d8b162 mantine-Text-root">0 / 9</p></div><div style="--progress-size:var(--progress-size-sm)" class="m_db6d6462 mantine-Progress-root" data-size="sm"><div style="--progress-section-size:0%;--progress-section-color:var(--mantine-color-gray-filled)" class="m_2242eb65 mantine-Progress-section" role="progressbar" aria-valuemax="100" aria-valuemin="0" aria-valuenow="0" aria-valuetext="0%"></div></div></div><button style="padding-inline:0rem" class="mantine-focus-auto m_f0824112 mantine-NavLink-root m_87cf2631 mantine-UnstyledButton-root" type="button"><span class="m_690090b5 mantine-NavLink-section" data-position="left"><div style="--ti-size:var(--ti-size-sm);--ti-bg:transparent;--ti-color:var(--mantine-color-indigo-light-color);--ti-bd:calc(0.0625rem * var(--mantine-scale)) solid transparent;color:inherit" class="m_7341320d mantine-ThemeIcon-root" data-variant="transparent" data-size="sm"><svg xmlns="http://www.w3.org/2000/svg" width="24" height="24" viewBox="0 0 24 24" fill="none" stroke="currentColor" stroke-width="1.2" stroke-linecap="round" stroke-linejoin="round" class="tabler-icon tabler-icon-message "><path d="M8 9h8"></path><path d="M8 13h6"></path><path d="M18 4a3 3 0 0 1 3 3v8a3 3 0 0 1 -3 3h-5l-5 3v-3h-2a3 3 0 0 1 -3 -3v-8a3 3 0 0 1 3 -3h12"></path></svg></div></span><div class="m_f07af9d2 mantine-NavLink-body"><span class="m_1f6ac4c4 mantine-NavLink-label">Обсуждения (архив)</span><span class="m_57492dcc mantine-NavLink-description"></span></div></button><div style="--toc-bg:var(--mantine-color-blue-light);--toc-color:var(--mantine-color-blue-light-color);--toc-size:var(--mantine-font-size-sm);--toc-radius:var(--mantine-radius-sm);margin-top:var(--mantine-spacing-xl)" class="m_bcaa9990 mantine-TableOfContents-root" data-variant="light" data-size="sm"></div></div><div class="mantine-hidden-from-sm"><div style="--stack-gap:0rem;--stack-align:stretch;--stack-justify:flex-start" class="m_6d731127 mantine-Stack-root"><a style="--button-color:var(--mantine-color-white);margin-bottom:var(--mantine-spacing-xs);padding:0rem;text-decoration:none" class="mantine-focus-auto m_849cf0da mantine-focus-auto m_77c9d27d mantine-Button-root m_87cf2631 mantine-UnstyledButton-root m_b6d8b162 mantine-Text-root mantine-Anchor-root" data-underline="hover" href="/courses/basic-algorithms/lessons/algorithm-complexity/finish_unit?unit=theory" data-disabled="true" data-block="true" disabled=""><span class="m_80f1301b mantine-Button-inner"><span class="m_811560b9 mantine-Button-label">→</span></span></a><button style="--ai-size:var(--ai-size-sm);--ai-bg:transparent;--ai-hover:var(--mantine-color-indigo-light-hover);--ai-color:var(--mantine-color-indigo-light-color);--ai-bd:calc(0.0625rem * var(--mantine-scale)) solid transparent;padding-block:var(--mantine-spacing-lg);color:inherit;width:100%" class="mantine-focus-auto m_8d3f4000 mantine-ActionIcon-root m_87cf2631 mantine-UnstyledButton-root" data-variant="subtle" data-size="sm" data-disabled="true" type="button" disabled=""><span class="m_8d3afb97 mantine-ActionIcon-icon"><svg xmlns="http://www.w3.org/2000/svg" width="24" height="24" viewBox="0 0 24 24" fill="none" stroke="currentColor" stroke-width="1.2" stroke-linecap="round" stroke-linejoin="round" class="tabler-icon tabler-icon-list-numbers "><path d="M11 6h9"></path><path d="M11 12h9"></path><path d="M12 18h8"></path><path d="M4 16a2 2 0 1 1 4 0c0 .591 -.5 1 -1 1.5l-3 2.5h4"></path><path d="M6 10v-6l-2 2"></path></svg></span></button><button style="--ai-size:var(--ai-size-sm);--ai-bg:transparent;--ai-hover:var(--mantine-color-indigo-light-hover);--ai-color:var(--mantine-color-indigo-light-color);--ai-bd:calc(0.0625rem * var(--mantine-scale)) solid transparent;padding-block:var(--mantine-spacing-lg);color:inherit;width:100%" class="mantine-focus-auto mantine-active m_8d3f4000 mantine-ActionIcon-root m_87cf2631 mantine-UnstyledButton-root" data-variant="subtle" data-size="sm" type="button"><span class="m_8d3afb97 mantine-ActionIcon-icon"><svg xmlns="http://www.w3.org/2000/svg" width="24" height="24" viewBox="0 0 24 24" fill="none" stroke="currentColor" stroke-width="1.2" stroke-linecap="round" stroke-linejoin="round" class="tabler-icon tabler-icon-message "><path d="M8 9h8"></path><path d="M8 13h6"></path><path d="M18 4a3 3 0 0 1 3 3v8a3 3 0 0 1 -3 3h-5l-5 3v-3h-2a3 3 0 0 1 -3 -3v-8a3 3 0 0 1 3 -3h12"></path></svg></span></button></div></div></div></div></div></div></div>
</main>
<footer class="bg-dark fw-light text-light px-3 py-5">
<div class="row small">
<div class="col-12 col-sm-6 col-md-3">
<div class="h5 mb-3">Хекслет</div>
<ul class="list-unstyled">
<li>
<a class="nav-link link-light py-1 ps-0" href="/pages/about">О нас</a>
</li>
<li>
<a class="nav-link link-light py-1 ps-0" href="/testimonials">Отзывы</a>
</li>
<li>
<span class="nav-link link-light py-1 ps-0 external-link" data-href="https://b2b.hexlet.io" role="button">Корпоративное обучение</span>
</li>
<li>
<a class="nav-link link-light py-1 ps-0" href="/blog">Блог</a>
</li>
<li>
<a class="nav-link link-light py-1 ps-0" href="/qna">Вопросы и ответы</a>
</li>
<li>
<a class="nav-link link-light py-1 ps-0" href="/glossary">Глоссарий</a>
</li>
<li>
<span class="nav-link link-light py-1 ps-0 external-link" data-href="https://help.hexlet.io" data-target="_blank" role="button">Справка</span>
</li>
<li>
<a class="nav-link link-light py-1 ps-0" target="_blank" rel="noopener noreferrer" href="/map">Карта сайта</a>
</li>
</ul>
</div>
<div class="col-12 col-sm-6 col-md-3">
<div class="h5 fw-normal mb-3">Направления</div>
<ul class="list-unstyled">
<li>
<a class="nav-link link-light py-1 ps-0" href="/courses_devops">DevOps
</a></li>
<li>
<a class="nav-link link-light py-1 ps-0" href="/courses_data_analytics">Аналитика
</a></li>
<li>
<a class="nav-link link-light py-1 ps-0" href="/courses_backend_development">Бэкенд
</a></li>
<li>
<a class="nav-link link-light py-1 ps-0" href="/courses_programming">Программирование
</a></li>
<li>
<a class="nav-link link-light py-1 ps-0" href="/courses_testing">Тестирование
</a></li>
<li>
<a class="nav-link link-light py-1 ps-0" href="/courses_front_end_dev">Фронтенд
</a></li>
</ul>
</div>
<div class="col-12 col-sm-6 col-md-3">
<div class="h5">Профессии</div>
<ul class="list-unstyled">
<li>
<a class="nav-link link-light py-1 ps-0" href="/programs/devops-engineer-from-scratch">DevOps-инженер с нуля</a>
</li>
<li>
<a class="nav-link link-light py-1 ps-0" href="/programs/go">Go-разработчик</a>
</li>
<li>
<a class="nav-link link-light py-1 ps-0" href="/programs/java">Java-разработчик</a>
</li>
<li>
<a class="nav-link link-light py-1 ps-0" href="/programs/python">Python-разработчик </a>
</li>
<li>
<a class="nav-link link-light py-1 ps-0" href="/programs/data-analytics">Аналитик данных</a>
</li>
<li>
<a class="nav-link link-light py-1 ps-0" href="/programs/qa-engineer">Инженер по ручному тестированию</a>
</li>
<li>
<a class="nav-link link-light py-1 ps-0" href="/programs/php">РНР-разработчик</a>
</li>
<li>
<a class="nav-link link-light py-1 ps-0" href="/programs/frontend">Фронтенд-разработчик</a>
</li>
</ul>
</div>
<div class="col-12 col-sm-6 col-md-3">
<div class="h5">Навыки</div>
<ul class="list-unstyled">
<li>
<a class="nav-link link-light py-1 ps-0" href="/programs/python-django-developer">Django</a>
</li>
<li>
<a class="nav-link link-light py-1 ps-0" href="/programs/docker">Docker</a>
</li>
<li>
<a class="nav-link link-light py-1 ps-0" href="/programs/php-laravel-developer">Laravel</a>
</li>
<li>
<a class="nav-link link-light py-1 ps-0" href="/programs/postman">Postman</a>
</li>
<li>
<a class="nav-link link-light py-1 ps-0" href="/programs/js-react-developer">React</a>
</li>
<li>
<a class="nav-link link-light py-1 ps-0" href="/programs/js-rest-api">REST API в Node.js</a>
</li>
<li>
<a class="nav-link link-light py-1 ps-0" href="/programs/spring-boot">Spring Boot</a>
</li>
<li>
<a class="nav-link link-light py-1 ps-0" href="/programs/typescript">Typescript</a>
</li>
</ul>
</div>
</div>
<hr>
<div class="row">
<div class="col-12 col-sm-4 col-md-2">
<div class="fs-4">
<ul class="list-unstyled d-flex">
<li class="me-3">
<a aria-label="Telegram" target="_blank" class="link-light" rel="noopener noreferrer nofollow" href="https://t.me/hexlet_ru"><span class="bi bi-telegram"></span>
</a></li>
<li>
<a aria-label="Youtube" target="_blank" class="link-light" rel="noopener noreferrer nofollow" href="https://www.youtube.com/user/HexletUniversity"><span class="bi bi-youtube"></span>
</a></li>
</ul>
</div>
<div class="mb-2 d-flex flex-column">
<a class="link-light text-decoration-none" rel="nofollow" href="mailto:support@hexlet.io">support@hexlet.io</a>
<a class="link-light text-decoration-none py-2" target="_blank" href="https://t.me/hexlet_help_bot">t.me/hexlet_help_bot</a>
</div>
<ul class="list-unstyled d-flex">
<li class="me-3">
<span class="link-light text-decoration-none opacity-50 x-font-size-18 external-link" rel="nofollow" data-href="https://hexlet.io/locale/switch?new_locale=en" data-target="_self" role="button"><span class="my-auto">EN</span>
</span></li>
<li class="me-3">
<span class="link-light text-decoration-none opacity-50 x-font-size-18 opacity-100 external-link" rel="nofollow" data-href="https://ru.hexlet.io/locale/switch?new_locale=ru" data-target="_self" role="button"><span class="my-auto">RU</span>
</span></li>
<li class="me-3">
<span class="link-light text-decoration-none opacity-50 x-font-size-18 external-link" rel="nofollow" data-href="https://kz.hexlet.io/locale/switch?new_locale=kz" data-target="_self" role="button"><span class="my-auto">KZ</span>
</span></li>
</ul>
</div>
<div class="col-12 col-sm-4 col-md-3">
<ul class="list-unstyled fs-4">
<li class="mb-3">
<a class="link-light text-decoration-none" href="tel:8%20800%20100%2022%2047">8 800 100 22 47</a>
<span class="d-block opacity-50 small">бесплатно по РФ</span>
</li>
<li>
<a class="link-light text-decoration-none" href="tel:%2B7%20495%20085%2021%2062">+7 495 085 21 62</a>
<span class="d-block opacity-50 small">бесплатно по Москве</span>
</li>
</ul>
</div>
<div class="col-12 col-sm-4 col-md-3">
<div class="small mb-3">Образовательные услуги оказываются на основании Л035-01298-77/01989008 от 14.03.2025</div>
<ul class="list-unstyled small">
<li>
<a class="nav-link link-light py-1 ps-0" href="/pages/legal">Правовая информация</a>
</li>
<li>
<a class="nav-link link-light py-1 ps-0" href="/pages/offer">Оферта</a>
</li>
<li>
<a class="nav-link link-light py-1 ps-0" href="/pages/license">Лицензия</a>
</li>
<li>
<a class="nav-link link-light py-1 ps-0" href="/pages/contacts">Контакты</a>
</li>
</ul>
</div>
<div class="col-12 col-sm-12 col-md-4 small">
<div class="mb-2">
<div>ООО «<a href="/" class="text-decoration-none link-light">Хекслет Рус</a>»</div>
<div>108813 г. Москва, вн.тер.г. поселение Московский,</div>
<div>г. Московский, ул. Солнечная, д. 3А, стр. 1, помещ. 20Б/3</div>
<div>ОГРН 1217300010476</div>
<div>ИНН 7325174845</div>
</div>
<hr>
<div>АНО ДПО «<a href="/" class="text-decoration-none link-light">Учебный центр «Хекслет</a>»</div>
<div>119331 г. Москва, вн. тер. г. муниципальный округ</div>
<div>Ломоносовский, пр-кт Вернадского, д. 29</div>
<div>ОГРН 1247700712390</div>
<div>ИНН 7736364948</div>
</div>
</div>
</footer>
<div id="root-assistant-offcanvas"></div>
<script src="/vite/assets/assistant-CdBlNCiQ.js" crossorigin="anonymous" type="module"></script><link rel="modulepreload" href="/vite/assets/chunk-DsPFFUou.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/init-nkZBEvfU.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/ErrorFallbackBlock-naDSYSy9.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/MarkdownBlock-DbyKWoR_.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/gon-D3e4yh1x.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/mantine-CGMYrt2Y.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/shiki-V011pkdv.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/utils-DRqSHbQE.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/routes-CCH8ilKF.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/lib-XR8Qr8kR.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/dist-GCHh59xr.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/Box-B5-OOzBf.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/notifications.store-C-3AFSMn.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/useIsomorphicEffect-HJ6VK0D3.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/lib-KSp6QbZ0.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/axios-BEvgo0ym.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/classnames-l6ipYlLR.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/dayjs.min-BkKovM-s.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/debounce-jMQ_Cf4f.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/i18next-BlSq9s7B.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/client-U9M77rxp.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/react-dom-DaLxUz_h.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/useTranslation-Bx1Cdrkz.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/compiler-runtime-6XxiPFnt.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/jsx-runtime-CwjcCKJi.js" as="script" crossorigin="anonymous">
<link rel="modulepreload" href="/vite/assets/react-CkL4ZRHB.js" as="script" crossorigin="anonymous">
<script defer src="https://static.cloudflareinsights.com/beacon.min.js/v67327c56f0bb4ef8b305cae61679db8f1769101564043" integrity="sha512-rdcWY47ByXd76cbCFzznIcEaCN71jqkWBBqlwhF1SY7KubdLKZiEGeP7AyieKZlGP9hbY/MhGrwXzJC/HulNyg==" data-cf-beacon='{"version":"2024.11.0","token":"d11015b65d11429ea6b4a2ef37dd7e0b","server_timing":{"name":{"cfCacheStatus":true,"cfEdge":true,"cfExtPri":true,"cfL4":true,"cfOrigin":true,"cfSpeedBrain":true},"location_startswith":null}}' crossorigin="anonymous"></script>
</body>
</html>