Рекуррентное уравнение - Рекурсия внутри цикла

Question

Я пытался решить мою университетскую проблему об уравнениях повторения и вычислительной сложности, но я не могу понять, как установить уравнение повторения.

static void comb(int[] a, int i, int max) { 
    if(i < 0) { 
     for(int h = 0; h < a.length; h++) 
      System.out.print((char)(’a’+a[h])); 
     System.out.print("\n"); 
     return; 
    } 
    for(int v = max; v >= i; v--) { 
     a[i] = v; 
     comb(a, i-1, v-1); 
    } 
} 

static void comb(int[] a, int n) { // a.length <= n 
    comb(a, a.length-1, n - 1); 
    return; 
} 

Я попытался установить следующее уравнение

   O(n) + c      if i < 0 
T (n, i, j) = { 
       (j-i) T(n, i-1, j-1)   otherwise 

Решая

T(n, i, j) = (j-i) T(n, i-1, j-1) = 
(j-i) (j-1-i+1) T(n, i-2, j-2) = 
(j-i)^k T(n, i-k, j-k) 

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

Спасибо и извините за мой плохой английский.

Луиджи

Answer 1

С вашим выводом

T(n, i, j) = ... = (j-i)^k T(n, i-k, j-k) 

вы почти закончили! Просто установите k = i+1, и вы получите:

T(n, i, j) = (j-i)^(i+1) T(n,-1,j-i-1) = (j-i)^(i+1) O(n) = 
O(n (j-i)^(i+1))