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

Калькулятор превращает асимптотическую оценку памяти O(n) в конкретные цифры: сколько байт, килобайт, мегабайт и гигабайт займут n элементов заданного размера.

Как устроен расчёт

Пространственная сложность описывает, как растёт потребление памяти алгоритмом при росте входных данных. Нотация O(n) говорит о характере роста, но не о мегабайтах. Здесь считается «полезный» объём: память = n × b, где n — число элементов, b — размер одного элемента в байтах.

Типичные значения b: 1 байт — char/uint8, 4 байта — int32 и float, 8 байт — int64, double и указатель на 64-битной платформе. Результат переводится в двоичные единицы: 1 КБ = 1024 байта, 1 МБ = 2²⁰ = 1 048 576 байт, 1 ГБ = 2³⁰ байт (строго говоря, это КиБ, МиБ и ГиБ по IEC 80000-13).

Чтобы оценить структуру с другой сложностью, подставьте в n реальное количество элементов: для матрицы n×n это n², для списка смежности — число вершин плюс рёбер. Накладные расходы контейнеров и выравнивание калькулятор не учитывает, о чём и предупреждает.

Пример расчёта

Массив из 1 000 000 чисел int32 (4 байта): 1 000 000 × 4 = 4 000 000 байт = 3 906,3 КБ ≈ 3,81 МБ ≈ 0,004 ГБ. Если хранить те же числа как int64 или double (8 байт), получится 8 000 000 байт ≈ 7,63 МБ — ровно вдвое больше.

На что обратить внимание

• В языках с объектными обёртками реальный расход выше в разы: в CPython элемент списка — это 8-байтовый указатель плюс отдельный объект int (около 28 байт для небольших чисел).
• Динамические массивы (std::vector, ArrayList, list) резервируют запас ёмкости, а хеш-таблицы держат часть ячеек пустыми — закладывайте резерв.
• Для рекурсивных алгоритмов не забудьте стек вызовов: глубина рекурсии × размер кадра — тоже пространственная сложность.
• Различайте вспомогательную память (дополнительную к входу) и полную: сортировка слиянием требует O(n) дополнительно, сортировка кучей — O(1).