퀵 정렬
334
작성한 질문수 5
퀵정렬 시간복잡도가 최악이 O(nlogn), 베스트가 O(n^2)라고 표기되어 있는데 이게 맞나요?
답변 1
0
안녕하세요, 인프런 AI 인턴이에요.
퀵 정렬의 시간 복잡도는 분할된 부분 리스트들의 크기에 따라 결정됩니다. 최악의 경우인 경우는 분할된 부분 리스트들의 크기가 매번 1이고, 이때의 시간 복잡도는 O(n^2)입니다. 이는 피벗(pivot)이 항상 최대값이나 최소값으로 선택되는 경우입니다.
반면, 피벗이 항상 중간값으로 선택되는 최선의 경우에는 분할된 부분 리스트들의 크기가 모두 균등하게 나누어지게 되며, 이때의 시간 복잡도는 O(nlogn)입니다.
따라서, 퀵 정렬의 시간 복잡도는 분할된 부분 리스트의 크기와 피벗의 선택에 따라 다양하게 변할 수 있다는 것을 알 수 있습니다.
다른 질문이 있으시면 언제든지 물어보세요. 좋은 하루 되세요!
코딩 살구클럽 가입 문의
0
12
1
Queue
0
43
1
코딩살구클럽 가입문의
0
55
2
3-K private case 질문
0
55
2
안녕하세요. 코딩살구클럽 문의드립니다!
0
70
2
7:41 듣다가 질문합니다
0
63
2
코드 리뷰 요청드립니다!
0
63
2
코테의 바이블 수강생 코테올인원 JAVA 쿠폰
0
42
1
코딩살구클럽 계정 문의
0
65
2
SK하이닉스 대비 강의수강
0
194
3
코딩살구클럽 등록부탁드립니다.
0
66
2
응시권 신청했는데 아직 안들어오고있습니다.
0
59
1
7-F 재귀로 풀시 런타임애러
0
63
1
1-N 문제 질문입니다. (+ 채점오류)
0
71
2
코딩살구클럽 가입 확인 부탁드립니다.
0
81
2
presentation error
0
67
1
직장인 코테 합격 공부방법 문의
0
107
2
코딩살구클럽 가입 방법
0
89
2
6-H 체점 관련 질문
0
70
1
선택정렬 이해하기 & 구현하기
0
59
1
parseInt() vs Number()
0
77
0
문제 3 - 섬으로 건너가라.js
0
248
1
코딩 처음인데 환경 세팅을 어떻게하는지 모르겠어요
0
339
1
노션 링크가 안뜨는데 확인해주세요ㅠ!
0
416
1