Как было показано в предыдущих теоремах, плохой для алгоритма является такая библиотека, в которой на ... - Большая Энциклопедия Нефти и Газа



Выдержка из книги Гасанова Э.Э. Теория хранения и поиска информации


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

(cкачать страницу)

Смотреть книгу на libgen

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