|
пусть на месяц приходится (в среднем) М записей.
тогда если обходить подневно, то на один месяц будет М проверок.
если применить мою оптимизацию однократно, то будет M^(1/2) больших прыжков длиной M^(1/2), и один неудачный отрезок тоже длиной M^(1/2), который идем по дням.
итого 2 * M^(1/2) проверок.
но можно пойти дальше и сделать 3 "слоя": на первом прыгать через M^(2/3), на втором - через M^(1/3) внутри неудачного отрезка.
итого выходит уже 3 * M^(1/3) проверок, то есть при М = 1000000 всего 300 проверок на месяц. Недурственно.
|