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

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

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) Правильно?

источник

2016-10-23 de_dust

В общее время номер функции b называют это O(n), но пространство сложность O(log(n)).

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

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

источник

2016-10-23 21:23:04 mateuszlo

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

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

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

Я считаю, что сложность

O (журнал 3 базы (п))

источник

2016-10-23 21:03:49

Можете ли вы объяснить, почему вы так думаете? –

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

ответ

Смежные вопросы