[자료구조/알고리즘] 알고리즘과 시간복잡도, 공간복잡도, 빅-오 표기법

> 방법(method)

어떤 목적을 달성하기 위해 해야 할 작업에 대해 명확하게 지시한 것

 

> 알고리즘(algorithm)

방법 중에서도 작업의 횟수가 유한한 것. 절차, 방법, 명령어들의 집합을 말하기도 하며, 일련의 순서를 포함한다. 주로 컴퓨터가 작업을 처리하는 방법을 말한다.

 

> 시간 복잡도(time complexity)

알고리즘이 문제를 해결하는데 걸리는 시간. 처리해야하는 연산의 수와 연관된다. n개의 데이터가 주어졌을 때, 해당 알고리즘이 수행되는데 필요한 연산의 수를 n에 관한 함수, T(n)으로 표현한다. 이때 연산의 수는 최선의 경우, 평균적인 경우, 최악의 경우로 나누어 생각할 수 있는데 보통은 최악의 경우를 기준으로 생각한다.

ex) 선택 정렬 알고리즘

1. 주어진 리스트 중에 최소값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

출처: 위키백과

해당 알고리즘의 경우 이중 for문으로 구성되어, T(n)=n^2 + n - 2 이다.

시간 복잡도를 살피는 이유는, 데이터 양이 증가함에 따라 연산량이 어떻게 증가하는지 파악하기 위함이다. 위의 예시에서는 데이터 양이 10배 늘어난다면, 걸리는 시간은 약 100배 늘어나게 된다. (T(10n)/T(n) = 약 100)

 

> 공간 복잡도(space complexity)

알고리즘이 문제를 해결하는데 필요한 공간, 메모리. 역시나 입력 데이터의 수(n)으로 함수화하여 표기하는 것이 일반적이다. 최근 RAM 등 메모리의 성능이 크게 향상되면서 상대적 중요성은 감소했다.

 

> 빅-오 표기법

점근 표기법 중 상한점근법, 즉 최악의 경우를 고려하는 표기법이다. 시간 복잡도와 공간 복잡도는 모두 데이터 크기(n)가 커지면 함께 커질 수 밖에 없는데, 이때 n의 값이 커질수록 dominant term 외의 나머지의 영향력은 줄어든다는 것을 고려해 dominant term으로 시간 복잡도를 간략하게 표현하는 것을 말한다. 상수항이나 상수 계수 등은 표현하지 않는다. (즉, O(n^2 + n -2) -> O(n^2), O(2n) -> O(n))

ex)

O(1): 데이터 개수에 무관하게 일정한 시간이 걸리는 경우

• 큐, 스택에 항목 추가하거나 빼기
• 배열에 인덱스로 항목에 접근하기
• 트리에서 인접 노드를 찾을 때

O(n): 데이터 개수에 비례한 시간이 걸리는 경우 (T(n)= 2n, T(n) = 5n - 3 등)

• 배열 탐색 (for 문)
• 선형 검색(Linear Search)
• 두 문자열 간의 비교
• 회문(Palindrome) 검사

O(logn): dominant term이 logarithm function인 경우

• 이진 검색(Binary search)

O(nlogn): O(n) * O(logn)의 형태

• 병합 정렬
• 힙 정렬

O(n^2): 데이터 개수 제곱에 비례한 시간이 걸리는 경우 (T(n)= 2n^2, T(n) = 5n^2 +n 등)

• 버블 정렬
• 삽입 정렬
• 선택 정렬

외에도 O(n^3), O(2^n), O(n!) 등의 복잡도를 가진 알고리즘들이 존재하는데, 대부분 지양해야한다. 외판원 순회 문제(Traveling Salesperson Problem)가 대표적인 NP-완전문제의 경우 O(n!)의 시간 복잡도가 불가피하다고 한다.

외판원 문제는 다음과 같이 설명할 수 있다. 어떤 외판원이 n개의 도시를 방문할 계획을 수립하고 있다고 가정하자. 각 도시는 다른 모든 도시와 도로로 연결되어 있다. 출장 비용을 최소로 줄이기 위하여 외판원이 거주하고 있는 도시에서 각 도시를 한 번씩만 방문하고 다시 출발한 도시로 돌아오는 가장 최소 비용의 일주여행 경로를 찾고자 한다.

 

이러한 경우는 발견법(heuristics method)을 통해 최적해가 아닌 충분히 좋은 해를 찾아내는 것을 목표로 하기도 한다.