Адитья Бхаргава. Грокаем алгоритмы. Конспект книги с примерами реализации алгоритмов на java script.
Алгоритм на входе получает отсортированный список элементов. Возвращает позицию искомого элемента или null.
Пример: игра "угадай число". Загадано число от 1 до 100. При каждой попытке возвращается ответ: "мало", "много" или "угадал". Плохой способ – перебирать все числа подряд. При самом отрицательном сценарии потребуется 100 попыток. Эффективный способ – начнем с 50. Если мало, то пробуем 75. Если много, то 63 и тд, каждый раз исключая половину оставшихся возможных вариантов. Какое бы число не было задумано, его можно угадать не более чем за 7 попыток.
При простом поиске из 240 000 вариантов может потребоваться 240 000 попыток. При бинарном - максимум 18. Для списка из n элементов простой поиск занимает n шагов, бинарный log2n шагов.
Логарифм по смыслу противоположен возведению в степень. Логарифм по основанию 10 от 100 означает в какую степень нужно возвести 10, чтобы получить 100. Ответ 10
В нотации "О большое"(об этом позже), log всегда означает 2. Для списка из 8 элементов log8 == 3, тк 2^3 === 8.
Бинарный поиск работает только с отсортированным списком.
Скорость измеряется не временем, а ростом кол-ва операций.
Если максимальное к-во попыток совпадает с размером списка, при простом поиске, время выполнения - линейное время пыполнения.
При бинарном поиске - поиск выполняется за логарифмическое время.
Факториальное время - ужасный ужас - при очень длинном списке, поиск становится невероятно долгим. Наример, поиск кратчайшего расстояния для того, чтобы объехать n городов: 5 городов - 120 операций, 6 городов - 720, 7 городов - 5040.
линейное время - O(n) логарифмическое время - O(log n) факториальное время - O(n!)