퀵 정렬
321
작성한 질문수 5
퀵정렬 시간복잡도가 최악이 O(nlogn), 베스트가 O(n^2)라고 표기되어 있는데 이게 맞나요?
답변 1
0
안녕하세요, 인프런 AI 인턴이에요.
퀵 정렬의 시간 복잡도는 분할된 부분 리스트들의 크기에 따라 결정됩니다. 최악의 경우인 경우는 분할된 부분 리스트들의 크기가 매번 1이고, 이때의 시간 복잡도는 O(n^2)입니다. 이는 피벗(pivot)이 항상 최대값이나 최소값으로 선택되는 경우입니다.
반면, 피벗이 항상 중간값으로 선택되는 최선의 경우에는 분할된 부분 리스트들의 크기가 모두 균등하게 나누어지게 되며, 이때의 시간 복잡도는 O(nlogn)입니다.
따라서, 퀵 정렬의 시간 복잡도는 분할된 부분 리스트의 크기와 피벗의 선택에 따라 다양하게 변할 수 있다는 것을 알 수 있습니다.
다른 질문이 있으시면 언제든지 물어보세요. 좋은 하루 되세요!
채점 프로그램 미작동
0
8
2
삼성 코테 없어짐
0
15
1
링크드 리스트 중간 삽입삭제 시간복잡도 질문
0
10
1
재귀함수 종료조건
0
12
1
백준 서비스 종료로 인한 강의 자료 업데이트 요청드립니다.
0
28
1
백준 사이트 준비중이라 문제를 볼 수 가 없어요
0
32
1
코딩살구클럽 가입부탁드립니다
0
30
2
코딩살구클럽 가입 요청 확인부탁드립니다
0
31
2
해당 차수 영상이 짤려 나갑니다
0
46
1
채점기능
1
39
2
5-S 테스트 케이스 질문
0
36
2
주사위 게임
0
32
1
체점기
0
43
3
코살 문제풀이 환경
0
49
2
2 - T 오큰수 문제가 있는 것 같습니다.
0
43
1
추천 추가문제들
0
43
2
프로그래머스 코테 환경 관련해서 질문드립니다.
0
48
2
해당 문제에 대한 채점이 코딩살구클럽에서 올바르게 처리되지 않습니다.
0
44
2
균형 이진 트리 설명 시 높이 숫자
0
32
2
4-H 질문드립니다.
0
36
2
parseInt() vs Number()
0
61
0
문제 3 - 섬으로 건너가라.js
0
239
1
코딩 처음인데 환경 세팅을 어떻게하는지 모르겠어요
0
321
1
노션 링크가 안뜨는데 확인해주세요ㅠ!
0
408
1