class Algorithms {
public:
Algorithms lecture {
.author = "Р.А. Нестеров"
.year = "2026/27"
.course = "НИУ ВШЭ ПИ, 2 курс"
};
алгоритмы
и структуры данных
// 01. Корректность и сложность рекурсивного алгоритма
void selection_sort(Iter first, Iter last);
void recursion_complexity();
// 02. Алгоритмическая парадигма «разделяй-и-властвуй»
void merge_sort(Iter first, Iter last);
void recursion_tree();
// 03. Домашняя работа set_1
void set_hw_environment();
->03
03.00
краткая ретроспектива
и повторение
асимптотические границы временной сложности
интрузивный список: эффективное хранение
одних и тех же объектов в нескольких списках
void asymptotic_bounds();
асимптотический анализ
порядок роста $\Theta$, верхняя $\mathrm{O}$ и нижняя $\Omega$ граница
определения
для некоторых $c_1, c_2, n_0 >0$ и для всех $n \geqslant n_0$:
- $T(n) = \Theta(g(n)) \Leftrightarrow 0 \leqslant c_1g(n) \leqslant T(n) \leqslant c_2g(n)$
- $T(n) = \mathrm{O}(g(n)) \Leftrightarrow 0 \leqslant T(n) \leqslant c_2g(n)$
- $T(n) = \Omega(g(n)) \Leftrightarrow 0 \leqslant c_1g(n) \leqslant T(n)$
$T(n) = \Theta(g(n)) \Leftrightarrow T(n) = \mathrm{O}(g(n))$ и $T(n) = \Omega(g(n))$
какое соотношение всегда верно для $T(n) = T_1(n) + T_2(n)$,
$T_1(n) = \mathrm{O}(n^3)$
$T_2(n) = \Omega(n^2)$
* клик по ответу покажет, верный ли он
- $T(n) = \mathrm{O}(n^3)$
- $T(n) = \Theta(n^3)$
- $T(n) = \Omega(n^3)$
- $T(n) = \Omega(n^2)$
template <typename Tag> IntrusiveNode {...};
один объект — много списков
классический подход на основе std::list
#include <list>
#include <string>
struct Connection {
int socket_fd;
std::string buffer;
};
int main() {
std::list<Connection*> all;
std::list<Connection*> ready;
Connection c1{10, "Hello"};
Connection c2{11, "World"};
all.push_back(&c1);
all.push_back(&c2);
ready.push_back(&c1);
ready.push_back(&c2);
}
недостатки стандартной реализации
- дополнительные аллокации при вставке в списки
- фрагментация динамической памяти
- дополнительный расход памяти на каждый список
template <typename Tag> IntrusiveNode {...};
интрузивный список
реализация на основе множественного наследования
#include <string>
#include <iostream>
struct All { All *next = nullptr, *prev = nullptr; };
struct Ready { Ready *next = nullptr, *prev = nullptr; };
struct Connection : All, Ready {
int socket_fd;
std::string buffer;
};
int main() {
Connection c1 {.socket_fd = 10, .buffer = "Hello"};
Connection c2 {.socket_fd = 11, .buffer = "World"};
c1.All::next = &c2;
c2.All::prev = &c1;
c1.Ready::next = &c2;
c2.Ready::prev = &c1;
for (All* cur = &c1; cur; cur = cur->next) {
Connection* con = static_cast<Connection*>(cur);
std::cout << "FD: " << con->socket_fd << "\n";
}
}
множественное наследование
- ручное приведение типов
- дублирование логики для каждого базового класса
- общие сложности реализации
template <typename Tag> IntrusiveNode {...};
интрузивный список
типобезопасные конструкции: теги и шаблоны
#include <string>
#include <iostream>
struct TagAll {};
struct TagReady {};
template<typename Tag>
struct IntrusiveNode {
IntrusiveNode *next = nullptr, *prev = nullptr;
}
struct Connection
: IntrusiveNode<TagAll>, IntrusiveNode<TagReady> {
int socket_fd;
std::string buffer;
};
template<typename Container, typename Tag>
Container* get_container(IntrusiveNode<Tag>* node) {
return static_cast<Container*>(node);
}
int main() {
Connection c1 { .socket_fd = 10, .buffer = "Hello" };
Connection c2 { .socket_fd = 11, .buffer = "World" };
c1.IntrusiveNode<TagAll>::next = &c2;
c2.IntrusiveNode<TagAll>::prev = &c1;
for (IntrusiveNode<TagAll>* cur = &c1; cur; cur = cur->next) {
Connection* con = get_container<Connection, TagAll>(cur);
std::cout << "FD: " << con->socket_fd << "\n";
}
}
теги и шаблоны
- ошибки выявляются на этапе компиляции
- масштабируемость без дублирования логики
- сложности реализации метапрограммирования
- на практике лучше применять готовые решения
неделя №3
--> квиз Л2
03.01
рекурсивный алгоритм
сортировка выбором: прародитель сортировки
вставками и пузырькового алгоритма
корректность: инвариант и убывающая мера рекурсии
сложность: рекуррентное соотношение
метод итерации и математической индукции
для решения рекуррентного соотношения
#include <iostream>
#include <vector>
#include <algorithm>
template<typename Iter>
void selection_sort(Iter first, Iter last) {
if (std::distance(first, last) <= 1) return;
auto min_iter = std::min_element(first, last);
std::iter_swap(first, min_iter);
// auto max_iter = std::max_element(first, last);
// std::iter_swap(last - 1, max_iter);
selection_sort(first + 1, last);
// selection_sort(first, last - 1);
}
int main() {
std::vector<int> arr = {5, 2, 4, 6, 1, 3};
selection_sort(arr.begin(), arr.end());
std::cout << std::boolalpha;
std::cout << std::is_sorted(arr.begin(), arr.end());
}
#include <iostream>
#include <vector>
#include <algorithm>
template<typename Iter>
void selection_sort(Iter first, Iter last) {
if (std::distance(first, last) <= 1) return;
auto min_iter = std::min_element(first, last);
std::iter_swap(first, min_iter);
// auto max_iter = std::max_element(first, last);
// std::iter_swap(last - 1, max_iter);
selection_sort(first + 1, last);
// selection_sort(first, last - 1);
}
int main() {
std::vector<int> arr = {5, 2, 4, 6, 1, 3};
selection_sort(arr.begin(), arr.end());
std::cout << std::boolalpha;
std::cout << std::is_sorted(arr.begin(), arr.end());
}
утверждение 03.01
для любых итераторов $\mathrm{first}$ и $\mathrm{last}$, где $\mathrm{first}\leqslant \mathrm{last}$, верно, что алгоритм selection_sort упорядочит элементы диапазона $[\mathrm{first}, \mathrm{last})$ в порядке возрастания за конечное число шагов
доказательство
$d$ — расстояние между итераторами $\mathrm{first}$ и $\mathrm{last}$
инвариант $P(d) =\{$ диапазон $[\mathrm{first}, \mathrm{last})$ отсортирован $\}$
- база индукции: $d = 0$ или $d =1 \Rightarrow P(d)$ выполнен
-
пусть $P(k)$ верен
для всех $k < d$:.cpp: 9-10 минимум $\to\mathrm{first}$
.cpp: 14 вызов для длины $d-1$ -
$d$ — это также
мера рекурсии: $d \to d -1 \to ... \to 1 \to 0$
$d\leqslant 1 \Rightarrow$ немедленный выход
void recursion_complexity();
рекуррентное соотношение
определение временной сложности рекурсивного алгоритма
#include <iostream>
#include <vector>
#include <algorithm>
template<typename Iter>
void selection_sort(Iter first, Iter last) {
if (std::distance(first, last) <= 1) return;
auto min_iter = std::min_element(first, last);
std::iter_swap(first, min_iter);
selection_sort(first + 1, last);
}
$T(n) = \begin{cases} \mathrm{O}(1) & n \leqslant 1 \\ T(n-1) + \mathrm{O}(n) & n > 1 \end{cases}$
задача 03.01
найти $g(n)$, для которой выполняется асимптотическое
соотношение верхней границы $T(n) = \mathrm{O}(g(n))$
решение — итерационный метод
-
$T(n) = T(n-1)+\mathrm{O}(n)$ $\leqslant T(n-1) + kn$,
где $k$ — это константа, которую мы не выбираем
-
последовательно раскрываем соотношение:
$\begin{aligned} T(n) &\leqslant T(n-1) + kn = T(n-2) + k(n-1) + kn \end{aligned}$
$\begin{aligned} \phantom{T(n)} &= T(n-3) + k(n-2) + k(n-1) + kn \end{aligned}$
$\begin{aligned} \phantom{T(n)} &= \dots = T(0) + k(1 + 2 + 3 + \dots + n) \end{aligned}$
$\begin{aligned} \phantom{T(n)} &= \mathrm{O}(1) + \mathrm{O}(n^2) = \mathrm{O}(n^2) \end{aligned}$
ответ $g(n) = n^2$
void recursion_complexity();
рекуррентное соотношение
определение временной сложности рекурсивного алгоритма
#include <iostream>
#include <vector>
#include <algorithm>
template<typename Iter>
void selection_sort(Iter first, Iter last) {
if (std::distance(first, last) <= 1) return;
auto min_iter = std::min_element(first, last);
std::iter_swap(first, min_iter);
selection_sort(first + 1, last);
}
$T(n) = \begin{cases} \mathrm{O}(1) & n \leqslant 1 \\ T(n-1) + kn & n > 1 \end{cases}$
задача 03.01
найти $g(n)$, для которой выполняется асимптотическое
соотношение верхней границы $T(n) = \mathrm{O}(g(n))$
решение — математическая индукция
✅- основное предположение: $T(n) = \mathrm{O}(n^2) \Rightarrow T(n) \leqslant cn^2$
- гипотеза индукции: $T(m) \leqslant cm^2$ для всех $m < n$
-
выполним подстановку:
$\begin{aligned} T(n)=T(n-1) + kn & \leqslant c(n-1)^2 + kn \end{aligned}$
$\begin{aligned} \phantom{T(n)=T(n-1) + kn} &= cn^2 -2cn + c + kn \end{aligned}$
$\begin{aligned} \phantom{T(n)=T(n-1) + kn} &= cn^2 - ((2c-k)n - c) \leqslant cn^2 \end{aligned}$
ответ (1) верно при $n \geqslant c \,/\,(2c -k)$, что влечет $c > k \,/\, 2$
void recursion_complexity();
рекуррентное соотношение
определение временной сложности рекурсивного алгоритма
#include <iostream>
#include <vector>
#include <algorithm>
template<typename Iter>
void selection_sort(Iter first, Iter last) {
if (std::distance(first, last) <= 1) return;
auto min_iter = std::min_element(first, last);
std::iter_swap(first, min_iter);
selection_sort(first + 1, last);
}
$T(n) = \begin{cases} \mathrm{O}(1) & n \leqslant 1 \\ T(n-1) + kn & n > 1 \end{cases}$
задача 03.01
найти $g(n)$, для которой выполняется асимптотическое
соотношение верхней границы $T(n) = \mathrm{O}(g(n))$
решение — математическая индукция
❌- основное предположение: $T(n) = \mathrm{O}(n) \Rightarrow T(n) \leqslant cn$
- гипотеза индукции: $T(m) \leqslant cm$ для всех $m < n$
-
выполним подстановку:
$\begin{aligned} T(n)=T(n-1) + kn & \leqslant c(n-1) + kn \end{aligned}$
$\begin{aligned} \phantom{T(n)=T(n-1) + kn} &= cn - (c - kn) \leqslant cn \end{aligned}$
- $c -kn \geqslant 0 \Rightarrow 0 \leqslant n \leqslant c\,/\,k \Rightarrow n$ ограничено сверху!
03.02
разделяй-и-властвуй
сортировка слиянием и варианты ее реализации
дерево рекурсии: представление временной
сложности рекурсивного алгоритма
рекуррентное соотношение: правильно
избавляемся от знаков округлений
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
template<typename Iter>
void merge_sort(Iter first, Iter last) {
if (std::distance(first, last) <= 1) return;
auto mid = first + std::distance(first, last) / 2;
merge_sort(first, mid);
merge_sort(mid, last);
merge(first, mid, last);
}
int main() {
std::vector<int> arr = {5, 2, 4, 6, 1, 3};
merge_sort(arr.begin(), arr.end());
std::cout << std::boolalpha;
std::cout << std::is_sorted(arr.begin(), arr.end());
}
#include <vector>
#include <algorithm>
#include <iterator>
// Вариант 1. Единый буфер на весь алгоритм
template<typename Iter, typename BufIter>
void merge_sort(Iter first, Iter last, BufIter buf) {
if (std::distance(first, last) <= 1) return;
auto mid = first + std::distance(first, last) / 2;
merge_sort(first, mid, buf);
merge_sort(mid, last, buf);
merge(first, mid, last, buf);
}
template<typename Iter, typename BufIter>
void merge(Iter first, Iter mid, Iter last, BufIter buf) {
auto buf_mid = std::copy(first, mid, buf);
std::copy(mid, last, buf_mid);
// ...
}
template<typename Iter>
void merge_sort_v1(Iter first, Iter last) {
using ValueType = typename std::iterator_traits<Iter>::value_type;
std::vector<ValueType> buffer(std::distance(first, last));
merge_sort(first, last, buffer.begin());
}
// Вариант 2. Локальный буфер на каждый шаг
template<typename Iter>
void merge_sort(Iter first, Iter last) {
if (std::distance(first, last) <= 1) return;
auto mid = first + std::distance(first, last) / 2;
merge_sort(first, mid);
merge_sort(mid, last);
merge(first, mid, last);
}
template<typename Iter>
void merge(Iter first, Iter mid, Iter last) {
using ValueType = typename std::iterator_traits<Iter>::value_type;
std::vector<ValueType> buffer(std::distance(first, last));
// ...
}
// Вариант 3. In-place слияние через сдвиги
template<typename Iter>
void merge_sort(Iter first, Iter last) {
if (std::distance(first, last) <= 1) return;
auto mid = first + std::distance(first, last) / 2;
merge_sort(first, mid);
merge_sort(mid, last);
merge(first, mid, last);
}
template<typename Iter>
void merge(Iter first, Iter mid, Iter last) {
auto left = first, right = mid;
while (left < mid && right < last) {
if (*right < *left) {
std::rotate(left, right, right + 1);
++mid;
++right;
}
++left;
}
}
// Вариант 4. С помощью inplace_merge
template<typename Iter>
void merge_sort(Iter first, Iter last) {
if (std::distance(first, last) <= 1) return;
auto mid = first + std::distance(first, last) / 2;
merge_sort(first, mid);
merge_sort(mid, last);
std::inplace_merge(first, mid, last);
}
⭐️⭐️⭐️⭐️⭐️общий буфер
- одна аллокация перед началом работы
- $\mathrm{O}(n)$ затрат по памяти
⭐️⭐️локальный буфер
- $\mathrm{O}(n)$ аллокаций
- $\mathrm{O}(n)$ памяти в пике, всего — $\mathrm{O}(n \log n)$
⭐️без буфера
- нет аллокаций
- $\mathrm{O}(1)$ затрат по памяти
⭐️⭐️⭐️⭐️⭐️продакшен
- оптимизированные аллокации
- $\mathrm{O}(n)$ затрат по памяти
| массив | V1 | V2 | V3 | V4 |
|---|---|---|---|---|
| 5 000 | 0.4 | 0.7 | 1.3 | 0.7 |
| 10 000 | 0.7 | 1.4 | 4.0 | 1.1 |
| 50 000 | 3.7 | 6.8 | 32.9 | 3.4 |
| 100 000 | 4.9 | 7.0 | 110.36 | 5.0 |
| 500 000 | 21.8 | 29.8 | 3386.3 | 27.0 |
| 1 000 000 | 46.5 | 62.7 | — | 55.8 |
| 5 000 000 | 254.4 | 330.0 | — | 302.9 |
| 10 000 000 | 533.6 | 686.0 | — | 619.1 |
#include <vector>
#include <algorithm>
#include <iterator>
template<typename Iter>
void merge_sort(Iter first, Iter last) {
if (std::distance(first, last) <= 1) return;
auto mid = first + std::distance(first, last) / 2;
merge_sort(first, mid);
merge_sort(mid, last);
merge(first, mid, last);
}
$T(n) = \begin{cases} \mathrm{O}(1) & n \leqslant 1 \\ 2\cdot T(n\,/\,2) + \mathrm{O}(n) & n > 1 \end{cases}$
задача 03.02
найти $g(n)$, для которой выполняется асимптотическое
соотношение верхней границы $T(n) = \mathrm{O}(g(n))$
решение — математическая индукция
❌- основное предположение: $T(n) = \mathrm{O}(n) \Rightarrow T(n) \leqslant cn$
- гипотеза индукции: $T(m) \leqslant cm$ для всех $m < n$
- сложность merge: $T_{\text{merge}} = O(n) \leqslant kn$, где $k>0$
-
выполним подстановку:
$\begin{aligned} T(n)\leqslant 2\cdot T(n\,/\,2) + kn & \leqslant 2c\cdot (n\,/\,2) + kn \end{aligned}$
$\begin{aligned} \phantom{T(n)\leqslant 2\cdot T(n\,/\,2) + kn} &= cn +kn \leqslant cn \end{aligned}$
- получаем, что $k \leqslant 0$, что противоречит (3)!
#include <vector>
#include <algorithm>
#include <iterator>
template<typename Iter>
void merge_sort(Iter first, Iter last) {
if (std::distance(first, last) <= 1) return;
auto mid = first + std::distance(first, last) / 2;
merge_sort(first, mid);
merge_sort(mid, last);
merge(first, mid, last);
}
$T(n) = \begin{cases} \mathrm{O}(1) & n \leqslant 1 \\ 2\cdot T(n\,/\,2) + \mathrm{O}(n) & n > 1 \end{cases}$
задача 03.02
найти $g(n)$, для которой выполняется асимптотическое
соотношение верхней границы $T(n) = \mathrm{O}(g(n))$
решение — математическая индукция
✅- основное предположение: $T(n) = \mathrm{O}(n) \Rightarrow T(n) \leqslant cn^2$
- гипотеза индукции: $T(m) \leqslant cm^2$ для всех $m < n$
- сложность merge: $T_{\text{merge}} = O(n) \leqslant kn$, где $k>0$
-
выполним подстановку:
$\begin{aligned} T(n)\leqslant 2\cdot T(n\,/\,2) + kn & \leqslant 2c\cdot (n^2\,/\,4) + kn \end{aligned}$
$\begin{aligned} \phantom{T(n)\leqslant 2\cdot T(n\,/\,2) + kn} &= cn^2\,/\,2 +kn \end{aligned}$
$\begin{aligned} \phantom{T(n)\leqslant 2\cdot T(n\,/\,2) + kn} &= cn^2 - (cn^2\,/\,2 -kn) \leqslant cn^2 \end{aligned}$
- $cn^2\,/\,2 -kn \geqslant 0 \Leftrightarrow cn\,/\,2 -k \geqslant 0 \Leftrightarrow n \geqslant 2k\,/\,c$
ответ $T(n) = \mathrm{O}(n^2)$ при $c = k$ и $n \geqslant 2$
void recursion_tree();
дерево рекурсии
точное определение сложности рекурсивного алгоритма
#include <vector>
#include <algorithm>
#include <iterator>
template<typename Iter>
void merge_sort(Iter first, Iter last) {
if (std::distance(first, last) <= 1) return;
auto mid = first + std::distance(first, last) / 2;
merge_sort(first, mid);
merge_sort(mid, last);
merge(first, mid, last);
}
$T(n) = \begin{cases} \mathrm{O}(1) & n \leqslant 1 \\ 2\cdot T(n\,/\,2) + kn & n > 1 \end{cases}$
параметры дерева рекурсии
- высота / число уровней: $h = \log_2 n + 1$
- сложность $i$-го уровня: $2^i\cdot kn\,/\,2^i = kn$
- общая сложность: $kn(\log_2 n + 1) = \mathrm{O}(n \log n)$
void recursion_tree();
дерево рекурсии
точное определение сложности рекурсивного алгоритма
#include <vector>
#include <algorithm>
#include <iterator>
template<typename Iter>
void merge_sort(Iter first, Iter last) {
if (std::distance(first, last) <= 1) return;
auto mid = first + std::distance(first, last) / 2;
merge_sort(first, mid);
merge_sort(mid, last);
merge(first, mid, last);
}
$T(n) = \begin{cases} \mathrm{O}(1) & n \leqslant 1 \\ 2\cdot T(n\,/\,2) + kn & n > 1 \end{cases}$
задача 03.03
показать, что соотношение $T(n) = \mathrm{O}(n \log n)$ верно
решение — математическая индукция
✅- предположение: $T(n) = \mathrm{O}(n \log n) \Rightarrow T(n) \leqslant cn\cdot \log_2 n$
- гипотеза индукции: $\forall m < n \colon T(m) \leqslant cm\cdot \log_2 m$
-
выполним подстановку:
$\begin{aligned} T(n)\leqslant 2\cdot T(n\,/\,2) + kn & \leqslant 2c\cdot (n\,/\,2) \cdot \log_2(n\,/\,2) + kn \end{aligned}$
$\begin{aligned} \phantom{T(n)\leqslant 2\cdot T(n\,/\,2) + kn} &= cn\cdot \log_2(n\,/\,2) +kn \end{aligned}$
$\begin{aligned} \phantom{T(n)\leqslant 2\cdot T(n\,/\,2) + kn} &= cn\cdot \log_2 n -(c-k)n \end{aligned}$
$\begin{aligned} \phantom{T(n)\leqslant 2\cdot T(n\,/\,2) + kn} & \leqslant cn\cdot \log_2 n \end{aligned}$
ответ $c-k\geqslant 0 \Rightarrow T(n) =\mathrm{O}(n \log n)$ при $c \geqslant k$ и $n \geqslant 1$
#include <vector>
#include <algorithm>
#include <iterator>
template<typename Iter>
void merge_sort(Iter first, Iter last) {
if (std::distance(first, last) <= 1) return;
auto mid = first + std::distance(first, last) / 2;
merge_sort(first, mid);
merge_sort(mid, last);
merge(first, mid, last);
}
$T(n) = \begin{cases} \mathrm{O}(1) & n \leqslant 1 \\ T(\lfloor n\,/\,2\rfloor) + T(\lceil n\,/\,2\rceil) + kn & n > 1 \end{cases}$
задача 03.04
показать эквивалентность асимптотических границ для:
- $T(n) = 2 \cdot T(n\,/\,2) +kn$ и
- $T(n) = T(\lfloor n\,/\,2\rfloor) + T(\lceil n\,/\,2\rceil) + kn$
решение — замена переменной
- сдвинем оценку вправо с учетом $\lfloor x \rfloor \leqslant \lceil x \rceil \leqslant x + 1$: $T(n) \leqslant 2 \cdot T(n\,/\,2 + 1) + kn$
- пусть $S(n) = T(n + \alpha)$, для которой верно: $S(n) \leqslant 2 \cdot S(n\,/\,2) + kn \Rightarrow S(n) = \mathrm{O}(n \log n)$
-
чтобы найти $\alpha$, сопоставим оценки $T(n)$ и $S(n)$:
(2) $\Longrightarrow T(n+\alpha) \leqslant 2\cdot T(n\,/\,2 + \alpha) + k(n+\alpha)$
(1) $\Longrightarrow T(n+\alpha) \leqslant 2\cdot T((n+\alpha)\,/\,2 + 1) + k(n+\alpha)$
- $n\,/\,2 + \alpha = (n+\alpha)\,/\,2 + 1 \Rightarrow n = 2$
ответ $T(n) = S(n-2)$ и $T(n) = \mathrm{O}(n \log n)$
03.03
SET 1: домашняя работа
инфраструктура сдачи и проверки домашних работ: письменные и программные задачи
взаимодействие с SourceCraft и Manytask
void set_hw_environment();
домашние работы
из каких типов задач состоят
📝часть А
блок письменных задач
- применение теоретических аспектов, анализ алгоритмов, ...
- решения сдаются через SmartLMS и проходят ручную проверку
💻часть P
блок программных задач
- алгоритмические задачи — проверка правильности ответа
- реализация класса(-ов) в соответствии с интерфейсом
- решения сдаются в репозитории SourceCraft и проходят тесты в CI
⚡️часть K
специальная задача-кейс
- реализация класса(-ов) в соответствии с интерфейсом
- дополнительное покрытие юнит-тестами с помощью gtest
- решения сдаются в репозитории SourceCraft и проходят тесты в CI
void set_hw_environment();
домашняя работа set_1
инвариант цикла · асимптотический анализ · линейный контейнер
| ID | Баллы | Комментарий |
|---|---|---|
| a1_exact_complexity CORE | 7 | анализ временной сложности $T(n)$ |
| a2x_correctness extra | 8 | корректность алгоритма |
| a3_comparison CORE | 10 | сравнительный анализ нескольких алгоритмов |
| p1_list CORE | 15 | реализация списка |
| p2_array_rotate CORE | 8 | обработка одномерного массива |
| p3_unpack CORE | 7 | обработка строк |
| p4_wagons CORE | 8 | применение линейных контейнеров |
| p5_castle CORE | 7 | применение линейных контейнеров |
| k_swag CORE EXTRA | 20 + 10 | реализация очереди со скользящим окном и различными агрегатами |
// Лекция 03 завершена
// Резюме основных моментов
что мы
рассмотрели сегодня:
-
сложность рекурсивного алгоритма
сортировка выбором и рекуррентное соотношение
-
методы решения рекуррентных соотношений
итерация, математическая индукция с подстановкой
и дерево рекурсии -
алгоритмическая парадигма «разделяй-и-властвуй»
сортировка слиянием и варианты ее реализации
--> на следующей лекции
--> парадигма «разделяй-и-властвуй» (продолжение)
--> и мастер-теорема для анализа рекуррентных соотношений
};
return 0;
03->