[Algorithm] 시간 복잡도 & Big-O표기법

시간복잡도(Time Complexity)

특정 알고리즘이 문제를 해결하는데 걸리는 시간

정확한 값을 산출하는 것이 아니라 근사치를 계산한다.

 

점근적 표기법 - 시간복잡도를 나타내는데 사용됨

1) 최상의 경우 : 오메가 표기법(Big-Ω Notation)

최적의 입력을 한 상태에서 작업을 완료하는데 가장 빠른 시간

2) 평균의 경우 : 세타 표기법 (Big-θ Notation)

여러가지 다른 경우의 수를 입력하여, 총실행시간을 계산하고 시행횟수로 나눈다.

3) 최악의 경우 : 빅오 표기법 (Big-O Notation)

최악의 입력을 한 상태에서 작업을 완료하는데 가장 느린 시간

 

-> 평균인 세타 표기법을 사용하면 좋겠지만 평가하기가 까다로워 최악의 경우인 빅오를 많이 사용한다.

---

Big-O 표기법

- 점근적 상한선

- 계수와 낮은 차수의 항을 제외

- 상수는 과감하게 삭제(모두 1)

https://youtu.be/6Iq5iMCVsXA

1 < logn < n < nlogn < n^2 < 2^n < n!

 

O(1) - Constant

입력 데이터의 크기에 상관없이 언제나 일정한 시간이 걸린다.

데이터가 얼마나 증가하든지 상관없으며 거의 성능에 영향을 미치지 않는다.

예시 : 배열에서 특정 인덱스 찾기, 해시테이블 추가

printf("world");

 

O(log₂n) - Logarithmic

입력 데이터의 크기가 커질수록 처리 시간이 로그만큼 짧아지는 알고리즘이다.

데이터가 10배가되면, 처리시간은 2배가 됨.

초반은 빠르지만 후반부에 갈수록 시간이 증가한다.

예시 : 이진 탐색

def binary_search(li, item, first=0, last=None):
	if not last:
		last = len(li)

	midpoint = (last - first) / 2 + first

	if li[midpoint] == item:
		return midpoint

	elif li[midpoint] > item:
		return binary_search(li, item, first, midpoint)

	else:
		return binary_search(li, item, midpoint, last)

 

O(n) - Linear

입력 데이터의 크기에 비례해 처리 시간이 증가하는 알고리즘이다.

예를 들어 데이터가 10배가 되면, 처리시간도 10배가 됨.

예시 : 연결리스트 순회, 최대값 찾기, 1차원 for문

for(int i = 0; i < n; i++){
	printf("world");
}

 

O(nlog₂n) - Linear Logarithmic(선형 로그형)

데이터가 많아질수록 처리시간이 로그 배만큼 늘어나는 알고리즘이다. 

예를 들어 데이터가 10배가 되면, 처리시간은 약 20배가 된다. -> 컬렉션 정렬을 사용하는 경우

예시 : 병합 정렬, 퀵 정렬

 

O(n²) - Quadratic(전형적)

데이터가 많아질수록 처리시간이 급수적으로 늘어나는 알고리즘이다.

예를 들어 데이터가 10배가 되면, 처리시간은 최대 100배가 된다.

예시 : 이중 루프(n² matrix)가 대표적이며 m이 n보다 작을때에는 반드시 O(nm)으로 표시한다.

for(int i = 0; i < n; i++){
	for(int k = 0; k < n; k++){
		printf("world");
    }
}

 

O(2ⁿ) - Exponential(지수형 빅오)

데이터량이 많아질수록 처리시간이 기하급수적으로 늘어나는 알고리즘이다.

예시 : 피보나치수열, 재귀가 역기능을 할 경우

 

O(n!) - factorial(계승)

---

* 입력 값 N에 따른 시간복잡도

Complexity	1	10	100
O(1)	1	1	1
O(log N)	0	2	5
O(N)	1	10	100
O(N log N)	0	20	461
O(N^2)	1	100	10000
O(2^N)	1	1024	1267650600228229401496703205376
O(N!)	1	3628800	화면에 표현할 수 없음

 

정렬 알고리즘

 

자료구조 알고리즘

---

https://cooervo.github.io/Algorithms-DataStructures-BigONotation/index.html

Big O cheat sheets

https://blog.chulgil.me/algorithm/

https://velog.io/@leobit/%EB%B3%B5%EC%9E%A1%EB%8F%84Complexity

https://coding-factory.tistory.com/608

https://www.freecodecamp.org/news/time-is-complex-but-priceless-f0abd015063c/#.j7h5s1m2p