[Algorithm] 시간 복잡도와 공간 복잡도 / 코딩 테스트 계산 방법

---

복잡도는 알고리즘의 성능을 나타내는 지표로 시간 복잡도와 공간 복잡도로 나눌 수 있습니다.

즉, 시간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미하고, 공간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미합니다. 동일한 기능을 수행하는 알고리즘이 있다면 일반적으로 복잡도가 낮을수록 좋은 알고리즘입니다.

 

복잡도를 측정함으로써 다음의 2가지를 계산할 수 있습니다.

• 시간 복잡도 : 알고리즘을 위해 필요한 연산의 횟수
• 공간 복잡도 : 알고리즘을 위해 필요한 메모리의 양

알고리즘이란, 어떤 목적을 해결하기 위한 일련의 과정을 의미합니다. 문제를 해결하는 알고리즘은 다양하며 여러 가지 상황에 따라 시간 복잡도가 가장 낮은 알고리즘을 선택해서 사용하면 됩니다. 

시간 복잡도는 알고리즘의 시간적 효율성, 공간 복잡도는 알고리즘의 메모리 효율성을 의미합니다.

알고리즘의 실행 시간

• 입력 값의 크기에 따라 알고리즘의 실행시간을 검증해 볼 수 있습니다.
• 중요하지 않은 상수와 계수들을 제거하면 알고리즘의 실행시간에서 중요한 성장률에 집중할 수 있는데, 이를 점근적 표기법이라고 합니다. 여기서, 점근적이라는 의미는 가장 큰 영향을 주는 항만 계산한다는 의미입니다.

효율적인 알고리즘을 사용한다고 했을 때 보통 시간 복잡도와 공간 복잡도는 일종의 거래 관계가 성립합니다. 메모리를 조금 더 많이 사용하는 대신에 반복되는 연산을 생략하거나 더 많은 정보를 관리하면서 계산의 복잡도를 줄일 수 있습니다. 이때 메모리를 더 소모하는 대신에 얻을 수 있는 시간적 이점이 매우 큰 경우가 종종 있습니다. 실제로 메모리를 더 많이 사용해서 시간을 비약적으로 줄이는 방법으로 메모이제이션(memoization) 기법이 있습니다.

시간 복잡도(Time Complexity)

알고리즘 문제를 풀 때 단순히 복잡도라고 하면 보통은 시간 복잡도를 의미합니다. 코딩 테스트를 처음 접하는 사람이 가장 어렵다고 느끼는 부분이 시간제한입니다. 여기서 시간제한이라고 한다면 문제를 푸는 시간을 정한 것처럼 보일 수 있지만, 코딩 테스트에서는 작성한 프로그램이 모든 입력을 받아 이를 처리하고 실행 결과를 출력하는 데까지 걸리는 시간을 의미합니다. 그래서 해당 시간 안에 동작하는 프로그램을 작성해야 하며, 비효율적으로 작성하여 시간제한을 넘기면 '시간 초과'라는 메시지와 함께 오답 처리됩니다.

 

시간 복잡도 분석은 문제 풀이의 핵심입니다. 알고리즘 문제 풀이에 능숙한 숙련자들은 문제를 해석하기 전에 조건을 먼저 보기도 합니다. 문제의 조건부터 확인하면 문제를 풀기 위해 얼마나 효율적인 알고리즘을 작성해야 하는지 눈치챌 수 있기 때문입니다. 그렇기 때문에 입력 값이 커지면 커질수록 증가하는 시간의 비율을 최소화한 알고리즘을 구성해야 합니다.

 

시간 복잡도를 표현할 때는 빅오(Big-O) 표기법을 사용합니다. 빅오 표기법을 간단하게 정의하자면 가장 빠르게 증가하는 항만을 고려하는 표기법입니다.  즉, 함수의 상한만을 나타냅니다. 시간 개념이 아니라 알고리즘이 실행될 때 동작하는 모든 연산의 횟수가 몇 번인지 세는 것입니다.

시간 복잡도를 줄이는 방법으로는 반복하는 연산 횟수를 줄이거나, 적절한 자료구조 및 알고리즘을 사용하면 됩니다.

빅오 표기법

빅오 표기법은 인자가 특정한 값이나 무한대로 향할 때 함수의 극한적인 동작을 설명하는 수학적인 표기법으로, 불필요한 연산을 제거하여 알고리즘 분석을 쉽게 할 목적으로 사용합니다.

시간 복잡도 표기법

1. Big-O(빅-오) → 상한 점근
2. Big-Ω(빅-오메가) → 하한 점근
3. Big- θ(빅-세타) → 평균

위 세 가지 표기법은 시간 복잡도를 각각 최악, 최선, 평균의 경우에 구분하여 나타내는 방법입니다.

알고리즘의 성능 평가 유형에서는 이 중 빅오 표기법의 최악의 경우를 고려하기 때문에 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있습니다. 어느 정도의 시간이 "걸린다." 보다는 "걸릴 수 있다"를 고려하게 된다면 그에 맞는 대응이 가능합니다.

 

알고리즘에서 영향력이 없는 계수와 낮은 차수의 항은 무시할 수 있습니다. 가장 차수가 제일 높은 항 이외에 나머지 항은 무시할 수 있습니다. 예를 들어, O(5N^2 + N) = O(N^2)가 됩니다.

그리고 Big-O 표기법에서 데이터의 입력값의 크기에 따라 영향을 받기 때문에 상수는 1로 통일시킵니다.

예를 들어, O(N + 2) = O(N)이 됩니다.

위 그래프를 보면 시간 복잡도에 상관되어 n(인풋)의 크기에 따라 얼마나 많은 시간이 걸리는지 예상할 수 있습니다.

빅오 표기법	표현
O(1)	상수
O(logN)	로그
O(N)	선형
O(NlogN)	로그 선형
O(N^2)	다항
O(2^N)	지수

왼쪽부터 오른쪽까지 점점 시간 복잡도가 길어지는 표기법입니다.

n이 작을 때는 알고리즘 간에 차이가 거의 없지만 값이 커질수록 복잡한 알고리즘은 수행 시간이 기하급수적으로 길어집니다.

시간 복잡도를 낮출 수 있다면 프로그램에 대한 성능 개선을 기대할 수 있습니다.

• O(1)
  • O(1)은 입력값이 증가하더라고 시간이 일정한 복잡도입니다.
  • 예) 배열 또는 리스트에서 특정 인덱스 탐색 등
• O(logN)
  • 입력값이 증가할 때마다 시간이 로그 스케일로 증가하는 로그 복잡도입니다.
  • 예) 이진 탐색 알고리즘 등
• O(N)
  • O(N)은 입력값이 증가하면 시간도 같은 비율로 증가하는 선형 복잡도입니다.
  • 예) 반복문, 선형 탐색 알고리즘 등
• O(NlogN)
  • 입력값이 증가할 때마다 시간이 로그 값에 비례하여 증가하는 로그 선형 복잡도입니다.
  • 예) 병합 정렬, 힙 정렬 알고리즘 등
• O(N^2)
  • 입력값이 증가하면 시간이 n의 제곱수의 비율로 증가하는 2차 복잡도입니다.
  • 예) 선택 정렬, 버블 정렬, 퀵 정렬 알고리즘 등
• O(2^N)
  • 입력값이 증가하면 시간이 기하급수적으로 증가하는 기하급수적 복잡도입니다.
  • 예) 부분집합

공간 복잡도

공간 복잡도를 표기할 때도 시간 복잡도를 표기했던 것처럼 빅오(Big-O) 표기법을 사용합니다.

즉, 공간 복잡도 또한 O(NlogN), O(N^2) 등으로 표기합니다. 다만, 앞서 시간 복잡도에서 절대적인 제한 시간이 있던 것처럼, 메모리 사용량에도 절대적인 제한이 있습니다. 일반적으로 메모리 사용량 기준은 MB단위로 제시되어 있습니다. 즉, 코딩 테스트 문제에서 보이는 '시간제한 1초, 메모리 제한 128MB'와 같은 문장은 시간 복잡도와 공간 복잡도를 함께 제한하기 위해 명시하는 것입니다.

코딩 테스트 문제는 대부분 다수의 데이터에 대한 효율적인 처리를 요구하기 때문에 리스트(배열)를 사용해서 풀어야 합니다. 코딩 테스트에서는 보통 메모리 사용량을 128 ~ 512MB 정도로 제한합니다. 다시 말해 일반적인 경우 데이터의 개수가 1,000만 단위가 넘어가지 않도록 알고리즘 설계를 해야 한다는 의미입니다. 

 

공간 복잡도는 소프트웨어가 메모리를 다루는 양이 얼마인지에 대한 지표입니다.

최근 컴퓨터의 성능 발전으로 예전에 비해서 중요도는 떨어졌지만, 빅데이터 분야에서는 여전히 중요한 지표로 사용됩니다.

 

공간 복잡도에서 알고리즘을 실행시키기 위해 필요한 공간은 두 가지로 나눌 수 있습니다.

1. 알고리즘과 무관[고정 공간] : 코드를 저장하는 공간, 알고리즘을 실행할 시스템이 필요로 하는 공간 등이 있습니다.
2. 알고리즘과 연관[가변 공간] : 문제 해결을 위해 알고리즘이 필요로 하는 공간, 변수를 저장하는 공간, 순환 스택 등이 있습니다.

코딩 테스트 대비 계산 방법

코딩 테스트 문제를 풀 때 가능한 연산의 횟수는 시간제한 초수 * 1억입니다. 즉, 알고리즘의 최악의 경우에서 계산한 가능 연산 횟수를 초과하지 않으면 됩니다. 그렇기 때문에, 문제에서 주어지는 최대 입력 데이터 수를 보고 대략 가능한 시간 복잡도를 파악하고 구상할 수 있습니다.

데이터 수	시간 복잡도	연산 횟수
10^8	n, logn	1억번의 연산
10^6	nlogn	1억번의 연산
10^4	n^2	1억번의 연산
500	n^3	1억번의 연산
20	n!, 2^n	1억번의 연산

 

자료구조 지표

자료구조	평균		최악
	탐색	추가	탐색	추가	삭제

알고리즘 지표

알고리즘	공간 복잡도	시간 복잡도
	최악	최선	평균	최악

 

*위 자료구조 및 알고리즘 표는 개인 공부 및 개발 블로그 작성 동기를 위해 포스트 작성할 때마다 추가하도록 하겠습니다 :)