Оценка сложности алгоритмов: линейная сложность, квадратичная, логарифмическая...
Существует несколько способов измерения сложности алгоритма. Программисты обычно сосредотачивают внимание на скорости алгоритма, но не менее важны и другие показатели – требования к объёму памяти, например. Использование быстрого алгоритма не приведёт к ожидаемым результатам, если для его работы понадобится больше памяти, чем есть у компьютера.
При сравнении различных алгоритмов важно знать, как их сложность зависит от объёма входных данных.
$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)$
Константа так же отбрасывается, так как нам важно лишь во сколько раз возрастает время выполнения программы при увеличении размера входных данных.