알고리즘 복잡도 계산이 필요한 이우
하나의 문제를 푸는 알고리즘은 다양할 수 있음
- 정수의 절댓값 구하기
- 1, -1 --> 1
- 방법 1: 정수 값을 제곱한 값에 다시 루트를 씌우기
- 방법 2: 정수가 음수인지 확인해서, 음수일 때만, -1을 곱하기
다양한 알고리즘 중 어느 알고리즘이 더 좋은지 분석하기 위해, 복잡도를 정의하고 계산한다.
복잡도(Complexity)
- 시간 복잡도(Time Complexity): 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸렸는지를 의미 (알고리즘을 위해 필요한 연산의 횟수)
- 공간 복잡도(Space Complexity): 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미 (알고리즘을 위해 필요한 메모리의 양)
가장 중요한 시간 복잡도를 꼭 이해하고 계산할 수 있어야 한다.
효율적인 알고리즘을 사용한다고 했을 때, 보통 시간 복잡도와 공간 복잡도는 일종의 Trade off 관계가 성립한다. 메모리를 조금 더 많이 사용하는 대신에 반복되는 연산을 생략하거나 더 많은 정보를 관리하면서 계산의 복잡도를 줄일 수 있다.
시간 복잡도(Time Complexity)
알고리즘의 시간 복잡도는 연산의 횟수를 세고 처리해야 할 데이터의 수 n에 대한 연산 횟수의 함수 T(n)을 만들어서 계산한다.
연산 횟수의 카운팅에는 3가지 경우가 있다.
- 최선의 경우(Best Case)
- 최악의 경우(Worst Case)
- 평균적인 겨웅(Average Case)
알고리즘이 복잡해질수록 평균적 경우는 구하기 어려워진다. 따라서 보통 알고리즘의 성능은 최악의 경우로 파악한다.
시간 복잡도를 표현할 때는 빅오(Big-O) 표기법을 사용한다. 빅오 표기법이란 간단히 말해, 가장 빠르게 증가하는 항만을 고려하는 표기법이다. 예를 들어, 아래와 같은 코드가 있다고 가정해보자.
array = [1,2,3,4,5] # 5개의 데이터 (N = 5)
sum = 0 # 합계를 저장하는 변수
# 모든 데이터를 하나씩 확인하며 합계를 계산
for i in array :
sum += i
# 결과를 출력
print(sum) # 15가 출력된다
N개의 데이터가 있을 때, 위 코드는 현재 5개의 데이터가 있기 때문에, 연산 횟수는 5이다. 물론 sum이라는 변수에 ()을 할당하는 연산도 있고, print(sum)처럼 sum을 출력하는 부분도 있지만, 이런 연산 횟수가 N에 비례하기에 N이 커짐에 따라 이러한 부분은 무시할 정도록 작아진다.
따라서, 본 소스코드에서 가장 영향력이 큰 부분은 N에 비례하는 연산을 수행하는 반복문 부분이므로, 시간 복잡도를 O(N)이라고 표기할 수 있다.
빅-오 표기법에서는 O(2N)이나 O(3N) 등으로 표기하지 않고 다 O(N)으로 표기한다. 즉, N에 따라 비례하므로, 따로 그 앞의 상수는 무시한다.
다음과 같은 코드는 어떨까?
array = [1,2,3,4,5] # 5개의 데이터( N = 5)
for i in array :
for j in array :
temp = i * j
print(temp)
본 소스코드는 O(n²) 의 시간 복잡도를 가진다. 2중 for문을 가지기 때문에 쉽게 N * N 만큼의 연산이 필요하다는 것을 유추할 수 있지만, 실제로 모든 2중 반복문의 복잡도가 O(n²)를 가지는 것은 아니다. 소스코드가 내부적으로 다른 함수를 호출한다면, 내부 함수의 시간 복잡도까지 고려해야 한다. 따라서 소스코드를 정확히 분석한 뒤에, 시간 복잡도를 계산해야 하는 점을 기억하자.
자주 등장하는 시간 복잡도 표
O( 1) < O( log n) < O( n) < O( n* log n ) < O( n²) < O( n³) < O( 2n ) < O( n! )
순으로 표현되며, O 내부에 있는 n 계산이 작을 수록 성능은 더 좋은 것이다.
공간 복잡도(Space Complexity)
공간 복잡도 계산은 간단하다. 메모리를 얼마나 사용했는지 계산하면 된다. 공간 복잡도 역시 시간 복잡도처럼 보통 최악의 경우(Worst Case)를 따져 빅오 노테이션으로 그 복잡도를 판단하게 된다.
가령 크기가 n인 배열을 입력했는데, 알고리즘이 내부에서 n * n 의 이차원 배열을 생성한다면 이 알고리즘의 공간 복잡도는 n^2 가 된다.
공간 복잡도는 보통 시간 복잡도보다 중요하게 생각되지 않는 경우가 많다. 그러나 빅데이터 처리를 하는 경우, 공간 복잡도가 위와 같이 커지게 된다면, 메모리에 한 번에 올라가지 않아 프로그램을 실행할 수 없는 문제가 발생할 수 있다. 이 경우, 데이터를 나눠서 처리하고 다시 합치는 방법을 사용하게 된다.
int a[1000] // 4KB
int a[1000000] // 4MB
int a[2000][2000] // 16MB
'Algorithm' 카테고리의 다른 글
| [알고리즘] 자료구조: 트리(Tree) (0) | 2023.01.08 |
|---|---|
| [알고리즘] 자료구조: 해쉬 (0) | 2022.12.07 |
| [알고리즘] 자료구조: 링크드 리스트(Linked List) (1) | 2022.12.05 |
| [알고리즘] 자료구조 스택(Stack) (0) | 2022.12.04 |
| [알고리즘] 자료구조 : 큐 (Queue) (0) | 2022.12.04 |