- Aditya Y. Bhargava. Grokking Algorithms / Адитья Бхаргава. Грокаем алгоритмы
http://adit.io/ https://www.manning.com/books/grokking-algorithms https://github.com/egonschiele/grokking_algorithms https://www.litres.ru/aditya-bhargava/grokaem-algoritmy-illustrirovannoe-posobie-dlya-p-39158380/?track=from_my_books_my
Алгоритм - набор инструкций для выполнения задачи. Линейный поиск (плохой или тупой) - перебор элементов от первого к последнему. Бинарный поиск - алгоритм поиска, получающий на входе отсортированный список элементов, возвращает позицию элемента либо null. Выполняется за log2n шагов для списка из n элементов. Log (Логарифм) - операция, обратная возведению в степень.
Время выполнения алгоритмов растёт с разной скоростью. О(n) - худший возможный случай. Примеры О-большого:
- O(log n) - логарифмическое время. Пример: бинарный поиск.
- O(n) - линейное время. Пример: простой поиск.
- O(n * log n). Пример: эффективные алгоритмы сортировки (быстрая сортировка).
- O(n2). Пример: медленные алгоритмы сортировки (сортировка выбором).
- O(n!). Пример: очень медленные алгоритмы. Скорость алгоритма измеряется в темпе роста количества операций.
Время выполнения O(log n) быстрее O(n), а с увеличением размера списка, в котором ищется значение, оно становится намного быстрее. Скорость алгоритмов не измеряется в секундах. Время выполнения алгоритма описывается ростом количества операций. Время выполнения алгоритмов выражается как «O-большое».
Структуры данных: массивы и связанные списки. Массив - данные хранятся непрерывно. Нумерация начинается с 0. Произвольный доступ. Недостатки: 1. Неэффективное расходование памяти. 2. Придётся перемещать, если необходимо добавить элементы. Плюсы: 1. Высокая скорость. Связанные списки - данные хранятся где угодно. Каждый элемент хранит адрес следующего. Последовательный доступ. Недостатки: 1. Для доступ к элементу необходимо перебрать предыдущие элементы. Плюсы: 1. Можно добавлять элементы без изменения размера. 2. Подходят для вставки элементов. Операция - Массивы - Списки чтение - O(1) / быстро - О(n) / медленно запись - O(n) / медленно - О(1) / быстро вставка - O(n) / медленно - О(1) / быстро запись - O(n) / медленно - О(1) / быстро Массив связанных списков. Каждый элемент содержит ссылку на связанный список. Если требуется сохранить набор элементов, воспользуйся массивом или списком. В массиве все элементы в памяти хранятся рядом. Массивы обеспечивают быстрое чтение. Все элементы массива должны быть однотипными. В списке все элементы разбросаны по памяти, в каждом элементе хранится адрес на следующий. Списки обеспечивают быструю вставку, выполнение, запись.
Циклы - могут ускорить работу программы, рекурсия - программиста. Рекурсия - функция вызывает саму себя. В рекурсивном методе обязательно наличие базового (условия прерывания) и рекурсивного случая. Стек вызовов поддерживает две операции: занесение и извлечение элементов. Все вызовы функций сохраняются в стеке вызовов. Если стек вызовов станет очень большим, он займет много памяти.
Быстрая сортировка. Стратегия "Разделяй и властвуй".
- Базовый случай.
- Задача делится и сокращается до тех пор, пока не будет сведена к базовому случаю. Базовый случай для массива состоит из 1 или 0 элементов. Индуктивное доказательство состоит из двух частей:
- Базовый случай.
- Индукционный переход. Для алгоритма быстрой сортировки выберите случайный элемент. Константы в O-большом иногда могут иметь значение. Поэтому быстрая сортировка быстрее сортировки слиянием. При сравнении простой сортировки с бинарной константа почти не играет роли, потому что O(log n) превосходит O(n) по скорости при большом размере списка.
Хеш-таблицы. Хеш-функция - получает строку и возвращает число.
- Последовательность. При каждом повторном запросе возвращает одинаковый результат.
- Разным строкам, соответствуют разные числа.
- Знает размер массива и возвращает действительные индексы. Хеш-таблицы.
- Используют массивы для хранения данных.
- Определяют место хранения элементов при помощи хеш-функций. Реализация в виде словарей (Dictionary).