퀵 정렬
288
작성한 질문수 5
퀵정렬 시간복잡도가 최악이 O(nlogn), 베스트가 O(n^2)라고 표기되어 있는데 이게 맞나요?
답변 1
0
안녕하세요, 인프런 AI 인턴이에요.
퀵 정렬의 시간 복잡도는 분할된 부분 리스트들의 크기에 따라 결정됩니다. 최악의 경우인 경우는 분할된 부분 리스트들의 크기가 매번 1이고, 이때의 시간 복잡도는 O(n^2)입니다. 이는 피벗(pivot)이 항상 최대값이나 최소값으로 선택되는 경우입니다.
반면, 피벗이 항상 중간값으로 선택되는 최선의 경우에는 분할된 부분 리스트들의 크기가 모두 균등하게 나누어지게 되며, 이때의 시간 복잡도는 O(nlogn)입니다.
따라서, 퀵 정렬의 시간 복잡도는 분할된 부분 리스트의 크기와 피벗의 선택에 따라 다양하게 변할 수 있다는 것을 알 수 있습니다.
다른 질문이 있으시면 언제든지 물어보세요. 좋은 하루 되세요!
수강평 이벤트
0
15
2
진행 방법 질문드립니다!
0
26
2
안녕하세요. 바뀐 채점사이트 관련해서 문의드립니다.
0
19
1
갑자기 채점 사이트가 바뀌었어요
0
19
1
문제 리스트 페이지
0
22
1
part8 Notion 링크
0
22
1
채점 사이트 관련 질문드립니다
0
20
1
2-I) 왜 이 문제가 그래프이론 카테고리에 있는지 잘 모르겠습니다.
0
54
2
2주차 개념#12 트리 순회
0
25
2
백준 사이트 서비스 종료
0
111
3
잠겨버린 사물함 시간초과 관련 질문입니다.
0
25
1
백준 서비스 종료인데 도전 과제 프로그래머스 문제로 올려주실수 있으신가요
0
70
1
백준사이트가 종료된다고 합니다.
0
284
2
백준 서비스 종료
9
881
1
코딩테스트 처음인데 이런 공부방법이어도 괜찮을까요
0
57
2
Climbing Stairs 문제 basecase 생각하는 방법
0
31
1
itertools, sys같은 STL을 사용할 수 없는 경우 질문드립니다.(백준 11724)
1
32
1
DFS/BFS
1
37
2
3-3 정렬-2 선택정렬 로직
0
37
2
링크드 리스트 끝에서 k번째 값 출력하기
0
43
2
parseInt() vs Number()
0
42
0
문제 3 - 섬으로 건너가라.js
0
211
1
코딩 처음인데 환경 세팅을 어떻게하는지 모르겠어요
0
284
1
노션 링크가 안뜨는데 확인해주세요ㅠ!
0
370
1