Рекурсия в цикле сложности времени - PullRequest
Новая
       7

Рекурсия в цикле сложности времени

0 голосов
/ 22 декабря 2018

Я создал этот алгоритм для решения проблемы, используя стратегию возврата.Задача состоит в следующем:

Задано множество A из n целых чисел и двух целочисленных значений, m и c.Вычислить все подмножества A, m элементов, чтобы сумма их значений была c.

Алгоритм (в Java) : 

public class Algorithm {

    private List<Integer> a;
    private int m;
    private int c;

    /**
     * @param a Initial set
     * @param m Maximum number of elements stored in the subset
     * @param c Desired sum
     */
    Algorithm(List<Integer> a, int m, int c) {
        this.m = m;
        this.c = c;
        this.a = a;

        findSubsets(0, new int[m], 0, 0);
    }

    /**
     * @param i Index to go through the initial set
     * @param subset Solution candidate
     * @param level Current number of elements stored in the subset
     * @param sum  Current sum of the elements stored in the subset
     */
    private void findSubsets(int i, int[] subset, int level, int sum) {

        // Base case
        if (level == m) {
            if (sum == c) {
                System.out.println(Arrays.toString(subset));
            }
        }

        // Exploration
        else {
            while (i < a.size()) {
                subset[level] = a.get(i);

                findSubsets(i + 1, subset, level + 1, sum + a.get(i));

                i++;
            }
        }
    }
}

Сложность по времени:

С этим решением я экспериментально определил, что когда m стремится к n, сложность стремится к O (2 ^ n).Однако после прочтения руководств о том, как рассчитать сложность времени, я пока не могу определить этот результат математически.Я также очень заинтересован в среднем случае, и я очень растерялся из-за того, как его вычислить.

Я знал, что это может быть вопрос новичка, но я был бы очень признателен, если бы кто-нибудь мог мне помочь!Спасибо

Ответы [ 2 ]

0 голосов
/ 22 декабря 2018

Алгоритм вычисляет каждое подмножество, предполагая, что m = n.Для каждого 0<=i<n вы удваиваете количество подмножеств, которые были возможны на i-1, потому что для каждого подмножества на уровне i-1 есть два случая, чтобы привести их к уровню i: добавить a[i] или don 'т.

Например, если i = 2 и есть 4 возможных подмножества (например, {}, {A}, {B}, {AB}), то для i = 3 будет 4 подмножества, которые не 't содержит a[3] (так же, как и раньше) и 4 новых подмножества, которые содержат a[3] (например, {C}, {AC}, {BC}, {ABC}), всего 8 *. 1010 *

Поскольку мы удваиваем для каждого i<n, общее количество возможных подмножеств составляет 2^n, в случае, когда n = m.

0 голосов
/ 22 декабря 2018

Временная сложность вашего алгоритма будет O(m * 2^m), если учесть все подмножества A, что меньше или равно m, так как вы получаете level для каждого из них !.Умножение на m предназначено для суммирования значения каждого подмножества.

...