Złożoność czasowa wyliczenia sumy podzbiorów - algorytm, big-o, wyliczenie, suma podzbiorów

Zwykle, gdy mamy do czynienia z kombinacjami, wydaje się, że występuje złożoność Big-O O (n wybierz k). W tym algorytmie generuję wszystkie kombinacje w tablicy, które odpowiadają sumie docelowej:

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]]

Trudno mi tutaj określić Big-O, czy to jest O(n choose t) algorytm? Jeśli nie, co to jest i dlaczego?

Odpowiedzi:

Jeśli chodzi o zapewnienie najgorszej złożoności pod względem ustawionego rozmiaru, n, to jest Θ (2ⁿ). Biorąc pod uwagę dowolny zestaw, jeśli suma docelowa jest wystarczająco duża, skończysz wyliczając wszystkie możliwe podzbiory zestawu. Θ (2ⁿ), jak można zobaczyć na dwa sposoby:

• Każdy element można wybrać, czy nie.

• To jest twoje Θ (n wybierz k), podsumowałem wszystko k.

Bardziej wyrafinowana granica uwzględniałaby obie te rzeczy n i suma docelowa t. W tym przypadku, zgodnie z rozumowaniem drugiego punktu powyżej, jeśli wszystkie elementy (i suma docelowa) są dodatnimi liczbami całkowitymi, wówczas złożoność będzie sumą Θ (n wybierz k) dla k sumując tylko do t.

Twój algorytm jest przynajmniej O(2^n) i wierzę, że tak jest O(n * 2^n). Oto wyjaśnienie.

W twoim algorytmie musisz wygenerować wszystkie możliwe kombinacje zestawu (z wyjątkiem pustego zestawu). To jest:

O(2^n) przynajmniej. Teraz dla każdej kombinacji musisz je podsumować. Niektóre zestawy mają długość 1 na długości n, ale większość z nich byłaby gdzieś długa n/2. Więc wierzę, że twoja złożoność jest bliska O(n * 2^n).