N 가지 중 M개 뽑을 때 순서가 중요한 문제를 수식으로 나타내면 $nPr$ 입니다.
$nPr$ 은 순열이라고 합니다.
순열은 순서가 상관 있을 때 사용하죠. 즉, 순서가 중요합니다.
예를 들어, [1, 2] 와 [2, 1]은 다르다고 간주하죠.
시간복잡도는 상황에 따라 다르게 해석될 수 있습니다.
| 상황 | 시간복잡도 |
|---|---|
| r = n (모든 원소를 전부 순열 생성) | $O(N!)$ |
| r < n (일부만 뽑아 순열 생성) | $O(nPr)=O(n×(n−1)×⋯×(n−r+1))$ |
예를 들어서 n = 5, r = 5 라면 $nPr$ 은 120입니다. 시간복잡도는 $O(N!)$가 맞죠.
하지만 n = 5, r = 3 라면 $nPr$ 은 60입니다. 시간복잡도가 $O(N!)$는 아니죠. 정확하게는 $O(nPr)$입니다.
즉, 결론적으로 $nPr$의 시간복잡도는 일반적으로 $O(nPr)$ 입니다. 무조건 $O(N!)$은 아닙니다.
N과 M (1) 문제에서 시간복잡도는 뭘까요?
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 고르라고 했는데, 결국 N 가지 중 M개 뽑을 때 순서가 중요한 문제로 볼 수 있죠.