Как вычислить пространственную сложность функции A, когда A вызывает функцию B в цикле for?
Мне любопытно, как вычислить пространственную сложность и вспомогательное пространство функции A, когда A вызывает функцию B в цикле for. Давайте опишем два примера:
Случай 1: Что такое сложность пространства и вспомогательное пространство функции A
void A(int k) {
int c = 25;
for (int i = 0; i < k; i++) {
B();
}
}
void B () {
int d = 5;
}
случай 2: Что такое сложность пространства и вспомогательное пространство функции A
void A(int k) {
int c = 25;
for (int i = 0; i < k; i++) {
int d = 25;
}
}
В чем разница между этими двумя случаями? (конечно, если есть разница)
Решение
Цикл (как показано) ничего не добавляет к сложности пространства. На каждой итерации цикла кадр стека для B выделяется, а затем отбрасывается. B не выделяет память внутренне, поэтому его потребление пространства равно O (1), и поэтому A,
Если код выглядит так:
std::vector<int> B(int i) {
std::vector<int> result(i);
// Do something with result;
return result;
}
void A(int k) {
std::vector<std::vector<int>> storage;
for (int i = 0; i < k; i++) {
storage.push_back(B(i));
}
}
Тогда мы можем видеть, что каждый вызов функции B выделяет пространство O (k), и оно называется O (k) раз, поэтому сложность пространства A равна O (k²).
Другие решения
Других решений пока нет …