Sto leggendo Introduction to Algorithms 3rd Edition (Cormen and Rivest) e a pagina 69 nella "Soluzione brute-force" dichiarano che n scegliere 2 = Theta (n^2). Penserei che sarebbe in Theta (n!) Invece. Perché n sceglie 2 strettamente legato a n al quadrato? Grazie!La complessità di n scelta 2 è in Theta (n^2)?
n scegliere 2 è
n (n - 1)/2
Questo è
n /2 + n/2
Possiamo vedere che n (n-1)/2 = Θ (n) prendendo il limite delle loro come rapporti n tende all'infinito:
lim n → ∞ (n /2 + n/2)/n = 1/2
da questa esce ad un insieme finito, quantità diversa da zero, abbiamo n (n-1)/2 = Θ (n).
Più in generale: n scegliere k per qualsiasi costante k fisso è Θ (n k), perché è uguale a
n!/(k! (n - k)!) = n (n-1) (n-2) ... (n-k + 1)/k!
Che è un polinomiale di grado k in n con un coefficiente principale diverso da zero.
Spero che questo aiuti!
Naturalmente ! Per qualche ragione pensavo che n fosse k era (n!)/(K!). –
@ JennyShoars- Sarebbe sicuramente confuso. Spero che questo abbia chiarito le cose! – templatetypedef
n scegliere 2 = n (n + 1)/2 = (n^2 + n)/2 ... –
Cormen ha ragione. – 0x90
@ DennisMeng- È n (n-1)/2 piuttosto che n (n + 1)/2. – templatetypedef