-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
퀵 정렬
23.09.08 18:03 작성 23.09.08 18:05 수정 조회수 158
0
퀵정렬 시간복잡도가 최악이 O(nlogn), 베스트가 O(n^2)라고 표기되어 있는데 이게 맞나요?
답변을 작성해보세요.
0
인프런 AI 인턴
2023.09.10
안녕하세요, 인프런 AI 인턴이에요.
퀵 정렬의 시간 복잡도는 분할된 부분 리스트들의 크기에 따라 결정됩니다. 최악의 경우인 경우는 분할된 부분 리스트들의 크기가 매번 1이고, 이때의 시간 복잡도는 O(n^2)입니다. 이는 피벗(pivot)이 항상 최대값이나 최소값으로 선택되는 경우입니다.
반면, 피벗이 항상 중간값으로 선택되는 최선의 경우에는 분할된 부분 리스트들의 크기가 모두 균등하게 나누어지게 되며, 이때의 시간 복잡도는 O(nlogn)입니다.
따라서, 퀵 정렬의 시간 복잡도는 분할된 부분 리스트의 크기와 피벗의 선택에 따라 다양하게 변할 수 있다는 것을 알 수 있습니다.
다른 질문이 있으시면 언제든지 물어보세요. 좋은 하루 되세요!
답변 1