linear search (Линейный поиск) – время $O(n)$ и память $O(1)$. Это простейший алгоритм поиска подходящий для неотсортированных данных, который последовательно проверяет каждый элемент до тех пор, пока не будет найден ключ или пока коллекция не будет полностью пройдена.

Binary Search (Бинарный поиск) – время $O(logn)$ и память $O(1)$. Применяется в уже отсортированном массиве. Сравнивает искомое значение с серединой отсортированного массива и исключает половину оставшихся элементов.

Если искомое значение встречается несколько раз, метод может вернуть индекс любого из совпадающих элементов.

fn main() {
    let numbers = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100];
    println!("{:?}", numbers.binary_search(&70));  // Ok(6)
    println!("{:?}", numbers.binary_search(&35));  // Err(3)
    println!("{:?}", numbers.binary_search(&10));  // Ok(0)
}

Binary Search: поиск границ (Lower Bound / Upper Bound)

Binary Search применяется не только для поиска точного значения но и для поиска границ — Lower Bound / Upper Bound.

Это позволяет:

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

Рассмотрим массив, в котором некоторые значения повторяются: [1, 2, 2, 2, 3, 4, 4, 5]

Предположим, нам необходимо найти все вхождения числа 2. Можно последовательно перебрать массив, но в худшем случае потребуется (O(N)) операций. Поскольку массив отсортирован, мы можем воспользоваться бинарным поиском и за $O(logN)$ найти начало и конец диапазона одинаковых элементов.

Для этого используются две границы:

• Lower Bound — индекс первого элемента, который больше или равен искомому значению.
• Upper Bound — индекс первого элемента, который строго больше искомого значения.

В Rust эти операции можно выполнить с помощью стандартного метода slice::partition_point():

fn main() {
    let numbers = [1, 2, 2, 2, 3, 4, 4, 5];
    let target = 2;

    let lower = numbers.partition_point(|&x| x < target);
    let upper = numbers.partition_point(|&x| x <= target);

    println!("Lower Bound: {lower}"); // 1
    println!("Upper Bound: {upper}"); // 4

    println!("Количество вхождений: {}", upper - lower); // 3
    println!("Диапазон индексов: {lower}..{upper}"); // 1..4
}

В данном примере Lower Bound равен 1, а Upper Bound — 4. Следовательно, все вхождения числа 2 находятся в диапазоне индексов 1..4. Правая граница не включается, поэтому количество вхождений вычисляется как разность двух границ: 4 - 1 = 3.

Binary Search on Answer (бинарный поиск по ответу) — это приём, при котором бинарный поиск применяется не для нахождения элемента в массиве, а для нахождения минимального или максимального значения, при котором выполняется заданное условие. Например, обычный Binary Search ищет число в отсортированном массиве. Binary Search on Answer ищет ответ в диапазоне возможных значений, используя проверку вида: «Можно ли решить задачу с таким значением?»

Пример: есть несколько файлов, которые нужно скопировать на 3 сервера. Файлы нельзя разделять, а порядок файлов при распределении сохраняется. Нужно распределить их между серверами так, чтобы максимальная суммарная загрузка одного сервера была минимальной. Размеры файлов в гигабайтах: [10, 20, 30, 40, 50], их нужно распределить между тремя серверами.

Возможное распределение при лимите 60 GB

• Сервер 1: 10 + 20 = 30 GB
• Сервер 2: 30 GB
• Сервер 3: 40 + 50 = 90 GB

Такое распределение не подходит: третий сервер получает 90 GB, то есть превышает лимит 60 GB.

При лимите 90 GB распределение уже возможно:

• Сервер 1: 10 + 20 + 30 = 60 GB
• Сервер 2: 40 GB
• Сервер 3: 50 GB

Но, возможно, лимит можно уменьшить. Как найти минимальный подходящий лимит, не перебирая все значения от 50 до 150?

fn can_distribute(files: &[u32], servers: usize, limit: u32) -> bool {
    let mut used_servers = 1;
    let mut current_load = 0;
    for &file in files {
        if file > limit {
            return false;
        }
        if current_load + file > limit {
            used_servers += 1;
            current_load = file;
        } else {
            current_load += file;
        }
    }
    used_servers <= servers
}
fn min_max_load(files: &[u32], servers: usize) -> u32 {
    let mut left = *files.iter().max().unwrap();
    let mut right: u32 = files.iter().sum();
    while left < right {
        let mid = left + (right - left) / 2;
        if can_distribute(files, servers, mid) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    left
}
fn main() {
    let files = [10, 20, 30, 40, 50];
    println!("минимальный подходящий лимит = {} GB", min_max_load(&files, 3)); // 60
}

Где здесь бинарный поиск?

Мы ищем ответ в диапазоне от 50 до 150:

• 50 — размер самого большого файла, меньше этого лимита задача невозможна.
• 150 — сумма размеров всех файлов; такой лимит всегда позволяет разместить их на одном сервере.

На каждом шаге проверяем среднее значение mid. Если файлы можно распределить при этом лимите, пробуем уменьшить лимит. Если нельзя — увеличиваем его.

Для этого примера минимальный максимум равен 60 GB: распределение [10, 20, 30], [40], [50] использует три сервера, и ни один не загружен больше чем на 60 GB.

Временная сложность — $O(N\log S)$, где N — число файлов, а S — сумма их размеров. Это при условии, что проверка распределения выполняется за $O(N)$.

Interpolation Search (Интерполяционный поиск) – время $O(loglogn)$. Используется в больших отсортированных числовых массивах с приблизительно равномерным распределением. Предсказывает приблизительную позицию элемента на основании его значения, минимального и максимального значений диапазона. Например, если числа распределены равномерно от 0 до 1000, значение 900 логично искать ближе к концу массива.

fn interpolation_search(arr: &[i32], target: i32) -> Option<usize> {
    if arr.is_empty() {
        return None;
    }
    let mut low = 0;
    let mut high = arr.len() - 1;
    while low <= high
        && target >= arr[low]
        && target <= arr[high]
    {
        if arr[low] == arr[high] {
            return if arr[low] == target {
                Some(low)
            } else {
                None
            };
        }
        let pos = low
            + (((target as i64 - arr[low] as i64)
                * (high - low) as i64)
                / (arr[high] as i64 - arr[low] as i64)) as usize;

        if arr[pos] == target {
            return Some(pos);
        }
        if arr[pos] < target {
            low = pos + 1;
        } else {
            if pos == 0 {
                return None;
            }
            high = pos - 1;
        }
    }
    None
}
fn main() {
    let numbers = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100];
    println!("{:?}", interpolation_search(&numbers, 70)); // Some(6)
    println!("{:?}", interpolation_search(&numbers, 35)); // None
    println!("{:?}", interpolation_search(&numbers, 10)); // Some(0)
    println!("{:?}", interpolation_search(&numbers, 110)); // None
}

Здесь позиция вычисляется по формуле:

$$pos=low+\frac{(target-arr[low])(high-low)}{arr[high]-arr[low]}$$

Например, для массива [10, 20, 30, ..., 100] поиск числа 70 сразу оценивает позицию около индекса 6, вместо того чтобы последовательно проверять элементы.

Главное отличие от Binary Search: интерполяционный поиск эффективен для отсортированных массивов с примерно равномерным распределением значений, а Binary Search стабильно работает за $O(logN)$ независимо от распределения значений.

Exponential Search (Экспоненциальный поиск) – время $O(logn)$. Сначала быстро находит диапазон, в котором может находиться элемент, проверяя позиции 1, 2, 4, 8, 16 и далее. Затем применяет Binary Search внутри найденного диапазона.

Exponential Search (решает проблему по сравнению с обычным Binary Search, особенно полезен, когда искомый элемент находится близко к началу большого массива) он позволяет найти подходящий диапазон, когда заранее неизвестно, насколько далеко находится искомый элемент, например при поиске в очень большом отсортированном массиве или в последовательности с неизвестной границей.

fn exponential_search(arr: &[i32], target: i32) -> Option<usize> {
    if arr.is_empty() {
        return None;
    }
    if arr[0] == target {
        return Some(0);
    }
    let mut bound = 1;
    while bound < arr.len() && arr[bound] < target {
        bound *= 2;
    }
    let left = bound / 2;
    let right = bound.min(arr.len() - 1);

    arr[left..=right]
        .binary_search(&target)
        .ok()
        .map(|index| left + index)
}
fn main() {
    let numbers = [2, 5, 8, 12, 16, 23, 38, 45, 56, 72, 91];
    println!("index = {:?}", exponential_search(&numbers, 23)); // Some(5)
    println!("index = {:?}", exponential_search(&numbers, 56)); // Some(8)
    println!("index = {:?}", exponential_search(&numbers, 20)); // None
}

Search by Index – поиск можно ускорить, заранее организовав данные в подходящую структуру (HashMap, Tree, Trie). Например, для неотсортированного массива можно построить дополнительный HashMap, который позволит искать элементы по ключу за $O(1)$ в среднем вместо $O(n)$. Однако такой индекс требует дополнительной памяти для хранения ключей и ссылок на исходные элементы. Это особенно выгодно, когда поиск выполняется многократно, поскольку затраты на создание индекса окупаются за счёт ускорения последующих запросов.

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

Tree Search

Поиск данных в иерархической структуре, где элементы представлены узлами, связанными отношениями родитель–потомок.

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

Основные подходы:

• BST Search — поиск по упорядоченным ключам бинарного дерева поиска. Если ключ меньше текущего — переходим влево, если больше — вправо. В сбалансированном BST поиск занимает $O(logn)$.

• DFS (Depth-First Search) — поиск в глубину. Сначала исследует одну ветку дерева до конца, затем возвращается и проверяет другие. Подходит для поиска узлов, обхода вложенных структур и исследования путей.

• BFS (Breadth-First Search) — поиск в ширину. Сначала проверяет все узлы текущего уровня, затем переходит к следующему. Позволяет найти ближайший к корню подходящий узел и кратчайший путь по количеству рёбер.

Graph Search для поиска связи, достижимость и пути между объектами

SICP Глава 1. Построение абстракций с помощью процедур

Игра Turing Complete. Уровень: Tower of Alloy

Где рекурсия действительно применяется

Рекурсия особенно естественна для деревьев. Например, при обходе файловой системы функция обрабатывает содержимое каталога, а при обнаружении вложенного каталога выполняет те же действия для него.

Что происходит в памяти — Call Stack

Каждый вызов функции сохраняет своё состояние: аргументы, локальные переменные и место, куда нужно вернуться после завершения вызова. Cлишком большая глубина рекурсии может вызвать Stack Overflow или если базовый случай не достигается или не определен, может возникнуть проблема переполнения стека.

При рекурсии новые вызовы помещаются в Call Stack (стек вызовов). Когда достигается базовый случай, функции завершаются в обратном порядке. Т.е. функция может продолжить вычисления после возвращения вложенного вызова.

A → B → C → возврат C → возврат B → возврат A

Итерация обычно быстрее и экономнее по памяти для простых повторений, не создаёт вложенных вызовов, но для сложных структур может потребовать явного управления стеком. При рекурсии стек вызовов автоматически запоминает, где мы остановились и куда нужно вернуться после обработки вложенной задачи. При итерации иногда приходится создавать собственный стек (Stack), чтобы хранить эту информацию. Поэтому обход дерева это естественно для рекурсивного подхода, так как сам путь сохраняется в стеке вызовов, а для итеративного способа придется сохранять путь отдельно.

Direct Recursion — прямая рекурсия, функция непосредственно вызывает саму себя.

fn recursion(n: u32) {
    // Base Case
    if n == 0 {
        return; 
    }
    
    // Recursive Case
    // println!("{n}");// 5 4 3 2 1  
    recursion(n - 1); 
    println!("{n}"); // 1 2 3 4 5  
}
fn main() {
    recursion(5);
}

Рекурсивная функция и рекурсивный процесс — не одно и то же.

• Рекурсивная функция — функция вызывает саму себя.
• Рекурсивный процесс — вычисление, в котором по мере углубления рекурсии накапливаются незавершённые операции.

Рекурсивная функция может порождать итеративный процесс. Важно смотреть на то, как растут время вычисления, количество отложенных операций и используемая память.

1. Рекурсивный процесс (recursive process). Функция вызывает саму себя, а промежуточные операции откладываются до возвращения результата.

Например, факториал: $n!=n\cdot (n-1)!$

fn factorial(n: u64) -> u64 {
   let mut res = 1;
    if n == 0 {
        return res;
    } else {
        println!("down {n}");
        res = n * factorial(n - 1);
    }
    println!("up {n}");
    return res;
}
fn main(){
    let n: u64 = 4;
    println!("factorial({n}) = {}", factorial(n)); 
}

При factorial(4) вызовы накапливаются: 4 * (3 * (2 * (1 * 1))). Стек вызовов растёт с n, поэтому память — O(n).

Опасность рекурсивного процесса (recursive process) в том, что по мере углубления рекурсии накапливаются незавершённые операции до момента срабатывания базового случая. Каждому вызову функции может требоваться отдельный стековый кадр, в котором хранятся аргументы, локальные переменные и информация для продолжения вычислений после возврата из вложенного вызова.

factorial(4)
└── 4 * factorial(3)
        └── 3 * factorial(2)
                └── 2 * factorial(1)
                        └── 1 * factorial(0)
                                └── 1

После достижения базового случая вызовы начинают возвращать результаты в обратном порядке:

factorial(0) = 1
factorial(1) = 1 * 1 = 1
factorial(2) = 2 * 1 = 2
factorial(3) = 3 * 2 = 6
factorial(4) = 4 * 6 = 24

2. Итеративный процесс (iterative process). Рекурсивная функция может описывать процесс, который не накапливает отложенные вычисления. На каждом шаге состояние вычисления обновляется и передаётся следующему рекурсивному вызову через параметры. Все необходимые промежуточные результаты сохраняются в этом состоянии, поэтому после возврата из рекурсивного вызова не требуется выполнять дополнительные операции.

fn factorial(n: u64) -> u64 {
    fn iter(product: u64, counter: u64, max: u64) -> u64 {
        if counter > max {
            product
        } else {
            iter(product * counter, counter + 1, max)
            // это признак хвостовой ф-ции, так как после завершения этого вызова функция ничего больше не делает, 
            // она сразу возвращает полученный результат.
            // Если бы `iter() + 7` т.е. с чем-то складывалась, то тогда бы это была обычная рекурсия с накоплением вычислений
        }
    }

    iter(1, 1, n)
}
fn main(){
    let n: u64 = 4;
    println!("factorial({n}) = {}", factorial(n)); 
}

iter(1, 1, 4)
iter(1, 2, 4)
iter(2, 3, 4)
iter(6, 4, 4)
iter(24, 5, 4)
→ 24

Есть важный нюанс Rust: язык не гарантирует оптимизацию хвостовой рекурсии. Поэтому, хотя процесс логически итеративный, эта реализация всё ещё может использовать $O(N)$ памяти стека.

Tail Recursion — случай, когда рекурсивный вызов является последним действием функции. Некоторые языки и компиляторы могут оптимизировать такие вызовы, но в Rust гарантировать подобную оптимизацию нельзя.

Логически каждый шаг передаёт следующему вызову обновлённое состояние вычисления. Предыдущие состояния больше не нужны, поэтому при оптимизации хвостовой рекурсии можно не сохранять отдельный стековый кадр для каждого вызова. Однако Rust не гарантирует такую оптимизацию, поэтому стек может расти с глубиной рекурсии. Он может оставить обычные вложенные вызовы, каждый из которых занимает место в стеке.

Но если нужно, чтобы программа на Rust действительно использовала постоянный объём памяти, надёжнее написать цикл for.

Итеративный процесс можно реализовать без накопления отложенных вычислений.

Например, факториал с аккумулятором:

fn factorial(n: u64) -> u64 {
    let mut result = 1;

    for i in 1..=n {
        result *= i;
    }

    result
}
fn main(){
    let n: u64 = 4;
    println!("factorial({n}) = {}", factorial(n)); 
}

Здесь состояние вычисления хранится в result, дополнительная память — $O(1)$.

3. Древовидная рекурсия (tree recursion). Функция порождает несколько рекурсивных вызовов.

Классический пример — наивный Фибоначчи: $F(n)=F(n-1)+F(n-2)$

fn fib(n: u32) -> u64 {
    match n {
        0 => 0,
        1 => 1,
        _ => fib(n - 1) + fib(n - 2),
    }
}
fn main(){
    let n: u32 = 10;
    println!("fib({n}) = {}", fib(n)); 
}

Повторные вычисления, наивный рекурсивный Fibonacci многократно вычисляет одни и те же значения.

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2)
│   │   └── fib(1)
│   └── fib(2)
└── fib(3)  ← повторное вычисление!
    ├── fib(2)  ← тоже вычисляется повторно
    └── fib(1)

Количество вызовов растёт экспоненциально, поэтому программа может работать очень медленно даже при сравнительно небольшом N.Временная сложность экспоненциальная — $O(2^n)$, а глубина стека — $O(n)$.

Повторные вычисления иногда можно устранить с помощью Memoization — сохранения уже полученных результатов. Подробнее это относится к Dynamic Programming.

Например результаты вычисления можно сохранять, что бы не вычислять их заново.

fn fib(n: usize, memo: &mut Vec<Option<u64>>) -> u64 {
    if let Some(value) = memo[n] {
        return value;
    }
    let result = match n {
        0 => 0,
        1 => 1,
        _ => fib(n - 1, memo) + fib(n - 2, memo),
    };

    memo[n] = Some(result);
    result
}
fn main() {
    let n: usize = 10;
    let mut memo = vec![None; n + 1];
    println!("fib({n}) = {}", fib(n, &mut memo));
}

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

4. Indirect Recursion — косвенная рекурсия, когда функция A вызывает функцию B, которая снова вызывает A.

Пример: рекурсивный парсер, в котором функция разбора выражения вызывает разбор скобок, а разбор скобок снова вызывает разбор выражения.

fn parse_expression(input: &str) {
    println!("Разбираем выражение: {input}");

    if input.starts_with('(') && input.ends_with(')') {
        parse_parentheses(input);
    }
}
fn parse_parentheses(input: &str) {
    println!("Разбираем скобки: {input}");

    let inner = &input[1..input.len() - 1];
    parse_expression(inner);
}
fn main() {
    parse_expression("((42))");
}

Где применяется Divide and Conquer

Одно из главных преимуществ Divide and Conquer — возможность выполнять независимые подзадачи параллельно. Разделение задачи на независимые части лишь создаёт возможность выполнять их одновременно. Но использование потоков, асинхронности или нескольких ядер не всегда ускоряет программу.

Например, при Merge Sort можно сортировать левую и правую половины массива одновременно на разных ядрах процессора, а затем объединить результаты.

Но здесь есть ограничения:

• Стоимость разделения: создание подзадач тоже требует работы.
• Стоимость объединения: результаты иногда сложно или дорого собирать.
• Маленькие задачи: затраты на параллелизм могут превышать выигрыш.
• Память: отдельные подзадачи и промежуточные результаты иногда требуют дополнительной памяти.

Отличие от Dynamic Programming

Divide and Conquer обычно работает с независимыми подзадачами. Например, сортировка левой и правой половин массива не требует повторного решения одних и тех же подзадач.

Dynamic Programming применяется, когда подзадачи пересекаются и одни и те же результаты нужны многократно. Чтобы избежать повторной работы, результаты сохраняются и используются повторно.

Divide and Conquer определяет, как разделить задачу, а Recursion, Async и Parallelism — как организовать выполнение её частей. Наибольший выигрыш обычно получается, когда крупные независимые CPU-задачи (арифметика) выполняются параллельно, а мелкие — последовательно.

• Мало вычислений → последовательное выполнение.
• Много независимых вычислений → Parallelism / Thread Pool.
• Много операций ожидания → Async / Concurrency.
• Много мелких вычислительных подзадач → Thread Pool с группировкой.

Divide and Conquer + Parallelism: Обрабатываем изображение размером 20 000 × 20 000 пикселей. Делим его на независимые области, распределяем их по ядрам CPU через Rayon, затем собираем результат.

Divide and Conquer + Async/Concurrency: Необходимо получить и обработать данные из 1000 удалённых источников. Разделяем источники на группы, асинхронно загружаем данные с ограничением числа одновременных запросов, после чего объединяем результаты. Выбираем, когда основное время уходит на ожидание сети, а не на вычисления. Если последующая обработка данных тяжёлая, её можно отдельно передать в CPU-пул.

Хороший пример Divide and Conquer (разделяй и властвуй) — алгоритм сортировки Merge Sort (сортировка слиянием), разделить большую задачу на меньшие, решить их отдельно и объединить результаты.

Сложность Merge Sort — $O(n\log n)$ по времени и $O(n)$ по дополнительной памяти в этой реализации.

// Каждый вызов merge_sort порождает два рекурсивных вызова, 
// они образуют дерево вызовов (Tree Recursion)
fn merge_sort(arr: &[i32]) -> Vec<i32> {
    // Base case: массив из 0 или 1 элемента уже отсортирован
    if arr.len() <= 1 {
        return arr.to_vec();
    }
    // Divide: делим массив пополам
    let mid = arr.len() / 2;
    let left = merge_sort(&arr[..mid]);
    let right = merge_sort(&arr[mid..]);
    // Combine: объединяем отсортированные части
    merge(&left, &right)
}
fn merge(left: &[i32], right: &[i32]) -> Vec<i32> {
    let (mut i, mut j) = (0, 0);
    let mut result = Vec::with_capacity(left.len() + right.len());

    while i < left.len() && j < right.len() {
        if left[i] <= right[j] {
            result.push(left[i]);
            i += 1;
        } else {
            result.push(right[j]);
            j += 1;
        }
    }
    result.extend_from_slice(&left[i..]);
    result.extend_from_slice(&right[j..]);
    result
}
fn main() {
    let arr = [8, 3, 5, 4, 7, 6, 1, 2];
    println!("{:?}", merge_sort(&arr));
}

Stable Sort и Unstable Sort — эти понятия описывают, сохраняет ли алгоритм исходный порядок элементов с одинаковым ключом.

Зачем нужна стабильность? Например, мы сначала отсортировали сотрудников по имени, а потом стабильно отсортировали по зарплате. В результате сотрудники будут упорядочены по зарплате, а при одинаковой зарплате — по имени.

Стандартная сортировка Rust уже использует алгоритмы, подобранные для практического применения: sort() гарантирует стабильность, а sort_unstable() не гарантирует её и обычно не требует выделения дополнительного массива для сортировки.

In-place Sort — сортировка, которая работает непосредственно с исходным массивом и требует очень мало дополнительной памяти, обычно $O(1)$ для самой сортировки.

External Sort применяется, когда весь объём данных не помещается в оперативную память (RAM).

Как выбирать сортировку:

Сначала определить, нужна ли сортировка вообще. Затем оценить объём данных, требования к стабильности, памяти и частоте обновлений. И только при специальных ограничениях выбирать специализированный алгоритм.

В большинстве случаев достаточно стандартного sort() или sort_unstable(). Специализированные решения выбираются только тогда, когда объём данных, память или характер задачи делают обычную сортировку невыгодной.

Например, у нас есть 1 миллион пользователей, и нужно работать с их данными.

1. Нужна ли сортировка? Если требуется найти пользователя по ID — нет, лучше использовать HashMap с поиском $O(1)$ в среднем. Если нужно вывести пользователей по возрасту — сортировка нужна.
2. Объём данных: 1 миллион записей помещается в RAM — используем стандартную сортировку $O(nlogn)$. Если данные занимают 500 ГБ и не помещаются в RAM — External Merge Sort.
3. Стабильность: если сортируем пользователей по возрасту и хотим сохранить их исходный порядок среди ровесников — Stable Sort. Если порядок ровесников неважен — Unstable Sort.
4. Память: если дополнительной памяти мало — предпочтительна сортировка с минимальными дополнительными выделениями памяти, например sort_unstable() в Rust.
5. Частота обновлений: если пользователи постоянно добавляются, а нам необходимо поддерживать их в отсортированном порядке — лучше использовать B-Tree или индекс базы данных, чем заново сортировать весь массив после каждого добавления.
6. Специальные ограничения: если нужны только 10 самых старших пользователей — используем Top-K вместо сортировки всех миллиона записей.

Greedy не всегда приводит к оптимальному решению. Он работает только в задачах, где локально оптимальный выбор не мешает получить глобально оптимальный результат. Так как алгоритм просто берет первое лучшее и не учитывает, что можно взять вариант хуже но его комбинация с другими вариантами в итоге даст глобально лучший результат. Но иногда используется сознательно ради скорости.

Где Greedy действительно применяется:

Самое важное в изучении этой темы — научиться определять, когда локально оптимальный выбор действительно гарантирует глобально оптимальный результат, а когда нет.

Пример: есть список задач с временем начала и окончания. Нужно выполнить как можно больше задач за рабочий день.

#[derive(Debug)]
struct Task {
    name: &'static str,
    start: u32,
    end: u32,
}
fn select_tasks(tasks: &mut Vec<Task>) -> Vec<&'static str> {
    // Сортируем задачи по времени окончания
    tasks.sort_by_key(|task| task.end);

    let mut selected = Vec::new();
    let mut last_end = 0;
    for task in tasks.iter() {
        // Выбираем задачу, если она не пересекается с предыдущей
        if task.start >= last_end {
            selected.push(task.name);
            last_end = task.end;
        }
    }
    selected
}
fn main() {
    let mut tasks = vec![
        Task { name: "A", start: 9, end: 11 },
        Task { name: "B", start: 9, end: 10 },
        Task { name: "C", start: 10, end: 12 },
        Task { name: "D", start: 11, end: 13 },
        Task { name: "E", start: 12, end: 14 },
    ];
    let result = select_tasks(&mut tasks);
    println!("{:?}", result);
}

Алгоритм:

1. Сначала сортируем задачи по времени окончания.
2. Выбираем задачу, которая заканчивается раньше остальных.
3. Следующую задачу выбираем только тогда, когда она начинается после окончания предыдущей.
4. Повторяем, пока не закончатся задачи.

Почему это Greedy? Потому что на каждом шаге мы выбираем задачу с самым ранним временем окончания среди доступных (локально лучший). Не перебираем все комбинации и не возвращаемся к предыдущим решениям.

Если подзадачи независимы и не повторяются, хранение всех промежуточных результатов может не дать преимущества. В таком случае часто достаточно Divide and Conquer.

Dynamic Programming невыгодно применять когда слишком много состояний, тогда таблица DP может потребовать огромного количества памяти и времени. Либо если мало вычислений, тогда накладные расходы на хранение и поиск промежуточных результатов могут превышать выигрыш.

Два способа реализации DP (не вычислять одинаковую подзадачу повторно)

1. Memoization (Top-Down) — начинаем с исходной задачи, рекурсивно разбиваем её на меньшие и сохраняем результаты по мере вычисления. Если подзадача уже решена, берём значение из памяти.
2. Tabulation (Bottom-Up) — начинаем с самых простых подзадач и последовательно вычисляем более сложные, используя уже готовые результаты. Обычно реализуется циклом.

Практический пример: числа Фибоначчи. Наивная рекурсивная реализация с повторными вычислениями

Последовательность Фибоначчи определяется следующим образом: $$F(n)=F(n-1)+F(n-2)$$

Начальные значения: $F(0)=0,F(1)=1$

fn fib(n: u32) -> u64 {
    match n {
        0 => 0,
        1 => 1,
        _ => fib(n - 1) + fib(n - 2),
    }
}
fn main() {
    let n = 10;
    println!("fib({n}) = {}", fib(n));
}

Практический пример: числа Фибоначчи через Memoization (сохранение результатов уже вычисленных подзадач)

fn fib(n: usize, memo: &mut Vec<Option<u64>>) -> u64 {
    // Проверяем, вычисляли ли уже fib(n)
    if let Some(value) = memo[n] {
        return value;
    }

    // Вычисляем результат
    let result = match n {
        0 => 0,
        1 => 1,
        _ => fib(n - 1, memo) + fib(n - 2, memo),
    };

    // Сохраняем результат
    memo[n] = Some(result);
    result
}
fn main() {
    let n = 10;
    let mut memo = vec![None; n + 1];
    println!("fib({n}) = {}", fib(n, &mut memo));
}

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

fn fib(n: usize) -> u64 {
    if n <= 1 {
        return n as u64;
    }

    let mut dp = vec![0u64; n + 1];

    dp[0] = 0;
    dp[1] = 1;

    for i in 2..=n {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    dp[n]
}
fn main() {
    println!("{}", fib(10)); // 55
}

Где Backtracking применяется:

Особенно полезен Backtracking, когда нужно найти допустимую комбинацию при множестве ограничений, а не просто обнаружить элемент в структуре данных.

Пример: Sudoku 9×9

1. Находим первую пустую клетку.
2. Пробуем поставить цифру от 1 до 9.
3. Если цифра не нарушает правила Sudoku — ставим её и рекурсивно продолжаем решение.
4. Если дальше решить Sudoku не получается — отменяем выбор (board[row][col] = 0) и пробуем следующую цифру.
5. Если пустых клеток больше нет — задача решена.

type Board = [[u8; 9]; 9];

// Проверяем, можно ли поставить число в указанную клетку.
fn is_valid(board: &Board, row: usize, col: usize, num: u8) -> bool {
    for i in 0..9 {
        // Проверка строки и столбца.
        if board[row][i] == num || board[i][col] == num {
            return false;
        }
    }
    // Начало квадрата 3×3.
    let start_row = (row / 3) * 3;
    let start_col = (col / 3) * 3;
    for r in start_row..start_row + 3 {
        for c in start_col..start_col + 3 {
            if board[r][c] == num {
                return false;
            }
        }
    }
    true
}
fn solve(board: &mut Board) -> bool {
    for row in 0..9 {
        for col in 0..9 {
            if board[row][col] == 0 {
                // Пробуем все возможные варианты.
                for num in 1..=9 {
                    if is_valid(board, row, col, num) {
                        board[row][col] = num;
                        // Продолжаем поиск решения.
                        if solve(board) {
                            return true;
                        }
                        // Backtracking: отменяем выбор.
                        board[row][col] = 0;
                    }
                }
                // Ни одна цифра не подошла.
                return false;
            }
        }
    }
    // Пустых клеток нет — Sudoku решено.
    true
}
fn main() {
    let mut board: Board = [
        [0,0,9, 0,0,0, 0,0,0],
        [0,8,0, 6,0,5, 0,2,0],
        [5,0,1, 0,7,8, 0,0,0],

        [0,0,0, 0,0,0, 7,0,0],
        [7,0,6, 0,4,0, 1,0,2],
        [0,0,4, 0,0,7, 0,0,0],

        [0,0,0, 7,2,0, 9,0,3],
        [0,9,0, 3,0,1, 2,8,0],
        [0,0,0, 0,0,0, 6,0,0],
    ];
    if solve(&mut board) {
        for row in board {
            println!("{row:?}");
        }
    } else {
        println!("Решение не найдено");
    }
}

Например, алгоритм поставил 1 в пустую клетку. Это не нарушает правил прямо сейчас. Но через несколько рекурсивных вызовов выясняется, что следующую клетку невозможно заполнить никакой цифрой.

Тогда solve() возвращает false, предыдущая цифра удаляется, и алгоритм пробует 2, затем 3 и так далее.

Backtracking отличается от полного перебора (Brute Force) тем, что отбрасывает целую ветвь вариантов, как только обнаруживает нарушение ограничений. Алгоритм не обязан строить все возможные заполнения Sudoku и проверять их только в конце.

Какие бывают задачи поиска в строках:

1. Поиск точной подстроки. Самый простой подход — проверять возможные позиции начала подстроки и сравнивать символы.

   Такой наивный алгоритм может требовать $O(n\times m)$ времени, где n — длина текста, m — длина искомого шаблона.

   Для ускорения существуют специализированные алгоритмы:

   • KMP (Knuth–Morris–Pratt) — использует информацию о совпавших префиксах, чтобы не сравнивать одни и те же символы повторно. $O(n+m)$.
   • Boyer–Moore — сравнивает шаблон с конца и может пропускать большие участки текста, особенно когда шаблон достаточно длинный.
   • Rabin–Karp — использует хеши подстрок, что удобно для некоторых задач поиска множества шаблонов и сравнения фрагментов.

2. Regular Expressions — поиск по шаблонам. Применяется при: валидации формата, извлечение значений из текста, поиск логов по определённым шаблонам. Regex не следует использовать для произвольного разбора сложных вложенных языковых конструкций, например полноценного HTML. Для таких задач нужны парсеры.

   Скорость Regex зависит от движка и особенностей шаблона. Некоторые backtracking-движки могут работать очень медленно на неудачных выражениях.

3. Fuzzy Matching — приблизительное совпадение. Используется, когда строка может содержать ошибки или отличаться от искомой. Один из способов — Levenshtein Distance.

   Для больших словарей расстояние обычно не вычисляют подряд для каждого слова без дополнительных способов отбора кандидатов.

4. Поиск множества шаблонов — Aho–Corasick. Допустим, нужно искать слова error, warning, timeout и ещё 100 шаблонов в гигабайтах логов. Можно запускать отдельный поиск для каждого слова, но тогда текст придётся просматривать многократно.

   Aho–Corasick предварительно организует шаблоны в структуру, позволяющую искать их за один проход по тексту.

   Когда применять: фильтрация логов, поиск запрещённых слов, анализ текстов, обнаружение множества сигнатур.

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

Что важно учитывать при работе со строками:

• Регистр: Error и error могут считаться разными строками. Нужно заранее решить, должен ли поиск учитывать регистр.
• Unicode: символы могут иметь разное байтовое представление. Даже визуально одинаковые строки не всегда совпадают побайтово, поэтому иногда нужна Unicode-нормализация.
• Границы слов: поиск cat как подстроки найдёт совпадение и внутри catalog. Если нужно искать отдельное слово, это необходимо учитывать.

Search Engines

Системы для быстрого поиска информации в больших объёмах данных: текстах, документах, каталогах товаров, логах. В отличие от поиска по точному значению (например, ID пользователя), они позволяют находить результаты по словам, фразам, смыслу и различным условиям.

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

Основные подходы:

• Full-Text Search — поиск по словам и фразам. Может учитывать словоформы, опечатки и частичные совпадения. Например, запрос «купить телефон» может находить документы со словами «покупка телефонов».
• Vector / Semantic Search — поиск по смыслу. Тексты преобразуются в числовые векторы (embeddings), отражающие их семантические характеристики. Затем система ищет близкие векторы. Например, запрос «дешёвый автомобиль» может найти описание «бюджетная машина».
• Hybrid Search — объединяет текстовый и семантический поиск, чтобы учитывать одновременно точные слова и смысл запроса.

Примеры технологий: Elasticsearch, OpenSearch, Apache Solr, Meilisearch, Typesense, Qdrant.

Примеры применения:

• Интернет-магазин: пользователь вводит «беспроводные наушники Sony». Система ищет товары не только по названию, но и по описанию, бренду и характеристикам. Результаты можно фильтровать по цене, категории, наличию и сортировать по релевантности.
• Поиск по документам: пользователь вводит «ошибка подключения к базе данных». Система находит документы, в которых встречаются эти слова или их комбинации, даже если они находятся в разных частях текста.
• Поиск по логам: разработчик ищет все ошибки timeout за последние 24 часа, относящиеся к определённому сервису, и анализирует частоту их возникновения.
• Поиск по смыслу: пользователь спрашивает «как восстановить доступ к аккаунту», а система находит статью «Сброс забытого пароля», хотя формулировки различаются.

Компьютер — это машина, которая выполняет инструкции. Если взять обычную программу и задать ей одинаковые исходные данные, она выполнит одни и те же операции и получит одинаковый результат. Если алгоритму передать одинаковое начальное состояние, он воспроизведёт ту же последовательность. Именно поэтому такие генераторы называют PRNG (Pseudo-Random Number Generator) — генераторами псевдослучайных чисел.

Для получения случайности компьютер может использовать источники энтропии (внешние по отношению к этому алгоритму физические процессы)

Seed — это начальное значение, от которого генератор строит последовательность псевдослучайных чисел.

Полезно получать одинаковые псевдослучайные числа:

• при тестировании алгоритмов;
• при отладке;
• в симуляциях;
• в играх, когда нужно воспроизвести определённую последовательность событий.

У нас уже есть алгоритм PRNG, который умеет генерировать псевдослучайную последовательность. Но чтобы эта последовательность была непредсказуемой при запуске программы, нам нужно получить непредсказуемое начальное значение — seed. Для этого компьютер обращается к источнику энтропии: например, к аппаратному генератору случайных чисел, который измеряет физические процессы (электрический шум и т. п.), либо к системному генератору ОС, собирающему энтропию из доступных источников. Полученные случайные данные используются как seed для PRNG. После инициализации PRNG самостоятельно генерирует последовательность, изменяя своё внутреннее состояние при каждом вызове.

extern crate rand;
use rand::{RngExt, SeedableRng};
use rand::rngs::StdRng;

fn pseudorandom(seed: u64){
    let mut rng = StdRng::seed_from_u64(seed);

    for _ in 0..5 {
        let number = rng.random_range(1..=100);
        print!("{number} ");
    }
}
fn main() {
    // Одинаковый seed = одинаковая последовательность
    let mut seed: u64 = 123;
    println!("\n\nSeed: {seed}");
    pseudorandom(123);
    println!("");
    pseudorandom(123);

    // Получаем seed из системного источника случайности
    let mut system_rng = rand::rng();
    seed = system_rng.random();

    // Случайный seed = новая псевдослучайная последовательность
    println!("\n\nSeed: {seed}");
    pseudorandom(seed);
    println!("");

    seed = system_rng.random();
    println!("\nSeed: {seed}");
    pseudorandom(seed);
}