Найти временную сложность функции, где рекурсивный вызов находится в цикле for

Question

Вот моя функция:

function a(n)

     print 'a'
     if n == 0:
        return 
     for (int i = 0; i<=n-1; i++):
        a(i)
     return

Так что в основном я понимаю, что для каждого вызова мы также вызываем все номера функций, ведущие к n рекурсивно, а затем для каждой функции мы снова делаем то же самое , Моя главная проблема, однако, заключается в том, что for l oop каждый раз перепрыгивает на переменное число, так что это похоже на выполнение рекурсии внутри рекурсии.

Answer 1

Завершается ли он в первую очередь?

Для n == 0 он просто возвращается. Но для n == 1 он будет называть себя для n == 0, n == 1 и n == 2. Таким образом, вызов a(1) вызовет еще один вызов a(1) ...

IOW, это бесконечный l oop и покажет бесконечную сложность.

---

Теперь после изменение алгоритма будет прекращено. Итак, позвольте мне исследовать это заново.

Для n == 1 он будет вызывать себя только с n == 0.

Для n == 2 он будет вызывать себя для n == 0, n == 1 и еще n == 0 из-за n == 1; это делает 3 звонка.

Для n == 3 он будет звонить сам 3 раза + 3 раза + 1 раз, делает 7 раз.

Для n == 4 он будет звонить 4 раза + 7 раз + 3 раза + 1 раз, получается 15 раз.

Это очень похоже на O (2 ^ n - 1) = O (2 ^ n).

(Это легко доказать по индукции; количество вызовов будет 2 ^ n - 1, что, очевидно, верно для всех приведенных выше примеров. Учитывая, что это верно для некоторых n, из этого легко будет сделать вывод, что это верно для n + 1)

---

Поскольку доказательство по индукции не является очевидным для ОП, здесь оно выглядит так:

Прежде всего, поскольку кроме l oop внутри функции ничего не происходит, оно ' Я добавлю только постоянное количество операций на итерацию, что означает, что будет достаточно подсчитать количество вызовов к себе.

Выше, это доказано для n = 1.

Сейчас Предположим, что это было доказано для некоторых n. Теперь мы будем следовать, что это верно для n + 1.

По индукционной гипотезе количество вызовов для a(n + 1) = n + 1 + \sum_{i=0}^n (2^i - 1) (извините за обозначения; это сработало бы для mathexchange. В нем говорится «сумма для я иду от 0 до n из (2 ^ i - 1) ").

Теперь n + 1 + \sum_{i=0}^n (2^i - 1) = \sum_{i=0}^n (2^i) = 2^{n + 1} - 1, который должен был быть показан.

Это доказывает, что сложность O (2 ^ п).

Answer 2

Анализ @Ronald абсолютно прав.

Вот другая версия программы для подсчета количества повторений рекурсии для различных значений n

public class FindingRec
{

   static int count;

   static void rr(int n)
   {
      count++;
      // System.out.print(n + ", ");
      if (n == 0)
         return;

      for (int i = 0; i < n; i++)
      {
         rr(i);
      }
   }

   public static void main(String[] args)
   {
      for (int n = 0; n < 10; n++)
      {
         count = 0;
         rr(n);
         System.out.println("For n = " + n + ", Count: " + count);
      }
   }
}

А вот и вывод:

For n = 0, Count: 1
For n = 1, Count: 2
For n = 2, Count: 4
For n = 3, Count: 8
For n = 4, Count: 16
For n = 5, Count: 32
For n = 6, Count: 64
For n = 7, Count: 128
For n = 8, Count: 256
For n = 9, Count: 512

Итак, сложность в точности равна O (2 ^ n).