Big O сложность рекурсивной функции в цикле

Question

Я наткнулся на решение проблемы Leetcode поиска возрастающих подпоследовательностей. Я думаю, что решение имеет сложность O (N!) И может не масштабироваться для больших массивов.

Не могли бы вы подробнее рассказать, как вы рассчитали сложность для этого?

public class IncreasingSubsequences {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] a = new int[]{4, 6, 7, 8};
        findSubsequences(a);
    }

    public static List<List<Integer>> findSubsequences(int[] nums) {
        List<List<Integer>> res = new LinkedList<>();
        helper(new LinkedList<Integer>(), 0, nums, res);
        return res;
    }

    // [4, 6, 7, 7]
    private static void helper(LinkedList<Integer> list, int index, int[] nums, List<List<Integer>> res) {

        if (list.size() > 1){
            res.add(new LinkedList<Integer>(list));
            System.out.println(Arrays.toString(list.toArray()));
        }

        Set<Integer> used = new HashSet<>();

        for (int i = index; i < nums.length; i++) {
            if (used.contains(nums[i]))
                continue;
            if (list.size() == 0 || nums[i] >= list.peekLast()) {
                used.add(nums[i]);
                list.add(nums[i]);
                helper(list, i + 1, nums, res);
                System.out.println("Will remove" + list.get(list.size() - 1));
                list.remove(list.size() - 1);
                //System.out.println(">>" + Arrays.toString(list.toArray()));
            }
        }
    }

}

Answer 1

Время и сложность памяти почти O (N!), Как вы и подозревали. Точнее, дополнительная память - это O (N * 2 ^N ), а время - O (M * 2 ^N ). Где M - длина nums, исходного списка, а N - количество уникальных значений в нем (st N <= M). </p>

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

Если исходный набор содержит N (уникальных) значений в порядке возрастания nums, то набор мощности содержит 2 ^N уникальных наборов. Это также длина результирующего списка и количество вызовов рекурсивной функции.

Можно показать, что каждый элемент в исходном наборе появляется точно в половине подмножеств (в порядке возрастания) . Это означает, что если мы напишем все 2 ^N списков результата (которые представляют все подмножества) и объединим их, каждый элемент появится 2 ^N / 2 раза. Поскольку существует N уникальных значений, длина конкатенационного списка будет 2 ^N * N / 2, что составляет O (N * 2 ^N ).

Мы можем спокойно игнорировать длину списка верхнего уровня, который содержит все подмножества, так как он короче, чем все списки, объединенные вместе. Итак, наконец, дополнительная сложность пространства равна O (N * 2 ^N ). В этом же и сложность распечатки (ее длина). Если M> N, то в худшем случае все повторяющиеся элементы приходят в конце. Это приводит к тому, что все рекурсивные вызовы должны выполнять дополнительные операции MN в конце каждого вызова. Поскольку имеется 2 ^N вызовов, то сложность времени становится O (N * 2 ^N ) + O ((MN) * 2 ^N ) = O ( M * 2 ^N ).

Обратите внимание, что временная сложность почти оптимальна, поскольку временная сложность не может быть ниже, чем сложность дополнительной памяти. Хотя немного лучше масштабировать невозможно. Единственное неэффективное место - это обработка неуникальных значений. Если повторяющиеся значения удаляются из nums перед рекурсией, то M почти исключается из O () всего алгоритма. В этом случае временная сложность становится O (M + N * 2 ^N ), где для разумного M, st M <= N * 2 <sup>N , M можно исключить из выражение.