Стоимость java-метода с множественной рекурсией

У нас есть следующий метод Java:

static void comb(int[] a, int i, int max) {
    if(i < 0) {
        for(int h = 0; h < a.length; h++)
            System.out.print((char)(’a’+a[h]));
        System.out.print("\n");
        return;
    }
    for(int v = max; v >= i; v--) {
        a[i] = v;
        comb(a, i-1, v-1);
    }
}

static void comb(int[] a, int n) { // a.length <= n
    comb(a, a.length-1, n - 1);
    return;
}

Мне нужно определить асимптотическую оценку стоимости алгоритма comb(int[],int) в зависимости от размера входных данных. Поскольку я только начинаю заниматься этим типом упражнений, я не могу понять, означает ли в данном случае размер ввода размер массива a или какой-то другой параметр метода. После определения размера входных данных, как определить стоимость множественной рекурсии?

Подскажите, пожалуйста, рекуррентное уравнение, определяющее стоимость?


java recursion recurrence algorithm asymptotic-complexity
person Balboa    schedule 10.12.2015    source источник
comment
Если это назначение, оно должно быть частью вопроса о том, что использовать в качестве размера ввода. Или вы можете использовать оба ваших параметра одновременно.   -  person talex    schedule 10.12.2015
comment
рисование дерева рекурсии поможет   -  person Sleiman Jneidi    schedule 10.12.2015
comment
печать очень дорогая, если вы печатаете в файл, это примерно в 100 раз дороже, чем остальная часть вашего кода, но если вы пишете в консоль DOS, это может быть в 10 000 раз дороже. Если у вас есть алгоритм O (n ^ 2), в конечном итоге он может быть дороже, чем печать, но ваша проблема должна быть действительно большой.   -  person Peter Lawrey    schedule 10.12.2015

Ответы (3)


arrow_upward
1
arrow_downward

Чтобы определить сложность этого алгоритма, вы должны понимать, на какую «работу» вы тратите больше всего времени. Различные типы алгоритмов могут зависеть от различных аспектов его параметров, таких как размер ввода, тип ввода, порядок ввода и т. д. Это зависит от размера массива и n.

Такие операции, как System.out.print, (char), 'a' + a [h], a.length, h++ и так далее, являются операциями с постоянным временем и в основном зависят от команд процессора, которые вы получите после компиляции, и от процессора, на котором вы будете выполнять эти инструкции. Но в конце концов их можно суммировать, скажем, до константы C. Эта константа не будет зависеть от алгоритма и размера входных данных, поэтому вы можете смело исключить ее из оценки.

Этот алгоритм линейно зависит от размера ввода, потому что он циклически повторяет входной массив (с циклом от h = 0 до последнего элемента массива). И поскольку n может быть равно размеру массива (a.length = n - это наихудший случай для этого алгоритма, потому что он заставляет его выполнять рекурсию "размер массива"), мы должны учитывать этот входной случай в нашей оценке. И тогда мы получаем еще один цикл с рекурсией, который выполнит метод comb других n раз.

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

person Mikhailov Valentine    schedule 10.12.2015

arrow_upward
1
arrow_downward

Первоначальный вызываемый метод — comb(int[] a, int n), и вы знаете, что a.length <= n. Это означает, что вы можете ограничить время выполнения метода с помощью функции n, но вы должны подумать, можете ли вы вычислить лучшую оценку с помощью функции как n, так и a.length.

Например, если метод выполняет a.length * n шагов, и каждый шаг занимает постоянное количество времени, вы можете сказать, что метод занимает O(n^2) времени, но O(a.length * n) будет более точным (особенно если n намного больше, чем a.length.

Вы должны проанализировать, сколько раз метод вызывается рекурсивно и сколько операций происходит при каждом вызове.

person Eran    schedule 10.12.2015
comment
таким образом, в этом случае, поскольку у нас есть рекурсия внутри for, стоимость определяется количеством рекурсивных активаций, умноженным на количество раз, которое выполняется for? Итак, как я могу написать рекуррентное уравнение, которое позволит мне рассчитать стоимость? - person Balboa; 10.12.2015

arrow_upward
0
arrow_downward

В основном для заданного размера входного массива, сколько шагов требуется для вычисления ответа? Если вы удвоите размер ввода, что произойдет с количеством шагов? Суть в том, чтобы изучить ваши циклы и выяснить, сколько раз они выполняются.

person Neil Masson    schedule 10.12.2015