Скачать или смотреть 001 Асимптотический анализ алгоритмов Asymptotic analysis

   • Алгоритмы и Структуры данных C++  
Асимптотический анализ — это метод оценки производительности алгоритмов, который помогает понять их поведение при больших входных данных. Основная цель асимптотического анализа — оценить эффективность алгоритма, не зависящую от конкретных аппаратных характеристик или реализации программы. В основном нас интересует скорость выполнения (время) и объем используемой памяти (пространство).

Основные концепции асимптотического анализа:
Размер входных данных (n):

Это количество элементов, которое алгоритм должен обработать. Например, для сортировки массива, размер входных данных — это количество элементов в массиве.
Время выполнения:

Как изменяется количество операций, выполняемых алгоритмом, в зависимости от размера входных данных.
Пространственная сложность:

Объем памяти, требуемой алгоритмом, также зависит от размера входных данных.
Оценка времени выполнения:
Анализ обычно оценивается через функции, которые описывают количество шагов (или операций) в зависимости от размера входных данных. Оценка производится по трем основным показателям:

Лучший случай (Best Case):
Это время выполнения алгоритма при наиболее благоприятных условиях. Например, для алгоритма сортировки лучший случай может быть, если массив уже отсортирован.

Средний случай (Average Case):
Время выполнения алгоритма в среднем для произвольного набора входных данных.

Худший случай (Worst Case):
Время выполнения алгоритма при наихудших возможных входных данных. Например, для сортировки это может быть полностью обратный массив (например, отсортированный в обратном порядке).

О-большое нотация (Big O notation):
О-большое используется для описания верхней границы времени выполнения алгоритма в зависимости от размера входных данных (худший случай). Она игнорирует константы и менее значимые члены, сосредотачиваясь на том, как алгоритм масштабируется с увеличением входных данных.

Примеры сложности алгоритмов:
O(1) — Константная сложность:

Алгоритм выполняется за фиксированное количество времени, независимо от размера входных данных. Например, доступ к элементу массива по индексу.
O(log n) — Логарифмическая сложность:

Время выполнения увеличивается логарифмически с ростом размера входных данных. Пример: бинарный поиск.
O(n) — Линейная сложность:

Время выполнения увеличивается прямо пропорционально размеру входных данных. Пример: линейный поиск в массиве.
O(n log n) — Линейно-логарифмическая сложность:

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

Время выполнения увеличивается пропорционально квадрату размера входных данных. Пример: сортировка пузырьком или вставками для неотсортированных данных.
O(2^n) — Экспоненциальная сложность:

Время выполнения удваивается с каждым новым элементом. Пример: решения задач методом полного перебора, таких как решение задачи о рюкзаке с помощью метода "грубой силы".
O(n!) — Факториальная сложность:

Время выполнения растет очень быстро с увеличением входных данных. Пример: полный перебор всех возможных перестановок.