Complexidade do tempo da enumeração Subconjunto-Soma - algoritmo, big-o, enumeração, subconjunto-soma

Normalmente, quando se lida com combinações, a complexidade Big-O parece ser O (n escolha k). Nesse algoritmo, estou gerando todas as combinações dentro da matriz que correspondem à soma desejada:

def combos(candidates,start, target):
if target == 0:
return [[]]
res = []
for i in range(start,len(candidates)):
for c in combos(candidates, i+1, target-candidates[i]):
res.append([candidates[i]]+ c)
return res


print combos([2,1,10,5,6,4], 10)
# [[1, 5, 4], [10], [6, 4]]

Eu estou tendo dificuldade em determinar Big-O aqui, isso é um O(n choose t) algoritmo? Se não, o que é e por quê?

Respostas:

Se o objetivo é dar a pior complexidade em termos do tamanho do conjunto, nentão é Θ (2ⁿ). Dado qualquer conjunto, se a soma de destino for grande o suficiente, você acabará enumerando todos os subconjuntos possíveis do conjunto. Θ (2ⁿ), como pode ser visto de duas maneiras:

• Cada item pode ser escolhido ou não.

• É o seu N (n escolha k), resumindo tudo k.

Um limite mais refinado levaria em conta tanto n e a soma alvo t. Neste caso, seguindo o raciocínio do segundo ponto acima, então se todos os elementos (e soma alvo) forem inteiros positivos, então a complexidade será a soma de N (n escolha k) para k Somando apenas até t.

Seu algoritmo é pelo menos O(2^n) e eu acredito que é O(n * 2^n). Aqui está uma explicação.

Em seu algoritmo, você precisa gerar todas as combinações possíveis de um conjunto (exceto de um conjunto vazio). Então isso é:

O(2^n) finalmente. Agora, para todas as combinações, você precisa resumi-las. Alguns conjuntos são de comprimento 1 em é de comprimento n, mas a maioria deles seria em algum lugar de comprimento n/2. Então eu acredito que sua complexidade está próxima do O(n * 2^n).