Алгоритмы и сложность

19.11.2024

Программы с разными оценками сложности алгоритмов

В этом конспекте рассмотрены 5 программ с различной сложностью алгоритмов: O(1), O(log n), O(n), O(n²), и O(2ⁿ). Каждая программа снабжена пояснениями и примечаниями, чтобы лучше понять, как оценивается сложность.

---

1. Постоянная сложность O(1)

Пример задачи: Проверить, является ли число чётным.

#include <iostream>
using namespace std;

bool isEven(int number) {
    // Проверка остатка от деления на 2
    return number % 2 == 0;
}

int main() {
    int num = 4;
    cout << "Число " << num << (isEven(num) ? " чётное." : " нечётное.") << endl;
    return 0;
}

Объяснение

• Алгоритм выполняет одну и ту же операцию независимо от входных данных.

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

---

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

Пример задачи: Бинарный поиск в отсортированном массиве.

#include <iostream>
#include <vector>
using namespace std;

int binarySearch(const vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2; // Избегаем переполнения
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1; // Если элемент не найден
}

int main() {
    vector<int> numbers = {1, 3, 5, 7, 9, 11};
    int target = 7;
    int index = binarySearch(numbers, target);

    if (index != -1)
        cout << "Число найдено на индексе " << index << endl;
    else
        cout << "Число не найдено." << endl;
    return 0;
}

Объяснение

• Количество операций уменьшается в 2 раза на каждой итерации.

• Сценарий: массив из n элементов. За k шагов n становится 1. Формула: 2^k = n → k = log₂n.

---

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

Пример задачи: Найти сумму элементов массива.

#include <iostream>
#include <vector>
using namespace std;

int arraySum(const vector<int>& arr) {
    int sum = 0;
    for (int num : arr) { // Проходим по всем элементам
        sum += num;
    }
    return sum;
}

int main() {
    vector<int> numbers = {1, 2, 3, 4, 5};
    cout << "Сумма элементов массива: " << arraySum(numbers) << endl;
    return 0;
}

Объяснение

• Алгоритм посещает каждый элемент массива.

• Сложность растёт линейно с размером входных данных n.

---

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

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

#include <iostream>
#include <vector>
using namespace std;

void findPairsWithSum(const vector<int>& arr, int target) {
    for (int i = 0; i < arr.size(); ++i) {
        for (int j = i + 1; j < arr.size(); ++j) { // Вложенный цикл
            if (arr[i] + arr[j] == target) {
                cout << "Пара: (" << arr[i] << ", " << arr[j] << ")" << endl;
            }
        }
    }
}

int main() {
    vector<int> numbers = {1, 2, 3, 4, 5};
    int targetSum = 5;
    findPairsWithSum(numbers, targetSum);
    return 0;
}

Объяснение

• Два вложенных цикла означают, что для каждого элемента мы проверяем все остальные.

• Сложность: пропорциональна n × n = n².

---

5. Экспоненциальная сложность O(2ⁿ)

Пример задачи: Генерация всех подмножеств массива (рекурсия).

#include <iostream>
#include <vector>
using namespace std;

void generateSubsets(vector<int>& subset, const vector<int>& arr, int index) {
    if (index == arr.size()) {
        // Печать текущего подмножества
        cout << "{ ";
        for (int num : subset) {
            cout << num << " ";
        }
        cout << "}" << endl;
        return;
    }

    // 1. Не добавляем текущий элемент
    generateSubsets(subset, arr, index + 1);

    // 2. Добавляем текущий элемент
    subset.push_back(arr[index]);
    generateSubsets(subset, arr, index + 1);

    // 3. Убираем добавленный элемент (обратный ход)
    subset.pop_back();
}

int main() {
    vector<int> numbers = {1, 2, 3};
    vector<int> subset;
    generateSubsets(subset, numbers, 0);
    return 0;
}

Объяснение

• Рекурсия создаёт дерево вызовов, в котором каждый элемент либо включается, либо исключается. Пример: для n=3 будет 2³ = 8 подмножеств.

• Сложность: удваивается с каждым новым элементом n.

---

Итоги

Сложность	Пример	Ключевые моменты
O(1)	Проверка чётности	Постоянное время, одна операция.
O(log n)	Бинарный поиск	Делим задачу пополам на каждом шаге.
O(n)	Сумма массива	Линейный проход по данным.
O(n²)	Пары с суммой	Два вложенных цикла.
O(2ⁿ)	Все подмножества	Рекурсия, экспоненциальный рост вызовов.