Большой O хеш-таблицы по сравнению с деревом двоичного поиска
В соответствии с документацией ,
. Для переносимости приложение должно заполнять путь данных до максимально допустимого значения путем записи данных, пока метод write () не вернет короткий счетчик передачи. , Это позволяет немедленно начать play () и уменьшает вероятность опустошения.
blockquote>При строгом чтении это может показаться противоречащим предыдущему утверждению:
... вы можете при желании простить путь к данным до вызова play (), написав до
blockquote>bufferSizeInBytes...(выделено мной), но цель достаточно ясна: сначала вы должны получить короткую запись.
Это только для начала игры. Когда это произойдет, вы можете использовать
getPlaybackHeadPosition(), чтобы определить, когда доступно больше места. Я успешно использовал эту технику в своем собственном коде на многих различных устройствах / уровнях API.В качестве отступления: Вы должны быть готовы к тому, что
getPlaybackHeadPosition()изменится только большими шагами (если я правильно помню, этоgetMinBufferSize()/2). Это максимальное разрешение, доступное в системе;onMarkerReached()не может быть использован, чтобы сделать лучше.
6 ответов
Вы правы. Хеш-таблицы сортируются с помощью некоторой хеш-функции, а не по их естественному порядку сортировки, поэтому вам нужно будет извлечь все записи O (N) и отсортировать их O (NlogN), тогда как вы можете перемещаться по двоичному дереву поиска в естественном порядке в O ( N).
Однако обратите внимание, что в Java, например, есть LinkedHashSet и LinkedHashMap, которые дают вам некоторые преимущества Hash, но которые можно перемещать в том порядке, в котором они были добавлены, чтобы вы могли отсортировать их и может перемещаться по нему в этом отсортированном порядке, а также извлекать элементы по хешу.
Бинарное дерево поиска хранится таким образом, что, если вы сначала выполните обход в глубину, вы найдете элементы в отсортированном порядке (при условии, что у вас есть последовательная функция сравнения). Большой O для простого возврата элементов, уже находящихся в дереве, был бы Big O для обхода дерева.
Вы правы насчет хеш-таблиц, они не сортируются. Фактически, чтобы перечислить все в простой хеш-таблице, вы должны проверить каждую корзину, чтобы увидеть, что там есть, вытащить ее, а затем отсортировать то, что вы получите. Много работы, чтобы получить отсортированный список.
Верно, хеш-таблица не «отсортирована» так, как вы, вероятно, хотите. Элементы в хэш-таблицах, как правило, не совсем полностью отсортированы, хотя их расположение часто находится в некотором роде. Но они расположены в соответствии с хеш-функцией, которая обычно сильно различается для похожих фраз. Это не сортировка по какой-либо метрике, которую мог бы использовать человек.
Если главное, что вы делаете со своей коллекцией, - это распечатываете ее в отсортированном порядке, вам лучше использовать какой-нибудь тип BST.
Верно, печать отсортированных данных, хранящихся в хэш-таблице, будет медленнее, потому что хеш-таблица не содержит отсортированных данных. Это просто дает вам быстрый способ найти конкретный предмет. В « Big O Notation » сказано, что элемент может быть найден за постоянное время, то есть время O (1).
С другой стороны, вы можете найти элемент в двоичном дереве поиска в «логарифмическом времени» (O (log n)), потому что данные уже были отсортированы для вас.
Таким образом, если вы хотите распечатать отсортированный список, вам будет гораздо лучше, если данные будут храниться в отсортированном порядке ( то есть двоичное дерево).
Наслаждайтесь,
Роберт К. Картаино
Это вызывает несколько интересных вопросов. Является ли дерево поиска еще более быстрым, учитывая следующее?
- Включая время установки как для таблицы хеширования, так и для BST?
- Если алгоритм хеширования создает отсортированный список слов. Технически вы можете создать хеш-таблицу, которая использует алгоритм, который это делает. В этом случае скорость BST по сравнению с хеш-таблицей должна быть уменьшена до количества времени, необходимого для заполнения хеш-таблицы в отсортированном порядке.
Также ознакомьтесь со связанными соображениями по поводу списка пропуска и двоичного дерева: Список пропуска и двоичного дерева