Графы (часть 2)
Алгоритм Дейкстры позволяет нам найти кратчайший путь между любыми двумя вершинами графа.
Графы (часть 1)
Граф - это математическая абстракция реальной системы любой природы, объекты которой обладают парными связями. Граф, как математический объект, есть совокупность двух множеств. Множества вершин и множества ребер (парных связей/дуги).
Хеширование данных
Хэш таблица представляет собой эффективную структуру данных для реализации словарей. Хотя на поиск элемента в хэш таблице в наихудшем случае может потребоваться столько же времени что и в связанном списке О(n) на практике хеширование является намного эффективнее. Три вполне обоснованных допущениях математическое ожидания времени поиска элемента хэш таблицы составляют О(1).
АВЛ-деревья
АВЛ-дерево - это структура данных, придуманная в 1962 году советскими учеными. Это модификация классического бинарного дерева поиска, благодаря которой структура лучше сбалансирована и практически не может выродиться. Вырождение - это ситуация, когда у каждого узла оказывается только по одному потомку, и структура становится линейной (не оптимальной). Благодаря сбалансированности и почти невозможности вырождения дерева, информация хранится более эффективно, поэтому доступ к данным оказывается быстрее, и найти становится легче.
Деревья
Бинарные деревья поиска - это структура данных, которая позволяет хранить элементы в отсортированном порядке для эффективного поиска, вставки и удаления. Основные операции выполняются за время, пропорциональное глубине дерева. Для полного дерева с n узлами эти операции выполняются за O(logn). Бинарные деревья поиска также поддерживают запросы на поиск минимального и максимального элементов, предшествующего и последующего элементов.
Алгоритмы сортировки (часть 2)
Сортировка Шелла — это алгоритм сортировки, который улучшает классическую сортировку вставками. Он работает на принципе предварительного “разбиения” массива на подмассивы и сортировки элементов в этих подмассивах.