Программист и Преподаватель
Словарь - это абстрактный тип данных, который связывает ключи со значениями. Его ещё называют ассоциативный массив, карта, таблица символов, коллекция. Будет две статьи на эту тему, где мы покажем шесть картинок / способов реализации словаря, которые отличаются друг от друга по времени работы и по требованию к памяти.
В предыдущей статье мы познакомились с терминами и определениями теории графов. В этой же статье обсудим различные способы представления графа в памяти компьютера для его обработки. Покажем, какие структуры данных можно использовать, а также проговорим преимущества и недостатки каждого способа.
В этой статье мы познакомимся с основными терминами и определениями Теории графов. Каждый термин схематично показан на картинках.
Граф - это топологичекая модель, которая состоит из множества вершин и множества соединяющих их рёбер. При этом значение имеет только сам факт, какая вершина с какой соединена.
Один из самых необычных алгоритмов сортировки массива - это HeapSort, в основе которого лежит алгоритм сортировки выбором, используется структура данных «куча» для быстрого нахождения максимального элемента, а также способ хранения двоичного дерева в линейном массиве. Разберёмся со всем по порядку.
Какова сложность поиска элемента по ключу?
Это зависит от того, какую структуру данных использовать.
В односвязном списке - линейная сложность.
В отсортированном массиве или в двоичном дереве поиска - логарифмическая сложность.
В хэш-таблице - сложность константная. Но это в лучшем случае. А в худшем … стремится к линейной…
А можно ли создать идеальную хэш-таблицу, чтобы сложность поиска элемента даже в худшем случае оставалась константной?
В общем случае - нет. Но если список всех ключей установлен заранее и не изменяется, а хэш-коды у всех ключей различны, то можно построить идеальную хэш-таблицу без коллизий, где поиск любого элемента происходит за несколько тривиальных операций, причём, количество этих операций не зависит от размера хэш-таблицы.
Идеально! Поговорим о том, как это сделать.
Кстати, на курсе "Алгоритмы и структуры данных" на платформе OTUS у нас есть отдельный модуль, посвящённый вопросам создания хэш-таблиц.
Использовано изображение портала cartoonbank.ru
Статья подготовлена в преддверии старта курса «Алгоритмы и структуры данных»
Алгоритм Джонсона находит кратчайший путь между всеми парами вершин во взвешенном ориентированном графе с отрицательными весами без негативных контуров.
О, как звучит! Давайте разберём условие задачи по частям.
