О среднем значении суммарной длины цепочек, вычисляемых при дополнительных проверках в методе балансировки с особыми точками

Методы балансировки время-память используются для решения задачи обращения однонаправленной функции. Балансировка с особыми точками и несовершенными таблицами является одним из наиболее известных вариантов этих методов. Ранее Хонг и Мун получили оценку средней суммарной длины цепочек, вычисляемых при дополнительных проверках. В данной работе получено обобщение этого результата. В рамках новой теоретико-вероятностной модели построена двусторонняя оценка указанной величины. Полученные результаты применимы при любых ограничениях на длину основной цепочки, при любых правилах обрыва дополнительной цепочки, при использовании однонаправленных функций с нетипичными свойствами. Они также позволяют выявить область изменения параметров метода, в которой полученные оценки остаются достаточно точными.