[Algorithm] 시간복잡도(Time-Complexity)란? (feat. Big O)

안녕하세요 Foma 💻 입니다!

 

요즘 들어 알고리즘 공부를 하는데 알고리즘의 핵심인 시간복잡도에 대해서 정리하지 않은 것 같아서..

 

이번 기회에 구체적으로 시간복잡도에 대해서 정리해보겠습니다!

 

바로 시작할게요~

---

시간복잡도란? ⏱

 

컴퓨터공학 용어로, 컴퓨터 프로그램의 입력값과 연산 수행 시간의 상관관계를 나타내는 척도이다. 일반적으로 시간 복잡도는 점근 표기법을 이용하여 나타낸다.

 

즉, 계산되는 양에 따라서 시간이 얼마나 걸릴지를 나타내는 것입니다.

---

시간복잡도 표기법 🖊

 

시간복잡도 표기법은 빅오메가,빅세타,빅오 이렇게 3가지가 있습니다.

 

1. BigΩ (Best case)

 

빅오메가 표기법은 최선의 실행시간 즉, 가장 빠른 케이스를 나타내는 것입니다.

 

2. Big𝚯 (Average case)

 

빅세타 표기법은 최선과 최악의 평균 실행시간 즉, 평균적인 케이스를 나타내는 것입니다.

 

3. BigO (Worst case)

 

빅오 표기법은 최악의 실행시간 즉, 가장 느린 케이스를 나타내는 것입니다.

 

프로그램 상에서 문제라고 하면 느리게 실행될 때잖아요?

 

고로 보통의 경우 시간복잡도를 표기할 때 빅오 표기법을 사용합니다.

---

시간복잡도 수행시간 ⏰

 

빅오 표기법으로 시간복잡도 수행시간이 낮은 것부터 높은 것까지 설명하겠습니다.

 

1. O(1)

 

n이 몇개 있든지 간에 실행시간이 일정한 것을 의미합니다.

 

ex) 1부터 100만까지를 key로 가지고 있는 해쉬 테이블 중 7을 key로 가지고 있는 value 값을 찾을 때

 

2. O(logn)

 

logn은 log₂n과 동일합니다.

 

(저는 logn은 n을 절반으로 나눌 수 있는 수라고 이해하면 쉽더라구요.

 

log8을 절반으로 나눌 수 있는 수는 4 - 2 - 1이므로 3입니다.)

 

ex) 이진 탐색을 통해서 값을 찾을 때

 

3. O(n)

 

보통 n개의 모든 수를 탐색해서 찾아야 하는 수행시간을 의미합니다.

 

ex)1부터 100만까지 무작위로 숫자가 담긴 배열 중 7을 찾아야 할 떄

 

4. O(nlogn)

 

ex) 병합 정렬을 통해서 값을 정렬할 때

 

5. O(n^2)

 

보통 이중 for문을 이용해서 n개의 값을 n번 대입해야 하는 수행시간을 의미합니다.

 

ex) 배열 a의 값이 배열 b에 있는지 확인할 때

 

6. O(2^n)

 

2의 n제곱만큼 늘어나므로 n이 늘수록 정말 가파른 수행시간을 가지는 것을 의미합니다.

 

ex) 피보나치 수열,재귀 탐색을 통해 값을 찾을 떄

 

7. O(n!)

 

최악의 수행시간을 가지는 것을 의미합니다.

 

ex) 팩토리얼

 

n의 값이 커질수록 아래와 같은 그래프를 가지게 됩니다.

출처:http://bigocheatsheet.com/

 

n에 따라서 걸리는 수행시간은 아래와 같습니다.

 

시간/n	1	10	100
O(1)	1	1	1
O(logn)	0	2	5
O(n)	1	10	100
O(nlogn)	0	20	461
O(n^2)	1	100	10000
O(2^n)	2	1024	1267650600228229401496703205376
O(n!)	1	3628800	너무 큼...

---

오늘은 이렇게 시간복잡도 표기법과 걸리는 수행시간에 대해서 알아보았습니다.

 

이렇게 구체적으로 정리하고 나니깐 왜 빅오 표기법으로 수행시간을 설명하고 알고리즘을 효율적으로 짜야하는지

 

더 와닿네요!

 

혹시라도 틀린 점이나 궁금하신 사항이 있으면 댓글로 알려주세요!