Основы алгоритмов

Алгоритм — это чёткая конечная последовательность шагов для решения конкретной задачи.

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


Определение и свойства алгоритмов

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

Квалифицированный алгоритм должен обладать следующими пятью основными свойствами:

ХарактеристикаЗначениеКонтрпример
ВводВнешних входов может быть ноль или более.Отсутствие входных данных также допустимо, например генерация случайных чисел.
ВыводВыдаёт по крайней мере один результат«Алгоритм» без какого-либо вывода бессмысленен
ОпределённостьСмысл каждого шага должен быть ясен и однозначенРасплывчатые описания, такие как «увеличить соответствующим образом», недопустимы
КонечностьДолжен завершаться за конечное число шагов; он не может зацикливаться бесконечноОперационная система сама по себе не является алгоритмом, потому что теоретически работает бесконечно
ОсуществимостьКаждый шаг может быть реализован с помощью базовых операций«Деление на ноль» неосуществимо, и «сортировка за один шаг» также неосуществима

«Конечность» алгоритма не противоречит «бесконечному циклу» программы. Программа может попасть в бесконечный цикл из-за ошибки, но сам алгоритм должен завершаться за конечное число шагов. Разница в том, что алгоритм — это понятие на уровне «проектного замысла», а программа — понятие на уровне «фактического выполнения».


Способы представления алгоритмов

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

Псевдокод

Псевдокод использует текст, близкий к естественному языку, но имеющий определённый структурированный формат для описания логики алгоритма.

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

Например, псевдокод для поиска максимального значения в наборе чисел:

算法:FindMax
输入:数组 A,长度 n
输出:A 中的最大值

1. max = A[0]
2. for i = 1 to n-1:
3.     if A[i] > max:
4.         max = A[i]
5. return max

Блок-схема

Блок-схема наглядно отображает процесс выполнения алгоритма с помощью графических изображений.

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

Условные обозначения символов в блок-схемах:

Форма символаЗначение
Скруглённый прямоугольник (или эллипс)Начало / Конец
ПрямоугольникЭтап обработки
РомбРешение / Ветвление
ПараллелограммВвод / Вывод
СтрелкаНаправление потока

Анализ эффективности алгоритма

После разработки алгоритма также необходимо оценить его эффективность. Это в основном измеряется по двум измерениям.

Временная сложность

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

Обратите внимание, что нас интересует «тенденция роста», а не «точное количество выполнений». Потому что для крупномасштабных входных данных различия в постоянных множителях гораздо менее важны, чем различия в тенденциях роста.

Пространственная сложность

Пространственная сложность описывает тенденцию роста дополнительного объёма памяти, требуемого во время выполнения алгоритма, по мере увеличения размера входных данных n.

Акцент на «дополнительной» памяти здесь означает, сколько вспомогательного пространства нужно алгоритму помимо пространства, используемого для хранения самих входных данных.

Время и пространство часто являются парой компромиссов — обмен пространства на время или времени на пространство — распространённая стратегия компромисса при проектировании алгоритмов. Например: хеш-таблица использует дополнительное хранилище в обмен на время поиска O(1); а алгоритмы сортировки на месте используют немного больше вычислительных шагов, чтобы избежать дополнительного расхода пространства.


Нотация O-большое

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

Она описывает верхнюю границу тенденции роста времени выполнения или использования пространства по мере увеличения размера входных данных n в наихудшем случае для алгоритма.

Определение: если существуют положительные константы c и n0 такие, что для всех n ≥ n0 выполняется T(n) ≤ c × f(n), то это обозначается какT(n) = O(f(n))。

Интуитивное понимание: нотация O-большое игнорирует постоянные множители и члены младших порядков, фокусируясь только на наиболее быстро растущем члене.

Например: если алгоритму требуется 3n² + 100n + 500 операций, то при достаточно большом n член n² доминирует в росте, поэтому мы говорим, что это O(n²).

Распространённые уровни сложности

大 O 复杂度增长趋势对比图

На рисунке выше интуитивно показано, как каждый уровень сложности изменяется по мере роста размера входных данных n.

ОбозначениеNamen=10n=1000Типичные алгоритмы
O(1)Константный порядок11Доступ к массиву по индексу, поиск в хеш-таблице
O(log n)Логарифмический порядок~3~10Бинарный поиск, операции сбалансированного BST
O(n)Линейный порядок101000Линейный поиск, обход массива
O(n log n)Линейно-логарифмический порядок~30~10000Сортировка слиянием, быстрая сортировка (в среднем)
O(n²)Квадратичный порядок1001000000Пузырьковая сортировка, сортировка выбором
O(2ⁿ)Экспоненциальный порядок1024Астрономическое числоРешение задач о подмножествах методом полного перебора

Из таблицы видно, что при n=1000 O(1) по-прежнему требует только 1 операцию, O(n) требует 1000 операций, а O(n²) — 1 миллион операций.

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

В реальном программировании старайтесь, чтобы сложность ключевых алгоритмов не превышала O(n log n). Когда сложность достигает O(n²) или выше, следует уделять особое внимание тому, контролируем ли размер входных данных и есть ли лучшие альтернативы.


Примеры вычисления временной сложности

Ниже приведён простой фрагмент кода на C и анализ его временной сложности:

Пример

#include <stdio.h>

/* Функция: вычисление суммы элементов массива
Временная сложность: O(n)
n — длина массива, цикл выполняется n раз, и каждая итерация выполняет постоянное число операций */

int sumArray(int arr[], int n) {
    int total = 0;           /* O(1) — операция присваивания, выполняется один раз */
    for (int i = 0; i < n; i++) {  /* Тело цикла */
        total += arr[i];    /* O(1) — сложение и присваивание, выполняемые n раз */
    }
    return total;            /* O(1) — операция return, выполняется один раз */
}
/* Общая временная сложность: O(1 + n + 1) = O(n)
Слагаемые низшего порядка и константы игнорируются */


int main() {
    int nums[] = {5, 10, 15, 20, 25};
    int size = sizeof(nums) / sizeof(nums[0]);
    int result = sumArray(nums, size);
    printf("Сумма элементов массива: %d\n", result);  /* Вывод: Сумма элементов массива: 75 */
    return 0;
}

Теперь рассмотрим другой пример с вложенными циклами:

Пример

#include <stdio.h>

/* Функция: печатает таблицу умножения n×n
Временная сложность: O(n²)
Внешний цикл выполняется n раз, внутренний цикл выполняется n раз, всего n×n раз */

void printMulTable(int n) {
    for (int i = 1; i <= n; i++) {      /* Внешний цикл O(n) */
        for (int j = 1; j <= n; j++) {  /* Внутренний цикл O(n), всего n² итераций с учётом вложения */
            printf("%d\t", i * j);      /* Операция O(1) */
        }
        printf("\n");
    }
}
/* Общая временная сложность: O(n × n) = O(n²) */

int main() {
    printMulTable(5);  /* Вывод таблицы умножения 5×5 */
    return 0;
}

Примеры вычисления пространственной сложности

Пространственная сложность учитывает дополнительную память, выделяемую во время выполнения алгоритма.

Пример

#include <stdio.h>
#include <stdlib.h> /* Заголовочный файл для malloc/free */

/* Функция: создать новый массив, хранящий квадраты исходного массива
Пространственная сложность: O(n) — выделяет новый массив длины n */

int* squareArray(int arr[], int n) {
    int* result = (int*)malloc(n * sizeof(int));  /* Выделить дополнительное пространство для n значений int */
    if (result == NULL) {
        return NULL;  /* Вернуть NULL, если malloc завершится неудачно */
    }
    for (int i = 0; i < n; i++) {
        result[i] = arr[i] * arr[i];
    }
    return result;
}
/* Сложность по памяти O(n):
- Входной массив arr не учитывается (он сам является частью входных данных)
- Результирующий массив дополнительно выделяет n значений int, что является дополнительной памятью
- Переменная i использует константную память O(1), которая пренебрежимо мала по сравнению с O(n) */


int main() {
    int nums[] = {1, 2, 3, 4, 5};
    int n = 5;
    int* squared = squareArray(nums, n);
    if (squared != NULL) {
        for (int i = 0; i < n; i++) {
            printf("%d ", squared[i]);  /* Вывод: 1 4 9 16 25 */
        }
        printf("\n");
        free(squared);  /* Вручную освободите динамически выделенную память */
    }
    return 0;
}

Распространённые заблуждения новичков: временная и пространственная сложность анализируют «тенденции роста», а не точные значения. Постоянные коэффициенты, члены низшего порядка и различия между языками программирования игнорируются нотацией Big O. Поэтому O(2n) и O(n) эквивалентны — они обе представляют линейный рост.

Другие расширения