Как определить временную сложность этого кода?

Я только начал изучать алгоритмы,Как определить временную сложность этого кода?

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 (R C), но правильный ответ O (2^(R C)) Я не могу понять, почему. Пожалуйста, объясни.

источник

2017-02-09 Manasvini Ganesh

Это дважды рекурсивно. Если вы вычеркиваете вызовы в виде графика, вы получаете двоичное дерево вызовов. Однако алгоритм для меня не имеет смысла. –

Хм. Разве не O ((C + R) выбирает C), поскольку код по существу перечисляет пути от (0,0) до (C, R). ? Это O (2^(RC)) Я думаю, но это довольно плохая верхняя граница. Например, когда R = C, (C + R) выбирает C, это приблизительно 4^R/sqrt (pi * R), который растет намного медленнее, чем 2^(R^2). –

Возможно, в вопросе есть опечатка: O (2^(R + C)), а не O (2^(RC))? Глубина дерева поиска не более R + C, поэтому 2^(R + C) является разумным первым приближением к сложности. Конечно, R + C = O (RC), поэтому вопрос как таковой теоретически правильный, но не имеет практического смысла (по крайней мере, для меня). –

При наличии нескольких рекурсивных вызовов хорошим приближением является количество ветвей (вызовов), поднятых до мощности высоты «дерева».

В вашем случае, у вас есть две ветви:

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

Таким образом, мы начнем с базой 2.

Тогда высота (или глубина) вашего «дерева» определяется сколько элементов находится в вашем векторе; в вашем случае у вас есть R элементов, но каждый элемент имеет в нем элементы C. Итак, наша сила - это RC.

Таким образом, ваше время выполнения приблизится, в худшем случае к O (2^RC).

источник

2017-02-09 16:01:47 Cruiser

Максимальная глубина дерева R + C, а не RC, не так ли? Начальное расстояние от (R, C) равно R + C, а расстояние уменьшается на 1 каждый рекурсивный вызов. –

@PaulHankin Я думаю, это потому, что в худшем случае R * C пройдут все элементы, так как Cruiser объяснил, что это должно быть 2^(R * C) –

В худшем случае, в одном пути, R + C (или возможно, R + C-2, но это не имеет никакого значения для сложности) пройдены элементы, а не элементы RC. В векторе есть элементы RC, но шаги ваших поисковых путей в сетке идут только в направлениях (+1, 0) и (0, +1). –

Наихудший сценарий, findMinPath называет себя дважды в этой строке

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

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

источник

2017-02-09 16:01:12 doctorlove

Почему 2^(RC), а не, например, 2^(R + C). Так как R + C - максимальная глубина дерева поиска. –

Как определить временную сложность этого кода?

ответ

Смежные вопросы