Як визначити часову складність цього коду? - c ++, алгоритм, складність часу

Я тільки почав вивчати алгоритми,

int findMinPath(vector<vector<int> > &V, int r, int c){
int R = V.size();
int C = V[0].size();
if (r >= R || c >= C) return 100000000; // Infinity
if (r == R - 1 && c == C - 1) return 0;
return V[r][c] + min(findMinPath(V, r + 1, c), findMinPath(V, r, c + 1));
}

Я думаю, що відповідь має бути O (RC) але правильна відповідь O (2 ^ (RC)) Я не можу зрозуміти, чому. Будь ласка, поясніть.

Відповіді:

Коли ви маєте кілька рекурсивних викликів, хорошим наближенням є кількість гілок (викликів), піднятих до потужності висоти "дерева".

У вашому випадку ви маєте дві гілки:

findMinPath(V, r+1, c)
findMinPath(V, r, c+1)

Отже, ми почнемо з бази 2.

Тоді висота (або глибина) вашого "дерева" визначається кількістю елементів у вашому векторі; у вашому випадку Ви маєте елементи R, але кожен елемент має елементи C. Таким чином, наша влада - це RC.

Таким чином, ваш час виконання буде наближеним, в гіршому випадку до O (2 ^ RC).

Найгірший випадок, findMinPath дзвонить себе в цьому рядку

return V[r][c] + min(findMinPath(V, r + 1, c), findMinPath(V, r, c + 1));

Отже, найгірший випадок, кожен виклик буде включати ще два виклики, поки ця рекурсія не закінчиться. Отже, два до влади.