Блог

У меня проблема, и я борюсь со сложностью своего решения во времени и пространстве:

Задан массив целых чисел (возможные дубликаты) A и min , low , high являются целыми числами. Найдите общее количество комбинаций элементов в A этом:

• low <= A[i] <= high
• Каждая комбинация имеет как минимум min числа.
• Числа в одной комбинации могут быть дубликатами, поскольку они считаются уникальными в A, но комбинации не могут быть дубликатами. Например: [1,1,2] -> комбинации: [1,1],[1,2],[1,1,2] в порядке, но [1,1],[1,1], [1,2], [2,1] ... нет.

Пример: A=[4, 6, 3, 13, 5, 10], min = 2, low = 3, high = 5

Существует 4 способа объединения допустимых целых чисел в: [4,3],[4,5],[4,3,5],[3,5]

Вот мое решение, и оно работает:

 class Solution:
    def __init__(self):
        pass
    def get_result(self, arr, min_size, low, high):
        return self._count_ways(arr, min_size, low, high, 0, 0)
    def _count_ways(self, arr, min_size, low, high, idx, comb_size):
        if idx == len(arr):
            return 0
        count = 0
        for i in range(idx, len(arr)):
            if arr[i] >= low and arr[i] <= high:
                comb_size  = 1
                if comb_size >= min_size:
                    count  = 1
                count  = self._count_ways(arr, min_size, low, high, i   1, comb_size)
                comb_size -= 1
        return count
  

Я использую обратное отслеживание, поэтому:

Время: O(n!) потому что для каждого отдельного целого числа я проверяю каждое оставшееся число в худшем случае — когда все целые числа могут образовывать комбинации.

Пробел: O(n) мне нужно не более n вызовов в стеке вызовов, и я использую только 2 переменные для отслеживания моих комбинаций.

Верен ли мой анализ?

Кроме того, это немного выходит за рамки, но: должен ли я сделать какую-то памятку, чтобы улучшить ее?

Если я правильно понимаю ваши требования, ваш алгоритм слишком сложный. Вы можете сделать это следующим образом:

1. Вычислить массив B , содержащий все элементы A между low и high .
2. Возвращает sum of Choose(B.length, k) значение k = min .. B.length , где Choose(n,k) находится n(n-1)..(n-k 1)/k! .

Сложности во времени и пространстве O(n) возникают, если вы используете запоминание для вычисления числителей / знаменателей Choose функции (например, если вы уже вычислили 5*4*3 , вам нужно только одно умножение для вычисления 5*4*3*2 и т.д.).

В вашем примере вы получите B = [4, 3, 5] , so B.length = 3 , и результат

   Choose(3, 2)   Choose(3, 3) 
= (3 * 2)/(2 * 1)   (3 * 2 * 1)/(3 * 2 * 1) 
= 3   1
= 4
  

Ваш анализ временной сложности не совсем верен.

Я понимаю, к чему вы клоните O(n!) : for i in range(idx, len(arr)): цикл уменьшается в длину с каждым рекурсивным вызовом, поэтому кажется, что вы делаете n*(n-1)*(n-2)*... .

Однако рекурсивные вызовы из цикла длины m не всегда содержат цикл размера m-1 . Предположим, что ваш самый внешний вызов содержит 3 элемента. Цикл перебирает 3 возможных значения, каждое из которых порождает новый вызов. Первый такой вызов будет иметь цикл, который повторяет 2 значения, но следующий вызов повторяет только 1 значение, а последний сразу попадает в ваш базовый вариант и останавливается. Таким 3*2*1=((1 1) (1 1) (1 1)) образом, вместо этого вы получаете ((1 0) 1 0) .

Вызов _count_ways с массивом размера n занимает в два раза больше времени, чем вызов с размером n-1 . Чтобы увидеть это, рассмотрим первую ветвь в вызове size n , которая заключается в выборе первого элемента или нет. Сначала мы выбираем этот первый элемент, что приводит к рекурсивному вызову с размером n-1 . Во-вторых, мы не выбираем этот первый элемент, что дает нам n-1 элементы, оставшиеся для повторения, так что это похоже на то, как если бы у нас был второй рекурсивный вызов с размером n-1 .

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

Однако, поскольку вы пытаетесь только подсчитать комбинации, а не что-то с ними делать, это крайне неэффективно. Смотрите Ответ @Mo B. Для лучшего решения.