Что такое сложность времени и пространства для фрагмента рекурсивного кода ниже? - PullRequest
Новая
       26

Что такое сложность времени и пространства для фрагмента рекурсивного кода ниже?

0 голосов
/ 28 мая 2018

Ниже приведена рекурсивная функция для вычисления значения биномиального коэффициента C ', т.е. комбинации!Я хочу понять сложность этого и временного пространства в терминах N и K (при условии, что мы вычисляем NCK). 

public class ValueOfBinomialCofecientC {

static int globalhitsToThisMethod = 0;

    public static void main(String[] args) {
        // Calculate nCk. 
        int n = 61, k = 55;
        long beginTime = System.nanoTime();
        int ans = calculateCombinationVal(n, k);
        long endTime = System.nanoTime() - beginTime;

        System.out.println("Hits Made are : " +globalhitsToThisMethod + " -- Result Is : " + ans + " ANd Time taken is:" + (endTime-beginTime));
    }

    private static int calculateCombinationVal(int n, int k) {
        globalhitsToThisMethod++;
        if(k == 0 || k == n){
            return 1;
        } else if(k == 1){
            return n;
        } else {
            int res = calculateCombinationVal(n-1, k-1) + calculateCombinationVal(n-1, k);
            return res;
        }
    }

}

1 Ответ

0 голосов
/ 07 августа 2018

Время выполнения очень интересно nCk.Рекурсивно это выражается как:

f(n,k) = f(n-1,k-1) + f(n-1,k)

Выразите каждый член, используя формулу комбинации nCk = n!/(k! * (n-k)!).Ответ будет раздутым, если я попытаюсь написать каждый шаг, но как только вы подставите это выражение, умножьте все уравнение на (n-k)! * k!/(n-1)!.Все это должно аннулироваться, чтобы дать вам n = k + n - k.

Возможно, существуют более общие подходы к решению многопеременных рекурсивных уравнений, но этот очень очевиден, если вы запишите первые несколько значений вплоть до n=5и k=5.

...