Теория чисел, псевдокод и анализ алгоритмов

ОБЯЗАТЕЛЬНОДЛЯ НОВИЧКОВ

Архитектору Инженеру

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

Теория чисел

Множество целых ℤ = {…, −2, −1, 0, 1, 2, …}. Делимость: b | a, если a = b·k при b ≠ 0.

• Простое p > 1 — ровно два делителя: 1 и p.
• Основная теорема арифметики: каждое n > 1 единственно раскладывается в произведение простых (с точностью до порядка).

НОД gcd(a,b) — наибольший общий делитель; НОК lcm(a,b) — наименьшее общее кратное. Алгоритм Евклида эффективно находит НОД — основа RSA, упрощения дробей, некоторых хеш-функций.

В IT теория чисел — фундамент криптографии (модульная арифметика, простые числа), генераторов псевдослучайных чисел и проверок целостности.

Псевдокод

Псевдокод — полуформальная запись алгоритма без привязки к языку. Не компилируется; цель — передать семантику шагов для команды, учебника или спецификации.

Принципы

• абстракция от типов («целое», «массив», «строка»);
• отступы вместо жёсткого синтаксиса;
• общие слова: «если», «пока», «для», «вернуть», «вызвать».

Конструкции

Последовательность:

ввести x
y ← x² + 2x + 1
вывести y

Ветвление:

если x < 0
    то вывод "отрицательное"
иначе если x = 0
    то вывод "ноль"
иначе
    вывод "положительное"

Циклы: пока условие (предусловие), повторять … пока (постусловие, минимум одна итерация), для i от 1 до n.

Подпрограммы:

функция Факториал(n)
    если n ≤ 1
        то вернуть 1
    иначе
        вернуть n * Факториал(n - 1)

Псевдокод удобен на этапе проектирования; реализация на Python, C# или Go должна сохранять ту же логику.

Анализ алгоритмов

Анализ оценивает время и память в зависимости от размера входа n, независимо от железа и компилятора.

Тип анализа	Что даёт
Худший случай	гарантированная верхняя граница — основа в теории и SLA
Средний случай	ожидание при распределении входов
Лучший случай	редко информативен сам по себе

Асимптотика (O-большое)

Описывает рост при n → ∞, игнорируя константы и младшие члены:

• O(1) — доступ по индексу;
• O(log n) — бинарный поиск;
• O(n) — один проход;
• O(n log n) — эффективные сортировки;
• O(n²) — вложенные циклы по n;
• O(2^n), O(n!) — перебор, быстро становится неприемлемым.

Загрузка демо сложности…

Подробнее о классах сложности и примерах — в разделе Алгоритмы.

Рекурсия

Рекурсивная функция определяется через себя. Обязательны:

1. базовый случай (остановка);
2. рекуррентный шаг с «упрощением» аргумента.

Естественна для деревьев, списков, выражений. Риски: бесконечная рекурсия, переполнение стека — на глубоких структурах иногда переходят на итерацию или явный стек.

Дальше: Линейная алгебра.

---