공간 복잡도

공간 복잡도를 표기할 때도 빅오 표기법을 사용한다.

메모리 사용량 기준은 MB 단위로 제시됨.

 

코테 문제는 대부분 리스트를 사용해서 풀어야 한다. (효율적인 데이터 처리를 위함)

정수형 자료형인 int를 기준, 리스트 크기에 따른 메모리 사용량 확인해보자

• int a[1000]: 4KB
• int a[1,000,000]: 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) # 수행 시간 출력

 

 

위 코드를 활용한 예시

'선택 정렬' 과 '파이썬 기본 정렬 라이브러리' 속도 비교

 

import time
from random import randint

# 배열에 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] # swap

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

# 배열을 다시 무작위 데이터로 초기화
array = []
for _ in range(10000):
    array.append(randint(1, 100))

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

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

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

정렬 성능 측정 결과