시간 복잡도 - 빅오표기법

시간 복잡도는 알고리즘 복잡도 중에 하나이다.

이번 포스팅에서는 알고리즘 복잡도에서부터 시간복잡도, 빅오 표기법에 대해서 알아보자.

---

🌱 알고리즘 복잡도?

하나의 문제를 푸는 알고리즘은 다양할 수 있다.

다양한 알고리즘 중 어느 알고리즘이 더 좋은지를 판단하기 위한 평가방법이다.

 

이러한 알고리즘의 복잡도를 계산하는 다양한 방법들이 있다.

그중에 가장 중요한 것 두개를 꼽자면,

1) 시간 복잡도 : 알고리즘 실행속도

2) 공간 복잡도 : 알고리즘이 사용하는 메모리 사이즈

-> 예전에는 메모리가 비쌌기때문에 이게 중요하기도 했다.

-> 하지만 공간복잡도는 요즘엔 잘 계산하지않고 시간 복잡도를 주로 계산한다.

 

시간복잡도 표기법에는 Big O 표기법, 오메가 표기법, 세타 표기법이 있다. Big O 표기법은 최악의 실행시간을, 오메가 표기법은 최선의 실행시간을 나타내는데, 이중 빅오 표기법을 가장 많이 사용한다.

---

🌱 Big O 표기법

  빅오 표기법은 알고리즘 최악의 실행시간을 표기한다.

  즉 아무리 최악의 상황이라도, 이정도 성능을 보장한다는 뜻이다.

  O(n)은 입력 n에 따라 결정되는 시간복잡도 함수를 의미한다. n의 크기에 따라 기하급수적으로 시간복잡도가 늘어날 수 있다. 표현식에 가장 큰 영향을 미치는 n의 단위로 표기하면 된다. 예를들어 2n^2+3n+1이라면 빅오표기법상에는 O(n^2)이다.

 

# O(1)
if(n>10):
	print(n)

# O(n), 3n의 예
for num in range(3):
	for index in range(n):
		print(index)
        
# O(n^2)
for num in range(n):
	for index in range(n):
		print(index)

 

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n)

 

🌱 Big O 예제

1. O(1) : 스택에서 Push, Pop

2. O(log n) : 이진트리

3. O(n) : for 문

4. O(n log n) : 퀵 정렬(quick sort), 병합정렬(merge sort), 힙 정렬(heap Sort)

5. O(n^2) : 이중 for 문, 삽입정렬(insertion sort), 거품정렬(bubble sort), 선택정렬(selection sort)

6. O(2^n) : 피보나치 수열