Сложность алгоритмов

28.11.2024

ости эвристических алгоритмов

— это алгоритмы, которые находят приближённые решения задач, где точное решение найти сложно или невозможно за разумное время. В данном конспекте рассматривается, как оценивать их сложность с примерами.

---

Основные аспекты оценки сложности

1

Анализ времени выполнения

• Описание: Оценивается, как время выполнения изменяется в зависимости от размера входных данных.

• Ключевые категории:

  • Худший случай: Максимальное время выполнения.

  • Средний случай: Усреднённое время для случайных входных данных.

  • Лучший случай: Минимальное время выполнения.

2

Анализ потребления памяти

• Описание: Измеряется объём памяти, необходимый алгоритму для работы.

• Факторы:

  • Объём входных данных.

  • Использование вспомогательных структур (массивы, кэш, списки).

3

Число итераций

• Описание: Количество шагов, необходимых для достижения решения.

• Применение: Часто используется в итерационных алгоритмах (например, жадный алгоритм, генетические алгоритмы).

4

Качество решения

• Описание: Оценивается точность приближённого решения относительно оптимального.

• Метрические показатели:

  • Отклонение от оптимального решения.

  • Время достижения приемлемого качества.

---

Пример: Жадный алгоритм для задачи коммивояжёра

Код алгоритма на Python

import random


def generate_cities(n):
    return [(random.randint(0, 100), random.randint(0, 100)) for _ in range(n)]


def distance(a, b):
    return ((a[0] - b[0])**2 + (a[1] - b[1])**2) ** 0.5


def greedy_tsp(cities):
    n = len(cities)
    visited = [False] * n
    path = [0]  
    visited[0] = True
    
    for _ in range(n - 1):
        last = path[-1]
        next_city = min(
            ((i, distance(cities[last], cities[i])) for i in range(n) if not visited[i]),
            key=lambda x: x[1]
        )[0]
        path.append(next_city)
        visited[next_city] = True
    
    return path


cities = generate_cities(5)  
path = greedy_tsp(cities)
print("Маршрут:", path)

---

Шаги анализа сложности

Временная сложность:

1. Внешний цикл работает $n - 1$ раз, где $n$ — число городов.

2. На каждой итерации выполняется поиск ближайшего города среди оставшихся, что занимает $O(n)$ времени.

Итоговая сложность:

$O(n^2)$

Почему квадрат^2?

1. Внешний цикл:

   for _ in range(n - 1):

   Выполняется n−1n - 1 раз, по одному шагу для каждого города, кроме начального.

2. Внутренний поиск ближайшего города:

   min(((i, distance(...)) for i in range(n) if not visited[i]), ...)

   На каждой итерации проверяются расстояния до всех оставшихся городов $O(n)$.

3. Общий результат: Внутренний поиск $O(n)$ выполняется $n - 1$ раз, давая сложность:

   $O(n)⋅O(n) = O(n^2)$

Памятная сложность:

• Массив $visited$ для хранения статуса посещённых городов $O(n)$.

• Общая сложность памяти: $O(n)$.

Качество решения:

• Жадный алгоритм не гарантирует оптимальное решение, но на практике часто даёт хорошие результаты.

---

Оценка сложности других эвристических методов

1. Генетический алгоритм

• Временная сложность: зависит от размера популяции $P$ и числа поколений $G$.

$O(P⋅G⋅F(n))$

где $F(n)$ — время вычисления фитнес-функции.

• Памятная сложность: $O(P⋅n)$, где $n$ — размер индивида.

2. Алгоритм имитации отжига

• Временная сложность: зависит от числа итераций T, температуры охлаждения и времени вычисления фитнес-функции.

$O(T⋅F(n))$

• Памятная сложность: $O(1)$, так как хранится только текущее решение.

---

Сравнительная таблица эвристических алгоритмов

Алгоритм	Временная сложность	Памятная сложность	Особенности
Жадный алгоритм	$O(n^2)$	$O(n)$	Быстрое, но не всегда точное решение.
Генетический алгоритм	$O(P \cdot G \cdot F(n))$	$O(P⋅n)$	Эффективен для сложных задач.
Имитация отжига	$O(T⋅F(n))$	$O(1)$	Гибкость, но требует настройки параметров.

---

График маршрута коммивояжёра

На графике ниже показан пример маршрута, найденного жадным алгоритмом для случайно сгенерированных 10 городов:

Маршрут коммивояжёра

Описание графика:

• Синие точки — это города (случайные координаты на плоскости).

• Красные цифры — порядковые номера городов.

• Зелёная линия — маршрут, найденный алгоритмом.

Маршрут начинается с точки 00 и возвращается в неё после посещения всех остальных городов.