class Algorithms {
public:
Algorithms lecture {
.author = "Р.А. Нестеров"
.year = "2026/27"
.course = "НИУ ВШЭ ПИ, 2 курс"
};
алгоритмы
и структуры данных
// 01. Корректность циклического алгоритма
bool is_cycle_correct();
void insertion_sort(std::vector<int>& arr);
int gcd_euclidean(int a, int b);
int factorial_loop(int n);
// 02. Точная функция временной сложности алгоритма int exact_time_complexity(std::vector<int>& arr);// 03. Порядок роста точной функции сложности void order_of_growth();
->01
01.00
общие вопросы организации курса
цель и задачи курса
информационная поддержка: SmartLMS,
канал и лекционные материалы
общие правила работы и система оценки:
элементы контроля и автоматические оценки
тематическое наполнение первого семестра
void set_course_objectives();
цель и задачи курса
что мы планируем достичь к окончанию двух семестров
🎯 цель
⚙️ задачи
- освоить ключевые парадигмы проектирования алгоритмов
- освоить основные методы анализа временной сложности алгоритмов
- освоить подходы к разработке базовых и продвинутых структур данных
- получить опыт реализации программ на языке программирования C++
🏁 результаты
- точный, асимптотический и амортизированный анализ временной сложности алгоритмов
- разделяй-и-властвуй, жадность, динамическое программирование
- стохастические и приближенные алгоритмы и проблемы разрешимости
- внутренняя организация структур данных различной сложности
void set_course_assessment();
система оценивания
компоненты и правила формирования итоговой оценки за семестр
45% накоп
25% пр
30% экзамен
важно отметить
-
накопленная оценка — доля от максимума обычных баллов $RP$ с учетом бонусных баллов $BP$:
\[\min \left(\frac{RP + BP}{RP_{max}} \cdot 10; 10 \right)\] - правила оценки практики будут рассмотрены на первом занятии
- округление один раз перед итогом: \[\langle X\rangle.49 \longrightarrow \langle X\rangle\]
void set_course_assessment();
система оценивания
условные траектории получения итоговой оценки за семестр
⚡️ без экзамена
автомат «8 баллов» за семестр
- каждая домашняя работа выполнена не менее чем на 70%
- контрольная работа выполнена не менее чем на 70%
- оценка за практические занятия составляет не ниже 8 баллов
📝 cдать экзамен
оценка после устного экзамена
- желание повысить итоговую оценку за семестр и сдать устный экзамен
- не выполнены критерии получения автоматической оценки
- без экзамена не формируется удовлетворительная оценка
⚠️ накоп+пр
итоговая оценка без 30%
- без сдачи экзамена формируется удовлетворительная оценка
- просто не хочется идти на экзамен по тем или иным причинам
- не выполнены критерии получения автоматической оценки
01.01
корректность
циклического алгоритма
сортировка вставками, вычисление факториала
и наибольшего общего делителя
поиск и применение инварианта для обоснования
корректности циклического алгоритма
инициализация, итерация и выход из цикла
контрактное программирование в C++26
#include <vector>
void insertion_sort(std::vector<int>& arr) {
int n = arr.size();
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
arr
#include <vector>
void insertion_sort(std::vector<int>& arr) {
int n = arr.size();
int comparisons = 0;
int swaps = 0;
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
++comparisons;
++swaps;
}
arr[j + 1] = key;
++comparisons;
}
}
- сравнения 0
- перестановки 0
arr
key = arr[1]:
key = arr[2]:
key = arr[3]:
key = arr[4]:
key = arr[5]:
ключевые вопросы
- в каком случае алгоритм сортировки будет называться корректным?
- является ли алгоритм сортировки вставками корректным?
-
как обосновать корректность
циклического алгоритма в общем случае?
bool is_cycle_correct();
инвариант цикла: три точки
как обосновать корректность циклического алгоритма
#include <vector>
void insertion_sort(std::vector<int>& arr) {
int n = arr.size();
for (int i = 1; i < N; ++i) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
INIT
MNT сохранение
TRM
bool is_cycle_correct();
инвариант цикла: три точки
как обосновать корректность циклического алгоритма
#include <vector>
void insertion_sort(std::vector<int>& arr) {
int n = arr.size();
for (int i = 1; i < N; ++i) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
Определение 01.01
важно отметить
- общего способа поиска нварианта для любого цикла найдено не было
-
инвариант, интуитивно, отражает природу вычислений внутри цикла:
какова цель / что уже вычислено / что осталось вычислить - для поиска инварианта можно использовать трассировку цикла
📝 составить утверждение о корректности
🔎 найти инвариант $P$ цикла
💡 обосновать сохранение истинности $P$
#include <vector>
void insertion_sort(std::vector<int>& arr) {
int n = arr.size();
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
утверждение 01.01
для любого массива arr длины $n \ge 1$ верно, что алгоритм insertion_sort упорядочит элементы входного массива в порядке возрастания
условие упорядоченности: $\forall i \in [0, n-2] \colon arr[i] \le arr[i+1]$
доказательство
корректность insertion_sort опирается на инвариант цикла for:
что эквивалентно условию упорядоченности массива $arr[0..i-1]$
-
INIT —
размер массива
и счетчик цикла for $i=1 \Rightarrow arr[0..i-1]=arr[0..0]=arr[0]$
массив тривиально отсортирован -
MNT —
корректность
зависит от цикла while $P_{\mathrm{W}} = \{ \, arr[j+1..i-1] \longrightarrow arr[j+2..i]$
сохраняет порядок $\}$ -
TRM — выход из
основного цикла for$i=n \Rightarrow arr[0..i-1]=arr[0..n-1] \Rightarrow$
массив отсортирован
📝 составить утверждение о корректности
🔎 найти инвариант $P$ цикла
💡 обосновать сохранение истинности $P$
#include <iostream>
unsigned long long factorial_loop(int n) {
if (n < 0) return 0;
unsigned long long fact = 1;
for (int i = 2; i <= n; ++i) {
fact *= i;
}
return fact;
}
int main() {
std::cout << factorial_loop(5);
return 0;
}
$n! = 1 \cdot 2 \cdot . . . \cdot n$
$n! = (n-1)!\cdot n$
утверждение 01.02
для любого целого неотрицательного числа $n$ верно, что алгоритм factorial_loop возвращает корректное значение $n!$
условие корректности: $\forall n \ge 0 \colon \mathrm{fact} = n!$
доказательство
корректность вычисления факториала опирается на инвариант цикла for:
то есть, переменная $\mathrm{fact}$ хранит промежуточный факториал
-
INIT —
начальное значение
fact и счетчика for $i=1 \Rightarrow \mathrm{fact} = (i-1)! = 0! = 1 \Rightarrow$
инвариант $P$ тривиально выполнен -
MNT —
пусть перед $i$-ой итерацией
выполняется $\mathrm{fact} = (i-1)!$:$\mathrm{fact} = \mathrm{fact} \cdot i = (i-1)!\cdot i = i!$
$i = i + 1 \Rightarrow \mathrm{fact} = i! = ((i+1)-1)!$ -
TRM — выход из
основного цикла for$i=n+1 \Rightarrow \mathrm{fact} = ((n+1)-1)! = n! \Rightarrow$
факториал вычислен
📝 составить утверждение о корректности
🔎 найти инвариант $P$ цикла
💡 обосновать сохранение истинности $P$
#include <iostream>
int gcd_euclidean(int a, int b) {
if (a = 0) return b;
if (b = 0) return a;
while (a != b) {
if (a > b) a -= b;
else b -= a;
}
return a;
}
int main() {
std::cout << gcd_euclidean(104, 24);
return 0;
}
$\mathrm{GCD}(a, b) = \mathrm{GCD}(b, a)$
$\mathrm{GCD}(a-b, b) = \mathrm{GCD}(a, b)$
утверждение 01.03
для любой пары целых неотрицательных $a$ и $b$ верно, что алгоритм gcd_euclidean возвращает значение их наибольшего общего делителя
условие корректности: $\forall a,b \geqslant 0 \colon a = \mathrm{GCD}(a, b)$
доказательство
корректность вычисления НОДа опирается на инвариант цикла while:
где $a_0$ и $b_0$ — начальные значения $a$ и $b$
-
INIT — совпадение
с исходными значениями$a=a_0, b=b_0 \Rightarrow$
$\mathrm{GCD}(a, b) = \mathrm{GCD}(a_0, b_0)$ -
MNT —
пусть перед итерацией
$\mathrm{GCD}(a, b) = \mathrm{GCD}(a_0, b_0)$$a > b \Rightarrow \mathrm{GCD}(a-b, b) = \mathrm{GCD}(a, b)$
$b > a \Rightarrow \mathrm{GCD}(a, b-a) = \mathrm{GCD}(a, b)$ -
TRM — значения переменных
сравнялись$a = b \Rightarrow$
$\mathrm{GCD}(a, a) = a = \mathrm{GCD}(a_0, b_0)$
являются ли эти предикаты инвариантами цикла
* клик по ответу покажет, верный ли он
- $P_1 = \{\, a + b = b + a \,\}$
- $P_2 = \{\, 2+2 = 4 \,\}$
- $P_3 = \{\, true \,\}$
условия являются инвариантами, так как сохраняют свою истинность, однако не подходят для обоснования корректности
#include <vector>
void insertion_sort(std::vector<int>& arr) {
int n = arr.size();
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
bool is_cycle_correct();
инвариант цикла: в коде
внедрение инструкций assert или static_assert в программный код
#include <numeric>
#include <cassert>
int gcd_euclidean(int a, int b) {
assert(a > 0 && b > 0);
if (a = 0) return b;
if (b = 0) return a;
int a0 = a, b0 = b;
while (a != b) {
assert(std::gcd(a, b) == std::gcd(a0, b0));
assert(a > 0 && b > 0);
if (a > b) a -= b;
else b -= a;
}
assert(a == std::gcd(a0, b0))
return a;
}
- проверка происходит во время выполнения кода
- проверка сохранения инварианта успешно пройдена
bool is_cycle_correct();
инвариант цикла: в коде
внедрение инструкций assert или static_assert в программный код
#include <numeric>
#include <cassert>
int gcd_euclidean(int a, int b) {
assert(a > 0 && b > 0);
if (a = 0) return b;
if (b = 0) return a;
int a0 = a, b0 = b;
while (a != b) {
assert(std::gcd(a, b) == std::gcd(a0, b0));
assert(a > 0 && b > 0);
if (a > b) b -= a;
else a -= b;
}
assert(a == std::gcd(a0, b0))
return a;
}
- проверка происходит во время выполнения кода
- проверка сохранения инварианта не пройдена
bool is_cycle_correct();
инвариант цикла: в коде
внедрение инструкций assert или static_assert в программный код
#include <numeric>
#include <cassert>
int gcd_euclidean(int a, int b) {
assert(a > 0 && b > 0);
if (a = 0) return b;
if (b = 0) return a;
int a0 = a, b0 = b;
while (a != b) {
assert(std::gcd(a, b) == std::gcd(a0, b0));
assert(a > 0 && b > 0);
if (a > b) a -= 1;
else b -= a;
}
assert(a == std::gcd(a0, b0))
return a;
}
- проверка происходит во время выполнения кода
- проверка сохранения инварианта не пройдена
bool is_cycle_correct();
инвариант цикла: контракты в C++26
внедрение явных предусловий, постусловий и других проверок в программный код
#include <numeric>
#include <contracts>
int gcd_euclidean(const int a, const int b)
pre(a > 0 && b > 0) // предусловие — проверка при входе
post(result: result == std::gcd(a, b)) // постусовие — проверка при выходе
{
if (a = 0) return b;
if (b = 0) return a;
int aTemp = a, bTemp = b;
while (aTemp != bTemp) {
// проверка свойства в конкретный момент выполнения программы
contract_assert(std::gcd(aTemp, bTemp) == std::gcd(a, b));
contract_assert(aTemp > 0 && bTemp > 0);
if (aTemp > bTemp) aTemp -= bTemp;
else bTemp -= aTemp;
}
return aTemp;
}
компиляторы
версии компиляторов, которые нужно собирать самостоятельно:
-
GCC версии 15+ с флагами
-fcontracts и -std=c++26 -
Clang версии 19+ с флагами
-std=c++2c или -std=c++26
семантика проверки
-fcontracts-evaluation-semantic
=ignore
=observe
=enforce
=quick-enforce
01.02
функция временной сложности алгоритма
факторы, определяющие сложность алгоритма
вывод точной функции временной сложности — суммарного числа элементарных операций
точная временная сложность сортировки вставками
порядок роста — асимптотическое исследования поведения функции сложности
int exact_time_complexity();
анализ сложности insertion_sort
вывод точной функции временной сложности $T(n)$ и оценка порядка ее роста
#include <vector>
void insertion_sort(std::vector<int>& arr) {
int n = arr.size();
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
элементарные операции
выполняются за постоянное время
- арифметические операции
- память — чтение / запись / копирование и другие
- ветвление, вызовы функций
int exact_time_complexity();
анализ сложности insertion_sort
вывод точной функции временной сложности $T(n)$ и оценка порядка ее роста
#include <vector>
void insertion_sort(std::vector<int>& arr) {
int n = arr.size();
int i = 1;
while (i < n) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
i = i + 1;
}
}
* клик по строчке кода покажет ее точную сложность
элементарные операции
выполняются за постоянное время
- арифметические операции
- память — чтение, запись, копирование и другие
- ветвление, вызовы функций
точная функция сложности
$x$ — число итераций цикла while зависит от того, в каком порядке отсортирован массив
$T(n, x) = 10n\cdot x + 3n - 10x - 5$
отсортирован по возрастанию
$X=1\Rightarrow T_B(n) = 13n - 15$
отсортирован по убыванию
$X\in[1,n-1]\Rightarrow ... \Rightarrow T_W(n) = 5n^2-2n-5$
факторы и случаи сложности
сложность определяется и размером массива, и характеристикой его отсортированности
-
лучший случай: $T_B$ — линейная функция
-
худший случай: $T_W$ — квадратичная функция
-
средний случай: ???
асимптотическая сложность
отбрасываем несущественные части $T(n)$
чем можно пренебречь при $n \to \infty$?
-
вкладом $13$, а также $(-15)$ в $T_B(n)$
записываем $T_B(n)$ $=\Theta(n)$ -
вкладом $5$, а также $(-2n-5)$ в $T_W(n)$
записываем $T_B(n)$ $=\Theta(n^2)$
$\Theta$ — символ Ландау для порядка роста функции
void order_of_growth();
порядок роста функции
определение символа $\Theta$ и связь с графиками функций
определение 01.02
$T(n)$ имеет тот же порядок роста, что и $g(n)$, то есть,
$T(n) = \Theta(g(n))$, если $T(n)$ принадлежит
множеству
$\Theta(g(n))=\{ T(n) \,\vert\, 0 \leqslant c_1g(n) \leqslant T(n) \leqslant c_2g(n) \}$
для некоторых $c_1$, $c_2 > 0$ и $\forall n \geqslant n_0$
ключевые свойства
- $T(n) = \Theta(g(n)) \Leftrightarrow T(n) \in \Theta(g(n))$
- $0 < \lim\limits_{n\to \infty} \frac{T(n)}{g(n)} < \infty \Rightarrow T(n) = \Theta(g(n))$
- $T(n)$, начиная с $n_0$, «зажата» между $c_1g(n)$ и $c_2g(n)$
$0\leqslant 3n \leqslant T(n) = 4n+6 \leqslant 6n$, где $g(n) = n$
верно для всех $n$, начиная с $n_0 = 3$, при $c_1=3$ и $c_2=6$
$0\leqslant 0.5n^2 \leqslant T(n) = n^2+1 \leqslant 2n^2$, где $g(n)=n^2$
верно для всех $n$, начиная с $n_0 = 1$, при $c_1=0.5$ и $c_2=2$
ествественно, что $T(n)=n^2+1 \neq \Theta(n)$
поскольку расположение графиков функций неоднозначно
какие из этих функций принадлежат множеству $\Theta(n^2)$
...имеют тот же порядок роста, что и $n^2$
- $T_1(n) = (n^3 + 5n)\,/\,(n+2)$
- $T_2(n) = n^2 \cdot \log_2(n^3)$
- $T_3(n) = \lfloor \sqrt{n^4 +100n} \rfloor$
- $T_4(n) = \sum_{i=1}^n i^2$
- $T_5(n) = n^{2.01}$
#include <vector>
#include <iterator>
#include <algorithm>
// Вариант 1. Наивная реализация
void insertion_sort(std::vector<int>& arr) {
int n = arr.size();
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
// Вариант 2. STL-продакшен реализация
template<std::random_access_iterator Iter>
void insertion_sort_prod(Iter first, Iter last) {
for (auto it = first; it != last; ++it) {
auto where = std::upper_bound(first, it, *it);
std::rotate(where, it, it + 1);
}
}
| размер вектора | наивная (мс) | продакшен (мс) | ускорение |
|---|---|---|---|
| 5 000 | 4.79 | 1.02 | 4.7x |
| 10 000 | 15.68 | 2.32 | 6.8x |
| 20 000 | 35.49 | 5.13 | 6.9x |
| 40 000 | 95.23 | 16.1 | 5.9x |
| 50 000 | 146.72 | 26.57 | 5.5x |
| 100 000 | 601.22 | 127.22 | 4.7x |
| 200 000 | 2458.2 | 570.92 | 4.3x |
| 300 000 | 5581.05 | 1317.47 | 4.2x |
* время работы сортировки с оптимизациями компилятора на случайно заполненных массивах
// Лекция 01 завершена
// Резюме основных моментов
что мы
рассмотрели сегодня:
-
инвариант циклического алгоритма
обоснование корректности цикла на примере
сортировки вставками, факториала и НОДа -
вывод точной функции временной сложности $T(n)$
подсчет общего количества элементарных операций
и факторы временной сложности алгоритма -
асимптотический анализ порядка роста
ведущие слагаемые в функции $T(n)$ и символ $\Theta$ [ тета ]
--> на следующей лекции
--> ADT Контейнер, отношения между объектами
--> и линейные контейнеры
};
return 0;
01->