Общее число хвостовых блоков в члене из Ah есть 2й, или приблизительно ra / logra. ... - Большая Энциклопедия Нефти и Газа



Выдержка из книги Сборник N.N. Проблемы математической логики Сложность алгоритмов и классы вычислимых функций


Общее число хвостовых блоков в члене из Ah есть 2й, или приблизительно ra / logra. Теорема 1 устанавливает, что общее время вычисления в худшем случае должно быть пропорционально произведению числа хвостовых блоков, подлежащих сравнению, и максимального числа квадратов на ленте, нужных для записи всей существенной информации о базовом сегменте. Таким образом, невозможно улучшить вполне очевидный способ записи всех наборов, которые присутствуют в базовом сегменте, а потом просмотреть эту запись для каждого вновь поступившего хвостового блока.

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

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

Общее число хвостовых блоков в члене из Ah есть 2й,  или приблизительно ra / logra.  Теорема 1 устанавливает,  что общее время вычисления в худшем случае должно быть пропорционально произведению числа хвостовых блоков,  подлежащих сравнению,  и максимального числа квадратов на ленте,  нужных для записи всей существенной информации о базовом сегменте.  Таким образом,  невозможно улучшить вполне очевидный способ записи всех наборов,  которые присутствуют в базовом сегменте,  а потом просмотреть эту запись для каждого вновь поступившего хвостового блока.