Серия «Алгоритмы и структуры данных»

Пример задачи бинарного поиска

Начнем с примера задачи бинарного поиска. Допустим, вам нужно отыскать фамилию в телефонном справочнике, который начинается на букву “К”. Вместо того чтобы листать с начала, вы быстрее найдёте нужную страницу, открыв справочник посередине, так как “К” вероятно будет ближе к центру. Такой же подход удобен при поиске слова на букву “О” в словаре - начинать стоит с середины. Бинарный поиск — это универсальный алгоритм, применимый для решения многих задач поиска. Он работает с предварительно отсортированным массивом элементов. Если искомый элемент содержится в массиве, бинарный поиск указывает его позицию. В случае отсутствия элемента алгоритм возвращает значение null. В дальнейшем я объясню, почему важна сортировка массива перед началом поиска.

Как работает метод бинарного поиска

Давайте рассмотрим, как работает метод бинарного поиска на примере игры. Представьте, что я загадал число от 1 до 100, и ваша задача — угадать его, используя минимальное количество попыток. После каждой вашей догадки я буду отвечать: “слишком мало”, “слишком много” или “верно”. Если начать угадывать последовательно, начиная с 1, это будет неэффективно. Например, если я загадал число 99, вам потребуется 99 попыток, чтобы добраться до него. Теперь представим более эффективный метод — бинарный поиск. Начнем с середины диапазона, то есть с 50. Если я скажу, что это “слишком мало”, вы тут же исключите все числа от 1 до 50. Затем попробуйте число 75. Если я скажу “слишком много”, вы исключите числа от 76 до 100. Таким образом, каждый раз вы сокращаете количество возможных вариантов вдвое. Следующая попытка будет 63, что находится посередине между 50 и 75.

Бинарный поиск эффективен, потому что с каждой попыткой вы исключаете половину оставшихся чисел. Независимо от того, какое число я загадал, вы сможете угадать его за 7 или меньше попыток. Это показывает мощь алгоритмов и как они могут упростить решение задач. В среднем, бинарный поиск в списке из ( n ) элементов находит элемент за (log2n) шагов, в то время как линейный поиск потребует в среднем ( n ) шагов. Это делает бинарный поиск значительно быстрее, особенно для больших списков.

Реализация бинарного поиска на псевдокоде

Объяснение

• Устанавливаем начальные границы поиска: Начало и Конец.

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

• Находим индекс Середина как среднее между Начало и Конец.

• Сравниваем элемент в середине с искомым элементом:

  • Если они равны, возвращаем индекс Середина.

  • Если элемент в середине меньше искомого, сдвигаем начальную границу за середину.

  • Если элемент в середине больше искомого, сдвигаем конечную границу перед середину.

• Если элемент не найден, возвращаем -1.

Реализация алгоритма бинарного поиска на c++

Анализ эффективности алгоритмов

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

Бинарный поиск

Давайте рассмотрим бинарный поиск. Какое преимущество он предоставляет с точки зрения времени? В классическом подходе мы проверяем каждый элемент последовательно. Если у нас есть список из 100 элементов, нам может потребоваться до 100 проверок. В случае списка из 4 миллиардов элементов, число попыток может достигнуть 4 миллиардов. Время выполнения в таком случае растет пропорционально размеру списка, что является примером линейного времени выполнения.

С бинарным поиском ситуация иная. В списке из 100 элементов потребуется всего лишь 7 проверок. А для списка из 4 миллиардов элементов — не более 32 проверок. Довольно впечатляюще, не правда ли? Бинарный поиск работает за логарифмическое время, что делает его значительно более эффективным.

“Большое О”

“Большое О” - это специальная нотация, которая описывает скорость выполнения алгоритма. Это полезно знать, потому что время от времени вам может потребоваться использовать алгоритмы, разработанные другими людьми, и важно понимать, насколько быстро или медленно они работают.

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

Это один из примеров того, как время выполнения двух алгоритмов увеличивается с разной скоростью. Анна пытается выбрать между сортировкой пузырьком и быстрой сортировкой. Ее алгоритм должен работать быстро и правильно. С одной стороны, быстрая сортировка работает быстрее. У Анны есть всего 10 секунд, чтобы отсортировать данные; если она не успеет это сделать, то пользователь может уйти. С другой стороны, сортировка пузырьком проще в написании и вероятность ошибок в нем ниже. Конечно, Анна не хочет допустить ошибку в коде сортировки данных. И тогда, для большей уверенности, Анна решает измерить время выполнения обоих алгоритмов для списка из 100 элементов.

Предположим, проверка одного элемента занимает 1 миллисекунду (мс). При сортировке пузырьком Анне придется проверить 100 элементов, поэтому сортировка займет 100 мс. С другой стороны, при быстрой сортировке достаточно проверить всего 7 элементов (log⁡2100log2100 равно примерно 7), и сортировка займет 7 мс. Но реальный список может содержать более миллиарда элементов. Сколько времени в таком случае потребуется для выполнения сортировки пузырьком? А при быстрой сортировке?

Анна проводит быструю сортировку с 1 миллиардом элементов, и на это уходит 30 мс (log⁡21,000,000,000log21,000,000,000 равно примерно 30). “32 мс! - думает Анна. - Быстрая сортировка в 15 раз быстрее сортировки пузырьком, потому что сортировка пузырьком для 100 элементов заняла 100 мс, а быстрая сортировка заняла 7 мс. Значит, сортировка пузырьком займет 30 х 15 = 450 мс, верно? Гораздо меньше отведенных 10 секунд”. И Анна выбирает сортировку пузырьком. Верен ли ее выбор?

Нет, Анна ошибается. Глубоко ошибается. Время выполнения для сортировки пузырьком с 1 миллиардом элементов составит 1 миллиард миллисекунд, а это 11 дней! Проблема в том, что время выполнения для быстрой сортировки и сортировки пузырьком увеличивается с разной скоростью.

“Большое О” описывает, насколько быстро работает алгоритм. Предположим, имеется список размера n. Сортировка пузырьком должна проверить каждый элемент, поэтому ей придется выполнить n операций. Время выполнения “Большое О” имеет вид O(n).

А теперь другой пример. Для проверки списка размером n быстрой сортировке потребуется log⁡logn операций. Как будет выглядеть “Большое О”? O(log⁡logn).

В общем случае “Большое О” выглядет так: O(f(n)), где f(n) - это количество операций, которые придется выполнить алгоритму. Оно называется “Большое О”, потому что перед количеством операций ставится символ “О” (а большое - потому что в верхнем регистре).

Примеры “Большого О”

Вот пять типичных примеров “О-большого”, которые часто встречаются в алгоритмах и структурах данных. Они представлены в порядке от самого быстрого к самому медленному:

• O(log⁡logn), или логарифмическое время. Это время, которое обычно требуется для выполнения бинарного поиска.

• O(n), или линейное время. Это время, которое обычно требуется для выполнения простого поиска.

• O(n log⁡logn). Это время, которое обычно требуется для выполнения эффективных алгоритмов сортировки, таких как быстрая сортировка.

• O(2n2). Это время, которое обычно требуется для выполнения медленных алгоритмов сортировки, таких как сортировка выбором.

• O(n!). Это время, которое обычно требуется для выполнения очень медленных алгоритмов, таких как решение задачи о коммивояжере.

Эффективность алгоритмов определяется не по времени выполнения в секундах

Алгоритмы с временем выполнения O(log n) работают быстрее, чем алгоритмы с временем выполнения O(n). И чем больше размер списка, по которому производится поиск, тем заметнее становится эта разница.

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

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

Реализация алгоритмов

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

Рекомендации по чтению

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

• “Алгоритмы: построение и анализ” - Томас Х. Кормен, Чарльз Э. Лейзерсон, Рональд Л. Ривест и Клиффорд Штайн. Это классический учебник, который подробно описывает большинство важных алгоритмов.

• “Алгоритмы на Python” - Майкл Т. Гудрич, Роберто Тамассиа и Майкл Голдвассер. Эта книга объясняет алгоритмы на языке Python, что может быть полезно для тех, кто хочет изучать алгоритмы на конкретном языке программирования.

• “Структуры данных и алгоритмы в Java” - Майкл Т. Гудрич и Роберто Тамассиа. Это еще одна отличная книга для изучения алгоритмов, особенно если вы предпочитаете Java.

• “Алгоритмы + структуры данных = программы” - Никлаус Вирт. Это классическая книга, которая объясняет, как алгоритмы и структуры данных работают вместе, чтобы создать эффективные программы.

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

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

В псевдокоде используется:

1. Выражения: Используйте арифметические операции, чтобы вычислить значения.

2. Объявления метода: Определите функции или методы для выполнения конкретных задач.

3. Структура принятия решений: Используйте условные операторы (if-else) для выбора разных путей в зависимости от условий.

4. Циклы: Используйте циклы (например, for или while) для повторения действий.

5. Индексирование массива: Обращайтесь к элементам массива по индексу.

6. Обращения к методам: Вызывайте методы объектов для выполнения определенных действий.

7. Возвращаемое значение метода: Убедитесь, что ваши методы возвращают нужные значения.

Давайте подробнее разберемся с алгоритмом нахождения наибольшего общего делителя (НОД) для двух натуральных чисел N и M.

1. Инициализация: Пусть P будет минимальным из чисел N и M. Это позволяет сократить диапазон поиска общих делителей.

2. Инициализация t: Устанавливаем t равным 1. Начальное значение НОД.

3. Проверка P: Если P равно 1, переходим к шагу 5. В противном случае переходим к шагу 4.

4. Поиск делителей:Задаем i последовательностью всех целых чисел от 2 до P.

5. По возрастанию проверяем каждое i:Если M делится на i без остатка (M % i == 0) и N делится на i без остатка (N % i == 0), то обновляем t: t = i. Это означает, что i является общим делителем для N и M.

6. Завершение алгоритма: Результатом НОД будет значение t.

Пример: Пусть N = 12 и M = 18.

• P = min(12, 18) = 12.

• t = 1 (начальное значение).

• Проверяем i от 2 до 12:i = 2: 12 % 2 == 0 и 18 % 2 == 0, обновляем t: t = 2.

• i = 3: 12 % 3 == 0 и 18 % 3 == 0, обновляем t: t = 3.

• i = 4: 12 % 4 == 0 и 18 % 4 != 0 (не делится на 4).

• …

• i = 12: 12 % 12 == 0 и 18 % 12 == 0, обновляем t: t = 12.

• НОД(12, 18) = 6 (так как 6 - наибольший общий делитель).

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