Изменения

|statement=

Ожидаемое время работы эволюционного алгоритма поиска эйлерова цикла в графе по RLS будет:

<tex>O(\frac{\Delta(G)^2} {d(G)} \cdot m \cdot log \, m)</tex> для стратегии, ориентированной на вершины;

<tex>O(\Delta(G) \cdot m \cdot log \, m )</tex> для стратегии, ориентированной на ребра;

<tex>O(\delta d(G) \cdot m \cdot log \, m )</tex> для стратегии, ориентированной на пары.

|proof=Предположим, что значение функции приспособленности в данный момент <tex>k</tex>. Тогда путей не менее <tex>k/2</tex>. Если путь является циклом, то в нем есть хотя бы одна вершина, соединяющая данный путь с каким-то другим, то есть найдется пара <tex>(u, w)</tex>, к которой можно применить мутацию и уменьшить количество путей. Если путь не является циклом, то так же найдется пара, при применении к которой мутации либо уменьшится количество путей, либо путь замкнется в цикл. Количество мутаций, которые уменьшают функцию приспособленности <tex>\Omega(k)</tex>. Как следствие, вероятность выбрать подходящую пару <tex>\Omega(q \cdot k)</tex>, где <tex>q</tex> — вероятность выбрать подходящую пару. Поэтому ожидаемое время достижения улучшения будет <tex>O(\frac{1} {k \cdot q})</tex>. Изначально значение функции приспособленности не более <tex>2m</tex>. Суммируя по всем <tex>k</tex> без учета констант получаем: