🔥 🚀 Важно для всех, кто работает с Java! 🔥
На JavaRocks ты найдешь уникальные туториалы, практические задачи и редкие книги, которых не найти в свободном доступе. Присоединяйся к нашему Telegram-каналу JavaRocks — стань частью профессионального сообщества!
Этот урок будет отличаться тем, что он лишь косвенно связан с Java. Сегодня мы поговорим об алгоритмах.
Алгоритм – это некая последовательность действий, которую необходимо выполнить для достижения желаемого результата.
Нам постоянно приходится решать задачи, и значительную их часть можно выполнить с помощью уже известных алгоритмов. Представим, что нам нужно отсортировать по алфавиту список из 100 слов. Это довольно простая задача, и её можно решить разными способами.
Например, один из алгоритмов действий – купить или загрузить толковый словарь, найти каждое в нем каждое нужное нам слово, выписать номер страницы, на котором оно расположено, и только потом по полученным номерам страницы расположить наши слова в нужном порядке. Задача будет решена, но эффективно ли?
Оценка сложности алгоритма
Для оценки сложности алгоритмов существует Big O нотация, она позволяет оценить, насколько время выполнения алгоритма зависит от размера входных данных.
Очевидно, что чем больше объём данных для отправки, тем больше времени потребуется для его работы, и если эти показатели увеличиваются пропорционально, то мы имеем дело с линейной зависимостью. В Big O нотации сложность такого алгоритма выражается как O(n).
Допустим, нам надо через Интернет отправить файл объемом 800 терабайт в место, находящееся за 8000 километров. При стандартной скорости передачи данных (100 мегабит в секунду) это займет более 700 дней, то есть почти два года!
Ранее существовал сервис Amazon Snowmobile, который предоставлял услугу транспортировки носителей информации на грузовике. Если грузовик будет ехать со скоростью 80 км/ч, он преодолеет расстояние в 8000 км за 100 часов, это чуть больше четырех дней. Разница существенная!
Сложность такого алгоритма не линейна: для грузовика не имеет значения, как сильно вы его загрузите. Его средняя скорость не будет зависеть от таких показателей.
Постоянная временная сложность O(1) означает, что время, необходимое алгоритму для выполнения операций, не зависит от размера входных данных. Перейдём к примерам.
Сравнение постоянной и линейной сложности
Предположим, вам дан массив из 100 чисел, и вам нужно вывести каждое из них на консоль.
Вы пишете цикл for, который выполняет эту задачу:
int[] numbers = new int[100];
// ...заполните массив числами
for (int i: numbers) {
System.out.println(i);
}Сложность этого алгоритма линейная, т.е. O(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, в который мы вставляем несколько чисел.
Алгоритмическая сложность здесь постоянная, то есть O(1). Мы вставляем каждое число в начало списка, при этом элементы никуда не перемещаются, а обновляются только ссылки.
Если первое число в нашем списке – x, и мы вставляем число y в начало списка, то все, что нам нужно сделать, это:
x.previous = y;
y.previous = null;
y.next = x;Когда мы обновляем ссылки, не имеет значения, сколько чисел уже есть в LinkedList, одно или миллиард.
Сложность алгоритма постоянна, то есть O(1).
Алгоритм бинарного поиска
Представьте, что ваша задача – найти одно конкретное число в массиве из 100 чисел. Точнее, проверить, есть оно там или нет. Как только нужное число будет найдено, поиск завершится, и в консоли появится следующее сообщение: “Искомое число найдено! Его индекс в массиве = ….”
Здесь решение очевидно: нужно перебирать элементы массива по одному, начиная с первого (или с последнего), и проверять, совпадает ли текущее число с искомым. Соответственно, количество действий напрямую зависит от количества элементов в массиве. Это линейная сложность, т.е. O(n).
Добавим условие: пусть массив, в котором нужно найти число, отсортирован по возрастанию. Конечно, можно топорно применить вышеизложенный алгоритм, но лучше использовать двоичный поиск.
В отсортированном массиве нужно найти число 23. Делим массив на 2 части и выясняем значение среднего. У нас 9 ячеек, значит, нужно обратиться к числу по индексу 4. Мы получим 16, а нам нужно 23. Это значит, что все числа до 16 нам проверять не нужно: они гарантированно меньше искомого, потому что наш массив отсортирован. Мы провели только одну операцию, и уже половину вариантов отсекли!
С оставшимися 5 элементами повторим предыдущий шаг. “Срединный” элемент равен 57, и это число больше искомого. Мы исключаем ещё 3 варианта – само число 56 и два элемента после него.
Остаётся проверить только 2 числа по индексам 5 и 6. Проверив первое, сразу же обнаруживаем искомый элемент. Итак, индекс числа 23 равен 5.
Такой поиск называется бинарным, потому что основан на многократном делении данных пополам. Если бы мы использовали линейный поиск для поиска числа, нам потребовалось бы до 10 сравнений, но с помощью двоичного поиска мы справились с задачей всего за 3!
При двоичном (бинарном) поиске наблюдается гораздо меньшая зависимость от количества элементов в массиве, чем при линейном поиске.
Логарифмическая сложность
При 10 элементах в массиве линейный поиск потребует максимум 10 сравнений, а бинарный – максимум 4, что в 2,5 раза меньше. Если у нас 1000 элементов, то линейный поиск потребует 1000 операций, а бинарный – только 10, что меньше уже в 100 раз.
Обратите внимание: количество элементов в массиве увеличилось в 100 раз (с 10 до 1000), но количество сравнений, необходимых для двоичного поиска, увеличилось всего в 2,5 раза (с 4 до 10).
Если рассмотрим поиск среди 10 000 элементов, разница будет еще более впечатляющей: 10 000 сравнений для линейного поиска и всего 14 сравнений для бинарного. И если количество элементов увеличивается в 1000 раз (с 10 до 10000), то количество сравнений возрастает всего в 3,5 раза (с 4 до 14).
Сложность алгоритма бинарного поиска является логарифмической, т.е. O(log n).
В наших интересах использовать алгоритм по основанию 2, чтобы найти то число, при возведении двойки в которое мы получим нужный результат. Ниже представлена таблица значений, в первой колонке – количество элементов списка, во второй – количество операций при линейном поиске, в последней – количество операций при поиске бинарном.
Если такой таблицы не окажется под рукой, можно произвести расчеты самостоятельно, задав вопрос: в какую степень нам нужно возвести двойку, чтобы результат был больше или равен количеству проверяемых элементов? Для 10 000 это 14-ая степень. Если возвести 2 в 13-ую степень, получившееся число (8192) окажется слишком маленьким. А 2 в 14-ой степени (= 16384) удовлетворяет нашему условию.
Полезные материалы
Можно начать с книги Адитьи Бхаргавы «Грокаем алгоритмы». В ней примеры представлены на Python, это лучший вариант для начинающих, потому что главы написаны простым языком.
Из более серьёзного чтения – «Структуры данных и алгоритмы в Java» Роберта Лафоре и «Алгоритмы на Java» Роберта Седжвика. Для математически подкованных читателей прекрасный вариант – книга Томаса Кормена «Алгоритмы: вводный курс»
Разумеется, теория бесполезна без практики: задачи можно найти на сайтах HackerRank и LeetCode.
Перевод статьи «Algorithmic complexity».