Почему мы говорим, что $O(2n+5)$ — это то же самое, что $O(n)$?

Потому что при стремлении n к бесконечности, константы 2 и 5 становятся пренебрежимо малыми.

Сравните если n=1_000_000 то 2n+5=2_000_005, это в 2 раза больше, чем n, рост остается линейным.

А вот разница между $O(n)$ и $O(n^2)$ при n=1_000_000 — это уже разница между 1_000_000 и 1_000_000_000_000. Эта разница будет только бесконечно увеличиваться с ростом n

Так же:

Сложность $O(A+B)$ — последовательный перебор независимых наборов, сперва набора данных A потом B

for (int a: arrA){
    print(a);
}
for (int b: arrB){
    print(b);
}

Сложность $O(A\ast B)$ — зависимый перебор данных, на каждый елемент набора A выполняется полный перебор набора B

for (int a: arrA){
    for (int b: arrB){
        print(a, b);
    }
}

Сложность $O(N+N)=O(N)$ — последовательный перебор зависимых наборов

for (int a: arrA){
    print(a);
}
for (int a: arrA){
    print(a);
}

Сложность $O(n^2)$ — зависимый перебор данных, когда на каждый елемент набора A выполняется полный перебор того же набора A

for (int a: arrA){
    for (int b: arrA){
        print(a, b);
    }
}

Сложность $O(\surd n)$ — когда перебор идет до корня из n. Вместо перебора всех n элементов, мы перебираем только √n элементов.

Что такое корень:

√n = число, которое умножили само на себя и получили n

√25=5, потому что 5×5=25

$O(\surd n)$ гораздо лучше чем $O(n)$, но хуже чем $O(logn)$:

// Проверяем, является ли число n простым
bool isPrime(int n) {
    if (n < 2) return false;
    
    // Перебираем делители только до sqrt(n)
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            return false;  // Нашли делитель - число не простое
        }
    }
    return true;  // Делителей не найдено - число простое
}

Сложность $O(logn)$ — алгоритм, который отбрасывает половину данных на каждом шаге. На каждой итерации цикла или каждом шаге рекурсии, алгоритм уменьшает объем задачи в 2 или более раз. Это очень эффективно, потому что количество шагов растет очень медленно даже при огромном n.

int n = 100;
while (n > 1) {
    n = n / 2;  // На каждом шаге делим пополам
    printf("%d\n", n);
}

Сложность $O(2^n)$ — когда на каждом элементе ветвимся на 2 варианта, это очень медленно. Уже при n=60, 2ⁿ это огромное значение!

Пример, все возможные подмножества множества:

// n = 3 элемента: {A, B, C}
// Все возможные подмножества:
{}
{A}
{B}
{C}
{A, B}
{A, C}
{B, C}
{A, B, C}

fn main() {
    let arr = [1, 2, 3];
    let n = arr.len();

    // 2^n возможных подмножеств
    for i in 0..(1 << n) {
        print!("{{ ");

        for j in 0..n {
            // Проверяем j-й бит
            if i & (1 << j) != 0 {
                print!("{} ", arr[j]);
            }
        }
        println!("}}");
    }
}

Сложность $O(n!)$ — когда перебираем все возможные перестановки, это катастрофически медленно. Уже при n=20 перебирать все варианты невозможно — их огромное количество!

n = 10 → 10! = 3_628_800 перестановок

Где встречается $O(n!)$:

• Задача коммивояжера (маршрут через N городов)
• Расстановка N ферзей на шахматной доске
• Все возможные анаграммы слова
• Любая задача "перебрать все варианты порядка"

Генерация всех перестановок массива:

fn generate_permutations(arr: &mut [i32], start: usize) {
    if start == arr.len() {
        println!("{arr:?}");
        return;
    }

    for i in start..arr.len() {
        arr.swap(start, i);
        generate_permutations(arr, start + 1);
        arr.swap(start, i);
    }
}
fn main() {
    generate_permutations(&mut [1, 2, 3, 4, 5, 6], 0);
}

Временная сложность алгоритма - константная $O(1)$

Алгоритм всегда занимает одинаковое количество времени, независимо от объема данных. Пример: поиск элемента массива по его индексу.

fn algo_1(v: &[i32], index: usize) -> Option<i32>{
    if index < v.len(){
        return Some(v[index]);
    }
    None    
} 
fn main(){
    let x = &[1, 2, 4];
    unsafe {
        assert_eq!(x.get_unchecked(1), &2);
    }

    // или
    let mut vec = vec![1,2,3];
    vec.push(4);
    vec.pop();

    // или
    assert!(algo_1(&vec, 2).is_some());
}

Временная сложность алгоритма - логарифмическая $O(logN)$

($logN$ это $lo{g}_{2}N$ в какой степени должна быть двойка чтобы получилось N, это и будет количество операций).

Каждая итерация сокращает вдвое количество элементов/значений. Перевод числа в двоичное представление.

Логарифм по основанию a от аргумента x — это степень, в которую надо возвести число a, чтобы получить число x

$lo{g}_{2}64=6$ так как $2^6=64$

Довольно здорово. Подобные алгоритмы уменьшают вдвое объем данных на каждой итерации. Если у вас 100 элементов, то чтобы найти ответ, потребуется около 7 шагов. При наличии 1000 элементов требуется 10 шагов. А для 1000000 элементов требуется всего 20 шагов. Это очень быстро даже для больших объемов данных.

Пример: бинарный поиск.

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 - left) / 2;
        if arr[mid] == target {
            return Some(mid);
        } else if arr[mid] < target {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    None
}
fn main() {
    let arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19];
    println!("{:?}", binary_search(&arr, 13)); // Some(6)
    println!("{:?}", binary_search(&arr, 4));  // None
}

Временная сложность алгоритма - корень из N ($sqrtN$)

Условие выхода из цикла $x^2$ следовательно цикл прекратится когда x >= sqrt N

Корень n-й степени из числа a определяется как такое число b, что b^n=a Здесь n — натуральное число, называемое показателем корня (или степенью корня); как правило, оно больше или равно 2, потому что случай n=1 не представляет интереса.

Пример: Корнями 2-й степени из числа 9 являются +/-3 т.е. $9sqr{t}^2=3$ так как $3^2=9$,а $64sqr{t}^3=4$ так как $4^3=64$

И график $O(sqrtN)$ будет расти быстрее, следовательно медленнее работать чем график $O(logN)$ так как для N=64 => log_2 64 = 2^6 = 64 => 6 это < 64 sqrt^2 = 8^2 = 64 => 8 т.е. для log мы двойку возводим в нужную степень, а для sqrt нужно само число для возведения в квадрат

fn algo_sqrt(n: usize) -> usize {
    let mut x = 0;
    while x * x < n {
        x += 1;
    }
    x
}
fn main() {
    let n = 64;
    let result = algo_sqrt(n);
    println!("n = {n}");
    println!("Iterations result = {result}");
}

Временная сложность алгоритма - линейная $O(N)$ Время выполнения увеличивается пропорционально размеру задачи.

Хорошая производительность. Если у вас 100 элементов, это выполняет 100 единиц работы. При удвоении количества элементов алгоритм будет выполняться ровно в два раза дольше (200 ед. работы). Пример: последовательный поиск, здесь алгоритм последовательно проверяет элементы массива, пока не найдёт искомое значение или пока элементы не закончатся.

fn algo_3(v: &[i32], n: i32) -> bool {
    for i in v {
        if *i == n {
            return true;
        }
    }
    false
}
fn main() {
    let numbers = [10, 20, 30, 40, 50];
    println!("{}", algo_3(&numbers, 30)); // true
    println!("{}", algo_3(&numbers, 99)); // false
}

Временная сложность алгоритма - линейная $O(N+M)$

fn algo_5(n: &[i32], m: &[i32], element: &i32) -> Option<i32> {
    let mut value: Option<i32> = None;
    for &i_n in n {
        if i_n > *element {
            value = Some(i_n);
        }
    }
    let value = value?;
    for &i_m in m {
        if value == i_m {
            return Some(i_m);
        }
    }
    None
}
fn main() {
    let n = [2, 5, 8, 3];
    let m = [1, 3, 5, 9];
    let element = 2;
    println!("{:?}", algo_5(&n, &m, &element)); // Some(3)
}

Временная сложность алгоритма - билинейная $O(N\ast M)$

Достойная производительность. Это немного хуже линейного, но не так уж плохо. Пример: самые быстрые алгоритмы сортировки общего назначения.

Если алгоритм обрабатывает каждый элемент массива размером (N) для каждого элемента массива размером (M)

fn algo_6(n: &[i32], m: &[i32]) -> usize {
    let mut count = 0;
    for i_n in n {// N итераций
        for i_m in m {// M итераций на каждую итерацию внешнего цикла
            if i_n == i_m {
                count += 1;
            }
        }
    }
    count
}
fn main() {
    let n = [1, 2, 3];
    let m = [2, 3, 4, 5];
    println!("{}", algo_6(&n, &m)); // 2
}

Временная сложность алгоритма - полиномиальная (квадратичная) сложность $O(N^2)$

$1+2+3+4+...+N=>O(N^2)$

$N-1\ast N-1=N^2$

Часто встречается в алгоритмах с вложенными циклами.

Как-то медленно. Если у вас 100 элементов, это $100^2=10000$ единиц работы. Удвоение количества предметов делает процесс медленнее в четыре раза (поскольку 2 в квадрате равно 4). Пример: алгоритмы, использующие вложенные циклы, такие как сортировка вставками.

fn bubble_sort(v: &mut [i32]) {
    for i in 0..v.len() {
        for j in 0..v.len().saturating_sub(i + 1) {
            if v[j] > v[j + 1] {
                v.swap(j, j + 1);
            }
        }
    }
}
fn main() {
    let mut numbers = [5, 2, 8, 1, 3];
    println!("Before: {:?}", numbers);
    bubble_sort(&mut numbers);
    println!("After:  {:?}", numbers);
}

// или
for i in 0..n {
  for j in 0..n {
    ...
  }
}

Временная сложность алгоритма - полиномиальная (кубическая) сложность $O(N^3)$

Шаг за пределы квадратичной сложности. По мере увеличения размера задачи время выполнения увеличивается еще быстрее. Это происходит в алгоритмах с тремя вложенными циклами, например в алгоритмах с трехмерными массивами.

Низкая производительность. Если у вас 100 элементов, это $100^3=1000000$ единиц работы. Удвоение входного размера делает его в восемь раз медленнее. Пример: умножение матрицы.

fn matrix_multiply(a: &[Vec<i32>], b: &[Vec<i32>]) -> Vec<Vec<i32>> {
    let n = a.len();
    let mut result = vec![vec![0; n]; n];
    for i in 0..n {
        for j in 0..n {
            for k in 0..n {
                result[i][j] += a[i][k] * b[k][j];
            }
        }
    }
    result
}
fn main() {
    let a = vec![
        vec![1, 2],
        vec![3, 4],
    ];
    let b = vec![
        vec![5, 6],
        vec![7, 8],
    ];
    println!("{:?}", matrix_multiply(&a, &b));
    // [[19, 22], [43, 50]]
}

Временная сложность алгоритма - экспоненциальная $O(2^N)$

$2^0+2^1+2^3+...+2^N=>O(2^N)$

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

Пример: перебираем все подмножества массива

fn generate_subsets(v: &[i32]) {
    let n = v.len();
    for mask in 0..(1_usize << n) {
        let mut subset = Vec::new();
        for i in 0..n {
            if mask & (1 << i) != 0 {
                subset.push(v[i]);
            }
        }
        println!("{subset:?}");
    }
}
fn main() {
    let v = [1, 2, 3];
    generate_subsets(&v);
}

Временная сложность алгоритма - факториал $O(n!)$ Они в основном используются в перестановочных и комбинаторных задачах.

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

Пример: перебор всех перестановок массива.

fn generate_permutations(v: &mut [i32], start: usize) {
    if start == v.len() {
        println!("{v:?}");
        return;
    }
    for i in start..v.len() {
        v.swap(start, i);
        generate_permutations(v, start + 1);
        v.swap(start, i);
    }
}
fn main() {
    let mut v = [1, 2, 3];
    generate_permutations(&mut v, 0);
}