Как я могу вычислить количество раз, когда определенная функция будет выполнена в рекурсии

Этот вопрос относится к ударному коду:

cost = [[1, 10, 75, 92],
         [-1, 0, 35, 50],
         [-1, -1, 0, 80],
         [-1, -1, -1, 0]]

def min_cost(source, destination):
   if s==d or s == d-1:
       return cost[s][d]
    mc = cost[s][d]
    for i in range(s+1, d):
        tmp = min_cost(s, i) + min_cost(i, d)
    if tmp < mc:
        mc = tmp
return mc

Когда я сделал сухой ход, я увидел, что min_cost (1,3) получает исполнение 2 раза. Я прочитал в одной книге, где автор упомянул, если бы у нас было 10 станций между ними, тогда min_cost (1, 3) будет работать 144 раза.

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

Ответы

Ответ 1

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

def min_cost(s, d):
    global count
    count += 1
    if s==d or s == d-1:
        return cost[s][d]
    mc = cost[s][d]
    for i in range(s+1, d):
        tmp = min_cost(s, i) + min_cost(i, d)
    if tmp < mc:
        mc = tmp
    return mc

for n in range (2, 8):
    cost = [[0 for i in range (n)] for j in range (n)]
    count = 0
    min_cost(0, n-1)
    print (str (n) + ': ' + str (count))

Выход:

2: 1
3: 3
4: 9
5: 27
6: 81
7: 243

Итак, мы видим, что число вызовов для ds = k равно 3 степени (k-1). Знание того, что мы должны доказать, иногда значительно упрощает поиск доказательства.

Теперь, к самому доказательству. Это будет доказательство по индукции. Во-первых, обратите внимание, что количество вызовов min_cost(s, d) зависит только от значения ds, а не от индивидуальных значений s и d.

База состоит в том, что для ds=1 мы получаем один вызов. Для ds>1 мы делаем наш один вызов, и из него следуют следующие вызовы:

min_cost(s, s+1) and min_cost(s+1, d)
min_cost(s, s+2) and min_cost(s+2, d)
...
min_cost(s, d-1) and min_cost(d-1, d)

Таким образом, для ds=k число вызовов f(k) равно:

f(k) = 1 +
       f(1) + f(k-1) +
       f(2) + f(k-2) +
       ... +
       f(k-1) + f(1)
     = 2 * (f(1) + f(2) + ... + f(k-1))

Если по индуктивному предположению мы уже доказали, что f (v) = 3 v для всех v <k, то f (k):
1 + 2 * (3 1 + 3 2 +... + 3 k-1), что тривиально 3 k завершая наше доказательство.

Наконец, обратите внимание, что, хотя представленный алгоритм является экспоненциальным, основная проблема может быть решена в полиномиальное время, наиболее просто в O ((ds) ^ 2), мнимая вызовы, для которых мы уже выполнили всю работу.

Ответ 2

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

Пример в псевдокоде:

function recursionfunction(x, y, recursioncount) {
    if(expressionIsFalse) {
        recursionfunction(x, y, recursioncount+1);
    } else {
        return recursioncount;
    }
}

print recursionfunction('','', 0);

Другим способом работы является назначение переменной по ссылке, указатель или глобальная переменная (в зависимости от языка программирования) и увеличение этого счетчика.

Это вам помогло?

Ответ 3

Я думаю, что глобальная переменная, которая лежит вне функции (член вашего класса, если в Java или глобальный var в C++/C), и увеличивая его значение на каждый каждый раз, когда вы его вызываете, должен сделать трюк.