Python 51 - 시간복잡도, 공간복잡도, 빅오표기법 ( 알고리즘 공부 )

목차

1. 시간복잡도

2. 공간복잡도

3. 시간과 메모리 측정

개요

---

복잡도는 알고리즘의 성능을 나타내는 척도이다.

복잡도는 시간 복잡도와 공간 복잡도로 나눌 수 있다.

쉽게 말하면 시간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미하고, 공간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미한다. 복잡도를 측정함으로써 다음과 같은 2가지를 계산할 수 있다.

시간 복잡도 : 알고리즘을 위해 필요한 연산의 횟수

공간 복잡도 : 알고리즘을 위해 필요한 메모리의 양

 

1. 시간 복잡도

---

알고리즘 문제를 풀 때 단순히 ‘복잡도’라고 하면 보통은 시간 복잡도를 의미한다.

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

빅오 표기법을 간단히 정의하자면 가장 빠르게 증가하는 항만을 고려하는 표기법이다.

다시 말해 함수의 상한만을 나타낸다. 예를 들어보자.

a = [3,5,1,2,4]
sum_a = 0
for x in a:
    sum_a +=x
print(sum_a)

위의 예제에서는 5개의 데이터를 받아 차례로 5회 더해준다.

(N=5) 이때 연산 횟수는 N에 비례하는 것을 알 수 있다.

물론 sum_a에 0을 대입하는 연산도 있고 출력하는 부분도 있지만 이런 연산 횟수는 N이 커짐에 따라

무시할 수 있을 정도로 작아질 것이다. 따라서 가장 영향력이 큰 부분은 N에 비례하는 연산을 수행하는

반복문 부분이므로 시간 복잡도는 O(N)이라고 표기한다.

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

a와 b에 값을 대입하는 대입 연산과 출력 함수를 무시하고 보면 연산 횟수는 1회이다.

이는 상수 연산이므로 시간 복잡도는 O(1)이다.

a = [3,5,1,2,4]
for i in a:
    for j in a:
        temp = i*j
        print(temp)

데이터의 개수가 N개일 때, O(N^2)의 복잡도를 가진다.

2중 반복문을 이용하여 각 원소에 대하여 다른 모든 원소에 대한 곱셈 결과를 매번 출력하고 있기 때문이다.

일반적으로 코딩 테스트에서는 최악의 경우에 대한 연산 횟수가 가장 중요하다.

그러니 최악의 경우의 시간 복잡도를 우선으로 고려해야 한다.

다음은 자주 등장하는 시간 복잡도 표인데 위에 있을수록 더 빠르다.

시간 복잡도에 따라서 부르는 명칭이 있는데 예를 들어 O(1)는 ‘상수 시간’, O(N)은 ‘선형 시간’등으로 불린다.

빅오 표기법명칭

O(1)	상수 시간
O(log N)	로그 시간
O(N)	선형 시간
O(NlogN)	선형 로그 시간
O(N^2)	이차 시간
O(N^3)	삼차 시간
O(2^n)	지수 시간

O(N^k)의 경우 다항 시간에 동작하는 알고리즘이라고 말한다.

일반적으로 코딩 테스트 환경에서는 O(N^3)을 넘어가면 문제 풀이에 사용하기 어렵다.

왜냐하면 C언어를 기준으로 연산 횟수가 10억을 넘어가면 통상 1초 이상의 시간이 소요되기 때문이다.

이때 N의 크기가 5000을 넘는다면 10초 이상의 시간이 걸릴 수 있으며, 파이썬의 경우 더욱 오래 걸릴 것이다.

코딩 테스트 문제에서 시간 제한은 1 ~ 5초가량이므로 보통 연산 횟수가 10억을 넘어가면 오답 판정을 받을 수 있다.

일반적으로 문제를 풀 때의 예시를 아래에서 소개하겠다.

제한 시간이 1초인 문제에 대한 예시이다.

• N의 범위가 500인 경우 : 시간 복잡도가 O(N^3)인 알고리즘으로 설계하면 풀이 가능
• N의 범위가 2,000인 경우 : 시간 복잡도가 O(N^2)인 알고리즘으로 설계하면 풀이 가능
• N의 범위가 100,000인 경우 : 시간 복잡도가 O(NlogN)인 알고리즘으로 설계하면 풀이 가능
• N의 범위가 10,000,000인 경우 : 시간 복잡도가 O(N)인 알고리즘으로 설계하면 풀이 가능

코딩 테스트 환경에서는 1초에 2,000만에서 1억정도의 연산을 처리할 수 있다.

대부분의 시간제한은 1초인 경우가 많기 때문에 복잡도를 신중히 고려해야한다.

 

2. 공간 복잡도

---

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

앞서 시간 복잡도에서 1초라는 절대적인 제한이 있던 것처럼, 메모리 사용량에도 절대적인 제한이 있다.

일반적으로 메모리 사용량 기준은 MB단위로 제시된다. 쉽게 말하자면 코딩 테스트 문제에서 보이는 ‘시간 제한 1초, 메모리 제한 128MB’와 같은 문장이 시간 복잡도와 공간 복잡도를 제한하기 위하여 명시하는 것이다.
코딩 테스트 문제는 대부분 리스트(배열)을 사용해서 풀어야 한다.

대부분의 문제는 다수의 데이터에 대한 효율적인 처리를 요구하기 때문이다.

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

코딩 테스트에서 보통 메모리 사용량을 128 ~ 512MB 정도로 제한한다.

다시 말해 일반적인 경우 데이터의 개수가 1,000만 단위가 넘어가지 않도록 알고리즘 설계를 해야한다는 의미이다.

파이썬에서는 int 자료형이 없지만, 파이썬에서도 대략 100만 개 이상의 데이터가 들어갈 수 있는 크기의 리스트를 선언하는 경우는 적다는 점을 기억하자. 만약 크기가 1,000만 단위 이상이라면 알고리즘을 잘못 설계한 것이 아닌지 고려해봐야한다.

 

3. 시간과 메모리 측정

---

파이썬에서는 프로그램 수행 시간과 메모리 사용량을 측정할 수 있다.

알고리즘 공부 과정에서 시간을 측정하는 작업을 굉장히 많이 사용한다.

실질적으로 알고리즘의 소요 시간을 확인해야 자신이 제대로 알고리즘을 작성하고 있는지 체크할 수 있기 때문이다.

따라서 수행 시간을 측정하는 것이 알고리즘의 효율성을 측정하는 가장 기본적인 방법이다.

import time
start_time = time.time()
end_time = time.time()
print('time :',end_time-start_time)

보통 어떤 알고리즘을 설계한 뒤에 시간 복잡도를 경험적으로 증명하고 싶을 때는 위와 같은 형태의 코드를 자주 이용한다. 선택 정렬과 파이썬의 기본 정렬 라이브러리 속도를 비교하는 코드로 예시를 들어보자. 선택 정렬은 최악의 경우 O(N^2)이고, 파이썬 기본 정렬 라이브러리는 최악의 경우 O(NlogN)을 보장하여 상대적으로 빠르다.

from random import randint
import time
arr=[]
for _ in range(10000):
    arr.append(randint(1,100))
start_time=time.time()

for i in range(len(arr)-1):
    min =i
    for j in range(i+1,len(arr)):
        if arr[min]>arr[j]:
            min=j
    arr[i],arr[min]=arr[min],arr[i]
end_time=time.time()

print("성능 측정 :",end_time-start_time)

arr=[]
for _ in range(10000):
    arr.append(randint(1,100))

start_time=time.time()
arr.sort()
end_time=time.time()

print("성능 측정 :",end_time-start_time)

## 출력 결과
성능 측정 : 13.048523664474487
성능 측정 : 0.002000570297241211

확연한 성능차이가 발생한다. 따라서 설계한 알고리즘의 성능을 실제로 확인하기 위해서, 시간 측정

라이브러리를 사용해보는 습관을 기르는 것이 좋다.

 

---

본 포스팅은 ‘이것이 코딩 테스트다 with 파이썬’을 읽고 공부한 내용을 바탕으로 작성하였습니다.

 

 

 

 

 

작성자 엄코딩 eomcoding