47
правок
Изменения
→Время работы алгоритма
<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> без учета констант получаем:
<tex>\sum_{k=1}^{m} \frac{1} {k \cdot q} = \frac{1} {q} \sum_{k=1} ^{m} \frac{1} {k} = O(\frac{1} {q}log \, m)</tex>
