시간복잡도 / 공간복잡도

복잡도

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

" 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지 "

 

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

" 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지 "

 

 

일반적으로 시간 복잡도와 공간 복잡도는 거래 관계 trade-off 성립

- 시간을 비약적으로 줄이는 기법 존재 : Memoization 등

 

 

시간 복잡도

• 빅오 Big-O 표기법

가장 빠르게 증가하는 항만을 고려하는 표기법

즉, 함수의 상한만 나타낸다.

 

시간 복잡도 낮은 순서

 

(번역) 알고리즘 쉽게 이해하기 : 시간 복잡도와 Big-O 표기, Captain Pangyo

[알고리즘] 시간복잡도 (Time Complexity), 별토끼 DEVLOG

시간 복잡도가 클수록 입력 데이터의 크기가 증가할수록 실행 시간이 급격하게 증가한다.

시간제한을 준수하기 위해 적절한 알고리즘을 선택해야 한다.

 

---

 

실행시간이 입력 자료의 수 N에 영향을 받지 않고 일정함

$$ O(1) $$

상수 시간(Constant time)

a = 1
b = 2
print(a + b)

---

 

 

실행시간이 입력 자료의 수 N에 영향을 받고 증가

$$ O(logN) $$

로그 시간(Log time)

큰 문제를 일정한 크기를 갖는 작은 문제로 쪼갤 때

이진 탐색

 

 

$$ O(N) $$

선형 시간

for x in array:
    summary += x

입력 자료의 개수 N와 시간이 선형적인 관계를 가짐

입력자료마다 일정한 시간을 할당하는 경우

 

$$ O(NlogN) $$

로그 선형 시간

큰 문제를 일정한 크기, 일정한 횟수로 나누어 푸는 경우

logN +logN +.... = N* logN 

 

 

$$ O(N^2)$$

이차 시간

# N = 5
array = [1, 2, 3, 4, 5]

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

반복문 내부에서 소스 코드가 다른 함수를 호출한다면 내부 함수의 시간 복잡도까지 고려해야 한다.

$$ O(N^3)$$

삼차 시간

# N = 5
array = [1, 2, 3, 4, 5]

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

 

$$ O(2^n)$$

지수 시간

 

 

주의 : 빅오 표기법은 상수를 크기에 상관없이 무시하기 때문에 적절하지 않은 경우가 존재한다.

$$  N^3 + N^2 + N + 999999999999999 $$

• 빅오 표기법에서 시간 복잡도가 더 크더라도 상수항과 계수에 따라 실제 연산 횟수는 작을 수 있다.
• 빅오 표기법에서 시간 복잡도가 같더라도 상수항과 계수에 따라 실제 연산 횟수는 다를 수 있다.

 

 

시간 복잡도 분석

시간 복잡도 분석은 문제 풀이의 핵심

문제의 조건을 파악하고 주어진 시간제한을 고려하여 사용할 알고리즘을 좁혀가는 방식

 

시간제한 : 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. 사용 가능한 알고리즘 리스트 작성
    3. 적절한 알고리즘 선택

  

 

효과적으로 문제를 풀기 위해서 2가지 방식을 병행하자

• 데이터의 개수와 시간제한을 보고 알고리즘을 찾는 top-down 방식
• 문제를 파악하고 적절한 알고리즘을 선택하는 bottom-up 방식

 

 

 

 

 

공간 복잡도

빅오 표기법을 이용하여 표기

메모리 사용량의 기준은 MB 단위

일반적으로 코딩 테스트에서 메모리 사용량은 128 ~ 512MB로 제한된다.

데이터의 개수가 1,000만 단위를 초과하지 않도록 알고리즘 설계

 

 

시간 측정법

import time

start_time = time.time() # 코드 실행 시작 시각

# 프로그램 소스 코드 실행
# {
#    ...
# }

end_time = time.time() # 코드 실행 종료 시각

run_time = end_time - start_time # 수행 시간
print("time : ", run_time) # 출력

 

---

21년 11월에 있을 프로그래머스 인공지능 데브 코스 3기를 대비해서 1달 만에 생기초부터 프로그래머스 기준 Lv2까지 도전한다. 한 달 남짓한 시간에 학업과 다른 일들을 병행하며 어느 정도 수준까지 도달할 수 있을지 궁금하다.

 

 

 

reference

(번역) 알고리즘 쉽게 이해하기 : 시간 복잡도와 Big-O 표기 – Captain Pangyo (wordpress.com)

[알고리즘] 시간 복잡도 (Time Complexity) (tistory.com)

[알고리즘] 시간복잡도 (Time Complexity)