복잡도

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

시간복잡도

• 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지 를 의미
• 작성된 프로그램이 모든 입력을 받아 이를 처리하고 실행결과를 출력하는 데까지 걸리는 시간을 의미

시간복잡도를 표현할 때는 **빅오 표기법**을 사용한다. 간단히 정의하자면, 가장 빠르게 증가하는 항만을 고려하는 표기법이다.

N개의 데이터가 있을 때, 모든 데이터의 값을 더한 결과를 출력하는 프로그램을 생각해보자.
이는 합계를 저장할 하나의 변수를 선언한 뒤에 모든 데이터를 하나씩 확인하며 해당 값을 합계 변수에 더해주는 식으로 알고리즘을 작성할 수 있다.

예제 코드1

array = [3, 5, 1, 2, 4] #5개의 데이터(N=5)
summary = 0 #합계 저장할 변수

#모든 데이터를 하나씩 확인하며 합계를 계산
for x in array:
	summary += x
   
#결과 출력
print(summary)

해당 예제에는 5개의 데이터(N=5)를 받아 5회 더해준다. 이렇게 더해주는 연산의 횟수는 N에 비례함을 알 수 있다. summary에 0의 값을 대입하는 연산이나 summary값을 출력하는 연산도 존재하지만 이는 N이 커짐에 따라 더해주는 연산의 횟수와는 비교안될 정도로 작아진다.
따라서 해당 소스코드에서 가장 영향이 큰 부분은 N의 값이므로 이의 시간복잡도는 O(N)이다.

예제 코드2

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

해당 코드는 a와 b에 값을 대입하는것을 제외하고는, 연산 횟수가 1이다. 상수 연산이므로 시간복잡도는 O(1)이다.

예제 코드3

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

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

해당 코드는 데이터의 개수가 N개일 때, O(N^2)의 시간복잡도를 가진다. 하지만 모든 2중 반복문의 시간 복잡도가 O(N^2)은 아니다.

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

공간 복잡도

• 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미
• 알고리즘을 위해 필요한 메모리의 양

int a[1000] : 4KB
int a[1000000] : 4MB
int a[2000][2000] : 16MB

시간과 메모리 측정

파이썬에서는 프로그램 수행 시간과 메모리 사용량을 측정할 수 있다. 즉, 실제 프로그램의 수행 시간을 측정하는 것은 알고리즘의 효율성을 측정하는 가장 기본적인 방법이다.

수행 시간 측정 소스코드

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

#프로그램 소스코드
end_time = time.time()
print("time :", end_time - start_time) #수행 시간 출력

선택 정렬과 기본 정렬 라이브러리의 수행 시간 비교

from random import randint
import time

#배열에 10,000개의 정수를 삽입
array = []
for _ in range(10000):
	array.append(randint(1,100)) #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):
	array.append(randint(1,100)) #1부터 100사이의 랜덤한 정수
    
#기본 정렬 라이브러리 성능 측정
start_time = time.time()

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

end_time = time.time() #측정 종료
print("기본 정렬 라이브러리 성능 측정:", end_time - start_time) #수행 시간 출력

출력

선택 정렬 성능 측정: 35.841460943222046
기본 정렬 라이브러리 성능 측정: 0.0013387203216552734