Какова пространственная сложность этого алгоритма (n или log (n))?

#algorithm #complexity-theory #pseudocode #space-complexity

#алгоритм #теория сложности #псевдокод #пространственная сложность

Вопрос:

У меня есть вопрос относительно пространственной сложности (памяти) этого конкретного фрагмента псевдокода:

 int b(int n, int x) {
   int sol = x;
   if (n>1) {
      for (int i = 1; i <= n; i  ) {
         sol = sol i;
      }
      for (int k=0; k<3; k  ) {
         sol = sol   b(n/3,sol/9);
      }
   }
   return sol;
}

Вызывается код: b(n,0)

Мое мнение таково, что пространственная сложность прогрессирует линейно, то есть n , потому что по мере того, как входные данные n растут, увеличивается и количество объявлений переменных ( sol ).

В то время как мой друг настаивает, что это должно быть log(n) . Я не совсем понял его объяснение. Но он сказал что-то о втором for цикле и о том, что три рекурсивных вызова выполняются последовательно.

Итак, n или log(n) правильно?

Ответ №1:

Общее количество раз, когда b вызывается функция, равно O(n) , но пространственная сложность равна O(log(n)) .

Рекурсивные вызовы в вашей программе приводят к увеличению стека выполнения. Каждый раз, когда выполняется рекурсивный вызов, все локальные переменные помещаются в стек (размер стека увеличивается). И когда функция возвращается из рекурсии, локальные переменные извлекаются из стека (размер стека уменьшается).

Итак, что вы хотите вычислить здесь, это максимальный размер стека выполнения, который равен максимальной глубине рекурсии, что явно O(log(n)) .

1. Извините, но я не могу понять, почему максимальная глубина рекурсии находится в O(log(n)) . Почему бы не, например O(sqrt(n)) ? И если это в O(log(n)) , какое основание имеет логарифм и почему?

2. Вы начинаете с вызова функции для n. Затем каждый раз, когда вы вызываете b, вы делите n на 3, так что у вас получается n / 3, n / 9, n / 27 …, n / 3 ^ d (где d — глубина рекурсии). Таким образом, знаменатель увеличивается экспоненциально — вот почему для достижения 1 (это когда рекурсия останавливается) требуется логарифмическое количество шагов из n.

3. А, кажется, теперь я понял. Но не означает ли это, что база журналов должна быть равна 3? Такое, что O(log_3(n)) ?

4. Да, основание логарифма равно 3, но это не имеет значения из соображений сложности. O (log_3(n)) = O (log_2(n)) = O(log_whatever(n)). Таким же образом, что O (n) = O (2n) = O (7n).

5. O (n ^ 2) отличается от O (n ^ 3) и от O (n ^ 4). Причина, по которой база журналов не имеет значения, заключается в том, что (например) log_2 (n) = c * log_3 (n), где c — некоторое постоянное число. Вы можете прочитать на wiki , как изменить базу журнала.

Ответ №2:

Я думаю, что сложность

O (база log 3 (n))