각 정렬 알고리즘에 대한 사례별 시간 복잡도가 옳게 짝지어진 것은?최선… | [7급 국가직 알고리즘] 23년 1회차 기출문제 상세 페이지

삽입 정렬은 최선 $\Omega(n)$, 최악 $O(n^2)$로 옳게 짝지어져 있다.
이미 정렬된 입력이면 원소마다 한 번만 비교해 선형 시간에 끝나고, 역순 입력이면 매번 앞 원소를 모두 밀어야 해 이차 시간이 된다.
선택 정렬은 입력 상태와 관계없이 남은 구간 전체에서 최솟값을 찾으므로 최선도 $\Omega(n^2)$이다.
힙 정렬은 최악에도 $O(n\log_2(n))$을 보장하므로 최악 $O(n^2)$가 틀리다.
퀵 정렬은 피봇이 계속 한쪽 끝으로 치우치면 최악 $O(n^2)$가 되므로 최악 $O(n\log_2(n))$가 틀리다.