[알고리즘] 시간복잡도 & 공간복잡도

알고리즘 성능 측정

• 무엇이 좋은 알고리즘일까? 정확성, 작업량, 메모리, 가시성, 확장성 ... 등등
• 모두 중요하지만, 실제 상황에 따라 우선 순위가 적용될 것이다. 정성적으로 판단하는 것들을 제외하고, 정량적으로 판단하기 위한 기준이 필요해 보인다.
• 특히, 코딩테스트와 같은 메모리와 수행 시간이 정해진 문제를 풀때 유용한 판단 방식에 집중한다.

이러한 문제를 해결하기 위하여

 

시간복잡도

• 알고리즘 작업량(수행 시간)을 예상할 때 사용한다.
• 코딩테스트에서 테스트 케이스가 전부 공개되지 않기때문에 직접 돌려가면서 확인할 수 없다. 따라서 시간복잡도를 계산하여 작업 시간을 추측한다. 우선은 시간복잡도는 수행되는 명령문의 수라고 생각하자.
  

예를들면, 
100이하의 모르는 수를 찾아간다. 그 수는 75라고 하자.
[1경우] 1->2->3->4 이렇게 순서대로 확인할 수 있다.
[2경우] 100->50->75 가운데 값의 업다운을 통해 찾아갈 수 있다.
보통의 경우에 [2경우]가 더 적은 명령문으로 수를 찾는다.

흔하게 만나는 시간 부족

 

시간 복잡도 표기법 (빅-오 표기법, Big-O Notation)

• 코딩테스트에 사용하기 위한 지식까지 접근한다. (깊은 내용은 여기를 참고)
• 빅-오 표기법은 시간 효율을 알기위해 "자잘한건 무시하고 가장 영향이 큰 n에 대해 생각하겠다" 정도로 생각할 수 있다.
• 이때, 최악의 경우에 걸리는 수행을 생각한다. (정답은 가장 마지막에 발견될 것이다.)

위 콘셉트에 따라 간단화를 위해 (1) 계수는 생략하다. (2) 가장 영향력이 큰 요소만 고려한다. 라는 두가지 원칙으로 표시된다.

예를들면,
(1) 계수 생략: O(3n + 2) => O(n)
(2) 가장 큰 요소: O(3n^2 + 2n + 20) => O(n^2)

 

시간 복잡도 적용

대표적으로 아래와 같이 사용된다.
1. N번을 순환하는 단일 for문: O(N)
2. N번을 순환하는 이중 for문: O(N^2)
3. 이진탐색 알고리즘 (숫자맞추기): O(NlogN)

• 가능한 적은 복잡도의 코드 작성 

시간 소요: O(N) < O(NlogN) < O(N^2) < O(N^3) ... 

시간복잡도에 따른 효율을 확실하게 볼 수 있다.

• 문제 유형에 따라 감각적으로 판단 (출처)

문제 유형에 따라 판단 (Worst는 피하자)

주의 사항

입력을 받는 방식에 따른 시간이라던가, 내부 함수 호출 방식 등 다양한 요소에서 시간이 소요될 수 있다. 따라서, 시간이 오래걸리는 특정 방법들 (예를들면 깊은 재귀함수)을 피하며 코드를 짜는 습관이 중요하다.

 

수행시간 직접 측정하기

import time
start_time = time.time()	        # 측정 시작
"""
프로그램 코드 수행
"""
end_time = time.time()	            	# 측정 종료
print('time:', end_time - start_time)	# 수행 시간

 

---

공간 복잡도

• 시간 복잡도가 더 크게 영향을 미친다. 메모리는 여유있는 경우가 많다.
• 빅데이터로 인하여 데이터가 증가하는 속도가 메모리 발전 속도를 넘는다면 중요도가 올라가지 않을까 싶다.
• 자세하게 알고싶으면 여기를 참고하자.

공간 복잡도 표기법 (빅-오 표기법) 및 사용

• 표기법은 위 시간복잡도와 같이 구한다.
• 시간복잡도와 다르게, 신뢰할만한 공간 복잡도에 따른 메모리 상관 관계를 찾지 못했다.
• 사용하는 언어에 따른 공간 효율이 크게 다르기 때문일것이다.