다음 순열을 구하는덴 필요한 시간복잡도
- 포인트지점 을 찾는것 (즉, arr[point-1]>arr[point] 가 아닌 순간찾기) O(n)
- 포인트 지점 이후의 숫자들중 "arr[point-1]보다 크면서" "그중 가장 작은 숫자" 찾기,
arr[n-1]부터 앞으로 가면서 가장 먼저 나오는 숫자이다. O(n)
- 포인트지점과 방금찾은 수 swap O(1)
- 포인트지점 이후의 숫자들 꺼꾸로 해주기 맨앞맨뒤 바꿔가면된다. O(n)
각각의 O(n)들은 독립적이므로 O(3n+1) = O(n)이다.
============================================
모든 순열을 찾는 방식
길이가 n인 수열의 갯수는 n!개이다.
갯수 n!개에 대한 각각 다음 순열을 찾는데 걸리는 시간은 O(n)이다.
즉, 시간복잡도는 n! * O(n) 즉 n*n!
tip ) 모든 순열을 찾는데 걸리는시간이 크므로 수열의 길이 10이하일떄에는 모든 순열을 찾는 방법을 이용한다.
do{
하고싶은계산
}while( arr.start(), arr.end() ) );==============================================