Основы алгоритмов
Алгоритм — это чёткая конечная последовательность шагов для решения конкретной задачи.
Понимание базовых понятий алгоритмов и методов анализа эффективности — важная предпосылка для изучения структур данных и алгоритмов.
Определение и свойства алгоритмов
В информатике алгоритм — это конечная последовательность инструкций, каждая из которых представляет одну или несколько операций.
Квалифицированный алгоритм должен обладать следующими пятью основными свойствами:
| Характеристика | Значение | Контрпример |
|---|---|---|
| Ввод | Внешних входов может быть ноль или более. | Отсутствие входных данных также допустимо, например генерация случайных чисел. |
| Вывод | Выдаёт по крайней мере один результат | «Алгоритм» без какого-либо вывода бессмысленен |
| Определённость | Смысл каждого шага должен быть ясен и однозначен | Расплывчатые описания, такие как «увеличить соответствующим образом», недопустимы |
| Конечность | Должен завершаться за конечное число шагов; он не может зацикливаться бесконечно | Операционная система сама по себе не является алгоритмом, потому что теоретически работает бесконечно |
| Осуществимость | Каждый шаг может быть реализован с помощью базовых операций | «Деление на ноль» неосуществимо, и «сортировка за один шаг» также неосуществима |
«Конечность» алгоритма не противоречит «бесконечному циклу» программы. Программа может попасть в бесконечный цикл из-за ошибки, но сам алгоритм должен завершаться за конечное число шагов. Разница в том, что алгоритм — это понятие на уровне «проектного замысла», а программа — понятие на уровне «фактического выполнения».
Способы представления алгоритмов
При разработке и передаче алгоритмов обычно используются два способа представления.
Псевдокод
Псевдокод использует текст, близкий к естественному языку, но имеющий определённый структурированный формат для описания логики алгоритма.
Он не зависит от синтаксиса какого-либо конкретного языка программирования, что позволяет удобно быстро выражать идеи.
Например, псевдокод для поиска максимального значения в наборе чисел:
算法: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²).
Распространённые уровни сложности
На рисунке выше интуитивно показано, как каждый уровень сложности изменяется по мере роста размера входных данных n.
| Обозначение | Name | n=10 | n=1000 | Типичные алгоритмы |
|---|---|---|---|---|
| O(1) | Константный порядок | 1 | 1 | Доступ к массиву по индексу, поиск в хеш-таблице |
| O(log n) | Логарифмический порядок | ~3 | ~10 | Бинарный поиск, операции сбалансированного BST |
| O(n) | Линейный порядок | 10 | 1000 | Линейный поиск, обход массива |
| O(n log n) | Линейно-логарифмический порядок | ~30 | ~10000 | Сортировка слиянием, быстрая сортировка (в среднем) |
| O(n²) | Квадратичный порядок | 100 | 1000000 | Пузырьковая сортировка, сортировка выбором |
| O(2ⁿ) | Экспоненциальный порядок | 1024 | Астрономическое число | Решение задач о подмножествах методом полного перебора |
Из таблицы видно, что при n=1000 O(1) по-прежнему требует только 1 операцию, O(n) требует 1000 операций, а O(n²) — 1 миллион операций.
В сценариях с крупномасштабными данными выбор алгоритма с подходящей сложностью может приводить к различиям в производительности на порядки.
В реальном программировании старайтесь, чтобы сложность ключевых алгоритмов не превышала O(n log n). Когда сложность достигает O(n²) или выше, следует уделять особое внимание тому, контролируем ли размер входных данных и есть ли лучшие альтернативы.
Примеры вычисления временной сложности
Ниже приведён простой фрагмент кода на C и анализ его временной сложности:
Пример
/* Функция: вычисление суммы элементов массива
Временная сложность: 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;
}
Теперь рассмотрим другой пример с вложенными циклами:
Пример
/* Функция: печатает таблицу умножения 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 <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) эквивалентны — они обе представляют линейный рост.