Total space и Auxiliary space
Оценка, которую мы изучали ранее, называется Time Complexity или Временная сложность.
Не смотря на название, не думаем про секунды, миллисекунды и т.д.
Существует еще одна оценка - оценка по памяти или же пространственная оценка/сложность (Space complexity).
Пространственная сложность показывает, сколько памяти (помимо самой входной информации) требуется алгоритму в зависимости от размера входа n.
___
Немного душноты
Существует Total space и Auxiliary space.
Total space - вся используемая память, включая память под входные данные.
Auxiliary space (вспомогательная память) - память, дополнительная к входу.
Когда говорим про пространственную сложность, мы имеем в виду Auxiliary space.
___
Что стоит считать при оценке пространственной сложности:
- массивы;
- хеш-таблицы;
- стек рекурсии;
- дополнительные структуры;
- и т.д.
Что не стоит считать:
- константные ссылки/указатели, размер которых не зависит от n (они O(1)).
___
Обозначения и оценка абсолютно такие же как и у временной сложности.
Далее разберем примеры...
___
course_intro
