Перейти к основному содержимому

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

ОБЯЗАТЕЛЬНОДЛЯ НОВИЧКОВ
Архитектору Инженеру

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

Теория чисел​

Множество целых ℤ = {…, −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(√n), O(n³) — реже, но встречаются в теории чисел и матрицах;
  • O(2^n), O(n!) — перебор, быстро становится неприемлемым.

Play ITЗагрузка интерактивного демо…

Полный справочник с примерами на структурах данных и сортировке — Нотация Большое O; построчный разбор на Python — Lab / Big-O — 1128; практика задач — сортировка и поиск.

Мастер-теорема для divide-and-conquer​

Если время рекурсии удовлетворяет T(n) = a·T(n/b) + f(n), порядок роста часто выводят по сравнению f(n) с n^(log_b a) — см. таблицы и примеры в Рекуррентные соотношения. Типичный итог: merge sort → Θ(n log n), бинарный поиск → Θ(log n).

Рекурсия​

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

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

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

Запись рекуррентного соотношения для оценки сложности (T(n) = 2T(n/2) + n и т.п.) — в Рекуррентные соотношения.

В теории вычислимости "рекурсия" — отдельная глава: примитивные и частично рекурсивные функции, связь с машиной Тьюринга. Не путайте приём в коде с формальным классом вычислимых функций.

Дальше: Линейная алгебра. Назад по дискретке: Рекуррентные соотношения.

Связанные темы

Содержание