Найти рекуррентное соотношение этого алгоритма? - PullRequest
Новая
       8

Найти рекуррентное соотношение этого алгоритма?

1 голос
/ 04 февраля 2010

Предполагая, что n = B-A + 1, мне нужно вывести рекуррентное соотношение этого алгоритма: 

void recurringalgorithm(int *a, int A, int B){
  if (A == B){
    for (int j=0;j<B;j++){
      cout<<a[j];  
    }
    cout<<endl;
    return;
  }
  for (int i=A;i<B;i++){
    dosomething(a[A],a[i]);
    recurringalgorithm(a,A+1,B);
    dosomething(a[A],a[i]);
  }
}

Помощь

1 Ответ

4 голосов
/ 04 февраля 2010

Предположим, сложность вашего рекурсивного алгоритма составляет h(A,B).

Из вашего кода вы можете разделить h на 2 случая: 

h(A,B) = { complexity-of-if-branch          if A = B
         { complexity-of-rest-of-the-code   otherwise

«Сложность ветки» тривиальна. Для «сложности остальной части кода», поскольку она включает recurringalgorithm, вам нужно будет снова включить h.

Например, если функция определена как 

function hh(A,B) {
    for (var i = A+1; i < B; ++ i)
        hh(i, B);
}

Тогда сложность будет 

hh(A,B) = hh(A+1, B) + hh(A+2, B) + ... + hh(B-1, B)

Вы можете сравнить это с вашим кодом для обобщения.

(Кстати, сложность h(A,B) = O(B * (B-A)!))

...