[Algorithm 이론] 시간/공간 복잡도

알고리즘 코딩 테스트를 볼때 코드가 돌아가는 시간과 메모리의 제한이 있다.
이에 대한 기본적인 개념과 적용 방법에 대해 알아보자

시간/공간 복잡도

복잡도

• 알고리즘 공부에 앞서 코테를 보면 제한 시간과, 제한 메모리가 명시되어 있다.
• 그냥 막 짠다고 무조건 되는 것이 아니고, 효율적인 코딩을 하라는 뜻.
  

1) 시간 복잡도 : 알고리즘을 위해 필요한 연산의 횟수

• 모든 입력을 받아 처리하고 실행결과를 출력하는 데 걸리는 시간
• Big-O(빅오) 표기법으로 표현
  • 가장 빠르게 증가하는 항만 고려
    • 예시-1을 보면 연산 횟수는 데이터 개수에 비례 = O(N)으로 O(5)
    • 예시-2을 보면 연산 횟수는 for문이 2개 이므로 O($N^2$)으로 O(25)가 된다
  • But, 절대적인 것은 아니고 알고리즘 내부 로직에 따라서 달라질 수 있음.
  • 10억이 넘어가면 오답이라 생각
• 아래 표는 위로 갈수록 빠름

빅오 표기법	명칭	N=1000일 때 연산 횟수
O(1)	상수 시간	1
O($\log N$)	로그시간	10
O(N)	선형 시간	1000
O($N\log N$)	로그 선형 시간	9965
O($N^2$)	이차 시간	1,000,000
O($N^3$)	삼차 시간	1,000,000,000
O($2^N$)	지수 시간	1.07e+301

TIP!

• 시간 제한이 1초일 때
  • N의 범위 500 : O($N^3$)인 알고리즘 설계
  • N의 범위 2,000 : O($N^2$)인 알고리즘 설계
  • N의 범위 100,000 : O($NlogN$)인 알고리즘 설계
  • N의 범위 10,000,000 : O(N)인 알고리즘 설계

# 예시-1
array = [3, 5, 1, 2, 4]  # 데이터 5개
summary = 0

for i in array:
    summary += i

# 예시-2
array = [3, 5, 1, 2, 4]  # 데이터 5개

for i in array:        # for문-1
    for j in array:    # for문-2
        temp = i * j

2) 공간 복잡도 : 알고리즘을 위해 필요한 메모리의 양

• Big-O 표기법 이용
• 데이터의 개수가 1,000만 단위가 넘어가지 않도록 알고리즘 설계해야 함
• 가독성을 해치지 않는 선에서 최대한 복잡도가 낮게 프로그램을 작성
  
  

3) 시간과 메모리 측정

• 실질적으로 알고리즘의 소요 시간을 확인해야 제대로 작성하고 있는지 체크 가능

# 수행 시간 측정 예시 코드-1
import time

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

time :  0.0

# 수행 시간 측정 예시 코드-2
from random import randint
import time

start_time = time.time()

array = []
for _ in range(10000):
    array.append(randint(1, 100))


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)

선택 정렬 성능 측정:  10.139973878860474