Какое худшее время для этого кода O (R * C)?

Question

я наткнулся на этот вопрос на InterviewBit:

int memo[101][101]; 
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; 
    if (memo[r][c] != -1) return memo[r][c]; 
    memo[r][c] = V[r][c] + min(findMinPath(V, r + 1, c), findMinPath(V, r, c + 1)); 
    return memo[r][c]; 
} 

Callsite : 
memset(memo, -1, sizeof(memo)); 
findMinPath(V, 0, 0); 

Предположим R = V.size() и C = V[0].size() и V имеет положительные элементы

Не будет ли код создания бинарного дерева рода вызов функции, которая принимает O (2 ^{(m + n)}), так как каждый вызов функции вызывает два других вызова функций?

Answer 1

Этот алгоритм использует метод, известный как dynamic programming. Суть этого заключается в том, чтобы запомнить промежуточные результаты в таблице поиска и найти общее решение в виде комбинации частичных решений.

В этом конкретном случае вы можете видеть, что каждый вызов findMinPath будет либо листовым вызовом (не рекурсивом) с постоянной сложностью, либо сделать хотя бы одну запись в memo неотрицательной. Легко видеть, что если все записи в memo неотрицательны, функция никогда не будет рекурсивно. Поскольку существует только R × C элементов в memo, это верхняя граница общей сложности.

Тем не менее, реализация довольно неуклюжая. Зачем использовать глобальную переменную для memo и полагаться на ее инициализацию вызывающим абонентом -1? Кроме того, использование memset для записи массива целых чисел работает только для некоторых целых чисел со всеми одинаковыми байтами, что делает неперспективные предположения для целочисленного макета. И, наконец, есть уязвимость переполнения буфера, если R или C превышает магическое значение 101. Поэтому, если вы хотите быть педантичным, фактическая сложность постоянна.