Адитья Бхаргава. Грокаем алгоритмы. Конспект книги с примерами реализации алгоритмов на 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!)
Память компьютера можно представить в виде огромного шкафа с множеством ящиков. У каждого ящика есть адрес. Когда требуется сохранить в памяти какое-то значение, мы запрашиваем у компьютера место в памяти, а он выдает адрес для сохранения значения. Если нужно сохранить несколько значений, есть 2 основных способа: массивы и связные списки.
При использовании массива, все задачи хранятся в памяти непрерывно, друг за другом. В списках каждый элемент хранит в себе ссылку на следующий. При этом элементы могут размещаться в памяти где угодно.
Получить запись быстрее можно из массива - обратиться по нужному адресу. При такой же операции со списком нужно пройти по всей цепочке. С записью - наоборот. Нужна всего одна операция для записи значения в список и n операций для записи в массив.
чтение из списка – O(n) запись в список – O(1) удаление из списка – O(1)
чтение из массива – O(1) запись в массив – O(n) удаление из массива – O(n)
Легкий для понимания алгоритм, но очень медленно работает – O(n^2); Каждый раз перебирается n элементов-1
Рекурсия - вызов функции самой себя. Состоит из двух частей: базового и рекурсивного случая. В базовом - условие выхода.
Под вызов каждой функции определяется блок в памяти для всех переменных. Блоки определяются в стек. Вызов ф-и из другой ф-и приостанавливает ее действие - частично завершенное состояние.
Работает быстрее сортировки выбором и часто применяется. Базовый случай - пустой массив или массив из одного элемента. O(n log n) – в среднем. В худшем случае – O(n^2); Зависит от опорного элемента.
Хэш-функция – функция, которая получает строку(набор байтов) и возвращает число. Хэш-таблицы – структура данных, связывающая ключи со значениями. O(1) – в среднем. Отлично подходят для хранения кэша.
Коллизия - ситуация, когда двум ключам назначается один элемент массива. Простейшее решение – связный список в этом элементе. Хорошая хэш-функция создает минимальное кол-во коллизий.
Граф моделирует набор связей. Каждый граф состоит из узлов и ребер.
Этот алгоритм отвечает на два вопроса: существует ли путь от одного узла к другому и какой путь кратчайший. Поиск производится сначала по связям первого уровня, потом второго урвня и тд. Связи, по которым нужно продолжать поиск добавляются в список и образуют очередь. Очередь относится к категории структур FIFO (First In, First Out).
Время выполнения – O(V+E) V – кол-во вершин, E – кол-во ребер;
Дерево - граф, в котором нет ребер, указывающих в обратном направлении
Если известна "стоимость" каждого ребра, граф – взвешенный. Для поиска кратчайшего пути во взвешенном(без отрицательных весов), направленном графе, используется алгоритм Дейкстры.
На каждом шаге алгоритма выбирается локальное оптимальное решение. В итоге получается глобально-оптимальное. Время выполнения – O(n^2)