Использование словаря вместо сортировки, а затем поиск

Я изучал хэш-таблицы и пришла мысль:Использование словаря вместо сортировки, а затем поиск

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

Мы можем преобразовать список в словарь в O(n) (я думаю) время, потому что мы должны пройти через все элементы.
Мы добавляем все эти элементы в словарь, и это занимает O(1) время
Когда словарь будет готов, мы можем искать для любого элемента в O(1) времени (в среднем) и O(n) наихудший

сейчас если говорить о среднем случае O(n) лучше, чем другие алгоритмы сортировки, потому что в лучшем случае они принимают O(nlogn). И если я прав обо всем, что я сказал, то почему бы так не сделать?

Я знаю, что есть разные вещи, которые вы можете сделать с отсортированными элементами, которые нельзя сделать в несортированном словаре или массиве. Но если мы придерживаемся только поиска, то это не лучший способ выполнить поиск, чем другая сортировка алгоритмы?

источник

2016-04-28 john smith

Или мы просто перебираем несортированный список в O (n) для поиска элемента? – timgeb

@timgeb тогда, если вам нужно выполнить поиск n раз, тогда у вас есть сложность 'n * O (n)', и если вы сначала отсортируете, а затем выполните поиск n раз, это будет 'n * O (logn)'. И, согласно john теории вы можете выполнять поиск столько раз, сколько хотите в 'O (1)' время, которое намного лучше, чем то, что вы говорите –

@jamessmith да, но вы не упоминали, что хотите много раз искать. В этом случае преобразуйте список в набор (зачем вам нужен dict?) в O (n), то выполните любую последующую проверку герметичности в O (1). Сохранение отсортированного списка, которое вы можете делить пополам, полезно только тогда, когда вам нужен порядок и/или дублирующие элементы. – timgeb

Правильно, хорошо спроектированный хеш-стол может избивать сортировку и поиск.

Для правильного выбора, есть много факторов, входящих в игру, такие как в месте требование, динамизм набора данных, количество запросов против встройки/удалений, легкость построить эффективную функцию хэширования ...

источник

2016-04-28 09:48:35

Двоичного является методом поиска, который использует тот факт, что список key с, в которых key является для поиска уже отсортирован, он не требует от вас, чтобы отсортировать, а затем искать, делая его худший случай поиск время O(log n).

Если вы не отсортированный список key с и хотите найти key, то вам придется идти на линейный поиск, который в худшем случае будет работать с O(n) сложности, нет необходимости сортировки, а затем поиск, который определенно медленнее, так как самые известные сортировочные альгоды могут работать только в O(n log n) раз.

Построение dictionary из list в key с, а затем выполняет поиск не имеет преимуществ здесь, потому что линейный поиск даст то же самое для более высокой производительности, а также существует необходимость вспомогательной памяти, которая была бы необходима в случае dictionary; однако , если у вас есть несколько поисковых запросов и небольшое пространство для ключей с использованием dictionary может иметь преимущество, поскольку создание словаря - это однократная работа O(n), а последующие запросы могут быть сделаны O(1) за счет некоторой памяти, которая будет использоваться dictionary ,

источник

2016-04-28 09:27:19 anand

«если вы уже знаете ключ, который вы ищете, он не будет называться поиском» - я не понимаю этого предложения. Вы ищете * наличие * ключа, который вы знаете заранее. Как вы можете искать то, что не знаете? –

«самые известные сортирующие альготы» - на самом деле математически доказано, что сортировка не может принимать меньше, чем 'O (n log n) + c'. Сегодня алгоритмы пытаются минимизировать константу 'c'. –

«линейный поиск, который в худшем случае будет работать с сложностью O (n), нет необходимости сортировать, а затем искать, что определенно медленнее, так как наиболее известные сортировки algos могут работать только в« O (n log n) »времени. почему вы принимаете это как случай, который я сказал в вопросе "(предположим, что я хочу искать несколько раз)" –

Использование словаря вместо сортировки, а затем поиск

ответ

Смежные вопросы