[이것이 코딩테스트다] 시간복잡도와 공간복잡도

📚 복잡도 

복잡도는 알고리즘의 성능을 나타내는 척도이다.

시간복잡도 : 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래걸리는지를 의미 

공간복잡도 : 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미

복잡도를 측정함으로써 시간 복잡도에서는 알고리즘을 의해 필요한 연산의 횟수를, 공간 복잡도에서는 메모리의 양을 계산할 수 있다. 일반적으로 복잡도가 낮을수록 좋은 알고리즘이다.

 

---

⚡ 시간 복잡도

시간 복잡도를 표현할 때는 빅오Big-O 표기법을 사용한다.

 

빅오 표기법은 가장 빠르게 증가하는 항만을 고려하는 표기법이다. 다시 말해 함수의 상한만을 나타낸다.

 

[예제 1] 시간 복잡도 O(N)

5개의 데이터를 받아 차례로 5회 더해준다(N = 5). 이 때 연산횟수는 N에 비례하는 것을 알 수 있다. N에 비례하는 연산을 수행하는 반복문 부분이므로 시간 복잡도를 O(N)이라고 표기한다. 

array   = [3, 5, 1, 2, 4] # 5개의 데이터(N = 5)
summary = 0               # 합계를 저장할 변수


# 모든 데이터를 하나씩 확인하며 합계를 계산
for x in array:
    summary += x
    
# 결과 출력
print(summary)

 

[예제 2] 시간 복잡도 O(1)

a 와 b 변수에 값을 대입하고 출력 시 a+b 연산한 값을 출력한다. 이 소스코드의 연산 횟수는 1이다.

단순히 더하기 연산 한 번이 수행되기 때문이다. 이는 상수 연산이므로 시간 복잡도는 O(1) 이 된다.

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

 

[예제 3] 시간 복잡도 O(N²)

다음은 데이터의 개수가 N개 일 때, O(N²) 의 시간 복잡도를 가진다.

2중 반복문을 이용하여 각 원소에 대하여 다른 모든 원소에 대한 곱셉 결과를 매번 출력하고 있기 때문이다.  

array = [3, 5, 1, 2, 4]

for i in array:
    for j in array:
        temp = i * j
        print(temp)

하지만 모든 2중 반복문의 시간 복잡도가 O(N²) 은 아니다.

만약 소스코드가 내부적으로 다른 메서드를 호출한다면 내부 메서드의 시간 복잡도까지 고려해야 한다. 

따라서 소스코드를 정확히 분석한 뒤에 시간 복잡도를 계산해야 한다는 점을 기억하자.

 

일반적으로 코딩 테스트에서는 최악의 경우에 대한 연산 횟수가 가장 중요하다. 그러니 최악의 경우의 시간 복잡도를 우선적으로 고려해야 한다.

 

다음 <시간 복잡도 표>는 위쪽에 있을 수록 더 빠르다.

빅오 표기법	명칭	N이 1,000 일 때의 연산 횟수
O(1)	상수 시간	-
O(logN)	로그 시간	-
O(N)	선형 시간	1,000
O(NlogN)	로그 선형 시간	10,000
O(N²)	이차 시간	1,000,000
O(N³)	삼차 시간	1,000,000,000
O(2ⁿ)	지수 시간	-

 

시간 복잡도 분석은 문제 풀이의 핵심이다. 문제의 조건부터 확인하면 문제를 풀기 위해 얼마나 효율적인 알고리즘을 작성해야 하는지 파악 할 수 있다.

 

다음은 모두 시간제한이 1초인 문제에 대한 시간복잡도 설계 예시이다.

• N의 범위 500 인 경우 : O(N³) 알고리즘을 설계하면 문제를 풀 수 있다.
• N의 범위 2,000 인 경우 : O(N²) 알고리즘을 설계하면 문제를 풀 수 있다.
• N의 범위 100,000 인 경우 : O(NlogN) 알고리즘을 설계하면 문제를 풀 수 있다.
• N의 범위 10,000,000 인 경우 : O(N) 알고리즘을 설계하면 문제를 풀 수 있다.

 

 

 

 

 

---

⚡ 공간 복잡도

공간 복잡도를 표기할 때도 시간 복잡도를 표기했던 것처럼 빅오 표기법을 이용한다.

일반적으로 메모리 사용량 기준은 MB 단위로 제시된다. 

 

코딩 테스트 문제는 대부분 리스트(배열)를 사용해서 풀어야 한다. 대부분의 문제는 다수의 데이터에 대한 효율적인 처리를 요구하기 때문이다. 

 

정수형 자료형인 int를 기준으로 리스트 크기에 따른 메모리 사용량은 다음과 같다. 

• int a[1000] : 4KB
• int a[1000000] : 4KB
• int a[2000][2000] : 16MB

코딩 테스트에서는 보통 메모리 사용량을 128 ~ 512MB 정도로 제한한다.

 

---

⚡ 시간과 메모리 측정

파이썬에서는 프로그램 수행 시간과 메모리 사용량을 측정할 수 있다. 알고리즘의 효율성을 측정하는 가장 기본적인 방법이다. 특정한 프로그램의 수행 시간을 측정하는 소스코드 예시는 다음과 같다.

import time

start_time = time.time() # 측정 시작

# 프로그램 소스코드 시작
# ...
# 프로그램 소스코드 끝

end_time = time.time()   # 측정 종료
print("time: " , end_time - start_time) # 수행 시간 출력

---

🐾 정리

 '이것이 코딩테스트다' 책을 공부하면서 이전에 알고리즘 문제풀 때 염두해두지 못했던 부분들을 하나씩 배워나갈 수 있을 거란 생각이 든다.

 특히나 시간복잡도와 공간복잡도는 모든 알고리즘 조건에 포함되어 있는 내용인데도 불구하고, 복잡도를 생각하지 않고 풀었던 것 같다. 이번에 복잡도에 대해 공부한 만큼 시간복잡도가 낮은 효율적인 알고리즘을 작성할 수 있도록 노력해야겠다.

 

 

 

※ 해당 포스팅은「이것이 취업을 위한 코딩테스트다(나동빈 저)」책 내용을 바탕으로 작성하였습니다.