Как вычислить пространственную сложность функции A, когда A вызывает функцию B в цикле for?

Question

Мне интересно, как вычислить сложность пространства и вспомогательное пространство функции A, когда A вызывает функцию B в цикле for.Давайте опишем два примера:

---

case 1: Что такое сложность пространства и вспомогательное пространство функции A

void A(int k) {
    int c = 25;
    for (int i = 0; i < k; i++) {
        B();
    }
}

void B () {
   int d = 5;
}

---

case 2: Какова сложность пространства и вспомогательное пространство функции A

void A(int k) {
  int c = 25;
  for (int i = 0; i < k; i++) {
     int d = 25;
  }
}

---

В чем разница между этими двумя случаями?(конечно, если есть разница)

Answer 1

Цикл (как показано) ничего не добавляет к сложности пространства.На каждой итерации цикла выделяется кадр стека для 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²).