[IT 개념 정리] 시간/공간 복잡도 & 정렬 알고리즘

정렬 알고리즘에 대해서 정리 하기전 자료구조에 이어 알고리즘을 하게 되면 가장 많이 사용하는 개념인

'시간복잡도 / 공간복잡도'에 대해서 먼저 정리를 해보려고 한다.

 

1. 시간 복잡도 / 공간 복잡도

• 시간 / 공간 복잡도는 왜 구하는 것인가?
   알고리즘의 성능을 분석하기 위해서 사용하는 개념이다. 데이터 양이 많아지고 처리해야하는 방식의 변화에 따라 많은 시간과 공간이 쓰이게 되면서 해당 데이터 처리에 최적의 알고리즘을 사용하기 위해 사용 된다.
   기본적으로 동일한 하드웨어에서 사용 된다는 가정하에 시간 / 공간 복잡도를 계산 한다.
• 시간 복잡도(Time Complexity) $T(n)$ : 알고리즘을 수행하는데 연산(산술, 대입, 비교, 이동)이 몇번 이뤄지는가?
  
  • 빅오 표기법 : 시간 복잡도를 계산할때 상대적으로 불필요한 연산은 제거하여 알고리즘을 분석하여 좀더 간편하게 시간 복잡도를 표기하는 방법
    ex) 양의 정수 $n$을 $n$번 곱하는 경우를 $n*n$, $n$을 $n$번 더한것, $n*n$번 1을 더한것으로 나눠 보았을때 시간 복잡도로 각각 $2t$, $(2n+1)t$, $(2n^2+1)t$로 볼 수 있지만 빅도 표기법으로 표시한다면 $O(n)$, $O(n)$, $O(n^2)$로 볼 수 있다.
  • 빅오표기법

    	1	4	8	32
    $O(1)$	1	1	1	1
    $O(logn)$	0	2	3	5
    $O(n)$	1	4	8	32
    $O(nlogn)$	2	8	24	160
    $O(n^2)$	1	16	64	1,024
    $O(n^3)$	1	64	512	32,768
    $O(2^n)$	2	16	256	4,294, 967,296
    $O(n!)$	1	24	40,326	26,313×10^33

  • 최선, 최악, 평균 : 동일 알고리즘이어도 자료의 시작 형태에 따라 다른 실행 시간을 가진다.
    ex) 정렬 알고리즘의 경우 시작부터 정렬된 자료인경우, 정반대 형태의 정렬인 경우에 따라 실행 시간이 다르다
• 공간 복잡도(Space Complexity) : 프로그램을 실행시킨 후 완료까지의 필요한 자원 공간의 양
  • 총 공간 = 고정 공간 + 가변 공간 = $S(P) = c + Sp(n)$
    고정 공간 : 코드 저장 공간, 단순 변수, 상수 등
    가변공간 : 특정 인스턴스에 의존하는 크기를 가진 구조화 변수, 함수 호출시 추가공간 등 동적 공간
    ex) 1~n까지의 합을 더할때 함수의 재귀적 호출을 통한 방법 vs 변수할당을 통한 루프
         재귀 함수 호출 : n번의 함수 호출로 공간 복잡도: $O(n)$
         변수 할당을 통한 루프 : 루프에 필요한 변수만 저장하므로 공간 복잡도 $O(1)$
• 시간복잡도와 공간 복잡도를 이용해 최적의 알고리즘(작은 시간/공간 복잡도를 가진)을 찾아야 한다.
  시간 / 공간 복잡도는 반비례적인 경향이 있으므로 사용하는 환경에 따라 둘중 우선순위를 두어 판단하면 된다.

2. 정렬 알고리즘

 정렬 알고리즘은 정렬 하는 방식에 따라 정말 많은 종류가 있다. 그 중 대표적인 몇가지 알고리즘에 대해서 정리 해보려고 한다.

 정렬 알고리즘은 크게 실행방법에 따라 비교정렬과 분산정렬로 나눌수 있다. 

 - 비교 정렬 : 삽입 정렬(Insertion Sort), 선택 정렬(Selection Sort), 합병 정렬(Merge Sort), 퀵 정렬(Quick Sort),
                  힙 정렬(Heap Sort), 거품정렬(Bubble Sort), 쉘 정렬(Shell Sort) 등

 - 분산 정렬 : 기수 정렬(Radix Sort) 등

 대부분 우리가 들어본 정렬은 비교 정렬이다.

 

정렬 알고리즘 위키피디아

정렬 알고리즘 - 위키백과, 우리 모두의 백과사전

---

 

• 삽입 정렬(Insertion Sort)
  - 정렬된 집합에 새로운 원소의 적절한 위치를 찾아 삽입하는 정렬 방식
  - 공간복잡도는 $O(n)$이고 평균 시간복잡도는 $O(n^2)$이다. 
  - 배열이 작을 경우 효율적이다.

 

• 선택 정렬(Selection Sort)
  - 전체 원소들 중에 정렬 위치에 맞는 것을 선택해 해당 위치로 이동시키는 정렬 방식
  - 공간복잡도는 $O(n)$이고 평균 시간복잡도는 $O(n^2)$이다
  
  

• 합병 정렬(Merge Sort)
  - 분할정복(Divide and Conquer) 방식으로 설계된 정렬 방식
  - 분할정복 방식에 의해 큰 배열을 크기가 1이 될떄까지 반으로 자른 후 잘린 배열을 정렬하며 합친다.
  - 공간 복잡도는 $O(n)$이고 평균 시간 복잡도는 $O(nlogn)$이다

 

• 퀵 정렬(Quick Sort)
  - 합병 정렬과 마찬가지로 분할정복 방식을 이용한 정렬 방식이다.
  - 공간 복잡도는 $O(n)$이고 평균 시간 복잡도는 $O(nlogn)$이며 최악의 시간 복잡도는 $O(n^2)$이다.
  - 비교 방법
  1. 기준이 되는 pivot point를 잡은 후 양 쪽 끝 인덱스(Left, Right)와 피벗 값의 비교를 진행한다.
  2. Right 비교 진행을 우선으로 Right < Left 일 경우에만 반복되고 Right 값과 pivot값을 비교
      (pivot<Right : Right를 좌측으로 이동, pivot > Right : 반복 중지)한다.
  3. Left 비교는 Left < Right일 경우에만 반복되고 Left 값과 pivot값을 비교
      (pivot < Left : 반복 중지, pivot > Left : Left를 우측으로 이동)
  4. Left와 Right를 바꿔준다.
  5. 2~4과정을 Left < Right 가 될떄까지 반복하고 반복 종료 후 Left와 pivot값을 바꾼다.
  6. Left를 기준으로 좌 우로 1~5를 반복한다. 

• 버블 정렬(Bubble Sort)
  - 연속된 2개의 인덱스를 비교하여 비교 방식(오름차순, 내림차순)에 따라 정렬하는 정렬 방식이다.
  - 대부분의 상황에서 최악의 시간복잡도를 보이지만 이미 정렬된 경우에는 1번만 비교하면 된다.
  - 공간 복잡도는 $O(n)$이고 평균 시간 복잡도는 $O(n^2)$이다.

• 힙 정렬(Heap Sort)
  - 완전 이진트리중 하나인 heap을 사용한 정렬 방식이다.
  - 평균 시간 복잡도는 $O(nlogn)$이며 최악의 경우도 동일하다. 또한 추가적인 배열을 사용하지 않아 공간 효율도 좋다. (퀵 정렬과 비교했을때 평균적으로 퀵정렬이 빠르나 최악의 경우 힙 정렬이 더 빠르다)
  - 비교방법
  
  1. 배열의 모든 원소를 힙에 넣는다.
  2. 힙의 루트 원소의 값을 빼며 마지막 자식을 루트로 옮긴다.
  3. 2를 반복하여 빠진 원소를 차례로 정렬한다.

• 쉘 정렬(Shell Sort)
  - 삽입 정렬이 이미 정렬된 배열에서 최적의 성을 내는 것을 활용한 정렬 방법이다.
  - 삽입 정렬을 일정 간격으로 수행하고 최종적으로 전체를 삽입 정렬로 마무리한다.
  - 간격에 따라 수행 시간이 다르다.

• 기수 정렬(Radix Sort)
  - 데이터의 비교를 통한 정렬이 아닌 분산 정렬을 이용한 정렬 방법이다.
  - 시간 복잡도는 $O(kn)$이 나오며 자릿수가 있는 데이터(정수, 문자열 등)에만 사용 가능하다.
  - 데이터를 비교하는 정렬은 $O(nlogn)$의 최적의 시간복잡도가 나오지만 k가 상수일경우 기수 정렬은 $O(n)$의 시간 복잡도로 더욱 빠른 정렬이 되는 경우도 있다.
  - 각 자리수를 기준으로 점차 정렬을 진행한다.

 

 

정렬 알고리즘 비교

 

※ 각 이미지는 구글을 통해 검색 하였으며 이미지를 클릭하면 원본을 확인 할 수 있습니다.