lese ich Introduction to Algorithms 3rd Edition (Cormen and Rivest) und auf Seite 69 in der "A-Brute-Force-Lösung", dass sie feststellen, n = 2 Theta wählen (n^2). Ich würde denken, dass es stattdessen in Theta (n!) Sein würde. Warum wählt n 2 fest an n-Quadrat gebunden? Vielen Dank!Die Komplexität von n wähle 2 ist in Theta (n^2)?
n wählen 2
n (n - 1)/2
Dies ist
n /2 + n/2
können wir, dass n siehe (n-1)/2 = Θ (n), indem die Grenze ihrer Verhältnisse wobei wenn n gegen Unendlich geht:
lim n → ∞ (n /2 + n/2)/n = 1/2
Da diese heraus kommt zu einer endlichen, von Null verschiedenen Menge, haben wir n (n-1)/2 = Θ (n).
Allgemeiner: n wählen für jede feste Konstante k k ist Θ (n k), weil es zu
n gleich ist! (K (n! - k))/= n (n-1) (n-2) ... (n-k + 1)/k!
Welches ist ein Polynom k-ten Grades in n mit einem führenden Koeffizienten ungleich Null.
Hoffe, das hilft!
Natürlich ! Ich dachte aus irgendeinem Grund, dass n wählen k war (n!)/(K!). –
@ JennyShoars - Das wäre auf jeden Fall verwirrend. Hoffe das hat alles geklärt! – templatetypedef
wählen, n 2 = n (n + 1)/2 = (n^2 + n)/2 ... –
Cormen richtig ist. – 0x90
@ DennisMeng- Es ist n (n-1)/2 statt n (n + 1)/2. – templatetypedef