Algorithms

Временная сложность измеряет, сколько времени потребуется алгоритму для завершения работы в зависимости от размера входных данных. Она выражается через количество базовых операций (например, сравнение, присваивание), которые выполняются алгоритмом. Временную сложность обычно записывают с использованием нотации O-большое (Big-O), которая описывает верхнюю границу времени выполнения алгоритма по мере увеличения размера входных данных. Временная сложность важна, потому что она помогает оценить, насколько быстро будет выполняться алгоритм на больших объемах данных.

Примеры временной сложности:

• O(1) — Константная сложность: время выполнения не зависит от размера входных данных.

• O(n) — Линейная сложность: время выполнения растет пропорционально размеру входных данных.

• O(n^2) — Квадратичная сложность: время выполнения растет пропорционально квадрату размера входных данных.

• O(log n) — Логарифмическая сложность: время выполнения растет пропорционально логарифму от размера входных данных.

Пространственная сложность измеряет, сколько памяти потребуется алгоритму для завершения работы в зависимости от размера входных данных. Она также выражается через нотацию O-большое и описывает верхнюю границу потребления памяти алгоритмом. Пространственная сложность включает память, используемую для хранения входных данных и дополнительную память, требуемую для выполнения алгоритма (например, для хранения временных переменных, рекурсивного стека и т.д.). Пространственная сложность важна, потому что она помогает оценить, сколько памяти потребуется алгоритму, что особенно критично в условиях ограниченных ресурсов.

Примеры пространственной сложности:

• O(1) — Константная сложность: алгоритм использует фиксированное количество памяти, независимо от размера входных данных.

• O(n) — Линейная сложность: память, используемая алгоритмом, растет пропорционально размеру входных данных.

О-нотация (Big O notation) — это способ описания асимптотической сложности алгоритмов, который показывает, как время выполнения или использование памяти алгоритма изменяется в зависимости от размера входных данных. Она позволяет оценить эффективность алгоритмов и сравнить их производительность.

• Анализ алгоритмов. О-нотация позволяет определить, насколько эффективно работает алгоритм и насколько он масштабируется с увеличением объема данных.

• Сравнение алгоритмов. Позволяет сравнить различные алгоритмы по их эффективности и выбрать наиболее подходящий для конкретной задачи.

• Проектирование. Помогает в разработке алгоритмов и структур данных, чтобы обеспечить их эффективность и производительность.

Концепции

• Асимптотическая сложность. О-нотация выражает поведение алгоритма при стремлении размера входных данных к бесконечности. Она помогает понять, как изменяется сложность алгоритма с увеличением объема данных.

• Пределы. О-нотация показывает верхнюю границу времени выполнения алгоритма, что позволяет гарантировать, что алгоритм не будет работать хуже определенного времени выполнения или использования памяти.

Классы

• O(1) — Константное время: Время выполнения алгоритма не зависит от размера входных данных. Например, доступ к элементу массива по индексу имеет сложность O(1).

• O(log n) — Логарифмическое время: Время выполнения алгоритма растет логарифмически по отношению к размеру входных данных. Примером является бинарный поиск в отсортированном массиве.

• O(n) — Линейное время: Время выполнения алгоритма растет пропорционально размеру входных данных. Например, перебор элементов массива имеет сложность O(n).

• O(n log n) — Линейно-логарифмическое время: Время выполнения алгоритма растет быстрее, чем линейное, но медленнее, чем квадратичное. Часто встречается в алгоритмах сортировки, таких как быстрая сортировка и сортировка слиянием.

• O(n^2) — Квадратичное время: Время выполнения алгоритма пропорционально квадрату размера входных данных. Примером является пузырьковая сортировка и некоторые алгоритмы поиска пар.

• O(2^n) — Экспоненциальное время: Время выполнения алгоритма растет экспоненциально с увеличением размера входных данных. Такие алгоритмы часто неэффективны для больших данных и могут быть использованы в задачах, где требуется полный перебор, например, в задачах коммивояжера.

• O(n!) — Факториальное время: Время выполнения алгоритма растет очень быстро по сравнению с размером входных данных. Это типично для задач, где требуется перебор всех возможных перестановок, например, в некоторых задачах комбинаторики.

Подразумевает нахождение баланса между временной и пространственной сложностью, так как улучшение одного показателя может ухудшить другой.

Массивы

Последовательный набор элементов одного типа, доступ к которым осуществляется по индексу. Хранение данных в фиксированном размере, часто используется для реализации других структур данных (например, стека или очереди).

Связанные списки

• Односвязные списки. Состоят из узлов, где каждый узел содержит данные и ссылку на следующий узел.

• Двусвязные списки. Узлы имеют ссылки как на следующий, так и на предыдущий узел.

• Кольцевые списки. Последний узел указывает на первый узел, образуя кольцо.

Стек

Структура данных, работающая по принципу LIFO (Last In, First Out), где последний добавленный элемент извлекается первым. Реализация функций отката, обратного обхода, алгоритмов рекурсии.

Очередь

Структура данных, работающая по принципу FIFO (First In, First Out), где первый добавленный элемент извлекается первым. Реализация задач планирования, обработки задач в порядке их поступления.

Дек (двусторонняя очередь)

Структура данных, которая позволяет добавлять и удалять элементы с обоих концов. Реализация алгоритмов, которые требуют двустороннего доступа к данным.

Хэш-таблица

Структура данных, использующая хэш-функцию для быстрой вставки, поиска и удаления элементов. Реализация ассоциативных массивов, кэшей, для эффективного поиска данных.

Дерево

Организация данных в иерархии, упорядоченный поиск, реализация кучи (heap).

Бинарное дерево поиска (BST)

Балансированные деревья (AVL, красно-черное, B-дерево)

Дерево B и B+

Графы

Моделирование сетевых структур, нахождение кратчайших путей, маршрутизация.

Матрица смежности

Список смежности

Куча

Специальное дерево, где значения узлов удовлетворяют определенному свойству (макс-куча или мин-куча). Реализация алгоритмов сортировки (сортировка кучей), приоритетных очередей.

Trie (Префиксное дерево)

Дерево, используемое для хранения строк, где общие префиксы представляют общие ветви. Поиск строк, автозаполнение, хранение словарей.

Или двоичный поиск. Эффективный алгоритм для поиска элемента в отсортированном массиве или списке. Принцип работы бинарного поиска заключается в том, что он делит отсортированный массив на две части и продолжает поиск только в той половине, где может находиться искомый элемент, исключая другую половину.

• Время работы бинарного поиска — O(log n), где n — количество элементов в массиве. Это намного быстрее, чем линейный поиск, который работает за O(n).

• Бинарный поиск можно применять только к отсортированным массивам или спискам.

• Благодаря своей эффективности, бинарный поиск часто используется для поиска в больших объемах данных.

Cтруктура данных, в которой каждый узел имеет не более двух дочерних узлов (левый и правый). Используются для решения различных задач, таких как оптимизация поиска и упорядочивание данных.

• Узел (Node). Каждый узел содержит данные (значение) и ссылки на два дочерних узла (левый и правый).

• Корень (Root). Самый верхний узел дерева, от которого начинается все дерево. У корня нет родительского узла.

• Листовой узел (Leaf Node). Узел, не имеющий дочерних узлов. Листовые узлы находятся в самом нижнем уровне дерева.

• Внутренний узел (Internal Node). Узел, который имеет хотя бы одного дочернего узла.

• Глубина (Depth). Расстояние от корня до узла. Глубина корня равна 0, глубина его детей — 1, и так далее.

• Высота (Height). Максимальная глубина среди всех узлов дерева. Высота листа равна 0, а высота дерева — максимальная глубина среди всех листовых узлов.

Виды бинарных деревьев

• Бинарное дерево поиска (Binary Search Tree, BST). В этом дереве для любого узла значение левого дочернего узла меньше значения узла, а значение правого дочернего узла больше. Это свойство упрощает поиск, вставку и удаление узлов.

      5
     / \
    3   8
   / \
  2   4

• Сбалансированное бинарное дерево. Например, AVL-дерево или красно-черное дерево, где поддерживается балансировка, чтобы обеспечить логарифмическое время поиска, вставки и удаления.

• Дерево отрезков (Segment Tree). Используется для эффективных запросов диапазона и обновлений. Например, для работы с диапазонами в массиве.

• Куча (Heap). Специальное бинарное дерево, которое удовлетворяет свойству кучи. В минимальной куче значение каждого узла меньше или равно значениям его дочерних узлов, а в максимальной куче — больше или равно.

Операции над бинарным деревом

• Вставка (Insertion). Добавление нового узла в дерево с сохранением его свойств. Например, в BST новый узел вставляется в соответствии с его значением, чтобы сохранить порядок.

• Поиск (Search). Поиск узла с определенным значением. В бинарном дереве поиска это делается по сравнению значений и перемещению по левому или правому поддереву.

• Удаление (Deletion). Удаление узла из дерева. Это может быть более сложным процессом, поскольку необходимо поддерживать свойства дерева после удаления узла.

• Обход (Traversal). Проход по всем узлам дерева.

Способы обхода бинарного дерева

• Прямой обход (Pre-order). Посещение корня, затем левого поддерева, затем правого поддерева.

• Средний обход (In-order). Посещение левого поддерева, корня, затем правого поддерева. Этот метод выводит узлы в отсортированном порядке для BST.

• Посредственный обход (Post-order). Посещение левого поддерева, правого поддерева, затем корня.

• Уровневый обход (Level-order). Посещение узлов по уровням от верхнего к нижнему.

Cбалансированное бинарное дерево поиска, которое обеспечивает эффективные операции поиска, вставки и удаления, сохраняя при этом сбалансированность. Это достигается за счет применения набора правил, которые управляют цветами узлов и структурой дерева. Глубина дерева всегда остается логарифмической по отношению к количеству узлов, что гарантирует эффективные операции.

Свойства красно-черного дерева

• Каждый узел — либо красный, либо черный.

• Корень дерева всегда черный.

• Все листья (пустые узлы) являются черными.

• Если узел красный, то оба его дочерних узла должны быть черными (то есть два красных узла не могут быть соседними).

• Для любого узла, все пути от этого узла до его потомков-листьев содержат одинаковое количество черных узлов.

Операции в красно-черном дереве

• Вставка (Insertion). При вставке нового узла в красно-черное дерево могут возникать нарушения правил. После вставки выполняется серия операций (повороты и перекраска), чтобы восстановить свойства дерева.

• Удаление (Deletion). Удаление узла также может нарушить свойства дерева. После удаления выполняются операции восстановления, включая повороты и перекраску узлов.

• Поиск (Search). Поиск выполняется как в обычном бинарном дереве поиска. В красно-черном дереве поиск эффективен благодаря поддерживаемой сбалансированности.

• Освежить в памяти курс алгоритмов и структур данных (вспомнить основные структуры данных, их сильные и слабые стороны, особенности, базовые алгоритмы типа сортировок и обходов графов; не нужно ботать доказательство корректности, достаточно понимания как они работают).

• Порешать задачки на литкоде, потренироваться доводить задачи до конца (чтобы решение проходило все тесты). Обязательно набить руку на easy (аккуратность), желательно попробовать medium (комбинация простых алгоритмов/структур данных), hard смотреть не обязательно (хардкорные алгоритмы)

• При работе с массивом демонстрировать умение итерироваться по индексу, не выходя за его пределы.

• При работе с деревом демонстрировать умение рекурсивно обходить его, не входя в бесконечную рекурсию.

• Демонстрировать знание и практическое умение корректно работать с массивами, хеш-таблицами, бинарными деревьями.

• prefix sum: https://leetcode.com/tag/prefix-sum

• linked lists: https://leetcode.com/problems/merge-k-sorted-lists, https://leetcode.com/problems/linked-list-cycle, https://leetcode.com/problems/add-two-numbers, https://leetcode.com/problems/reverse-linked-list

• binary search: https://leetcode.com/problems/binary-search, https://leetcode.com/problems/guess-number-higher-or-lower, https://leetcode.com/problems/search-a-2d-matrix, https://leetcode.com/problems/search-in-rotated-sorted-array, https://leetcode.com/problems/find-minimum-in-rotated-sorted-array, https://leetcode.com/problems/search-in-rotated-sorted-array-ii

• hash table: https://leetcode.com/problems/single-number (решить за O(1) по памяти), https://leetcode.com/problems/two-sum, https://leetcode.com/problems/4sum, https://leetcode.com/problems/group-anagrams, https://leetcode.com/problems/valid-anagram, https://leetcode.com/problems/find-all-anagrams-in-a-string

• queue/stack: https://leetcode.com/problems/valid-parentheses

• dfs/bfs: https://leetcode.com/problems/number-of-islands, https://leetcode.com/problems/remove-invalid-parentheses

• sort: https://leetcode.com/problems/merge-intervals

• heap/hash: https://leetcode.com/problems/top-k-frequent-words, https://leetcode.com/problems/top-k-frequent-elements

• two pointers: https://leetcode.com/problems/container-with-most-water, https://leetcode.com/problems/partition-labels

• sliding window: https://leetcode.com/problems/sliding-window-median, https://leetcode.com/problems/sliding-window-maximum, https://leetcode.com/problems/longest-repeating-character-replacement

• tree: https://leetcode.com/problems/same-tree, https://leetcode.com/problems/symmetric-tree, https://leetcode.com/problems/balanced-binary-tree, https://leetcode.com/problems/path-sum-ii

• greedy problems: https://leetcode.com/problems/best-time-to-buy-and-sell-stock, https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii, https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee, https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown

1. Как определить временную и пространственную сложность алгоритма?

2. Объясни разницу между сортировкой пузырьком, вставками, слиянием и быстрой сортировкой. Каковы их временные сложности?

3. В чем разница между массивом и связным списком?

4. Какая средняя алгоритмическая сложность поиска значения в отсортированном массиве?

   O(log n) логарифмическая сложность

5. Какая средняя алгоритмическая сложность у быстрой сортировки?

   O(n log n) логарифмическая сложность