Explicação da complexidade de tempo O (n2 ^ n) para geração de powerset

Question

Estou trabalhando em um problema para gerar todos os conjuntos de potência de um determinado conjunto.O algoritmo em si é relativamente simples:

def power_sets(A):
    """Returns the power set of A as a list of lists"""

    if len(A) == 0:
        return [[]]

    else:
        ps_n1 = power_sets(A[:-1]) # Powerset of set without last element
        # Add nth element to each subset of the powerset of n-1 elements
        ps_n = [sub + [A[-1]] for sub in ps_n1]

        # Combine the two sets and return 
        return ps_n1 + ps_n

É claro que a complexidade do espaço é $O(n2^n)$, já que existem $n$ itens do conjunto, e cada elemento está na metade do $2^n$ conjuntos.

No entanto, o livro no qual estou trabalhando diz que a complexidade do tempo também é $O(n2^n)$, o que faz todo o sentido intuitivamente, mas estou tendo dificuldade em justificá-lo matematicamente.

Além de dizer "há um número x de itens para mexer, então a complexidade do tempo é pelo menos igual", alguém pode oferecer uma explicação da análise do tempo de execução com base no tempo de execução das instruções no meu algoritmo?

Esta resposta praticamente apenas diz que o tempo de execução é assim por causa da complexidade do espaço (não muito satisfatório, mas como um aparte - o tempo de execução pode ser melhor que a complexidade do espaço?)

Eu vi esta resposta, mas para ser honesto, é um pouco difícil de entender.Parece sugerir na última linha que o tempo de execução é $O(n^2*2^{n!})$ (já que (eu acho) $ | P_i | = 2^i $), e isso também não parece certo.

Tentei desenhar a árvore de chamadas e não ajudou, pois só existem $n-1$ chamadas recursivas feitas e, pelo que posso dizer, cada uma gasta $O(n^2)$ tempo.

De qualquer forma, alguém pode oferecer uma explicação convincente para esse tempo de execução?

Answer 1

Observe aquilo:

$T(N) = 2T(N-1) + 2^{N-1}$

$T(1) = 2$

Observe que durante todo o tempo de execução, nosso algoritmo apenas gasta tempo gerando mais dados.Portanto, nossa função T representa a quantidade de tempo que a função gasta executando uma entrada de tamanho N e também a quantidade de dados que ela gera a partir de uma entrada de tamanho N.

Nós temos $2T(N-1)$ porque primeiro fazemos a chamada recursiva, e a linha a seguir faz uma cópia de todos os dados novamente, em preparação para adicionar o elemento que deixamos de fora na chamada recursiva.Nós aderimos exatamente $2^{N-1}$ cópias do elemento que deixamos intencionalmente de fora, então é daí que vem o último termo.Finalmente, T(1)=2 porque com 1 elemento retornamos 2 subconjuntos possíveis (o conjunto inteiro e o conjunto vazio).

Desenrolando esta recorrência temos:

$T(N)=2T(N-1)+2^{N-1}$

$\quad \quad =2(2(T(N-2)+2^{N-2})+2^{N-1}$

$\quad \quad =2(2(2(T(N-3)+2^{N-3})+2^{N-2})+2^{N-1}$

$...$

$\quad \quad = 2^N + (N-1)*2^{N-1}$

$\quad \quad = O(N*2^N)$