#algorithm #complexity-theory #space-complexity
#алгоритм #сложность -теория #сложность пространства
Вопрос:
Итак, Everbody знаком с постоянной O(1) или линейной O(N) сложностью пространства.
Но у меня есть вопрос, есть ли какой-либо случай, когда пространственная сложность алгоритма пропорциональна O(NLogn) или O(N^2) . Если это возможно, в чем его преимущество.
PS- Я исследовал различные сайты, но не получил удовлетворительного решения.
Комментарии:
1. Вы должны перенести это на обсуждение
2. Любой алгоритм, который возвращает результат размера
f(N), занимает как минимумO(f(N))дополнительное пространство (при условии, конечно, что результат не разделяет пространство с вводом).
Ответ №1:
Почти любой алгоритм можно заставить использовать O(N^2) память. Рассмотрим некоторые f(a,b) , где 0 < a,b < N и f дорого вычислять. Для сокращения времени выполнения очевидным решением является использование справочной таблицы размера N * N с предварительно рассчитанными результатами. Такой компромисс между временем выполнения и использованием памяти может быть сделан очень часто.
В общем, алгоритмы, использующие матрицы, обычно используют N*N память для хранения матриц. Например, чтобы повернуть точку в N=3 измерениях, вы можете использовать матрицу 3x3 вращения.