[이취코] 복잡도

복잡도

복잡도는 알고리즘의 성능을 나타내는 척도이며 두 가지로 분류할 수 있습니다.

• 시간복잡도

  • 특정한 크기의 이력에 대하여 알고리즘이 얼마나 오래 걸리는지 의미
  • 알고리즘을 위해 필요한 연산의 횟수

• 공간 복잡도

  • 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지 의미
  • 알고리즘을 위해 필요한 메모리의 양

시간 복잡도

코딩 테스트에서 시간 제한이란 작성한 프로그램이 모든 입력을 받아 이를 처리하고 실행결과를 출력하는 데까지 걸리는 시간을 의미합니다.

시간 복잡도를 표현할 때는 빅오(Big-O)표기법을 사용합니다. 이는 가장 빠르게 증가하는 항만을 고려하는 표기법 입니다. 즉, 함수의 상한만을 나타냅니다.

예제
5개의 데이터를 받아 이를 차례로 더해준다고 했을때, 연산 횟수는 N에 비례합니다.

array = [1, 2, 3, 4, 5]
sum = 0
for i in array:
    sum += i
print(sum)

소스코드에서 가장 영향력이 큰 것은 N에 비례하는 연산을 수행하는 것입니다. 주어진 숫자 N개를 연산하기 때문입니다. 그래서 시간 복잡도는 O(N)이 됩니다.

a = 15
b = 7
print(a+b)

위 소스코드의 시간 복잡도는 얼마일까요? 위에서는 대입 연산과 출력 연산을 제외하고 본다면 이 소스코드의 연산횟수는 더하기 연산 하나로 1입니다. 이 때 시간복잡도는 O(1) 입니다.

만약 이중 for문으로 5개의 숫자를 담은 리스트를 연산한다면 어떻게 될까요? NxN으로 보통은 O(N^2)지만 for문 안에서 다른 함수를 호출한다면 그 내부함수의 시간 복잡도 까지 고려해야 합니다. 그렇기 때문에 소스코드를 정확히 분석한 후에 시간복잡도를 계산해야 합니다.

일반적으로 연산 횟수가 가장 중요하지만 경우에 따라서 시간 복잡도를 먼저 계산해야하는 경우가 생깁니다.

빅오 표기법	명칭
O(1)	상수 시간
O(logN)	로그 시간
O(N)	선형 시간
O(NlogN)	로그 선형 시간
O(N^2)	이차 시간
O(N^3)	삼차 시간
O(2^n)	지수 시간

위의 표는 시간 복잡도 표입니다. 위쪽에 있을 수록 더 빠릅니다.

	N이 1,000일 때의 연산 횟수
O(N)	1,000
O(NlogN)	10,000
O(N^2)	1,000,000
O(N^3)	1,000,000,000

각기 다른 시간 복잡도의 연산 횟수가 N의 크기에 따라서 어떻게 분포되는 지 대략적인 연산 횟수를 비교한 표입니다.

시간 복잡도를 분석하면 문제를 풀기 전에 문제를 풀기 위해 얼마나 효율적인 알고리즘을 작성해야 하는지 파악이 가능합니다.

공간 복잡도

공간 복잡도를 표기할 때도 빅오 표기법을 이용합니다. 일반적으로 메모리 사용량 기준은 MB단위로 제시됩니다.