나는 Introduction to Algorithms 3rd Edition (Cormen and Rivest)을 읽으며 69 페이지의 "무차별 대처법"에서 n이 2 = Theta (n^2)를 선택한다고 명시하고 있습니다. 나는 그것이 Theta (n!)에있을 것이라고 생각할 것입니다. n이 2를 n 제곱에 단단히 묶는 이유는 무엇입니까? 감사!2를 선택하는 n의 복잡도는 Theta (n^2)에 있습니까?
N 2
n이 선택 (N - 1)/2
이것은
N 2/2+ N/2
우리는 n (n-1)/2 = Θ (N 2) N이 무한대로 그 비율 제한을 취하여 :
LIM N → ∞ (N 2/2 + N/2)/N 2 = 1/2
이 유한 한 0이 아닌 양으로 나오고 있기 때문에, 우리는 N이 (N-1)/2 = Θ (N 2).
더 일반적 : 그것은
N 동일 때문에 N 임의 정수 (k)에 고정시켜 K를 선택하면, Θ (N K)이다! (n-k)] = n (n-1) (n-2) ... (n-k + 1)/k!
n 번째 0 차 선도 계수가있는 n 차의 k 차 다항식입니다.
희망이 도움이됩니다.
물론 ! 나는 어떤 이유로 n이 k를 (n!)/(k!)라고 생각하고있었습니다. –
@ JennyShoars- 분명히 혼란스러워 할 것입니다. 희망이 물건을 취소! – templatetypedef
n 2 = n (n + 1)/2 = (n^2 + n)/2 ... –
을 선택하십시오. Cormen이 맞습니다. – 0x90
@ DennisMeng- n (n + 1)/2보다는 n (n-1)/2입니다. – templatetypedef