Модель без явного задания параметров кэша: различия между версиями

При выполнении поиска B-деревья обеспечивают стоимость O(logB N), что является оптимальным в модели ввода-вывода для поиска на базе сравнения. Эта стоимость достижима и в модели без явного задания параметров кэша, что было показано для статического [ ] и для динамического случая [13]. Позднее было предложено несколько вариантов деревьев поиска без явного задания параметров кэша. Кроме того, в [ ] было показано различие между алгоритмами без явного задания параметров кэша и алгоритмами модели ввода-вывода, а именно – что константы в границе O(logB N) доказуемо различаются.

Перестановка в модели ввода-вывода имеет сложность @(min{ Sort(N); Ng) в предположении, что элементы неделимы [2]. Было доказано [ ], что эта асимптотическая сложность не может быть получена в модели без явного задания параметров кэша, так что и в случае этой задачи разделение имеет место.

Была предложена реализация очередей с приоритетами на базе модели без явного задания параметров кэша с O(1/BlogM/B N/M) амортизированных переносов содержимого памяти .

К настоящему времени также разработаны алгоритмы модели без явного задания параметров кэша для задач вычислительной геометрии [1, 6, 7, 8, 10, 15], графовых задач [4, 17, 18, 23], для сканирования динамических множеств [ ], укладки статических деревьев [11], задач поиска на мультимножествах [21], динамического программирования [19], частичной устойчивости [10], матричных операций [22] и быстрого преобразования Фурье [22].