Komplexität beim Generieren aller Kombinationen

Question

Interviewfragen, bei denen ich mit "das könnte durch Generieren aller möglichen Kombinationen für die Array-Elemente gelöst werden" beginnen, sollen normalerweise dazu dienen, etwas Besseres zu finden.

Jedenfalls möchte ich hinzufügen "Ich würde definitiv eine andere Lösung bevorzugen, da dies O (X)" ist. Die Frage ist: Was ist die O (X) -Komplexität der Generierung aller Kombinationen für eine gegebene Menge?

Ich weiß, dass es n gibt!/(n-k)! k! Kombinationen (Binomialkoeffizienten), aber wie bekommt man die große O-Notation?

Answer 1

Erstens gibt es nichts falsch mit der Verwendung von O(n!/(n-k)!k!) - oder jede andere Funktion f(n) als O(f(n)), aber ich glaube, dass Sie für eine einfachere Lösung suchen, der immer noch den gleichen Satz hält.

Wenn Sie bereit sind, an der Größe der Teilmenge zu sehen k als konstant,

für k < = nk:

n!/((n-k)!k!) = ((n-k+1) (n-k+2) (n-k+3) ... n)/k! 

Aber das oben ist eigentlich (n^k + O(n^(k-1)))/k!, die in O(n^k) ist

Und falls n-k<k, erhalten Sie O(n^(n-k))

Das gibt uns O(n^min{k,n-k})

Answer 2

Als Folge zu @amit, eine obere Grenze von min {k, n-k} ist n/2.

Daher die obere Grenze für "n wählen k" Komplexität ist O (n^(n/2))