시간복잡도, 공간복잡도 [이코테-나동빈]

복잡도

: 일반적으로 알고리즘의 성능을 나타내는 척도

 

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

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

 

*복잡도가 낮을 수록 좋은 알고리즘

*시간복잡도와 공간복잡도는 Trade-Off 관계 

- 메모리를 많이 사용하는 대신 시간을 줄일 수 있고, 메모리를 적게 사용하는 대신 시간이 늘어날 수 있다.

시간복잡도(Time Complexity)

일반적(알고리즘 문제시)으로 시간복잡도 == 복잡도를 의미한다.

*시간복잡도가 중요한 이유는 알고리즘 테스트시에 제한시간을 넘겨 시간초과(Time Limit Exceeded)로 오답이 될 수있음

빅오(Big-O)

: 시간복잡도를 표현할 때 사용하는 표기법

*가장 빠르게 증가하는 항만을 고려하는 표기법(함수의 상한만을 나타냄)

#5개의 데이터(N = 5)
array = [3,5,1,2,4]

#합계를 저장할 변수
summary = 0

#데이터를 하나씩 확인하며 합계를 계산
for i in array:
  #summary = summary + i
  summary += i

print(summary)

#15

위의 예는 5개의 값을 받아 5번 더해주는 코드이다.

즉 N=5 연산 횟수가 N에 비례한다.

*변수를 대입하거나 출력하는 연산은 N의 횟수가 커짐에 따라 무시할 수 있을정도로 작아지니 무시하도록 한다.

가장 연산의 횟수에 가장 큰 영향력을 주는 부분이 for(반복문)문이기 때문에 시간복잡도는 O(N)이라고 표기한다.

 

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

#12

위의 예의 연산횟수는 a+b 즉 1이다. 단순하게 더하기 연산 한번만 수행하기 때문이다.

이는 O(1)으로 표시한다.

 

#5개의 데이터 N=5
array = [3,5,1,2,4,]

for i in array:
  for j in array:
    result = i*j
    print(result)
    
    #9
    #15
    #3
    #....

위의 예시는 데이터 수(현재는 5개) N개 일때, 2중 반복문을 사용하여 N x N(N 곱하기 N)의 연산을 하기 때문에

시간복잡도는 O(N²)으로 표기할 수 있다.

*하지만 모든 2중 반복문이 O(N²)은 아니다. 소코드를 분석하여 다른 시간복잡도를 고려해야한다.

표기법	명칭
O(1)	상수 시간
O(logN)	로그 시간
O(N)	선형 시간
O(NlogN)	로그 선형 시간
O(N²)	이차 시간
O(N³)	삼차 시간
O(2ⁿ)	지수 시간

*시간복잡도표

*위쪽에 있을 수록 더 빠르며 아래로 갈수록 느리다.

 

공간복잡도

*공간복잡도 또한 빅오(Big-O)표기법을 사용한다.

*시간복잡도의 시간제한(1초)가 있는것 처럼 메모리의 제한이 있다.

-'시간 제한 1초, 메모리제한 128MB' 

측정

import time
#측정 시작
start_time = time.time()
#소스코드 
array = [3,1,2,5,6]

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

#측정 종료
end_time = time.time()
print("사용시간 : ",end_time - start_time)

위의 예처럼 time 라이브러리를 import 한뒤에 start_time(시작시간)과 end_time(종료시간) 사이에 코드를 입력하여 

시간을 확인할 수 있다.