Рубрики

Вспомогательное пространство с рекурсивными функциями

Анализ

Условие: рекурсия

Память, используемая программой, иногда так же важна, как и время работы, особенно в стесненных условиях, таких как мобильные устройства.
Например, если нам нужно создать массив размером n, для этого потребуется пространство O (n). Если нам нужен двумерный массив размером nxn, для этого потребуется O (n 2 ).

Пространство стека в рекурсивных вызовах также считается дополнительным пространством, требуемым программой.
Например :

int sum(int sum)

{

   if (n <= 0)

       return 0;

   return n + sum(n-1);

}

В приведенном выше примере функции каждый вызов добавляет новый уровень в стек.

     Sum(5)
	->sum(4)
            ->sum(3)
	        ->sum(2)
	            ->sum(1)
	       	        ->sum(0)

Каждый из этих вызовов добавляется в стек вызовов и занимает реальную память. Таким образом, подобный код занял бы O (n) времени и O (n) вспомогательного пространства.
Однако то, что у вас всего n вызовов, не означает, что оно занимает O (n) место. Рассмотрим функции ниже, которые добавляют соседние элементы между 0 и n:
Пример:

// нерекурсивный код, который делает n вызовов
// но занимает O (1) лишний пробел.

int pairSumSequence(int n)

{

    int sum = 0;

    for (int i=0; i<n; i++)

        sum += pairSum(i, i+1);

    return sum;

}

  

int pairSum(int a, int b)

{

    return a + b ;

}

В этом примере будет примерно O (n) обращений к pairSum. Однако эти вызовы не существуют одновременно в стеке вызовов, поэтому нам нужно только пространство O (1).

Эта статья предоставлена Ранджу Кумари . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Вспомогательное пространство с рекурсивными функциями

0.00 (0%) 0 votes