Войти
В теории вычислительной сложности, а точнее в анализе алгоритмов с целым числом данных, трансдихотомическая модель является разновидностью машины с произвольным доступом, в которой предполагается, что машина размер слова соответствует размеру проблемы. Модель была предложена Майклом Фредманом и Дэном Уиллардом, которые выбрали ее название «потому, что дихотомия между моделью машины и размером проблемы разумно пересекается».
В такой задаче, как целочисленная сортировка, в которой нужно отсортировать n целых чисел, трансдихотомическая модель предполагает, что каждое целое число может храниться в одном слове компьютерной памяти, что операции с отдельными словами требуют постоянное время на операцию и что количество битов, которые могут быть сохранены в одном слове, должно быть не менее log 2 n. Цель анализа сложности в этой модели - найти временные рамки, которые зависят только от n, а не от фактического размера входных значений или машинных слов. При моделировании целочисленных вычислений необходимо предполагать, что машинные слова ограничены по размеру, потому что модели с неограниченной точностью являются неоправданно мощными (способны решать PSPACE-complete задачи за полиномиальное время). Трансдихотомическая модель делает минимальное допущение этого типа: что существует некоторый предел, и что предел достаточно велик, чтобы разрешить произвольную индексацию входных данных.
Помимо применения к целочисленной сортировке, трансдихотомическая модель также применялась для проектирования очередей приоритетов и проблем в вычислительной геометрии и алгоритмах графа.
.
