Блог

Простой пример — сортировка по сегментам. Для работы сортировки по сегментам должна быть доступна дополнительная информация. Входные данные a1, a2, . . . , an должны состоять только из положительных целых чисел, меньших m. (Очевидно, что возможны расширения к этому.) Если это так, то алгоритм прост: сохраните массив с именем count, размером m, который инициализируется всеми 0s. Таким образом, count содержит m ячеек или сегментов, которые изначально пусты. Когда ai считывается, увеличьте количество [ai] на 1. После того, как все входные данные будут прочитаны, просканируйте массив count, распечатав представление отсортированного списка. Этот алгоритм принимает O (m n); Если m равно O (n), то общее значение равно O (n).

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

Мой вопрос по приведенному выше абзацу

1. Что автор подразумевает под «он использует более мощную операцию, чем простые сравнения»?
2. Как алгоритм выполняет сравнение m-way, увеличивая соответствующий сегмент? Кстати, что такое m-way comparision?
3. Как описанная выше стратегия сортировки корзины связана с расширяемым хешированием? может ли кто-нибудь привести пример с расширяемым хешированием?

Спасибо!

1. более count[arr[i]] «мощный», чем сравнение, потому что это на самом деле *(count arr[i]) . каждая операция сравнения имеет 2 возможных значения: true / false, в то время как эта операция имеет гораздо более широкий диапазон значений, [все возможные адреса!] и, следовательно, она более «мощная»
2. увеличивая элемент, алгоритм «знает» позже, сколько элементов находится в этом «ведре», а позже: просто «выплесните» содержимое корзины. я полагаю, что автор имеет в виду сравнение с m способами, это «сравнение» с m возможными выходами, как я объяснил выше.
3. по сути, это хеширование, вы хэшируете свои элементы в диапазоне [0,m] . важность и отличие здесь в том, что два элемента хэшируются с одинаковым числом тогда и только тогда, когда они идентичны. это, конечно, может быть достигнуто, только если вы хэшируете элементы с тем же [или меньшим] диапазоном, чем изображение.