퀵 정렬
311
投稿した質問数 5
퀵정렬 시간복잡도가 최악이 O(nlogn), 베스트가 O(n^2)라고 표기되어 있는데 이게 맞나요?
回答 1
0
안녕하세요, 인프런 AI 인턴이에요.
퀵 정렬의 시간 복잡도는 분할된 부분 리스트들의 크기에 따라 결정됩니다. 최악의 경우인 경우는 분할된 부분 리스트들의 크기가 매번 1이고, 이때의 시간 복잡도는 O(n^2)입니다. 이는 피벗(pivot)이 항상 최대값이나 최소값으로 선택되는 경우입니다.
반면, 피벗이 항상 중간값으로 선택되는 최선의 경우에는 분할된 부분 리스트들의 크기가 모두 균등하게 나누어지게 되며, 이때의 시간 복잡도는 O(nlogn)입니다.
따라서, 퀵 정렬의 시간 복잡도는 분할된 부분 리스트의 크기와 피벗의 선택에 따라 다양하게 변할 수 있다는 것을 알 수 있습니다.
다른 질문이 있으시면 언제든지 물어보세요. 좋은 하루 되세요!
코딩살구클럽 오류
0
7
1
코살클 [3-F 괄호 추가하기] 프라이빗 9번 제보
0
13
0
코딩살구클럽 테스트 케이스 오류 제보
0
18
2
삼성 코딩테스트
0
17
2
틀린 이유를 못찾겠습니다
0
13
1
시간은 이상 , 미만 질문 드립니다.
0
10
1
문제 풀이 공부 방법 질문 드립니다.
0
12
2
5주차 C번 문제 채점 서비스 관련 에러 문의
0
17
3
문제 푸는 법
0
21
2
코딩 살구 클럽 3-B 보물섬 프라이빗 케이스 질문
0
18
2
예전 로드맵과 현재 강의 순서
0
24
1
1-I 채점 관련 질문
0
47
2
코딩살구클럽 가입 요청
0
46
2
1-11 소수 나열하기 (에라토스테네스의 체)
0
44
1
코딩살구클럽
0
49
2
코딩살구클럽가입
0
37
2
코딩 살구 클럽 가입 요청드립니다!!
0
54
2
해당 문제의 private test case가 잘못 기입되어 있는 것 같습니다.
0
48
1
시간복잡도와 구현복잡도 관계
0
36
0
코딩 살구 클럽 가입 요청 드립니다.
0
54
2
parseInt() vs Number()
0
58
0
문제 3 - 섬으로 건너가라.js
0
232
1
코딩 처음인데 환경 세팅을 어떻게하는지 모르겠어요
0
311
1
노션 링크가 안뜨는데 확인해주세요ㅠ!
0
398
1