Стоимость метода Java с несколькими рекурсии

Question

Мы имеем следующий метод 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 или какой-либо другой параметр метода. Как только вы определили размер ввода, как перейти к определению стоимости множественной рекурсии?

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

Answer 1

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

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

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

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

Answer 2

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

Answer 3

Оригинальный метод называется 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.

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