인프런 커뮤니티 질문&답변
작성한 질문수
Sort 알고리즘의 시간복잡도
작성
·
351
0
Part1 강의에서 연습문제로 구현했던 선택정렬(selection sort)의 시간복잡도는 무엇인가요? O의 n제곱이라고 생각하였는데 첫번째 for문에서는 n번을 순회하지만 내부의 두번째 for문에서는 n, n-1, n-2, ..., 2, 1 로 순회하는 횟수가 점점 줄어들어서 n제곱보다는 작은 시간복잡도를 가지는 것은 아닌가 해서요.
그리고 sort 알고리즘이 여러종류가 존재한다고 하셨었는데 그중 시간복잡도가 가장 작은 것을 사용하는 것이 최선의 선택인가요?
답변 2
2
Rookiss
지식공유자
O의 n제곱이라고 생각하였는데 첫번째 for문에서는 n번을 순회하지만 내부의 두번째 for문에서는 n, n-1, n-2, ..., 2, 1 로 순회하는 횟수가 점점 줄어들어서 n제곱보다는 작은 시간복잡도를 가지는 것은 아닌가 해서요.
-> n^2이 맞습니다. 물론 n, n-1, n-2 .. 이렇게 1씩 줄어들진 하지만
시간복잡도 계산할 때는 n이 무한대라고 생각하고
가장 많은 영향을 주는 부분에 집중하면 됩니다.
sort를 할 때 우리가 직접 구현할 일은 없고
보통 라이브러리에서 제공하는걸 사용하게 되는데
대부분 QuickSort로 되어 있고 평균적으로 nlogn 시간에 정렬을 해줍니다.
0
