Слайд 0: Введение в алгоритмическую сложность

Что такое алгоритмическая сложность?

Алгоритмическая сложность - это характеристика, показывающая, как растет время выполнения алгоритма при увеличении размера входных данных.

Основные классы сложности (O-нотация):

O(1) - Константная сложность

Время выполнения не зависит от размера входных данных

# Пример O(1) - получение статистики персонажа
def get_character_stat(character, stat_name):
    return character.stats[stat_name]  # Мгновенный доступ

O(log n) - Логарифмическая сложность

Время растёт логарифмически с увеличением входных данных

# Пример O(log n) - поиск персонажа по уровню
def find_character_by_level(sorted_characters, target_level):
    left, right = 0, len(sorted_characters) - 1
    while left <= right:
        mid = (left + right) // 2
        if sorted_characters[mid].level == target_level:
            return sorted_characters[mid]
        elif sorted_characters[mid].level < target_level:
            left = mid + 1
        else:
            right = mid - 1

O(n) - Линейная сложность

Время растёт линейно с увеличением входных данных

# Пример O(n) - поиск артефакта в инвентаре
def find_artifact(inventory, artifact_name):
    for artifact in inventory:  # Проверяем каждый артефакт
        if artifact.name == artifact_name:
            return artifact

O(n²) - Квадратичная сложность

Время растёт квадратично с увеличением входных данных

# Пример O(n²) - сравнение всех артефактов между собой
def compare_all_artifacts(artifacts):
    for i in range(len(artifacts)):
        for j in range(len(artifacts)):  # Для каждого - проверяем каждый
            if artifacts[i].crit_value > artifacts[j].crit_value:
                # Сравнение

Сравнение сложности на практике:

Для 1000 элементов:

  • O(1): 1 операция
  • O(log n): ~10 операций
  • O(n): 1000 операций
  • O(n²): 1,000,000 операций

Важно помнить:

  • O-нотация показывает худший случай
  • Константы и меньшие слагаемые опускаются
  • Важна асимптотика (поведение на больших n)
  • На маленьких наборах данных разница может быть незаметна

Задача: Анализ сложности

Определите сложность следующих операций:

Подсказка: Анализируйте количество проходов по данным:

# Пример анализа
def find_max_crit_damage(artifacts):
    max_cd = 0
    for artifact in artifacts:  # Один проход по списку
        if artifact.crit_dmg > max_cd:
            max_cd = artifact.crit_dmg
    return max_cd
# Сложность: O(n) - один проход по n элементам