Sort 알고리즘의 시간복잡도
444
投稿した質問数 8
Part1 강의에서 연습문제로 구현했던 선택정렬(selection sort)의 시간복잡도는 무엇인가요? O의 n제곱이라고 생각하였는데 첫번째 for문에서는 n번을 순회하지만 내부의 두번째 for문에서는 n, n-1, n-2, ..., 2, 1 로 순회하는 횟수가 점점 줄어들어서 n제곱보다는 작은 시간복잡도를 가지는 것은 아닌가 해서요.
그리고 sort 알고리즘이 여러종류가 존재한다고 하셨었는데 그중 시간복잡도가 가장 작은 것을 사용하는 것이 최선의 선택인가요?
回答 2
2
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
172
2
글꼴 바꿔도 자간이 좁아 찌그러져보이시는 분들
0
88
1
NullReferenceException 예외) 같은 실수하시는분 계실까봐 남겨요
0
66
1
parent를 Pos타입으로 만든 이유
0
74
1
콘솔창에 격자가 안나옴 미로 생성 X
0
133
1
격자 생성 안됨 무한루프
0
114
1
BFS 질문
0
143
2
격자 무한 출력
0
167
2
A* 의 PriorityQueue 관련 질문입니다
0
155
2
vscode에서 원그리기
0
180
1
환결설정 강의 원 그리기
0
122
1
15-17분
0
87
1
3:16초에 근데 이렇게 해가지고 부분에 "{}"를 만들어서 자식 node들을 생성하던데 왜 중괄호로 감싸게 만드는 건가요?
0
141
2
동적 배열 관련 질문입니다!
0
209
1
Big-o 표기법에서 시간 복잡도
0
167
1
7:40에서 언급하신 색상이 날아가는 문제 이해를 못하겠습니다
0
151
1
트리구현연습 강의 질문있어요
0
143
1
창은 뜨는데 맵이 나타나지 않아요.
0
175
1
Ctrl F5 하면 나오는 창은 어디서 설정할까요??
0
271
1
void CalcPathFromParent(Pos[,] parent)에 대해서
0
202
2
NullReferenceException예외가 발생했을때 어떻게 해야하나요?
0
229
1
[해결] 환경설정 강의에서 원이 이상하게 그려지는 문제
3
311
2
오른손 법칙에서 플레이어 점이 안 움직입니다
0
245
2
맵 만들기 오류
0
179
1