Сложность времени рекурсивной функции с несколькими ветвями

Question

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

Однако для приведенных ниже кодов,

const int N = 100, W = 100000; 
int p[N][W + 1]; // the values of element in the array p are 0, 1, 2. 
int output[N]; 

void find_path(int n, int w, int k) { 
    if (n < 0) { 
     for (int i=0; i<k; ++i) cout << output[i]; 
     return; 
    } 

    if (p[n][w] == 0) { 
     find_path(n-1, w, k); // the 1st branch 
    } 
    else if (p[n][w] == 1) { 
     output[k] = n; 
     find_path(n-1, w-weight[n], k+1); // the 2nd branch 
    } 
    else if (p[n][w] == 2) { 
     output[k] = n;     // the 3rd branch 
     find_path(n-1, w-weight[n], k+1); 
     find_path(n-1, w, k); 
    } 
} 

Вот мой анализ:

T(n) = T(n-1) + a // the 1st branch 
     T(n-1) + b // the 2nd branch 
     2*T(n-1) + c // the 3rd branch 

На первый взгляд, третья ветвь занимает больше времени, чем две другие ветви, Могу ли я просто игнорируйте 1-ю и 2-ю ветку?, поэтому сложность может быть T(n)=2*T(n-1), и результат O(2^n), Я прав?

Кроме того, что, если есть еще один find_path вызов во 2-й ветви

else if (p[n][w] == 1) { 
     output[k] = n; 
     find_path(n-1, w-weight[n], k+1); // the 2nd branch 
     find_path(n-1, w, k+1); 
    } 

Как вычислить временную сложность в этом случае?

Answer 1

Да, вы должны взять их максимум (для наихудшего случая), что соответствует третьей ветке. Из-за этого вы можете игнорировать 1-й и 2-й ветви. Затем повторение составляет T(n)<=2T(n-1)+O(1), так что T(n)=O(2^n).

По этой же причине вы можете добавить новый вызов во вторую ветвь «бесплатно».