[Python] 1. 복잡도

1. 복잡도

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

시간 복잡도

특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미, 알고리즘을 위해 필요한 연산 횟수를 계산할 수 있다. 알고리즘 문제를 풀 때, 단순히 '복잡도'라고 하면 보통은 시간 복잡도를 의미한다.  

cf) 빅오(Big-O) 표기법 : 시간 복잡도를 표현하는 방법, 가장 빠르게 증가하는 항만을 고려하는 표기법 

a = 5
b = 7
print(a + b)
# a와 b에 값을 대입하는 대입 연산과 출력 함수를 무시하고 보면, 연산 횟수는 1
# 단순 더하기 연산 한번이 수행되므로(상수 연산) 시간 복잡도는 O(1)

 

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

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

# 데이터의 개수가 N개일 때, 2중 반복문을 이용하여 
# 각 원소에 대하여 다른 모든 원소에 대한 곱셈 결과를 매번 출력하고 있기 때문에 
# O(N²)의 시간 복잡도를 가진다.

 

cf) 빅오 표기법

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

 

cf) 범위에 따른 시간 복잡도별 알고리즘 선택 예시

• N의 범위가 500인 경우 : 시간 복잡도가 O(N³)인 알고리즘을 설계하여 푼다. 
• N의 범위가 2,000인 경우 : 시간 복잡도가 O(N²)인 알고리즘을 설계하여 푼다.  
• N의 범위가 100,000인 경우 : 시간 복잡도가 O(NlogN)인 알고리즘을 설계하여 푼다. 
• N의 범위가 10,000,000인 경우 : 시간 복잡도가 O(N)인 알고리즘을 설계하여 푼다. 

 

공간 복잡도

특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미, 알고리즘을 위해 필요한 메모리의 양을 계산할 수 있다. 

int를 기준으로한 리스트 크기에 따른 메모리 사용량

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

코딩 테스트에서 보통 메모리 사용량은 128 ~ 512MB 정도로 제한한다. 즉, 일반적인 경우 데이터의 개수가 1,000만 단위가 넘어가지 않도록 알고리즘을 설계해야 한다는 의미이다. 

 

시간과 메모리 측정

수행시간 측정 소스코드

import time
start_time = time.time()

end_time = time.time()
print("time :", end_time - start_time)

 

선택 정렬과 Sort정렬의 수행시간 비교

from random import randint
import time

array = []
for _ in range(10000):
    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)

sort_start_time = time.time()

array.sort()

sort_end_time = time.time()

print("sort 시간:", sort_end_time - sort_start_time)

# 선택 정렬 시간측정 : 8.62038803100586
# Sort 정렬 시간측정 : 0.0010328292846679688

선택 정렬보다 파이썬 기본 라이브러리의 Sort정렬이 훨씬 빠른 것을 확인할 수 있다. 

 

 

 

'이것이 코딩테스트다'를 읽고 공부한 내용을 바탕으로 작성하였습니다.