Как найти временную сложность следующего рекурсивного кода?

Question

Как вывести сложность выполнения следующей программы?

public void function(int n){
   if(n==1) return;
   for(int i=0;i<n;i++){
     function(i)
   }
}

function(4);

Что я понимаю,

T(n) = n(T(n-1));
T(n-1) = (n-1)(T(n-2))
T(n-2) = (n-2)(T(n-2))

После замены n(T(n-1)) с последующим расширением,

T(n) = n((n-1)((n-2)(T(n-2))))

Что, по сути, не что иное, как

n*(n-1)*(n-2)...1 = n!

Однако в разных постах я вижу, что это 2^n, а не n!.Может кто-нибудь объяснить мне, если я что-то пропустил?

Answer 1

T(n) = n T(n-1) действительно будет O(N!) - но это неправильное рекуррентное соотношение для function.

Цикл работает от i = 0 до i = n-1, что означает, что рекурсивными вызовами являются function(0), function(1), function(2) ..., function(n-1). Следовательно, рекуррентное соотношение:

T(n) = T(0) + T(1) + T(2) + ... + T(n-1)

Есть хитрый трюк, чтобы помочь вам решить эту проблему. Рассмотрим термины в T(n-1) и напишите расширение вместе с расширением T(n):

T(n)   = T(0) + T(1) + T(2) + ... + T(n-3) + T(n-2) + T(n-1)
                                                      ------
T(n-1) = T(0) + T(1) + T(2) + ... + T(n-3) + T(n-2) 

Видите, куда это идет? Вычтите одно из другого, и останется только подчеркнутый член T(n-1):

T(n) - T(n-1) = T(n-1)
T(n) = 2 T(n-1)

Эта альтернативная форма повторения теперь разрешима так же, как и раньше:

T(n) = 2^2 T(n-2)
     = 2^3 T(n-3)
     = 2^4 T(n-4)
     = ...
     = O(2^n)

1029 * что и требовалось доказать *