Каковы временные и пространственные сложности этой функции powerset? - PullRequest
Новая
       87

Каковы временные и пространственные сложности этой функции powerset?

2 голосов
/ 01 мая 2019

Здравствуйте, я практиковал алгоритмы и структуры данных, и я решил https://leetcode.com/problems/subsets/, которая является функцией powerset, но, похоже, мое решение слишком медленное.Вот код: 

def subsets(array):
    set = [array]
    n = len(array)
    for i in range(n):
        tmp_subsets = subsets(array[:i] + array[i+1:])
        for subset in tmp_subsets:
            if subset not in set:
                set.append(subset)
    return set

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

Я думаю, что сложность времени здесьO(n^n), поскольку у дерева рекурсии есть n ветвей на уровень и * всего 1010 * уровней, это правильно?

Так что это хуже, чем оптимальное решение O(2^n).

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

space_for_level(0)+space_for_level(1)+...+space_for_level(n)
n + (n-1) +...+ 1 = O(n^2)

Но, в конце концов, когда я возвращаю все, размер set равен O(2^n), поэтому моя сложность пространства будет O(2^n + n^2) = O(2^n).

Верен ли мой анализ как для времени, так и для пространства?Любые указатели, которые помогут мне мыслить яснее, приветствуются.

1 Ответ

1 голос
/ 01 мая 2019

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

Сложность времени можно суммировать до следующего отношения повторения:

T(n) = n * T(n-1) + n * 2^(n-1)

, так как существует основнаяцикл выполняется n раз, и каждый раз подмножества оставшихся элементов (n-1) сначала генерируются (T(n-1)) и , а затем повторяются (2^(n-1)) .

примечание отношение предполагает, что любая другая операция в цикле занимает постоянное время , что является разумным приближением, поскольку ее эффекты по мере роста n минимальны.Например, эта операция: 

if subset not in set

не не требует постоянного времени (это занимает линейное время в длине списка, также set.append(subset) не является постоянным временем в целом), но позволяет пропуститьэто пока (вы понимаете, как анализировать код).

Отношение рекуррентности предполагает сложность , по крайней мере, экспоненциальную .

Пространственная сложность

Прежде всего генерируются все подмножества n, это означает, по крайней мере, сложность O(2^n).Однако из-за рекурсии и повторной генерации подмножеств на каждом шаге сложность пространства больше, чем это.В частности, на каждом шаге цикла генерируется одна текущая копия подмножеств n-1, а затем увеличивается до исходных подмножеств.У нас есть:

S(n) = S(n-1) + 2^n

, так как каждый вызов подмножества создает 1 промежуточную текущую копию оставшихся подмножеств (т. Е. S(n-1)) плюс это объединяет те в исходные подмножества, которые 2^n.

примечание мы не учитываем объем памяти, необходимый для хранения каждого элемента набора подмножеств, который сам требует хранениясложности около O(n), но для простоты считаем, что это постоянное хранилище O(1) (например, для сохранения подмножества в виде слова, в двоичном кодировании, для небольшого n <= 64), поэтому все хранилище подмножеств (безсчитая вспомогательное хранилище) будет просто иметь сложность O(2^n) (иначе, как отмечено в комментарии, сложность хранилища для простого хранения всех подмножеств n имеет порядок O(n 2^n)).

Отношение рекуррентности предполагаетсложность , по крайней мере, экспоненциальная .

Решение

Поскольку основная теорема не может быть применена для этих рекуррентных соотношений (так какнотаd) проверить методы решения рекуррентных отношений первого порядка с переменными коэффициентами , чтобы решить вышеуказанные отношения (сложность пространства подобна арифметической прогрессии, в то время как сложность времени имеет более сложную форму) и приобрести точную форму сложности(хотя решение может быть очень сложным, и оно все равно будет экспоненциальным в одну или другую сторону)

Лучшая сложность

Лучшая сложность времени и пространства может бытьдостигается путем использования структуры и свойств подмножеств (с учетом определенного порядка, например, лексикография ).

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

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

PS.Вы также можете исследовать подобные вопросы на computer.science.stackexchange , который более полно связан с алгоритмической сложностью

...