Адитья Бхаргава - Грокаем алгоритмы
Иллюстрированное пособие для программистов и любопытствующихНазвание: | Грокаем алгоритмы | |
Автор: | Адитья Бхаргава | |
Жанр: | Современные российские издания, Литература ХXI века (эпоха Глобализации экономики), Алгоритмы и структуры данных, Python | |
Изадано в серии: | Библиотека программиста | |
Издательство: | Питер | |
Год издания: | 2022 | |
ISBN: | 978-5-4461-0923-4 | |
Отзывы: | Комментировать | |
Рейтинг: | ||
Поделись книгой с друзьями! Помощь сайту: донат на оплату сервера |
Краткое содержание книги "Грокаем алгоритмы"
Алгоритмы - это всего лишь пошаговые алгоритмы решения задач, и большинство таких задач уже были кем-то решены, протестированы и проверены. Можно, конечно, погрузится в глубокую философию гениального Кнута, изучить многостраничные фолианты с доказательствами и обоснованиями, но хотите ли вы тратить на это свое время? Откройте великолепно иллюстрированную книгу и вы сразу поймете, что алгоритмы - это просто. А грокать алгоритмы - это веселое и увлекательное занятие.
К этой книге применимы такие ключевые слова (теги) как: Искусство программирования, Обучение программированию, Просто о сложном, Эффективные алгоритмы
Читаем онлайн "Грокаем алгоритмы" (ознакомительный отрывок). [Страница - 5]
Так работает бинарный поиск. А вы только что узнали свой первый алгоритм! Попробуем поточнее определить, сколько чисел будет исключаться каждый раз.
При бинарном поиске каждый раз исключается половина чисел
Какое бы число я ни задумал, вы гарантированно сможете угадать его не более чем за 7 попыток, потому что с каждой попыткой исключается половина оставшихся чисел!
Предположим, вы ищете слово в словаре с 240 000 словами. Как вы думаете, сколько попыток вам понадобится в худшем случае?
При простом поиске может потребоваться 240 000 попыток, если искомое слово находится на самой последней позиции в книге. С каждым шагом бинарного поиска количество слов сокращается вдвое, пока не останется только одно слово.
Итак, бинарный поиск потребует 18 шагов — заметная разница! В общем случае для списка из n элементов бинарный поиск выполняется за log2n шагов, тогда как простой поиск будет выполнен за n шагов.
Логарифмы
Возможно, вы уже забыли, что такое логарифм, но наверняка помните, что такое возведение в степень. log10100 по сути означает, сколько раз нужно перемножить 10, чтобы получить 100. Правильный ответ — 2: 10 × 10. Итак, log10 100 = 2. Логарифм по смыслу противоположен возведению в степень.
Логарифм — операция, обратная возведению в степень
Когда я в этой книге упоминаю «O-большое» (об этом чуть позднее), log всегда означает log2. Когда вы ищете элемент с применением простого поиска, в худшем случае вам придется проверить каждый элемент. Итак, для списка из 8 чисел понадобится не больше 8 проверок. Для бинарного поиска в худшем случае потребуется не более logn проверок. Для списка из 8 элементов log 8 == 3, потому что 23 == 8. Итак, для списка из 8 чисел вам придется проверить не более 3 чисел. Для списка из 1024 элементов log 1024 = 10, потому что 210 == 1024. Следовательно, для списка из 1024 чисел придется проверить не более 10 чисел.
примечание
Бинарный поиск работает только в том случае, если список отсортирован. Например, имена в телефонной книге хранятся в алфавитном порядке, и вы можете воспользоваться бинарным поиском. А что произойдет, если имена не будут отсортированы?
Посмотрим, как написать реализацию бинарного поиска на Python. В следующем примере кода используется массив. Если вы не знаете, как работают массивы, не беспокойтесь: эта тема рассматривается в следующей главе. Пока достаточно знать, что серию элементов можно сохранить в непрерывной последовательности ячеек, которая называется массивом. Нумерация ячеек начинается с 0: первая ячейка находится в позиции с номером 0, вторая — в позиции с номером 1 и т.д.
Функция binary_search получает отсортированный массив и значение. Если значение присутствует в массиве, то функция возвращает его позицию. При этом мы должны следить за тем, в какой части массива проводится поиск. Вначале это весь массив:
low = 0
high = len(list) - 1
Каждый раз алгоритм проверяет средний элемент:
mid = (low + high) / 2 Если значение (low+high) нечетно, то Python автоматически округляет значение mid в меньшую сторону
guess = list[mid]
Если названное число было слишком мало, то переменная low обновляется соответственно:
if guess < item:
low = mid + 1
Книги схожие с «Грокаем алгоритмы» по жанру, серии, автору или названию:
Евгений Александрович Никулин - Компьютерная геометрия и алгоритмы машинной графики Жанр: Программирование графики Год издания: 2003 |
Сергей Тарасов - Дефрагментация мозга. Софтостроение изнутри Жанр: Программирование: прочее Год издания: 2013 Серия: Библиотека программиста |
Роберт Сесил Мартин - Чистая архитектура Жанр: Современные российские издания Год издания: 2018 Серия: Библиотека программиста |
Брэдфорд Такфилд - Алгоритмы неформально. Инструкция для начинающих питонистов Жанр: Алгоритмы и структуры данных Год издания: 2022 Серия: Библиотека программиста |
Другие книги из серии «Библиотека программиста»:
Роберт Сесил Мартин - Чистый код. Создание, анализ и рефакторинг Жанр: Программирование: прочее Год издания: 2019 Серия: Библиотека программиста |
Владстон Феррейра Фило - Теоретический минимум по Computer Science Жанр: Другие языки и системы программирования Год издания: 2018 Серия: Библиотека программиста |
Дэниел Г Грэм - Этичный хакинг практическое руководство по взлому Жанр: Хакерство Год издания: 2022 Серия: Библиотека программиста |
Михал Яворски, Тарек Зиаде - Python. Лучшие практики и инструменты Жанр: Python Год издания: 2021 Серия: Библиотека программиста |