퀵 정렬
298
投稿した質問数 5
퀵정렬 시간복잡도가 최악이 O(nlogn), 베스트가 O(n^2)라고 표기되어 있는데 이게 맞나요?
回答 1
0
안녕하세요, 인프런 AI 인턴이에요.
퀵 정렬의 시간 복잡도는 분할된 부분 리스트들의 크기에 따라 결정됩니다. 최악의 경우인 경우는 분할된 부분 리스트들의 크기가 매번 1이고, 이때의 시간 복잡도는 O(n^2)입니다. 이는 피벗(pivot)이 항상 최대값이나 최소값으로 선택되는 경우입니다.
반면, 피벗이 항상 중간값으로 선택되는 최선의 경우에는 분할된 부분 리스트들의 크기가 모두 균등하게 나누어지게 되며, 이때의 시간 복잡도는 O(nlogn)입니다.
따라서, 퀵 정렬의 시간 복잡도는 분할된 부분 리스트의 크기와 피벗의 선택에 따라 다양하게 변할 수 있다는 것을 알 수 있습니다.
다른 질문이 있으시면 언제든지 물어보세요. 좋은 하루 되세요!
3-D 관련 질문
0
19
2
코살구 회원가입 문의
0
24
2
강의노트 접속 불가
0
20
2
코살구 로그인 문제
0
49
2
3-A 문제 풀이 관련 질문
0
44
3
2-O 질문 있습니다
0
35
2
2-T 문제에 관한 질문
0
36
2
코딩 살구 클럽 접속 및 사용방법 문의
0
51
2
안녕하세요~. 현재 코살코딩클럽 사이트가 접속이 안됩니다~
0
63
2
코딩살구클럽 로그인문제
0
69
3
코딩 살구 클럽 로그인 문제
0
75
2
2-J 채점관련 질문
0
65
3
Part2 기출 문제 및 해설 자료 파일 없음 형태
0
52
2
코딩 살구 클럽 Python 지원 가능 여부
0
75
1
살구클럽 아이디 없음 문제
0
74
1
1-O 코딩살구클럽 채점관련 질문
0
57
2
히든 테스트 케이스가 사라졌습니다
0
55
1
38번 문제 보기 3,4번
1
45
3
14번 문제
1
45
2
채점서버 혹시 다른 언어 지원도 가능하게 해주실 수 있나요
1
73
2
parseInt() vs Number()
0
45
0
문제 3 - 섬으로 건너가라.js
0
217
1
코딩 처음인데 환경 세팅을 어떻게하는지 모르겠어요
0
291
1
노션 링크가 안뜨는데 확인해주세요ㅠ!
0
379
1