[알고리즘] 복잡도와 정렬

1. 복잡도(Complexity)

복잡도는 알고리즘의 성능과 효율성을 나타내는 척도이다. 크게 시간 복잡도와 공간 복잡도로 나눌 수 있다.

수행시간에 해당하는 것이 시간 복잡도 이고, 메모리 사용량에 해당하는 것이 공간 복잡도이다.

시간 복잡도

컴퓨터 프로그램의 입력값과 연산 수행시간의 상관관계를 나타내는 척도이다.

• 최상의 경우: 오메가 표기법
• 평균의 경우: 세타 표기법
• 최악의 경우: 빅오 표기법

알고리즘의 효율을 따졌을때 가장 중요한 부분은 n이 커질때 이므로
이것을 잘 나타내는 것이 빅오 표기법(최악의 경우)이다.

 

공간 복잡도

공간 복잡도란 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석,
알고리즘을 실행하여 종료할 때 까지의 필요한 기억장치의 크기를 말한다.

 

예를 들어, 다음과 같은 코드의 공간 복잡도는

func sum(arr: [Int]) -> Int {
  var x: Int = 0
  for i in 0..<arr.count {
    x = x + arr[i]
  }
  return x
}

arr 배열의 크기가 커질수록 선형적으로 증가하기 때문에 공간 복잡도는 O(n)이라고 할 수 있다.

 

2. 정렬 알고리즘

삽입 정렬(Insertion Sort)

삽입 정렬은 2번째 부터 시작하여 그 앞의 자료들과 비교하여 삽입할 위치를 지정한 후

자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘이다.

최악의 경우를 계산해보면 아래와 같다.

 

선택 정렬(Selection Sort)

1~n번째까지 다 탐색해서 가장 작은 값을 찾아 맨앞으로 가져오고,

2 ~ n번째까지 또 탐색해서 가장 작은 값을 찾아 두번째 위치로 가져오는 것을 반복하는 정렬이다.

 

선택 정렬은 최상, 평균, 최악 모두 시간 복잡도가 일정하다.
따라서, 시간 복잡도를 계산해보면 아래와 같다.

 

버블 정렬(Bubble Sort)

서로 인접한 두 원소를 검사하여 정렬하는 알고리즘이다.

인접한 두개의 원소를 비교하여 크기가 순서대로 되어있지 않으면 서로 교환한다.

버블 정렬도 위 삽입정렬과 마찬가지로 시간 복잡도가 최상, 평균, 최악 모두 일정하다.

또한, 위에 식과 마찬가지로 시간 복잡도는 O(n^2)이다.

 

병합 정렬(Merge Sort)

하나의 리스트를 두 개의 균등한 크기로 분할하고 부분리스트를 정렬한 다음,

두 개의 정렬된 부분리스트를 합하여 전체가 정렬된 리스트가 되게하는 방법이다.

병합 정렬은 다음의 단계로 이루어진다.

• 분할: 2개의 배열로 분할
• 정복: 부분 배열을 정렬
• 결합: 정렬된 부분 배열들을 하나의 배열에 합병

(분할) 그림처럼 주어진 배열을 최대한 분할한다.

 

(정복&결합) 다 쪼개지면 부분 배열을 정렬하기 위해서 맨 앞요소끼리 빼서 비교하고 큰 배열에 넣어준다.

 

병합 정렬은 항상 일정한 시간 복잡도를 가진다.

각 정렬의 단계에서 n번의 탐색을하고 정렬을 하고 높이는 log n 이기 때문에 O(n x log n) 이다.

 

퀵 정렬(Quick Sort)

병합 정렬과 달리 퀵 정렬은 리스트를 비 균등하게 분할한다.

리스트 안에 한 요소를 선택한다.(이때, 이 요소를 Pivot이라 함)

이 Pivot을 기준으로 작은 요소들은 Pivot의 왼쪽으로 큰 요소들은 Pivot의 오른쪽으로 옮겨진다.

Pivot을 제외하고 왼쪽 리스트와 오른쪽 리스트를 정렬한다.

 

각 행의 비교연산은 n이고

퀵정렬은 병합 정렬과 다르게 리스트를 비 균등하게 분할 하기 때문에 Pivot을 잘못 선택하면(최악의 경우)

분할시에 높이가 n까지 커질 수 있어서 빅오는 O(n^2)라고 할 수 있다.

 

우리가 Pivot의 값을 중위값으로 모두 잘 골랐다면 나눌때마다 데이터의 개수가 반으로 줄게 되므로 log n의 시간이 소요되고,

평균적인 경우에는 병합 정렬과 마찬가지로 n x log n의 시간복잡도를 가진다.