Работа с BigO нотацией. Пишем высокопроизводительный код

Расскажу просто о сложном. Погнали.

Big O — это способ описать, насколько быстро растёт время работы алгоритма по мере увеличения размера входных данных. Другими словами: насколько «дорого» становится задача для компьютера, когда данных всё больше и больше.

Основные идеи на пальцах

Big O показывает, что происходит с временем работы, когда данных становится по-настоящему много.
Не считаем точное время в секундах, интересуют только масштабы.

Как пошагово считать BigO?

Убери константы и незначительные части. Останется «основа» — с ней и будем работать.
Определи, сколько раз будет выполнена главная операция алгоритма.
Оцени, как это число растёт при увеличении данных (B O(n) "n" — количество данных).

Как формально записывать

O(1) — Константное время

Не зависит от размера входных данных.
Операции: доступ к элементу по индексу, пуш в Vec, чтение значения HashMap.

Rust

fn main() { let vec = vec![10, 20, 30]; println!("{}", vec[1]); // доступ по индексу — O(1) }

Где встречается:

vec[i]
hash_map.get("ключ")
stack.push(x)
pop() у стека или очереди

O(n) — Линейное время

Время выполнения растёт линейно от объёма данных.
Обычно это один цикл.

Rust

fn main() { let books = vec!["A", "B", "C"]; for book in books { println!("{}", book); // каждую книгу — один раз } }

Где встречается:

Поиск элемента в Vec
Проход по массиву, списку, строке
Подсчёт суммы, фильтрация и пр.

O(n²) — Квадратичное время

Вложенные циклы. Количество операций растёт как n * n.

Rust

fn main() { let items = vec![1, 2, 3]; for a in &items { for b in &items { println!("{} + {} = {}", a, b, a + b); } } }

Где встречается:

Сравнение всех со всеми (n * n)
Сортировки типа bubble sort
Проверка пар, комбинаций, взаимных связей

O(log n) — Логарифмическое время

Уменьшение задачи пополам на каждом шаге.
Бинарный поиск в отсортированном массиве — классика.

Rust

fn binary_search(arr: &[i32], target: i32) -> Option<usize> { let mut left = 0; let mut right = arr.len();

while left < right { let mid = (left + right) / 2; if arr[mid] == target { return Some(mid); } else if arr[mid] < target { left = mid + 1; } else { right = mid; } }

None }

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

Где встречается:

Бинарный поиск (Vec, slice)
BTreeMap, BTreeSet (в Rust — хранятся как сбалансированные деревья)
Деление диапазонов, рекурсия с делением

O(2ⁿ), O(n!) — Экспоненциальное / Факториальное

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

Rust

fn permutations(prefix: String, rest: String) { if rest.is_empty() { println!("{}", prefix); } else { for i in 0..rest.len() { let mut new_prefix = prefix.clone(); new_prefix.push(rest.chars().nth(i).unwrap());

let mut new_rest = rest.clone(); new_rest.remove(i);

permutations(new_prefix, new_rest); } } }

fn main() { permutations("".to_string(), "abc".to_string()); }

Где встречается:

Полный перебор (backtracking, brute force)
Задачи из комбинаторики
Рекурсии без оптимизаций (без кэша, без DP)

За сохранение ваших нервных клеток (и для их дальнейшего сохранения) можно подписаться на мой GitHub.

https://github.com/MarieRomanovich

Регулярно пощу репы, общаюсь, кидаю пулл реквесты)).
Welcome to CombatDevZone