===Время работы===
Из описания алгоритма видно, что во втором цикле перезаписывается каждая позиция массива Внешний цикл <tex>Zwhile</tex> не более одного отработает за <tex>O(n)</tex> итераций, так как внутри него <tex>i</tex> увеличивается не менее чем на <tex>1)</tex>. Значит время работы второго цикла составляет А внутренний цикл выполнит суммарно не более <tex>O(n)</tex>. Так же видноитераций, так как после него <tex>i</tex> увеличится на количество итераций внутреннего цикла, но <tex>i</tex> не может увеличиться более чем на <tex>n</tex>, что в первом цикле пробегается один раз каждая позиция массива так как каждое значение <tex>PZ[i]</tex>. Получается в итоге время работы алгоритма составляет не может превзойти <tex>O(n)</tex>.
== См. также ==
