Большой О хэш-таблицы против.Двоичное дерево поиска

Question

Что займет больше времени?

распечатайте все элементы, хранящиеся в бинарном дереве поиска, в отсортированном порядке или распечатайте все элементы, хранящиеся в хеш-таблице, в отсортированном порядке.

Распечатка элементов хеш-таблицы в отсортированном порядке займет больше времени, потому что хеш-таблица никогда не сортируется правильно?а БСТ есть?

Answer 1

Ты прав.Хэш-таблицы сортируются по некоторой хэш-функции, а не по их естественному порядку сортировки, поэтому вам придется извлечь все записи O(N) и отсортировать их O(NlogN), тогда как вы можете перемещаться по двоичному дереву поиска в естественном порядке за O( Н).

Однако обратите внимание, что в Java, например, есть LinkedHashSet и LinkedHashMap, которые дают вам некоторые преимущества Hash, но которые можно просматривать в том порядке, в котором они были добавлены, поэтому вы можете сортировать их и иметь возможность перемещаться по ним в этом порядке. отсортированный порядок, а также извлечение элементов по хешу.

Answer 2

Правильно, хеш-таблица не «сортируется» так, как вам, вероятно, хотелось бы.Элементы в хеш-таблицах обычно не совсем полностью отсортированы, хотя их расположение часто является своего рода близостью к сортировке.Но они упорядочены по хеш-функции, которая обычно сильно различается для похожих фраз.Это не сортировка по каким-либо показателям, которые мог бы использовать человек.

Если главное, что вы делаете со своей коллекцией, — это распечатываете ее в отсортированном порядке, лучше всего использовать какой-нибудь тип BST.

Answer 3

Двоичное дерево поиска хранится таким образом, что если вы выполняете обход в глубину, вы найдете элементы в отсортированном порядке (при условии, что у вас есть последовательная функция сравнения).Большое «О» простого возврата элементов, уже находящихся в дереве, будет большим «О» обхода дерева.

Вы правы насчет хеш-таблиц, они не сортируются.Фактически, чтобы перечислить все в простой хеш-таблице, вам нужно проверить каждую корзину, чтобы увидеть, что там находится, вытащить это, а затем отсортировать то, что вы получаете.Много работы, чтобы получить из этого отсортированный список.

Answer 4

Правильно, печать отсортированных данных, хранящихся в хеш-таблице, будет медленнее, поскольку хеш-таблица не является отсортированными данными.Это просто дает вам быстрый способ найти конкретный предмет.В "Обозначение Big OГоворят, что предмет можно найти за постоянное время, т.е.O(1) время.

С другой стороны, вы можете найти элемент в двоичном дереве поиска за «логарифмическое время» (O(log n)), поскольку данные для вас уже отсортированы.

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

Наслаждаться,

Роберт С.Картаино

Answer 5

Это поднимает пару интересных вопросов.Является ли дерево поиска еще быстрее, учитывая следующее?

1. Учет времени установки как для хэш-таблицы, так и для BST?
2. Если алгоритм хеширования создает отсортированный список слов.Технически вы можете создать хеш-таблицу, использующую соответствующий алгоритм.В этом случае скорость BST по сравнению с хеш-таблицей должна будет сводиться к количеству времени, необходимому для заполнения хеш-таблицы в отсортированном порядке.

Answer 6

Также ознакомьтесь с соответствующими соображениями относительно Skip List vs.Двоичное дерево: Пропустить список против.Двоичное дерево