삽입정렬 시간복잡도 (1) 썸네일형 리스트형 삽입 정렬의 시간 복잡도 삽입 정렬이란? 삽입정렬은 화투나 포커 같은 카드게임과 비슷하다. 카드를 뽑을때 마다 알맞은 위치에 넣어 정렬된 상태를 유지하기 때문이다. 삽입 정렬의 시간 복잡도 최악의 케이스: 뽑은 숫자들이 정렬된 하위 배열 원소들보다 작은 경우 (역순으로 정렬된 상태) 매번 뽑은 숫자의 자리를 위해 하위 배열의 크기 k만큼 움직여야한다. 이 외의 잡다한 코드(크기 비교, swap)는 상수시간이 걸리기때문에 c로 취급한다. k=1 부터 시작하므로 ( 최초에 정렬된 하위배열 크기는 1) c*1 + c*2 + c*3 + ... +c*(n-1) = c * (n^2+(n-1)/2) = O(n^2) 최선의 케이스: 뽑은 숫자들이 정렬된 하위 배열 원소들보다 큰 경우 (바르게 정렬된 상태) 정렬된 하위 배열 원소들은 움직이지 .. 이전 1 다음
