Сложность алгоритмов

Привет! Сегодняшняя лекция будет немного отличаться от остальных. Отличаться она будет тем, что имеет лишь косвенное отношение к Java. Если коротко: сложность алгоритма это не количество секунд, а то, насколько быстро растет число действий при росте объема данных. Записывают ее в виде Big-O. O(1) означает, что время не зависит от объема данных вообще, O(N) что оно растет пропорционально объему, а O(log n) что растет очень медленно, потому что каждый шаг отбрасывает половину оставшихся вариантов. Дальше разберем все три и на бытовых примерах, и на коде.

Кратко

• Сложность алгоритма это не время в секундах, а зависимость числа действий от объема входных данных.
• Записывают ее через Big-O, и скорость железа с шириной канала при этом сознательно игнорируют: оценивается сам алгоритм.
• O(1), постоянная сложность: время не зависит от объема данных. Пример: вставка элемента в начало LinkedList.
• O(N), линейная: данных вдвое больше, значит и времени вдвое больше. Пример: вывод всех элементов массива в цикле.
• O(log n), логарифмическая: каждый шаг отбрасывает половину вариантов. Пример: двоичный поиск в отсортированном массиве.
• Разница видна на больших данных: в массиве из 10 000 элементов перебор делает 10 000 проверок, а двоичный поиск всего 14.

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

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

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

• Одетым
• Чистым
• Сытым

Какой алгоритм позволит тебе добиться этого результата?

1. Проснуться по будильнику.
2. Принять душ, умыться.
3. Приготовить завтрак, сварить кофе/заварить чай.
4. Поесть.
5. Если не погладил одежду с вечера, погладить.
6. Одеться.
7. Выйти из дома.

Эта последовательность действий точно позволит тебе получить необходимый результат. В программировании вся суть нашей работы заключается в постоянном решении задач. Значительную часть этих задач можно выполнить, используя уже известные алгоритмы. К примеру, перед тобой стоит задача: отсортировать список из 100 имен в массиве. Задача эта довольно проста, но решить ее можно разными способами. Вот один из вариантов решения: Алгоритм сортировки имен по алфавиту:

1. Купить или скачать в Интернете “Словарь русских личных имен” 1966 года издания.
2. Находить каждое имя из нашего списка в этом словаре.
3. Записывать на бумажку, на какой странице словаря находится имя.
4. Расставить имена по порядку, используя записи на бумажке.

Позволит ли такая последовательность действий решить нашу задачу? Да, вполне позволит. Будет ли это решение эффективным? Вряд ли.

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

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

Что такое Big-O

Для оценки сложности алгоритмов в программировании создали специальное обозначение под названием Big-O (“большая О”). Big-O позволяет оценить, насколько время выполнения алгоритма зависит от переданных в него данных.

Линейная сложность: O(N)

Давай рассмотрим самый простой пример, передачу данных. Представь, что тебе нужно передать некоторую информацию в виде файла на большое расстояние (например, 5000 километров). Какой алгоритм будет наиболее эффективным? Это зависит от тех данных, с которыми ему предстоит работать. К примеру, у нас есть аудиофайл размером 10 мегабайт. В этом случае, самым эффективным алгоритмом будет передать файл через Интернет. Это займет максимум пару минут! Итак, давай еще раз озвучим наш алгоритм: “Если требуется передать информацию в виде файлов на расстояние 5000 километров, нужно использовать передачу данных через Интернет”. Отлично. Теперь давай проанализируем его. Решает ли он нашу задачу? В общем-то да, вполне решает. А вот что можно сказать насчет его сложности? Хм, а вот тут уже все интереснее. Дело в том, что наш алгоритм очень сильно зависит от входящих данных, а именно от размера файлов. Сейчас у нас 10 мегабайт, и все в порядке. А что, если нам нужно будет передать 500 мегабайт? 20 гигабайт? 500 терабайт? 30 петабайт? Перестанет ли наш алгоритм работать? Нет, все эти объемы данных все равно можно передать. Станет ли он выполняться дольше? Да, станет! Теперь нам известна важная особенность нашего алгоритма: чем больше размер данных для передачи, тем дольше времени займет выполнение алгоритма. Но нам хотелось бы более точно понимать, как выглядит эта зависимость (между размером данных и временем на их передачу). В нашем случае сложность алгоритма будет линейной. “Линейная” означает, что при увеличении объема данных время на их передачу вырастет примерно пропорционально. Если данных станет в 2 раза больше, и времени на их передачу понадобится в 2 раза больше. Если данных станет больше в 10 раз, и время передачи увеличится в 10 раз. Используя обозначение Big-O, сложность нашего алгоритма определяется как O(N). Это обозначение лучше всего запомнить на будущее: оно всегда используется для алгоритмов с линейной сложностью. Обрати внимание: мы вообще не говорим здесь о разных “переменных” вещах: скорости интернета, мощности нашего компьютера и так далее. При оценке сложности алгоритма в этом просто нет смысла: мы в любом случае не можем это контролировать. Big-O оценивает именно сам алгоритм, независимо от “окружающей среды”, в которой ему придется работать.

Постоянная сложность: O(1)

Продолжим работать с нашим примером. Допустим, в итоге выяснилось, что размер файлов для передачи составляет 800 терабайт. Если мы будем передавать их через Интернет, задача, конечно, будет решена. Есть только одна проблема: передача по стандартному современному каналу (со скоростью 100 мегабит в секунду), который используется дома у большинства из нас, займет примерно 708 дней. Почти 2 года! :O Так, наш алгоритм тут явно не подходит. Нужно какое-то другое решение! Неожиданно на помощь к нам приходит IT-гигант, компания Amazon! Ее сервис Amazon Snowmobile позволял загрузить большой объем данных в передвижные хранилища и доставить по нужному адресу на грузовике. Сам сервис Amazon закрыл в 2024 году, решив, что появились способы подешевле, но как иллюстрация постоянной сложности этот грузовик по-прежнему безупречен. Итак, у нас есть новый алгоритм! “Если требуется передать информацию в виде файлов на расстояние 5000 километров и этот процесс займет больше 14 дней при передаче через Интернет, нужно использовать перевозку данных на грузовике Amazon”. Цифра 14 дней здесь выбрана случайно: допустим, это максимальный срок, который мы можем себе позволить. Давай проанализируем наш алгоритм. Что насчет скорости? Даже если грузовик поедет со скоростью всего 50 км/ч, он преодолеет 5000 километров всего за 100 часов. Это чуть больше четырех дней! Это намного лучше, чем вариант с передачей по интернету. А что со сложностью этого алгоритма? Будет ли она тоже линейной, O(N)? Нет, не будет. Ведь грузовику без разницы, как сильно ты его нагрузишь, он все равно поедет примерно с одной и той же скоростью и приедет в срок. Будет ли у нас 800 терабайт, или в 10 раз больше данных, грузовик все равно доедет до места за 5 дней. Иными словами, у алгоритма доставки данных через грузовик постоянная сложность. “Постоянная” означает, что она не зависит от передаваемых в алгоритм данных. Положи в грузовик флешку на 1Гб, он доедет за 5 дней. Положи туда диски с 800 терабайтами данных, он доедет за 5 дней. При использовании Big-O постоянная сложность обозначается как O(1).

Те же примеры, но в коде

Раз уж мы познакомились с O(N) и O(1), давай теперь рассмотрим более “программистские” примеры :) Допустим, тебе дан массив из 100 чисел, и задача: вывести в консоль каждое из них. Ты пишешь обычный цикл for, который выполняет эту задачу

int[] numbers = new int[100];
// ..заполняем массив числами

for (int i: numbers) {
   System.out.println(i);
}

Какая сложность у написанного алгоритма? Линейная, O(N). Число действий, которые должна совершить программа, зависит от того, сколько именно чисел в нее передали. Если в массиве будет 100 чисел, действий (выводов на экран) будет 100. Если чисел в массиве будет 10000, нужно будет совершить 10000 действий. Можно ли улучшить наш алгоритм? Нет. Нам в любом случае придется совершить N проходов по массиву и выполнить N выводов в консоль. Рассмотрим другой пример.

public static void main(String[] args) {

   LinkedList<Integer> numbers = new LinkedList<>();
   numbers.add(0, 20202);
   numbers.add(0, 123);
   numbers.add(0, 8283);
}

У нас есть пустой LinkedList, в который мы вставляем несколько чисел. Нам нужно оценить сложность алгоритма вставки одного числа в LinkedList в нашем примере, и как она зависит от числа элементов, находящихся в списке. Ответом будет O(1), постоянная сложность. Почему? Обрати внимание: каждый раз мы вставляем число в начало списка. К тому же, как ты помнишь, при вставке числа в LinkedList элементы никуда не сдвигаются, происходит переопределение ссылок (если вдруг забыл, как работает LinkedList, загляни в одну из наших старых лекций). Если сейчас первое число в нашем списке это число x, а мы вставляем в начало списка число y, все, что для этого нужно:

x.previous = y;
y.previous = null;
y.next = x;

Для этого переопределения ссылок нам неважно, сколько чисел сейчас в LinkedList: хоть одно, хоть миллиард. Сложность алгоритма будет постоянной: O(1).

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

Без паники! :) Если при слове “логарифмический” тебе захотелось закрыть лекцию и не читать дальше - подожди пару минут. Никаких математических сложностей здесь не будет (таких объяснений полно и в других местах), а все примеры разберем “на пальцах”. Представь, что тебе нужно найти одно конкретное число в массиве из 100 чисел. Точнее, проверить, есть ли оно там вообще. Как только нужное число найдено, поиск нужно прекратить, а в консоль вывести запись “Нужное число обнаружено! Его индекс в массиве = ....” Как бы ты решил такую задачу? Здесь решение очевидно: нужно перебрать элементы массива по очереди начиная с первого (или с последнего) и проверять, совпадает ли текущее число с искомым. Соответственно, количество действий прямо зависит от числа элементов в массиве. Если у нас 100 чисел, значит, нам нужно 100 раз перейти к следующему элементу и 100 раз проверить число на совпадение. Если чисел будет 1000, значит и шагов-проверок будет 1000. Это очевидно линейная сложность, O(N). А теперь мы добавим в наш пример одно уточнение: массив, в котором тебе нужно найти число, отсортирован по возрастанию. Меняет ли это что-то для нашей задачи? Мы по-прежнему можем искать нужное число перебором. Но вместо этого мы можем использовать известный алгоритм двоичного поиска. В верхнем ряду на изображении мы видим отсортированный массив. В нем нам необходимо найти число 23. Вместо того, чтобы перебирать числа, мы просто делим массив на 2 части и проверяем среднее число в массиве. Находим число, которое располагается в ячейке 4 и проверяем его (второй ряд на картинке). Это число равно 16, а мы ищем 23. Текущее число меньше. Что это означает? Что все предыдущие числа (которые расположены до числа 16) можно не проверять: они точно будут меньше того, которое мы ищем, ведь наш массив отсортирован! Продолжим поиск среди оставшихся 5 элементов. Обрати внимание: мы сделали всего одну проверку, но уже отмели половину возможных вариантов. У нас осталось всего 5 элементов. Мы повторим наш шаг: снова разделим оставшийся массив на 2 и снова возьмем средний элемент (строка 3 на рисунке). Это число 56, и оно больше того, которое мы ищем. Что это означает? Что мы отметаем еще 3 варианта: само число 56, и два числа после него (они точно больше 23, ведь массив отсортирован). У нас осталось всего 2 числа для проверки (последний ряд на рисунке): числа с индексами массива 5 и 6. Проверяем первое из них, и это то, что мы искали: число 23! Его индекс = 5! Давай рассмотрим результаты работы нашего алгоритма, а потом разберемся с его сложностью. (Кстати, теперь ты понимаешь, почему его называют двоичным: его суть заключается в постоянном делении данных на 2). Результат впечатляет! Если бы мы искали нужное число линейным поиском, нам понадобилось бы 10 проверок, а с двоичным поиском мы уложились в 3! В худшем случае их было бы 4, если бы на последнем шаге нужным нам числом оказалось второе, а не первое. А что с его сложностью? Это очень интересный момент :) Алгоритм двоичного поиска гораздо меньше зависит от числа элементов в массиве, чем алгоритм линейного поиска (то есть, простого перебора). При 10 элементах в массиве линейному поиску понадобится максимум 10 проверок, а двоичному максимум 4 проверки. Разница в 2,5 раза. Но для массива в 1000 элементов линейному поиску понадобится 1000 проверок, а двоичному всего 10! Разница уже в 100 раз! Обрати внимание: число элементов в массиве увеличилось в 100 раз (с 10 до 1000), а количество необходимых проверок для двоичного поиска увеличилось всего в 2,5 раза, с 4 до 10. Если мы дойдем до 10000 элементов, разница будет еще более впечатляющей: 10000 проверок для линейного поиска, и всего 14 проверок для двоичного. И снова: число элементов увеличилось в 1000 раз (с 10 до 10000), а число проверок увеличилось всего в 3,5 раза (с 4 до 14). Сложность алгоритма двоичного поиска логарифмическая, или, если использовать обозначения Big-O, O(log n). Почему она так называется? Логарифм это такая штуковина, обратная возведению в степень. Двоичный логарифм использует для подсчета степени числа 2. Вот, например, у нас есть 10000 элементов, которые нам надо перебрать двоичным поиском. Сейчас у тебя есть таблица перед глазами, и ты знаешь, что для этого нужно максимум 14 проверок. Но что если таблицы перед глазами не будет, а тебе нужно посчитать точное число необходимых проверок? Достаточно ответить на простой вопрос: в какую степень надо возвести число 2, чтобы полученный результат был >= числу проверяемых элементов? Для 10000 это будет 14 степень. 2 в 13 степени это слишком мало (8192) А вот 2 в 14 степени = 16384, это число удовлетворяет нашему условию (оно >= числу элементов в массиве). Мы нашли логарифм: 14. Столько проверок нам и нужно! :)

Три вида сложности: сводка

Все, о чем шла речь выше, помещается в три строки:

Что почитать и где практиковаться

Алгоритмы и их сложность это тема слишком обширная, чтобы вместить ее в одну лекцию. Но знать ее очень важно: на многих собеседованиях ты получишь алгоритмические задачи. Для теории я могу порекомендовать тебе несколько книг. Начать можно с “Грокаем алгоритмы”: хотя примеры в книге написаны на Python, язык книги и примеры очень просты. Лучший вариант для новичка, к тому же она небольшая по объему. Из чтения посерьезней это книги Роберта Лафоре и Роберта Седжвика. Обе написаны на Java, что сделает изучение для тебя немного попроще. Ведь ты неплохо знаком с этим языком! :) Для учеников с хорошей математической подготовкой лучшим вариантом будет книга Томаса Кормена. Но одной теорией сыт не будешь! “Знать” != “уметь” Практиковать решения задач на алгоритмы можно на HackerRank и Leetcode. Задачки оттуда частенько используют даже на собеседованиях в Google и Facebook, так что скучно тебе точно не будет :) Для закрепления материала лекции, советую посмотреть отличное видео про Big-O на YouTube. Увидимся на следующих лекциях! :)

Вопросы и ответы

Что такое Big-O простыми словами?

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

Чем O(1) отличается от O(N)?

У O(1) время выполнения одинаково при любом объеме данных: сколько ни увеличивай вход, число действий не меняется. У O(N) оно растет вместе с данными пропорционально: вдвое больше элементов, вдвое больше работы. Вставка в начало LinkedList это O(1), перебор массива в цикле это O(N).

Почему в Big-O не учитывают скорость компьютера?

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

Что такое O(log n) и почему логарифм двоичный?

Логарифмическая сложность означает, что каждый шаг алгоритма отбрасывает половину оставшихся вариантов. Логарифм тут двоичный именно потому, что данные делятся надвое. Чтобы посчитать число шагов, достаточно спросить: в какую степень надо возвести 2, чтобы получилось не меньше числа элементов. Для 10 000 элементов это 14 степень, значит и проверок будет максимум 14.

Есть ли в Java готовый двоичный поиск?

Да, писать его вручную не нужно. В классе java.util.Arrays есть метод binarySearch() для массивов, а в java.util.Collections одноименный метод для списков. Оба возвращают индекс найденного элемента, а если элемента нет, отрицательное число. Одно условие обязательно: массив или список должны быть заранее отсортированы, иначе результат непредсказуем.

Какая сложность у основных операций ArrayList и LinkedList?

У ArrayList обращение по индексу это O(1), а вставка или удаление в начале это O(N): все элементы приходится сдвигать. У LinkedList наоборот: вставка и удаление по краям это O(1), а вот обращение по индексу это O(N), потому что до нужного узла надо дойти по ссылкам. Поиск значения через contains() в обоих случаях O(N).

Читайте также

• Реализация пузырьковой сортировки на Java
• Интерфейс List в Java и ArrayList
• Класс LinkedList в Java
• Топ 10 вопросов о коллекциях в Java