Изменения
→Анализ реализации с ранговой эвристикой
Если выбрать функцию <tex>\mathrm{B}</tex> так, чтобы ряд <tex>{\sum_{} \limits n \mathrm{B(k)} / 2^{\mathrm{k}}}</tex> сходился, то общее число шагов такого рода есть <tex>\mathrm{O(n)}</tex>.
Прежде чем выбрать функцию <tex>\mathrm{B(k)}</tex>, выясним, как оценить число шагов, при которых ранг сильно растет. Такие шаги мы сгруппируем не по вершинам, а по путям: на каждом пути поиска таких шагов мало, так как ранг не может многократно сильно расти (он меняется всего лишь от <tex>0</tex> и <tex>\log n</tex>). Таким образом, на каждом пути число шагов, при котором ранг сильно растёт, не превосходит числа итераций функции <tex>\mathrm{B}</tex>, которые нужно сделать, чтобы дойти от <tex>0</tex> и <tex>\log n</tex>.
Если положить <tex>\mathrm{B(k)} = 2^{\mathrm{k}}</tex>: тогда число итераций будет примерно равно <tex>\mathrm{O(\log^{*}n)}</tex>. Но тогда написанный выше ряд расходится. Возьмем меньшую функцию. Например, положим <tex>\mathrm{B(k)} = \lceil 1,9^{\mathrm{k}}\rceil </tex>, тогда ряд <tex>\sum_{} \limits \mathrm{B(k)} = \lceil 1,9^{\mathrm{k}}\rceil /2^{\mathrm{k}} \leqslant \sum_{} \limits \mathrm{B(k)} = (1,9^{\mathrm{k}}+1)/2^{\mathrm{k}}</tex> сходится. С другой стороны, число итераций функции <tex>\mathrm{B}</tex>, которые нужно сделать, чтобы от <tex>0</tex> дойти до какого-то числа, возрастет (по сравнению с функцией <tex>\mathrm{k}</tex>, стремящейся к <tex>2^{\mathrm{k}}</tex>) не более чем вдвое, поскольку <tex>\mathrm{B(B(k))} \geqslant 2^{\mathrm{k}}</tex>, и потому есть <tex>\mathrm{O(\log^*n)}</tex>.
}}
