Оценка сложности алгоритмов: линейная сложность, квадратичная, логарифмическая...

Существует несколько способов измерения сложности алгоритма. Программисты обычно сосредотачивают внимание на скорости алгоритма, но не менее важны и другие показатели – требования к объёму памяти, например. Использование быстрого алгоритма не приведёт к ожидаемым результатам, если для его работы понадобится больше памяти, чем есть у компьютера.

При сравнении различных алгоритмов важно знать, как их сложность зависит от объёма входных данных.

$T(n) \colon \mathbb{N} \to \mathbb{Q}^{+}$, причём $T(n) > 0$.

$T(n) = O(f(n))$ $\Leftrightarrow$ существуют $C, n_0 > 0$: $T(n) \le C \cdot f(n)$ для всех $n \ge n_0$.

Лемма 1. Если многочлен имеет вид

$$T(n) = a_0 n^b + a_1 n^{b-1} + \dots + a_{b-1} n + a_b,$$

то $T(n) = O(n^b)$.

Доказательство. Возьмём $n_0 = 1$ и $c = |a_0| + |a_1| + \dots + |a_b|$. Для $n \ge 1$ каждая степень $n^j \le n^b$, поэтому $T(n) \le c \cdot n^b$.

Лемма 2. Для любого $k \ge 1$ верно $n^k \ne O(n^{k-1})$.

Доказательство от противного. Пусть $n^k = O(n^{k-1})$: существуют $C, n_0$, что $n^k \le C \cdot n^{k-1}$ при $n \ge n_0$. Тогда $n \le C$ при всех $n \ge n_0$, а это неверно.

Нижняя оценка и Θ.

$T(n) = \Omega(f(n))$ $\Leftrightarrow$ существуют $c, n_0 > 0$: $T(n) \ge c \cdot f(n)$ для всех $n \ge n_0$.

$T(n) = \Theta(f(n))$ $\Leftrightarrow$ $T(n) = O(f(n))$ и $T(n) = \Omega(f(n))$, то есть существуют $c_1, c_2, n_0 > 0$: $c_1 \cdot f(n) \le T(n) \le c_2 \cdot f(n)$ для всех $n > n_0$.

Маленькая $o$

$T(n) = o(f(n))$ $\Leftrightarrow$ для любого $c > 0$ существует $n_0$: $T(n) \le c \cdot f(n)$ для всех $n \ge n_0$.

Пример: $\forall k \ge 1$: $n^{k-1} = o(n^k)$.

Классы сложности на примерах

Время работы алгоритма растёт с размером входа $n$ по-разному. Предел $n$ — наибольший размер входа, который алгоритм успевает обработать за секунду, если компьютер делает около $10^8$ простых операций в секунду. Полоска показывает предел в логарифмической шкале от $1$ до $10^{16}$: чем короче полоска, тем меньше $n$. Названия ведут к разделам курса.

КлассПредел $n$Пример алгоритма
$O(1)$любое $n$Стек на массиве
$O(\log n)$любое $n$Двоичный поиск
$O(\sqrt{n})$около $10^{16}$Корневая оптимизация
$O(n)$около $10^8$Обход бинарного дерева
$O(n\log n)$около $4\cdot10^6$Сортировка слиянием
$O(n^2)$около $10^4$Сортировка пузырьком
$O(n^3)$около $500$Алгоритм Флойда
$O(2^n)$около $26$Ханойские башни
$O(n!)$около $11$Перебор перестановок

$O(1)$ - время выполнения алгоритма константа (не зависит от количества элементов во входном множестве).

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

Пример: поиск минимального элемента в массиве (цикл по всем элементам массива).

Реализация на Python

# Поиск минимума в списке: O(n) по времени, один проход по элементам, O(1) дополнительной памяти
def find_min(items):
    """Возвращает наименьший элемент списка или None, если список пуст."""
    if not items:
        return None
    minimum = items[0]  # сначала считаем минимумом первый элемент
    for item in items:
        if item < minimum:
            minimum = item
    return minimum


def main():
    print(find_min([5, 3, 8, 1, 9, 2, 7]))
    print(find_min([]))


if __name__ == "__main__":
    main()

Реализация на Rust

// Поиск минимума в срезе: O(n) по времени, один проход по элементам, O(1) дополнительной памяти
pub fn find_min(items: &[i32]) -> Option<i32> {
    // Первый элемент - текущий минимум; у пустого среза минимума нет
    let (&first, rest) = items.split_first()?;
    let mut minimum = first;
    for &item in rest {
        if item < minimum {
            minimum = item;
        }
    }
    Some(minimum)
}

fn main() {
    println!("{:?}", find_min(&[5, 3, 8, 1, 9, 2, 7]));
    println!("{:?}", find_min(&[]));
}

Реализация на C++

// Поиск минимума в векторе: O(n) по времени, один проход по элементам, O(1) дополнительной памяти
#include <iostream>
#include <optional>
#include <vector>

// Возвращает наименьший элемент или пустой optional, если вектор пуст
std::optional<int> find_min(const std::vector<int>& items) {
    if (items.empty()) {
        return std::nullopt;
    }
    int minimum = items[0];  // сначала считаем минимумом первый элемент
    for (int item : items) {
        if (item < minimum) {
            minimum = item;
        }
    }
    return minimum;
}

int main() {
    const std::optional<int> minimum = find_min({5, 3, 8, 1, 9, 2, 7});
    std::cout << *minimum << '\n';
    std::cout << (find_min({}) ? "есть" : "нет") << '\n';
    return 0;
}

$O(n^2)$ - квадратичная сложность. Например, сортировки "пузырьком", вставками и т.д.

Реализация на Python

# Сортировка пузырьком: O(n^2) сравнений в среднем и в худшем случае
def bubble_sort(items):
    """Сортирует список по возрастанию на месте и возвращает его."""
    for last in range(len(items) - 1, 0, -1):
        # Самый большой из непросмотренных элементов «всплывает» в конец отрезка [0..last]
        for i in range(last):
            if items[i] > items[i + 1]:
                items[i], items[i + 1] = items[i + 1], items[i]
    return items


def main():
    print(bubble_sort([5, 3, 8, 1, 9, 2, 7]))


if __name__ == "__main__":
    main()

Реализация на Rust


// Сортировка пузырьком: O(n^2) сравнений в среднем и в худшем случае
pub fn bubble_sort(items: &mut [i32]) {
    for last in (1..items.len()).rev() {
        // Самый большой из непросмотренных элементов «всплывает» в конец отрезка [0..=last]
        for i in 0..last {
            if items[i] > items[i + 1] {
                items.swap(i, i + 1);
            }
        }
    }
}

fn main() {
    let mut items = vec![5, 3, 8, 1, 9, 2, 7];
    bubble_sort(&mut items);
    println!("{:?}", items);
}

Реализация на C++

// Сортировка пузырьком: O(n^2) сравнений в среднем и в худшем случае
#include <cstddef>
#include <iostream>
#include <utility>
#include <vector>

void bubble_sort(std::vector<int>& items) {
    // Самый большой из непросмотренных элементов «всплывает» в конец отрезка [0, last)
    for (std::size_t last = items.size(); last > 1; --last) {
        for (std::size_t i = 0; i + 1 < last; ++i) {
            if (items[i] > items[i + 1]) {
                std::swap(items[i], items[i + 1]);
            }
        }
    }
}

int main() {
    std::vector<int> items = {5, 3, 8, 1, 9, 2, 7};
    bubble_sort(items);
    for (int item : items) {
        std::cout << item << ' ';
    }
    std::cout << '\n';
    return 0;
}

Пример: поиск двух точек на плоскости с максимальным расстоянием между ними.

Реализация на Python

# Пара точек с максимальным расстоянием: перебор всех пар, O(n^2) по времени, O(1) дополнительной памяти
def farthest_pair(points):
    """Возвращает пару точек с наибольшим расстоянием или None, если точек меньше двух."""
    best_pair = None
    best_dist = -1  # квадрат расстояния: координаты целые, поэтому корень не нужен
    for i in range(len(points)):
        for j in range(i + 1, len(points)):
            (x1, y1), (x2, y2) = points[i], points[j]
            dist = (x1 - x2) ** 2 + (y1 - y2) ** 2
            if dist > best_dist:
                best_dist = dist
                best_pair = (points[i], points[j])
    return best_pair


def main():
    points = [(0, 0), (3, 4), (-1, 2), (6, -2), (1, 1)]
    print(farthest_pair(points))


if __name__ == "__main__":
    main()

Реализация на Rust

// Пара точек с максимальным расстоянием: перебор всех пар, O(n^2) по времени, O(1) дополнительной памяти
pub type Point = (i64, i64);

pub fn farthest_pair(points: &[Point]) -> Option<(Point, Point)> {
    let mut best_pair = None;
    // Квадрат расстояния: координаты целые, поэтому корень не нужен
    let mut best_dist = -1;
    for (i, &(x1, y1)) in points.iter().enumerate() {
        for &(x2, y2) in &points[i + 1..] {
            let dist = (x1 - x2).pow(2) + (y1 - y2).pow(2);
            if dist > best_dist {
                best_dist = dist;
                best_pair = Some(((x1, y1), (x2, y2)));
            }
        }
    }
    best_pair
}

fn main() {
    let points: [Point; 5] = [(0, 0), (3, 4), (-1, 2), (6, -2), (1, 1)];
    println!("{:?}", farthest_pair(&points));
}

Реализация на C++

// Пара точек с максимальным расстоянием: перебор всех пар, O(n^2) по времени, O(1) дополнительной памяти
#include <cstddef>
#include <iostream>
#include <optional>
#include <utility>
#include <vector>

struct Point {
    long long x;
    long long y;
};

std::ostream& operator<<(std::ostream& out, const Point& p) {
    return out << '(' << p.x << ", " << p.y << ')';
}

// Возвращает пару точек с наибольшим расстоянием или пустой optional, если точек меньше двух
std::optional<std::pair<Point, Point>> farthest_pair(const std::vector<Point>& points) {
    std::optional<std::pair<Point, Point>> best;
    long long best_dist = -1;  // квадрат расстояния: координаты целые, поэтому корень не нужен
    for (std::size_t i = 0; i < points.size(); ++i) {
        for (std::size_t j = i + 1; j < points.size(); ++j) {
            long long dx = points[i].x - points[j].x;
            long long dy = points[i].y - points[j].y;
            long long dist = dx * dx + dy * dy;
            if (dist > best_dist) {
                best_dist = dist;
                best = std::make_pair(points[i], points[j]);
            }
        }
    }
    return best;
}

int main() {
    const std::vector<Point> points = {{0, 0}, {3, 4}, {-1, 2}, {6, -2}, {1, 1}};
    const auto best = farthest_pair(points);
    std::cout << best->first << ' ' << best->second << '\n';
    return 0;
}

$O(n^3)$ - кубическая сложность.

Пример: поиск треугольника максимальной площади с вершинами в точках на плоскости (перебор вершин тройным циклом).

Реализация на Python

# Треугольник максимальной площади: перебор всех троек точек, O(n^3) по времени, O(1) дополнительной памяти
def twice_area(triangle):
    """Удвоенная площадь треугольника по векторному произведению (целое число, без дробей)."""
    (x1, y1), (x2, y2), (x3, y3) = triangle
    return abs((x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1))


def all_triangles(points):
    """Перебирает все тройки точек с индексами i < j < k тройным циклом."""
    for i in range(len(points)):
        for j in range(i + 1, len(points)):
            for k in range(j + 1, len(points)):
                yield points[i], points[j], points[k]


def largest_triangle(points):
    """Возвращает тройку вершин треугольника максимальной площади или None, если точек меньше трёх."""
    return max(all_triangles(points), key=twice_area, default=None)


def main():
    points = [(0, 0), (4, 0), (0, 3), (2, 1), (1, 1)]
    print(largest_triangle(points))


if __name__ == "__main__":
    main()

Реализация на Rust

// Треугольник максимальной площади: перебор всех троек точек, O(n^3) по времени, O(1) дополнительной памяти
pub type Point = (i64, i64);

// Удвоенная площадь треугольника abc: целое число, поэтому без дробей
pub fn twice_area(a: Point, b: Point, c: Point) -> i64 {
    ((b.0 - a.0) * (c.1 - a.1) - (c.0 - a.0) * (b.1 - a.1)).abs()
}

pub fn largest_triangle(points: &[Point]) -> Option<(Point, Point, Point)> {
    let mut best = None;
    let mut best_area = -1;
    for i in 0..points.len() {
        for j in i + 1..points.len() {
            for k in j + 1..points.len() {
                let area = twice_area(points[i], points[j], points[k]);
                if area > best_area {
                    best_area = area;
                    best = Some((points[i], points[j], points[k]));
                }
            }
        }
    }
    best
}

fn main() {
    let points: [Point; 5] = [(0, 0), (4, 0), (0, 3), (2, 1), (1, 1)];
    println!("{:?}", largest_triangle(&points));
}

Реализация на C++

// Треугольник максимальной площади: перебор всех троек точек, O(n^3) по времени, O(1) дополнительной памяти
#include <cstddef>
#include <cstdlib>
#include <iostream>
#include <optional>
#include <tuple>
#include <vector>

struct Point {
    long long x;
    long long y;
};

std::ostream& operator<<(std::ostream& out, const Point& p) {
    return out << '(' << p.x << ", " << p.y << ')';
}

// Удвоенная площадь треугольника abc: целое число, поэтому без дробей
long long twice_area(const Point& a, const Point& b, const Point& c) {
    return std::llabs((b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y));
}

// Возвращает тройку вершин треугольника максимальной площади или пустой optional, если точек меньше трёх
std::optional<std::tuple<Point, Point, Point>> largest_triangle(const std::vector<Point>& points) {
    std::optional<std::tuple<Point, Point, Point>> best;
    long long best_area = -1;
    for (std::size_t i = 0; i < points.size(); ++i) {
        for (std::size_t j = i + 1; j < points.size(); ++j) {
            for (std::size_t k = j + 1; k < points.size(); ++k) {
                long long area = twice_area(points[i], points[j], points[k]);
                if (area > best_area) {
                    best_area = area;
                    best = std::make_tuple(points[i], points[j], points[k]);
                }
            }
        }
    }
    return best;
}

int main() {
    const std::vector<Point> points = {{0, 0}, {4, 0}, {0, 3}, {2, 1}, {1, 1}};
    const auto [a, b, c] = *largest_triangle(points);
    std::cout << a << ' ' << b << ' ' << c << '\n';
    return 0;
}

Оценка $O(n)$ ассимптотическая (при $n$ стремящемся к бесконечности).

$O(\ln{n})$ - Бинарный поиск - логарифмическая сложность.

Реализация на Python

# Бинарный поиск в отсортированном списке: O(log n) сравнений
def binary_search(items, target):
    """Возвращает индекс target в отсортированном списке или None, если его там нет."""
    low, high = 0, len(items)  # искомое ищем в полуинтервале [low, high)
    while low < high:
        middle = (low + high) // 2
        if items[middle] == target:
            return middle
        if items[middle] < target:
            low = middle + 1
        else:
            high = middle
    return None


def main():
    values = [1, 3, 5, 7, 9, 11, 13]
    print(binary_search(values, 7))
    print(binary_search(values, 8))


if __name__ == "__main__":
    main()

Реализация на Rust


// Бинарный поиск в отсортированном срезе: O(log n) сравнений
use std::cmp::Ordering;

pub fn binary_search(items: &[i32], target: i32) -> Option<usize> {
    // Искомое ищем в полуинтервале [low, high)
    let (mut low, mut high) = (0, items.len());
    while low < high {
        let middle = low + (high - low) / 2;
        match items[middle].cmp(&target) {
            Ordering::Equal => return Some(middle),
            Ordering::Less => low = middle + 1,
            Ordering::Greater => high = middle,
        }
    }
    None
}

fn main() {
    let values = [1, 3, 5, 7, 9, 11, 13];
    println!("{:?}", binary_search(&values, 7));
    println!("{:?}", binary_search(&values, 8));
}

Реализация на C++

// Бинарный поиск в отсортированном векторе: O(log n) сравнений
#include <cstddef>
#include <iostream>
#include <optional>
#include <vector>

std::optional<std::size_t> binary_search(const std::vector<int>& items, int target) {
    // Искомое ищем в полуинтервале [low, high)
    std::size_t low = 0;
    std::size_t high = items.size();
    while (low < high) {
        std::size_t middle = low + (high - low) / 2;
        if (items[middle] == target) {
            return middle;
        }
        if (items[middle] < target) {
            low = middle + 1;
        } else {
            high = middle;
        }
    }
    return std::nullopt;
}

int main() {
    const std::vector<int> values = {1, 3, 5, 7, 9, 11, 13};
    for (int target : {7, 8}) {
        auto index = binary_search(values, target);
        if (index) {
            std::cout << "индекс " << *index << '\n';
        } else {
            std::cout << "нет\n";
        }
    }
    return 0;
}

$O(n\log{n})$ - быстрая сортировка Хоара (рус) - QuickSort, HeapSort, MergeSort.

Реализация на Python

# Быстрая сортировка Хоара: O(n log n) в среднем, O(n^2) в худшем случае
def quick_sort(items):
    """Сортирует список по возрастанию на месте и возвращает его."""
    sort_range(items, 0, len(items) - 1)
    return items


def sort_range(items, low, high):
    """Сортирует отрезок items[low..high] (границы включены) разбиением Хоара."""
    if low >= high:
        return
    pivot = items[(low + high) // 2]
    i, j = low, high
    while i <= j:
        while items[i] < pivot:
            i += 1
        while items[j] > pivot:
            j -= 1
        if i <= j:
            items[i], items[j] = items[j], items[i]
            i += 1
            j -= 1
    # После разбиения [low..j] не больше опорного, [i..high] не меньше опорного
    sort_range(items, low, j)
    sort_range(items, i, high)


def main():
    print(quick_sort([5, 3, 8, 1, 9, 2, 7, 3]))


if __name__ == "__main__":
    main()

Реализация на Rust


// Быстрая сортировка Хоара: O(n log n) в среднем, O(n^2) в худшем случае
pub fn quick_sort(items: &mut [i32]) {
    if items.len() <= 1 {
        return;
    }
    let pivot = items[items.len() / 2];
    // Индексы со знаком: j может стать -1, и это не должно переполнять usize
    let (mut i, mut j) = (0_isize, items.len() as isize - 1);
    while i <= j {
        while items[i as usize] < pivot {
            i += 1;
        }
        while items[j as usize] > pivot {
            j -= 1;
        }
        if i <= j {
            items.swap(i as usize, j as usize);
            i += 1;
            j -= 1;
        }
    }
    // После разбиения [0..=j] не больше опорного, [i..] не меньше опорного
    if j >= 0 {
        quick_sort(&mut items[..=j as usize]);
    }
    quick_sort(&mut items[i as usize..]);
}

fn main() {
    let mut items = [5, 3, 8, 1, 9, 2, 7, 3];
    quick_sort(&mut items);
    println!("{:?}", items);
}

Реализация на C++

// Быстрая сортировка Хоара: O(n log n) в среднем, O(n^2) в худшем случае
#include <iostream>
#include <utility>
#include <vector>

// Сортирует отрезок items[low..high] (границы включены) разбиением Хоара
void sort_range(std::vector<int>& items, int low, int high) {
    if (low >= high) {
        return;
    }
    int pivot = items[(low + high) / 2];
    int i = low;
    int j = high;
    while (i <= j) {
        while (items[i] < pivot) {
            ++i;
        }
        while (items[j] > pivot) {
            --j;
        }
        if (i <= j) {
            std::swap(items[i], items[j]);
            ++i;
            --j;
        }
    }
    // После разбиения [low..j] не больше опорного, [i..high] не меньше опорного
    sort_range(items, low, j);
    sort_range(items, i, high);
}

void quick_sort(std::vector<int>& items) {
    sort_range(items, 0, static_cast<int>(items.size()) - 1);
}

int main() {
    std::vector<int> items = {5, 3, 8, 1, 9, 2, 7, 3};
    quick_sort(items);
    for (int item : items) {
        std::cout << item << ' ';
    }
    std::cout << '\n';
    return 0;
}

При оценке сложности важна только самая старшая степень. Например:

$O(n^3+n^2+4n)=O(n^3)$

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