algorithms-and-data-structures.md

1. Оглавление
2. Общее
   1. Алгоритмическая сложность
3. Структуры данных
   1. Общее про деревья
   2. Список
   3. Очередь
   4. Множество
   5. Map
   6. Хэш-таблица
   7. Стек
   8. Куча
   9. Двоичная куча
   10. Двоичное дерево поиска
   11. Префиксное дерево
   12. Графы
   13. Quadtree
   14. Красно-черное дерево
4. Алгоритмы сортировки
   1. Быстрая сортировка
   2. Сортировка вставками
   3. Сортировка выбором
   4. Сортировка пузырьком
5. Алгоритмы поиска
   1. Бинарный поиск
   2. Поиск в глубину
   3. Поиск в ширину
6. Алгоритмы кэширования
   1. LRU (least recently used)
   2. MRU (most recently used)

• Общее:
  • Алгоритмическая сложность: как определить сложность алгоритма
    • Константная O(1)
    • Логарифмическая О(log n)
    • Линейное O(n)
    • Линейно-логарифмическое (O(n log(n)))
    • Квадратическая (O(n²))
    • Если алгоритм имеет сложность _ тогда его эффективность _
      • (о малое) o(n) - < n
      • (О большое) O(n) - <= n
      • (Тета) Θ(n) - = n
      • (Омега большое) Ω(n) - >= n
      • (Омега малое) ω(n) - > n
• Структуры данных: https://proglib.io/p/data-structures
  • Общее про деревья:
    • Высота дерева -
  • Список:
  • Очередь:
  • Множество:
  • Map:
  • Хэш-таблица:
  • Стэк:
    • Стэк область память выделяемая в полном объеме, при создании процесса (программы). Работает в порядке LIFO (Last In, First Out).
  • Куча:
    • Для выделения память из кучи происходит обращение к ОС
  • Двоичная куча: Это двоичное дерево, обладающее дополнительными свойствами
    • Значение любого узла не меньше (или не больше), чем значения у его потомков.
    • Глубина всех узлов отличается не более, чем на 1 уровень.
    • Последний слой заполняется слева направо без пропусков.
  • Двоичное дерево поиска: Это двоичное дерево, обладающее дополнительными свойствами
    • У всех узлов левого поддерева узла Х, значения меньше, чем у узла Х.
    • У всех узлов правого поддерева узла Х, значения больше, чем у узла Х.
  • Префиксное дерево:
  • Графы:
  • Quadtree: #TODO
  • Красно-черное дерево: #TODO
• Алгоритмы сортировки:
  • Быстрая сортировка:
    • Выбрать из массива опорный элемент.
    • Взять два указателя, которые идут от начала и конца массива, до тех пор, пока не встретят элемент больше и меньше опорного.
    • Поменять элементы местами и продолжить следование, пока указатели не пересекутся.
    • При пересечении найдена позиция в массиве для опорного элемента.
    • Рекурсивно повторить алгоритм для правого и левого отрезка.
    • Алгоритмическая сложность - линейно-логарифмическое (O(n log(n))), в худшем случае квадратическая (O(n²)), при выборе опорным наименьший, либо наибольший элемент.
  • Сортировка вставками:
    • В начале работы алгоритма, отсортированная последовательность пуста.
    • Поэлементно считываем массив и вставляем на нужную позицию в отсортированную последовательность.
    • Алгоритмическая сложность - в среднем квадратичная, в лучшем случае линейная (При уже отсортированном массиве).
    • Алгоритм можно улучшить, добавив бинарный поиск в момент вставки в отсортированную последовательность.
  • Сортировка выбором:
    • Проходим по всему массиву и находим наименьший элемент.
    • Меняем его с первым элементом массива, повторяем для оставшихся элементов.
    • Алгоритмическая сложность - квадратичная.
  • Сортировка пузырьком:
    • Итеративно проходим по массиву и меняем "пары" значений, до тех пор, пока они не будут отсортированы.
    • Алгоритмическая сложность: квадратичная.
• Алгоритмы поиска:
  • Бинарный поиск: #TODO
  • Поиск в глубину: #TODO
  • Поиск в ширину: #TODO
• Алгоритмы кэширования:
  • LRU (least recently used): Вытеснение давно неиспользуемых элементов. Реализуется, как вариант, очередью с приоритетами, при добавлении элемента в заполненную очередь, из неё убирается самый старый элемент. В таком виде сложность логарифмическая.
  • MRU (most recently used): #TODO