Основы алгоритмов и анализ сложности Big O

Введение в алгоритмизацию и зачем нужно оценивать эффективность кода

Добро пожаловать в курс «Основы алгоритмов и анализ сложности Big O». Это первая статья, и наша цель сегодня — заложить фундамент. Мы разберемся, что такое алгоритм на самом деле, почему работающий код не всегда является хорошим кодом, и зачем программистам нужна математика для оценки скорости программ.

Что такое алгоритм?

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

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

* Рецепт блинов: Взять муку, добавить молоко, разбить яйца, перемешать, жарить. Это алгоритм. * Путь на работу: Выйти из дома, дойти до метро, проехать 5 станций, пройти 200 метров. Это тоже алгоритм.

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

!Блок-схема, показывающая алгоритм приготовления кофе из входных ингредиентов.

Пример простейшего алгоритма в коде

Допустим, нам нужно найти сумму всех чисел в списке. Вот как это выглядит на языке Python:

Здесь алгоритм звучит так: «Создай переменную для суммы. Пройдись по каждому числу в списке. Прибавь число к сумме. Верни результат».

Почему просто «работает» — недостаточно?

Представьте, что вам нужно найти номер телефона друга в старом бумажном телефонном справочнике, где записи отсортированы по алфавиту. У вас есть два способа (два алгоритма) сделать это:

Алгоритм А (Наивный): Открывать справочник с первой страницы и читать каждое имя подряд, пока не найдете нужное.

Алгоритм Б (Умный): Открыть справочник посередине. Если имя друга по алфавиту идет раньше — отбросить вторую половину книги. Если позже — отбросить первую. Повторять процесс с оставшейся частью, пока имя не найдется.

Оба алгоритма приведут к результату. Оба работают. Но есть нюанс.

Если в справочнике 1000 страниц: * Алгоритм А в худшем случае заставит вас просмотреть 1000 страниц (если друг на фамилию «Яковлев»). * Алгоритм Б найдет нужную страницу примерно за 10 попыток.

В программировании разница между «просто работает» и «работает эффективно» может означать разницу между программой, которая выполняется за 1 секунду, и программой, которая зависнет на 100 лет.

!Иллюстрация разницы между последовательным перебором и методом деления пополам.

Проблема измерения скорости

Как нам понять, какой алгоритм быстрее? Первая мысль — запустить код и засечь время секундомером.

Однако этот метод ненадежен по нескольким причинам:

Разное железо: На мощном игровом ПК плохой алгоритм может сработать быстрее, чем хороший алгоритм на старом ноутбуке.

Фоновые процессы: Если во время теста антивирус начнет проверку диска, время выполнения вашего кода увеличится.

Зависимость от данных: Некоторые алгоритмы работают быстро на малых данных, но катастрофически замедляются на больших.

Поэтому в Computer Science мы не измеряем скорость в секундах. Мы измеряем ее в количестве операций.

Введение понятия

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

* Если мы сортируем массив из 10 чисел, . * Если мы ищем пользователя в базе из миллиона юзеров, .

Наша задача — понять, как растет количество операций при росте . Это называется асимптотическим анализом.

Рассмотрим простую математическую зависимость. Допустим, количество операций зависит от входных данных следующим образом:

Где: * — общее количество действий, которое совершит компьютер. * — количество элементов, которые нужно обработать (например, прочитать строк). * — какие-то подготовительные действия, которые выполняются всегда (например, объявление переменных).

Если , то операций . Если , операций . Мы видим, что количество работы растет линейно пропорционально .

А теперь представим другой алгоритм, где зависимость такая:

Где: * — количество операций. * — размер входных данных. * — квадрат размера данных (например, вложенный цикл, где мы сравниваем каждый элемент с каждым).

При , операций . Но при , операций уже ! Второй алгоритм при росте данных становится значительно медленнее первого.

Два кита эффективности: Time и Space

Когда мы говорим об эффективности, мы обычно подразумеваем два ресурса:

Time Complexity (Временная сложность): Как быстро растет время выполнения алгоритма при увеличении входных данных. Это то, о чем мы говорили выше (количество операций).

Space Complexity (Пространственная сложность): Сколько дополнительной оперативной памяти требуется алгоритму при увеличении входных данных.

Часто в программировании существует компромисс, называемый Space-Time Tradeoff (компромисс времени и памяти). Вы можете ускорить программу, используя больше памяти (например, кэшируя результаты), или сэкономить память, пересчитывая данные каждый раз заново (тратя время).

> «Преждевременная оптимизация — корень всех зол». > — Дональд Кнут, The Art of Computer Programming

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

Зачем это нужно на практике?

Вы можете спросить: «Зачем мне это знать, если современные компьютеры невероятно быстрые?»

Ответ прост: данные растут быстрее, чем скорость процессоров.

* Если вы пишете скрипт для обработки 50 файлов на своем компьютере, разница между эффективным и неэффективным алгоритмом будет незаметна (0.01 сек против 0.1 сек). * Если вы работаете в бэкенде веб-сервиса, который обрабатывает миллионы запросов в минуту, плохой алгоритм «положит» сервер, и компания потеряет деньги.

Знание основ алгоритмизации и умение оценивать сложность позволяет вам:

Предсказывать поведение программы под нагрузкой.

Выбирать правильные структуры данных (о которых мы поговорим в будущих статьях).

Писать код, который масштабируется.

Что нас ждет дальше?

В этой статье мы ввели понятие эффективности и выяснили, что секунды — плохая метрика. Нам нужен универсальный язык для описания того, как «тяжелеет» алгоритм с ростом данных.

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

Мы перейдем от абстрактных понятий к конкретным правилам, которые вы сможете применять в своей ежедневной работе.

Нотация Big O: определение, математический смысл и основные классы сложности

В предыдущей статье мы выяснили, что измерять скорость алгоритма в секундах — ненадежно. Мы пришли к выводу, что нам нужен способ описать, как количество операций растет вместе с увеличением входных данных . Сегодня мы изучим этот универсальный язык программистов — Big O Notation (О-большое).

Понимание Big O — это своего рода «суперспособность», которая позволяет вам взглянуть на кусок кода и сразу сказать: «Это будет работать быстро» или «Это убьет наш сервер при нагрузке».

Что такое Big O на самом деле?

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

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

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

!Иллюстрация того, что Big O описывает верхнюю границу сложности алгоритма.

Математический смысл и отбрасывание лишнего

Когда мы анализируем алгоритм, мы сначала считаем примерное количество операций. Допустим, мы написали функцию, которая делает следующее:

Инициализирует 5 переменных.

Проходит циклом по массиву из элементов, выполняя 3 действия для каждого элемента.

В конце выполняет еще 10 завершающих операций.

Формула количества операций выглядит так:

Где: * — общее количество операций. * — размер входных данных. * — операции внутри цикла (3 операции умноженные на повторений). * — сумма константных операций ().

Однако в Big O мы не пишем . Мы пишем просто . Почему?

Правило 1: Отбрасываем константы

При асимптотическом анализе (когда стремится к бесконечности) константы теряют значение.

Если , то: * *

Разница ничтожна. Множитель перед (в данном случае 3) тоже отбрасывается, потому что он не меняет характер роста функции. Линейный рост остается линейным, будь то , или .

Поэтому:

Правило 2: Оставляем только доминирующее слагаемое

Представьте алгоритм, который сначала проходит по массиву (цикл), а затем запускает вложенный цикл (каждый с каждым). Его сложность:

Где: * — сложность вложенного цикла. * — сложность простого цикла.

При : * *

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

Поэтому:

Основные классы сложности (Зоопарк Big O)

Существует несколько стандартных классов сложности, с которыми вы будете сталкиваться в 99% случаев. Расположим их от самых быстрых (лучших) к самым медленным (худшим).

!Сравнительный график роста количества операций для разных классов сложности Big O.

1. — Константная сложность

Это идеал. Время выполнения алгоритма не зависит от размера входных данных.

Пример: Получение элемента массива по индексу.

Будь в массиве 5 элементов или 5 миллиардов, компьютер просто обращается к нужному адресу памяти. Это занимает одно и то же время.

2. — Логарифмическая сложность

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

Математическая справка: Логарифм — это обратная операция возведению в степень. В информатике мы обычно используем логарифм по основанию 2.

Где: * — размер данных. * — степень, в которую нужно возвести 2, чтобы получить . Это и есть количество операций.

Если , то , так как . Для обработки тысячи элементов нужно всего 10 шагов!

Пример: Бинарный поиск (поиск в отсортированном списке, как в примере с телефонной книгой из прошлой статьи).

3. — Линейная сложность

Время выполнения растет прямо пропорционально количеству данных. Увеличили данные в 2 раза — время увеличилось в 2 раза.

Пример: Простой перебор массива (цикл for).

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

4. — Линеарифимическая сложность

Чуть медленнее, чем линейная, но значительно быстрее квадратичной. Это «золотой стандарт» для эффективных алгоритмов сортировки.

Пример: Быстрая сортировка (Quicksort), Сортировка слиянием (Merge Sort).

5. — Квадратичная сложность

Время выполнения пропорционально квадрату входных данных. Увеличили данные в 2 раза — время выросло в 4 раза (). Обычно это признак вложенных циклов.

Пример: Сравнение каждого элемента с каждым (Пузырьковая сортировка).

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

6. — Экспоненциальная сложность

Это зона опасности. Добавление всего одного элемента во входные данные удваивает время работы.

Пример: Рекурсивный расчет чисел Фибоначчи (без оптимизации), перебор всех подмножеств множества.

Если , количество операций уже превышает миллиард. Такие алгоритмы практически неприменимы для больших .

7. — Факториальная сложность

Самый медленный класс из распространенных. Количество операций равно произведению всех чисел от 1 до .

Где: * — факториал числа .

Пример: Задача коммивояжера полным перебором (поиск кратчайшего маршрута через городов).

Сводная таблица масштабов

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

| Сложность | Название | Примерное кол-во операций при | | :--- | :--- | :--- | | | Константная | 1 | | | Логарифмическая | ~7 | | | Линейная | 100 | | | Линеарифимическая | ~665 | | | Квадратичная | 10 000 | | | Экспоненциальная | (больше, чем атомов в грамме воды) |

Как определять сложность кода на глаз?

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

Простые действия (присваивание, арифметика, сравнение, доступ по индексу) — это .

Цикл по элементам — это .

Вложенный цикл (цикл внутри цикла) — это .

Цикл, где переменная удваивается или делится пополам на каждом шаге — это .

Последовательные действия складываются: (берем максимум).

Заключение

Мы разобрали, что Big O — это инструмент для оценки худшего сценария поведения алгоритма. Мы научились отбрасывать константы и выделять главное. Мы познакомились с основными классами сложности: от мгновенного до катастрофического .

В следующей статье мы перейдем от теории к практике и начнем разбирать структуры данных. Мы узнаем, как массивы устроены в памяти компьютера и почему добавление элемента в середину массива — это медленная операция .

Вычисление временной сложности: анализ циклов, вложенности и рекурсии

Мы уже знаем, что такое Big O, и познакомились с основными классами сложности. Но теория — это одно, а реальный код — совсем другое. Глядя на функцию в 50 строк, бывает трудно сразу сказать, работает она за или за .

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

Базовая арифметика сложности

Прежде чем нырять в циклы, вспомним правило, которое мы обсуждали ранее: простые операции считаются мгновенными.

К таким операциям () относятся: * Присваивание переменной (x = 5) Арифметические действия (+, -, , /) * Логические сравнения (if x > 10) * Доступ к элементу массива по индексу (arr[5]) * Вызов функции (если сама функция выполняется за константное время)

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

Анализ циклов: Линейный рост

Самый распространенный паттерн в программировании — это цикл for или while. Чтобы узнать сложность цикла, нужно ответить на вопрос: сколько раз выполняется тело цикла относительно входных данных ?

Простой цикл

Рассмотрим пример:

Здесь количество итераций напрямую зависит от длины списка items. Если в списке элементов, цикл выполнится раз.

Математически это записывается так:

Где: * — общее время выполнения. * — время выполнения одной итерации (константа). * — количество повторений.

В нотации Big O мы отбрасываем константу , получая сложность .

Цикл с шагом

А что, если мы идем не по каждому элементу, а через один?

В этом случае цикл выполнится раз. Но вспомним правила упрощения: константные множители не важны. Половина от бесконечности — это все еще бесконечность того же порядка.

Где: * — размер входных данных. * — константный множитель, который мы отбрасываем.

Сложность остается линейной.

Вложенные циклы: Правило умножения

Когда один цикл находится внутри другого, их сложности перемножаются. Это часто встречается при работе с матрицами (двумерными массивами) или при сравнении элементов «каждый с каждым».

Давайте посчитаем общее количество операций:

Где: * — общее количество операций. * — количество итераций внешнего цикла. * (второй множитель) — количество итераций внутреннего цикла на каждый шаг внешнего.

Сложность такого алгоритма — (Квадратичная).

!Визуализация выполнения вложенного цикла как заполнение площади квадрата со стороной n.

Важный нюанс: зависимые циклы

Иногда внутренний цикл зависит от переменной внешнего цикла:

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

Где: * — сумма всех итераций. * — количество элементов.

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

Последовательные циклы: Правило сложения

Если циклы идут один за другим, их сложности складываются.

Сложность:

Где: * — общая сложность. * — сложность каждого отдельного цикла.

Мы берем максимальную степень. Если бы первый цикл был , а второй , итоговая сложность была бы , так как квадратичная часть доминирует над линейной.

Логарифмические циклы: Деление и умножение

Не все циклы работают последовательно. Если переменная цикла изменяется не на +1, а умножается или делится, сложность меняется кардинально.

Рассмотрим пример:

Предположим, . Значения i будут: 1, 2, 4, 8, 16, 32. Цикл выполнится всего 6 раз.

Мы ищем количество шагов , такое что:

Где: * — множитель, на который мы умножаем i на каждом шаге. * — количество шагов (итераций). * — конечное значение, при котором цикл остановится.

Выразим :

Сложность такого алгоритма — . Это очень быстрые алгоритмы. К этому классу относится, например, бинарный поиск.

Рекурсия: Скрытая сложность

Анализ рекурсивных функций сложнее, потому что цикла не видно явно. Чтобы понять сложность рекурсии, нужно представить дерево рекурсивных вызовов.

Линейная рекурсия

Здесь функция вызывает саму себя 1 раз с аргументом . Дерево вызовов выглядит как прямая линия: .

Глубина рекурсии равна . Сложность — .

Множественная рекурсия (Экспоненциальная)

Классический пример «плохой» рекурсии — наивное вычисление чисел Фибоначчи:

Здесь каждый вызов порождает два новых вызова. Дерево ветвится.

!Дерево вызовов для функции Фибоначчи: один вызов превращается в два, два в четыре и так далее.

Количество узлов в таком дереве растет как (на самом деле ближе к , но в Big O мы оцениваем верхнюю границу как ).

Формула количества операций:

Где: * — количество операций. * — количество вызовов внутри одной функции. * — глубина рекурсии.

Сложность — . Это очень медленно. Для такая программа будет работать годами.

Пространственная сложность рекурсии

Важно помнить про Space Complexity. Рекурсия всегда потребляет память, так как каждый вызов функции сохраняется в стеке вызовов (Call Stack).

Если глубина рекурсии равна , то пространственная сложность будет , даже если временная сложность тоже . В отличие от цикла, который использует памяти, рекурсия может вызвать ошибку Stack Overflow (переполнение стека) при больших данных.

Итоговый алгоритм анализа

Чтобы определить сложность любой функции:

Найдите все циклы и рекурсивные вызовы.

Оцените сложность каждого блока отдельно.

Если блоки вложены — перемножьте их сложности.

Если блоки идут последовательно — сложите их и оставьте только самое «тяжелое» слагаемое.

Отбросьте все константы.

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

Пространственная сложность алгоритмов и оценка потребления памяти

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

Но время — не единственный ресурс, за который мы платим. Второй важнейший ресурс — это память (RAM).

Представьте, что вы написали супербыстрый алгоритм, который обрабатывает данные за миллисекунды. Но для работы ему требуется 64 ГБ оперативной памяти, а на сервере доступно только 8 ГБ. Ваш алгоритм просто не запустится или приведет к сбою системы.

Сегодня мы поговорим о Space Complexity (Пространственной сложности) — метрике, которая показывает, сколько дополнительной памяти требуется алгоритму для работы.

Что такое пространственная сложность?

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

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

Входные данные vs Вспомогательная память

При анализе важно различать два понятия:

Input Space (Память под входные данные): Место, которое занимают сами данные, переданные в функцию (например, массив из миллиона чисел).

Auxiliary Space (Вспомогательная память): Дополнительное место, которое алгоритм выделяет в процессе своей работы (переменные, новые массивы, стек вызовов).

В алгоритмических интервью и анализе мы обычно фокусируемся на Auxiliary Space. Нас интересует: «Сколько лишней памяти съест этот код?».

Основные классы пространственной сложности

Давайте разберем, откуда берется потребление памяти, на конкретных примерах.

— Константная сложность

Самый экономный вариант. Алгоритм использует фиксированное количество переменных, независимо от того, сколько данных вы ему скормили.

Пример: Вычисление суммы элементов массива.

Даже если в списке numbers будет миллиард чисел, функция создаст только одну переменную total (и, возможно, временную переменную для цикла). Объем дополнительной памяти не меняется.

Математически это можно записать так:

Где: * — потребляемая память в зависимости от . * — размер входных данных. * — константа (фиксированный объем памяти).

В нотации Big O это .

— Линейная сложность

Потребление памяти растет прямо пропорционально количеству входных данных. Это происходит, когда мы создаем копии данных или новые структуры, зависящие от размера входа.

Пример: Функция, которая возвращает список квадратов чисел.

Если на вход пришел массив из 10 чисел, мы создадим новый массив из 10 чисел. Если пришел миллион — создадим массив на миллион элементов.

Формула потребления памяти:

Где: * — общая память. * — количество элементов. * — размер памяти под один элемент. * — константа под служебные переменные.

Отбрасывая константы, получаем .

!Визуальное сравнение фиксированной памяти O(1) и растущей памяти O(n).

— Квадратичная сложность

Чаще всего встречается при создании двумерных массивов (матриц) или таблиц для динамического программирования.

Пример: Создание таблицы умножения размером .

Здесь мы храним строк, в каждой из которых элементов. Общее количество ячеек — . Сложность .

Скрытый пожиратель памяти: Стек вызовов

С переменными и массивами все понятно: мы явно видим их в коде (new Array, []). Но есть вид памяти, который новички часто упускают из виду. Это Stack Space (память стека), используемая при вызове функций, особенно в рекурсии.

Когда вызывается функция, компьютер сохраняет её состояние (локальные переменные, адрес возврата) в специальной области памяти — стеке вызовов.

Рекурсия и память

Вспомним пример с факториалом из прошлой статьи:

Кажется, что здесь нет новых переменных. Значит, сложность ? Нет.

Чтобы вычислить factorial(5), компьютер должен помнить состояние factorial(5), пока вычисляет factorial(4). Тот ждет factorial(3), и так далее.

Цепочка вызовов:

factorial(5) ждет...

factorial(4) ждет...

factorial(3) ждет...

factorial(2) ждет...

factorial(1) возвращает 1.

В памяти одновременно висят кадров стека (stack frames).

Следовательно, пространственная сложность такой рекурсии — .

!Иллюстрация стека вызовов при рекурсии: каждый вызов занимает место в памяти.

> Важно: Если глубина рекурсии слишком велика, память стека закончится, и вы получите ошибку Stack Overflow (Переполнение стека).

Space-Time Trade-off (Компромисс времени и памяти)

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

Этот принцип называется Space-Time Trade-off.

Пример: Поиск дубликатов

Допустим, у нас есть массив чисел, и нужно проверить, есть ли в нем повторы.

Вариант 1: Экономим память (Brute Force) Берем каждое число и сравниваем со всеми остальными (вложенные циклы). * Время: — очень медленно. * Память: — не создаем ничего лишнего.

Вариант 2: Экономим время (Использование Хеш-таблицы) Проходим по массиву один раз и запоминаем каждое встреченное число в отдельном множестве (Set). * Время: — быстро. * Память: — нам нужно место для хранения множества.

Мы «купили» скорость, заплатив за нее оперативной памятью. В современной разработке, где память относительно дешевая, мы часто выбираем второй вариант. Но если вы программируете микроконтроллер с 2 КБ памяти, вам придется выбрать первый вариант.

Строки и их неизменяемость

В некоторых языках программирования (например, Python, Java, C#) строки являются неизменяемыми (immutable). Это важный нюанс для пространственной сложности.

Рассмотрим код:

Кажется, что мы просто добавляем букву. Но так как строку нельзя изменить, компьютер каждый раз:

Создает новую строку в памяти.

Копирует туда старое содержимое.

Добавляет новый символ.

Удаляет старую строку.

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

Итоговая таблица

Давайте подытожим, что влияет на пространственную сложность:

| Что в коде | Примерная сложность | Почему? | | :--- | :--- | :--- | | Переменные, константы | | Занимают фиксированное место | | Массив длины | | Хранит элементов | | Двумерный массив | | Хранит элементов | | Рекурсия глубины | | Стек вызовов хранит состояний | | Сортировка слиянием (Merge Sort) | | Требует дополнительный массив для слияния | | Сортировка пузырьком | | Сортирует «на месте» (in-place) |

Заключение

Теперь у вас есть полная картина эффективности алгоритмов.

* Time Complexity говорит нам, не зависнет ли программа. * Space Complexity говорит нам, не вылетит ли программа с ошибкой нехватки памяти.

Хороший инженер всегда ищет баланс. Иногда стоит потратить лишний мегабайт памяти, чтобы ускорить запрос в 100 раз. А иногда, работая с Big Data, экономия каждого байта становится критической задачей.

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

Практический анализ сложности на примере популярных алгоритмов сортировки и поиска

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

В этой статье мы не просто выучим, как работают популярные алгоритмы поиска и сортировки. Мы применим наши знания Big O, чтобы препарировать их и понять, почему одни методы считаются стандартами индустрии, а другие годятся только для учебников.

Алгоритмы поиска: Иголка в стоге сена

Поиск данных — одна из самых частых операций в мире. Каждый раз, когда вы вводите запрос в Google или ищете контакт в телефоне, работает алгоритм поиска. Рассмотрим два фундаментальных подхода.

Линейный поиск (Linear Search)

Это самый простой и интуитивный метод. Представьте, что у вас есть колода карт, разбросанная по столу, и вам нужно найти туза пик. Вы берете карты по одной и смотрите: «Это туз пик? Нет. А это? Нет». И так до тех пор, пока не найдете.

В коде это выглядит как обычный перебор:

Анализ сложности:

* Лучший случай: Искомый элемент находится в самом начале (индекс 0). Время выполнения — . * Худший случай: Элемент находится в самом конце или отсутствует вовсе. Нам придется проверить все элементов.

Следовательно, временная сложность линейного поиска — .

Бинарный поиск (Binary Search)

Теперь представьте, что карты аккуратно сложены по порядку (от двойки до туза). Чтобы найти восьмерку, вам не нужно перебирать всё подряд. Вы снимаете колоду посередине. Если там десятка, вы понимаете: «Восьмерка меньше десятки, значит, она в левой половине». Правую половину можно смело выбросить.

Это и есть принцип «Разделяй и властвуй».

> Важное условие: Бинарный поиск работает только с отсортированными данными.

Анализ сложности:

На каждом шаге мы сокращаем область поиска вдвое. Мы начинаем с элементов, затем , затем , и так далее, пока не останется 1 элемент.

Математически мы ищем количество шагов , при котором:

Где: * — начальное количество элементов. * — делитель (мы делим массив пополам). * — количество шагов (итераций цикла). * — конечный размер области поиска (один элемент).

Решая это уравнение относительно , получаем логарифм:

Где: * — искомое количество операций. * — логарифм от по основанию 2.

Сложность бинарного поиска — .

!Визуализация разницы в количестве шагов между линейным и бинарным поиском.

Разница колоссальна. Если (миллиард): * Линейный поиск сделает 1 миллиард операций. * Бинарный поиск сделает всего около 30 операций ().

Алгоритмы сортировки: От простого к эффективному

Чтобы использовать мощь бинарного поиска, данные нужно сначала отсортировать. И здесь мы сталкиваемся с огромным разнообразием алгоритмов.

Пузырьковая сортировка (Bubble Sort)

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

Анализ сложности:

Мы видим вложенный цикл.

Внешний цикл выполняется раз.

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

Применяем правило умножения для вложенных циклов:

Где: * — время выполнения. * — количество элементов в массиве.

Сложность — . Это квадратичная сложность. Если увеличить массив в 10 раз, сортировка замедлится в 100 раз. Для больших данных этот метод непригоден.

Сортировка слиянием (Merge Sort)

Чтобы преодолеть проклятие , инженеры придумали более хитрые алгоритмы, использующие рекурсию. Один из лучших примеров — Merge Sort.

Алгоритм работает в два этапа:

Разделение (Divide): Массив рекурсивно делится пополам, пока не останутся кусочки длиной в 1 элемент.

Слияние (Conquer): Кусочки соединяются обратно, но уже в правильном порядке.

!Дерево рекурсивных вызовов Merge Sort: сначала деление, потом слияние.

Анализ сложности:

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

Сколько раз мы можем поделить массив пополам? Как мы выяснили в бинарном поиске, высота такого дерева деления равна .

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

Общая сложность равна произведению высоты дерева на работу на каждом уровне:

Где: * — общее время выполнения. * — количество операций слияния на одном уровне (ширина уровня). * — количество уровней деления (высота дерева).

Сложность — .

Это значительно быстрее, чем . Для миллиона элементов: * операций. * операций.

Разница в 50 000 раз!

Пространственная сложность: Плата за скорость

Вспомним про Space Complexity.

* Bubble Sort меняет элементы местами прямо внутри исходного массива. Ему нужна всего одна временная переменная для обмена. Его пространственная сложность — . * Merge Sort требует создания новых массивов для хранения разделенных частей и результата слияния. В худшем случае ему требуется столько же дополнительной памяти, сколько занимает сам массив. Его пространственная сложность — .

Здесь мы снова видим Space-Time Trade-off: Merge Sort намного быстрее по времени, но «дороже» по памяти.

Сводная таблица популярных алгоритмов

Вот шпаргалка, которая поможет вам ориентироваться в эффективности базовых алгоритмов:

| Алгоритм | Лучший случай (Time) | Средний случай (Time) | Худший случай (Time) | Память (Space) | | :--- | :--- | :--- | :--- | :--- | | Линейный поиск | | | | | | Бинарный поиск | | | | | | Bubble Sort | (если уже отсортирован) | | | | | Merge Sort | | | | | | Quick Sort | | | | |

Примечание: Quick Sort (Быстрая сортировка) — еще один популярный алгоритм. В среднем он работает так же быстро, как Merge Sort, и требует меньше памяти, но в худшем случае (неудачный выбор опорного элемента) может деградировать до .

Почему это важно на практике?

Вы можете сказать: «В Python есть встроенная функция .sort(), зачем мне знать про пузырьки и слияния?»

Понимание «под капотом»: Встроенная сортировка Python (Timsort) — это гибрид Merge Sort и Insertion Sort. Зная их плюсы и минусы, вы понимаете, почему она работает эффективно на реальных данных.

Выбор инструмента: Если вы знаете, что ваш массив почти отсортирован, простой алгоритм вставки ( в лучшем случае) может обогнать мощный Quick Sort.

Собеседования: Вопросы про сложность сортировок — это фильтр, отсеивающий кандидатов, не понимающих основ Computer Science.

Заключение

Сегодня мы увидели, как абстрактные формулы Big O обретают смысл в реальном коде. Мы выяснили, что: * Бинарный поиск превращает перебор миллиарда элементов в 30 шагов. * Вложенные циклы (как в Bubble Sort) — зло для больших данных. * Разделяй и властвуй (как в Merge Sort) — ключ к созданию быстрых алгоритмов класса .

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