Это займет больше времени?Big O of Hash Table против дерева двоичного поиска
распечатать все элементы, хранящиеся в двоичном дереве поиска в отсортированном порядке, или распечатать все элементы, хранящиеся в хеш-таблице в отсортированном порядке.
Для сортировки элементов хеш-таблицы в отсортированном порядке потребуется больше времени, потому что хеш-таблица никогда не сортируется правильно? и BST?
Вы правы. Hashtables сортируются по некоторой хэш-функции, а не по их естественному порядку сортировки, поэтому вам нужно будет извлечь все записи O (N) и отсортировать их O (NlogN), тогда как вы можете пересечь двоичное дерево поиска в естественном порядке в O (N).
Обратите внимание, что в Java, например, есть LinkedHashSet и LinkedHashMap, которые дают вам некоторые преимущества Hash, но которые могут быть пройдены в том порядке, в котором он был добавлен, чтобы вы могли сортировать его и иметь возможность перемещать его в этом отсортированном порядке, а также извлекать элементы хэшем.
Правильно, хэш-таблица не «сортируется» так, как вы, вероятно, хотите. Элементы в хэш-таблицах не совсем сортируются, как правило, хотя расположение часто бывает в окрестности сортировки. Но они упорядочены в соответствии с хеш-функцией, которая обычно дико отличается от аналогичных фраз. Это не какая-то метрика, которую человек использовал бы.
Если главное, что вы делаете с вашей коллекцией, это распечатать его в отсортированном порядке, вам лучше использовать какой-либо тип BST.
Двоичное дерево поиска хранится таким образом, что если вы выполните первый проход глубины, вы найдете элементы в отсортированном порядке (при условии, что у вас есть функция согласованного сравнения). Большой O просто возвращающих предметов, уже находящихся в дереве, будет Большой O, пересекающий дерево.
Вы верны в отношении хеш-таблиц, они не отсортированы. Фактически, чтобы перечислить все в простой хеш-таблице, вы должны проверить каждое ведро, чтобы увидеть, что там, вытащить его, а затем отсортировать, что вы получаете. Много работы, чтобы получить отсортированный список из этого.
Исправить, распечатать отсортированные данные, хранящиеся в хеш-таблице, будут медленнее, потому что хеш-таблица не сортирует данные. Это просто дает вам быстрый способ найти определенный предмет. В «Big O Notation» говорится, что элемент можно найти в постоянное время, то есть время O (1).
С другой стороны, вы можете найти элемент в двоичном дереве поиска в «логарифмическом времени» (O (log n)), поскольку данные уже были отсортированы для вас.
Итак, если вы хотите напечатать отсортированный список, вам гораздо лучше иметь данные, хранящиеся в отсортированном порядке (т. Е. Двоичное дерево).
Наслаждайтесь,
Роберт С. Cartaino
Это поднимает несколько интересных вопросов. Является ли дерево поиска еще быстрее, учитывая следующее?
Также проверьте связанные соображения Список Скип против бинарного дерева: Skip List vs. Binary Tree