시간복잡도와 공간복잡도

복잡도란?

알고리즘의 성능을 나타내는 척도.

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

1) 시간 복잡도

코딩테스트에서 시간 복잡도는 작성한 프로그램이 모든 입력을 받고 처리, 및 실행 결과를 출력하는데 걸리는 시간을 의미한다.

1-1 BIG-O 표기법

간단하게 정의할 때, 가장 빠르게 증가하는 항만을 고려하는 표기법이다.

이 표에서 아래로 갈수록 입력한 값의 양(N)을 늘릴 때, 연산량이 많아지게 되고, 이는 연산시간이 늘어나게 된다.

또한 BIG-O 표기법에서는 차수가 가장 큰 항만을 남기게 된다.

하지만 연산횟수가 $N_3$ +5N_2+1,000,000$인 알고리즘에서 상수 값이 연산시간에 큰 영향을 주기 때문에 BIG-0 표기법이 절대적인 시간 복잡도의 척도라고 보기 어렵다.

파이썬은 타 언어보다 연산 시간이 오래걸리며, 코딩 테스트 문제에서 시간제안은 1~5초 가량이므로, 일반적으로 $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) 공간 복잡도

시간 복잡도와 같이 빅오 표기법을 사용, 메모리 사용량 기준은 일반적으로 MB이다.

코딩테스트에서는 보통 리스트(배열)을 이용하여 풀어야한다.(다수 데이터에 대한 효율적인 처리 요구)

자료형의 종류: 정수형, 실수형, 복소수형, 문자열, 리스트, 튜플, 사전

실수형에 대한 오류는 다음과 같다.

0.3+0.6 = 0.9가 아닌 이유: IEEE754 표준에서는 4BYTE, 8BYTE의 고정된 크기를 지원하므로, 실수 정보 표기에 어려움이 있다.
(예: 2진수에서는 0.9를 정확히 표현할 수 없어, 미세한 오차 발생)
따라서 round()를 통한 반올림으로 정확히 계산

나누기 연산자(/)를 통해 계산된 값은 실수형으로 반환된다.

3) 시간과 메모리 측정

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

# 프로그램 소스코드

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