Как делать оценку сложности?

19.11.2024 - Инструкция для студентов

Как оценивать сложность алгоритмов?

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

---

Основные виды сложности

1. Временная сложность Определяет, сколько операций выполняется алгоритмом для обработки данных. Обозначается через O(n), где n — размер входных данных.

2. Пространственная сложность Показывает, сколько памяти требуется для выполнения алгоритма. Учитываются как входные данные, так и используемые переменные.

---

Как определить сложность

1

Анализ по коду

• Найти основные блоки: циклы, рекурсию, ветвления.

• Определить количество операций для каждого блока.

2

Оценить вклад каждого блока

• Циклы: сколько итераций и операций на каждой итерации.

• Рекурсия: определить количество вызовов.

• Вложенные структуры: учитывать вложенность циклов и условий.

3

Учесть порядок роста

• Игнорировать константы и незначимые члены. Например: вместо 5n + 3 писать O(n).

---

Часто встречающиеся порядки роста

Тип сложности	Обозначение	Пример
Константная	O(1)	Поиск элемента в хэш-таблице
Линейная	O(n)	Проход по массиву
Логарифмическая	O(log n)	Бинарный поиск
Линейно-логарифмическая	O(n log n)	Быстрая сортировка
Квадратичная	O(n²)	Сравнение всех пар элементов
Кубическая	O(n³)	Тройная вложенность циклов
Факториальная	O(n!)	Перебор всех перестановок

---

Пример оценки сложности

Алгоритм с циклом и условием:

#include <iostream>
#include <vector>

// Функция проверяет, есть ли в массиве положительные числа
bool hasPositive(const std::vector<int>& arr) {
    for (int i = 0; i < arr.size(); i++) { // Цикл выполняется n раз
        if (arr[i] > 0) { // Проверка на каждом шаге
            return true;  // Если найден положительный элемент, алгоритм завершается
        }
    }
    return false; // Если не найдено, возвращается false
}

int main() {
    std::vector<int> data = {-1, -2, -3, 4, -5};
    std::cout << (hasPositive(data) ? "Есть положительное" : "Нет положительных");
    return 0;
}

Разбор сложности:

• Цикл: выполняется n раз (в худшем случае). Сложность: O(n).

• Условие внутри цикла: выполняется за O(1).

• Итоговая сложность: O(n).

---

Рекомендации для анализа

---

Примечания

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

• Некоторые алгоритмы имеют разные сложности для лучших, средних и худших случаев (например, сортировка вставками).

• Линковщик: программа, которая объединяет объектный код и зависимости в финальный исполняемый файл (.EXE).