286
правок
Изменения
Нет описания правки
Из-за описанного выше, для оценки сложности алгоритмов во внешней памяти была предложена другая модель. Модель гласит следующее: существует какая-то внешняя память и процессор со своей внутренней памятью. Внутренняя память ограничена и имеет размер порядка <tex>M</tex> машинных слов. Внешняя память считается безграничной в рамках рассматриваемой задачи, то есть имеет размер хотя бы порядка <tex>N</tex> машинных слов, где <tex>N</tex> {{---}} размер задачи. Чтение и запись из внешней памяти происходит блоками последовательных данных размера <tex>B</tex> машинных слов. В качестве меры сложности принимается количество операций ввода-вывода, которые выполняет алгоритм, где одна операция ввода-вывода это либо чтение из внешней памяти одного блока размера <tex>B</tex>, либо запись.
У данной модели есть один существенный недостаток: мы никак не учитываем время, которое тратится на вычисления, а считаем только обращения к диску. Из-за этого многие задачи в данной модели решаются быстрее, чем в модели с ''RAM-машиной''. Например, прочитав какой-то блок, далее мы имеем право произвести экспоненциальный по сложности перебор , и это никак не будет учитываться. Поэтому нужно иметь в виду, что данная модель стремится эффективно использовать жесткий диск, а не балансировать между использованием процессора и жесткого диска.
== Размер блока ==
Рассмотрим как именно изменять веса элементов. Построим и отсортируем по ключу <tex>3</tex> таблицы:
# Таблица <tex>Conn</tex> из пар <tex>(i, j)</tex>, где каждая пара значит , что после <tex>i</tex>-ого элемента идет <tex>j</tex>-ый (может быть получена из входных данных за время линейного сканирования)
# Таблица <tex>W</tex> из пар <tex>(i, w_i)</tex>, хранящая веса элементов
# Таблица <tex>D</tex>, в которой записаны удаляемые элементы
По возвращению из рекурсии аналогично пересчитываются ранги элементов. Рассмотрим <tex>3</tex> таблицы:
# Таблица <tex>RevConn</tex> из пар <tex>(j, i)</tex>, где каждая пара значит , что после <tex>i</tex>-ого элемента идет <tex>j</tex>-ый
# Таблица <tex>W</tex> из пар <tex>(i, w_i)</tex>, хранящая веса элементов
# Таблица <tex>R</tex> из пар <tex>(i, r_i)</tex>, в которой записаны ранги элементов модифицированного списка
