Пространственная сложность измеряет объём памяти, используемый алгоритмом относительно размера входных данных. Как и для временной сложности, используется нотация Big O.
Распространённые виды пространственной сложности:
O(1) — Константная: фиксированное количество переменных
O(log n) — Логарифмическая: глубина стека рекурсивных вызовов
O(n) — Линейная: одна копия входных данных
O(n²) — Квадратичная: двумерная матрица размером с входные данные
Важное различие:
- Вспомогательная память: дополнительная память помимо входных данных
- Общая память: входные данные + вспомогательная память
Примеры:
O(1): сортировка на месте (Bubble Sort), обмен значениями переменных
O(log n): рекурсивный бинарный поиск (стек вызовов)
O(n): Merge Sort (временные массивы), хеш-таблицы
O(n²): таблицы динамического программирования, матрицы смежности
Похожие алгоритмы
Частые вопросы
- Что такое Пространственная сложность?
- Распространённые виды пространственной сложности: O(1) — Константная: фиксированное количество переменных O(log n) — Логарифмическая: глубина стека рекурсивных вызовов O(n) — Линейная: одна копия входных данных O(n²) — Квадратичная: двумерная матрица размером с входные данные
- Какова сложность Пространственная сложность?
- Пространственная сложность объясняется с помощью пошаговой визуализации, включая временную и пространственную сложность.
- Для кого предназначена визуализация Пространственная сложность?
- Визуализация Пространственная сложность рассчитана на начальный уровень в категории «Основы». Полезна для студентов, подготовки к собеседованиям и практического изучения.
- Какие алгоритмы связаны с Пространственная сложность?
- В той же категории (Основы) вы можете изучить: Big O Notation, Recursion, Two Pointers. Каждый из них имеет интерактивную визуализацию.