[이코테] 복잡도 Complexity

0. 복잡도

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

- 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)로 나뉨

- 시간 복잡도: 알고리즘이 얼마나 오래 걸리는지?

- 공간 복잡도: 알고리즘이 얼마나 많은 메모리를 차지하는지?

- 시간 복잡도와 공간 복잡도는 거래 관계가 성립: 메모리를 조금 더 많이 사용 -> 반복 연산 생략 or 더 많은 정보 관리

 

1. 시간 복잡도

빅오표기법 사용: 가장 빠르게 증가하는 항만을 고려하는 표기법

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

- 위쪽에 있을 수록 빠른 속도

- 일반적으로 O(N^3)가 넘어가면 문제 풀이에서 사용하기가 어려움

 

!! 시간 복잡도 분석은 문제 풀이의 핵심

 

시간 제한이 1초인 문제에 대해서

• N의 범위가 500인 경우: 시간 복잡도가 O(N^3)인 알고리즘 설계
• N의 범위가 2,000인 경우: 시간 복잡도가 O(N^2)인 알고리즘 설계
• N의 범위가 100,000인 경우: 시간 복잡도가 O(NlogN)인 알고리즘 설계
• N의 범위가 10,000,000인 경우: 시간 복잡도가 O(N)인 알고리즘 설계

 

2. 공간 복잡도

동일하게 빅오표기법 사용

코딩테스트에서는 보통 128 ~ 512MB로 제한 -> 데이터의 개수가 1,000만 단위가 넘어가지 않도록 알고리즘을 설계해야 함

 

3. 시간과 메모리 측정

실제 프로그램의 수행 시간을 측정하는 것은 알고리즘의 효율성을 측정하는 가장 기본적인 방법!

 

수행 시간 측정 소스코드

import time
start_time = time.time()

end_time = time.time()

print('time: ', end_time - start_time)

ex) 선택 정렬과 파이선의 기본 정렬 라이브러리의 속도를 비교할 때

from random import randint
import time

# 배열에 10,000개의 정수 삽입
array = []

for _ in range(10000):
    # 1부터 100사이 랜덤 정수
    array.append(randint(1, 100))
    
# 선택 정렬 프로그램 성능 측정
start_time = time.time()

# 선택 정렬 프로그램 소스코드
for i in range(len(array)):
    min_index = i # 가장 작은 원소의 인덱스
    
    for j in range(i + 1, len(array)):
    
        if array[min_index] > array[j]:
            min_index = j
    
    array[i], array[min_index] = array[min_index], array[i] # 스왑
    
end_time = time.time() # 측정 종료

print('선택 정렬 성능 측정: ', end_time - start_time)


# 배열 초기화
array = []

for _ in range(10000):
    # 1부터 100사이 랜덤 정수
    array.append(randint(1, 100))
    
# 기본 정렬 라이브러리 성능 측정
start_time = time.time()

# 기본 정렬 라이브러리 사용
array.sort()

end_time = time.time() # 측정 종료

print('기본 정렬 라이브러리 성능 측정: ', end_time - start_time)