[MIT] 파이썬을 이용한 알고리즘의 이해 - 선형 시간 정렬(정수 정렬)

 

 

BoostCourse의 "[MIT]파이썬을 이용한 알고리즘의 이해" 강의 내용을 정리한 글입니다.

 

 

✔ 비교 모델

: 비교 모델의 아이디어는 비교를 할 때 어떤 연산을 사용할지 제한하는 것입니다. 

• 모든 입력 항목은 블랙박스입니다.(ADTs)
  → 블랙박스 : 정확히 무엇인지 모른다는 것을 의미
• 유일하게 가능한 연산은 비교입니다.(<, ≤, >, ≥, =)
• 시간 비용은 단순히 비교한 횟수로 정의합니다.

 

 

 

✔ 의사 결정 나무(Decision tree)

: 어떠한 비교 알고리즘에서도 비교할 수 있는 모든 경우의 수와 비교 결과 및 최종 결론으로 이루어진 트리로 표현할 수 있습니다. 특정한 값 n(문제의 크기)부터 시작하는 것입니다.

예시

의사 결정 나무	알고리즘
내부 노드	이진 결정(비교 모델만 다룸)
단말 노드	찾는 답에 해당
루트-단말 경로	알고리즘의 단일 실행
경로의 길이	실행 시간
트리의 높이(루트의 높이)	최악의 경우에서의 실행 시간

 

 

 

✔ 검색 하한

: n개의 전처리 항목들이 존재하고 그중에 특정 항목을 비교 모델에서 찾는 것(비교만 할 때)은 최악의 경우에는 Ω(lg n)만큼 시간이 걸립니다.

⁉️ 증명

: 의사 결정 나무는 이진입니다. 그리고 최소 n개의 단말 노드를 가집니다. 답 하나당 단말 노드 한 개가 됩니다.

→ 높이(최악의 실행 시간) ≥ lg n

 

 

 

✔ 정렬 하한

: 결정 트리가 이진이고 단말 노드는 최소한 답의 개수만큼 있어야 하기 때문입니다. 같은 답이 여러 단말에 나오면 단말의 개수가 더 늘어납니다. 가능한 답은 n!의 수를 가집니다. 최악의 경우에는  Ω(n lg n)만큼 시간이 걸립니다.

→ 높이 ≥ [lg(n!) = n lg(n)]

 

 

 

✔ 선형 시간 정렬(정수 정렬)

: 정렬하려는 n개의 키가 정수입니다. 각각의 정수는 워드(상수 시간 안에 다룰 수 있는 것)에 대응됩니다. 즉 비교 외에도 다른 것을 더 할 수 있습니다.

 

⁉️ 계수 정렬

: 작은 양의 정수들인 키에 따라 객체를 수집하는 알고리즘입니다. 

L = array of k empty lists
for j in range(n):
    L[key(A[j])].append(A[j])
    
output = []
for i in range(k):
    output.extend(L[i])

⏱️시간 복잡도 : O(n+k)

⭐ k : 음수가 아닌 키 값 범위

 

⁉️ 기수 정렬

: 기수 별로 비교 없이 수행하는 정렬 알고리즘입니다. 가장 낮은 자리 숫자 순서로 정수를 정렬합니다. 그 다음 낮은 자리 숫자 순으로 정렬합니다. 이렇게 해서 가장 높은 자리 숫자까지 정렬합니다.

⏱️시간 복잡도 : O(w(k+n))

⭐ w : 기수의 크기

      k : 기수의 도메인 크기