Data Structure - 시간 복잡도(Time Complexity)

1. 시간 복잡도

- 어떤 문제를 해결하는데에 있어 어떤 알고리즘이 가장 빠른지 판단하기 위해 알고리즘의 효율성을 수치적으로 계산한 것이다.

- 알고리즘의 효율성을 측정하기 위해서 알고리즘이 복잡한 정도를 계산하는데 여기에는 시간과 공간, 2가지가 있다. 

• 시간 복잡도
  - 알고리즘의 실행 속도
• 공간 복잡도
  - 알고리즘이 사용하는 메모리의 양/사이즈 

* 현업에서 주로 사용하는 것은 시간복잡도이다. 시간복잡도에 대하여 자세히 알아보자.

 

c) 시간 복잡도의 핵심 요소 - 반복문

- 알고리즘 구조에서 어느 부분에서 가장 시간을 많이 소요하는지를 파악하는 것이 핵심이다. 

- 입력의 크기가 커질수록 반복문의 수행시간이 증가하게 되며, 이는 곧 알고리즘의 수행시간을 증가시킨다. 

 

d) 시간복잡도의 표기법 종류 

• Big O(빅-오) 표기법 [ O(N) ]
  - 알고리즘 최악의 실행 시간을 표기(최악의 상황에서도 보장하는 알고리즘의 수행 속도를 의미
  - 성능 보장을 의미하기때문에 가장 많이 사용하는 표기법이다.
• 오메가 표기법 [Ω(N)]
  - 알고리즘 최상의 실행 시간을 표기
• 세타 표기법 [Θ(N)]
  - 알고리즘 평균 실행 시간을 표기

---

2. Big O(빅-오) 표기법에 대하여

1) 표기법

- n이란 입력값의 크기를 의미하는 것이고n에 의해 알고리즘이 받는 영향력(반복수)을 표기하는 것이다.

2) 표기방식에 따른 시간복잡도의 차이

O(1)이 가장 좋은/빠른 시간복잡도이다.

3) n을 계산하는 방법 

 

ex1) O(1)으로 표기하는 경우 

 

 

ex2) O(n)으로 표기하는 경우 

 

 

ex3) O(n^2)으로 표기하는 경우 

 

참고) n(입력의 크기)에 따라 달라지는 수행시간이 달라진다는 것 

https://miro.medium.com/max/631/1*uSo07VUOd9WhOUtgc7jX1g.png

---

3. 알고리즘에 따라 달라지는 시간 복잡도

문제) 1부터 n까지의 합을 구하는 알고리즘을 만들고 시간복잡도를 계산하라.

 

알고리즘-1)

- 위의 알고리즘은 입력값 n에 의해 n번 더해지는 식이므로 n값에 의해 반복횟수가 정해지는 알고리즘이다.

- 그러므로 시간복잡도는 O(n)이다. 

 

알고리즘-2)

- 위의 알고리즘은 n에 따라 n번 반복수행 하지 않고 n과는 상관없이 딱 한번만 연산을 수행한다. 

- 그러므로 시간복잡도는 O(1)이다. 

 

결론)

- 위에서 봤듯이 시간복잡도의 효율성은 다음과 같다.

- O(1)이 O(n)보다 더 빠른/효율적인 시간복잡도를 의미한다. 

- 시간복잡도는 반복문에 의해 좌우된다.

- 알고리즘-1은 반복문이 있고 알고리즘-2는 반복문이 없다. 여기서 반복문의 효율성은 차이가 난다. 

- 그러므로 동일한 문제에 대해서 알고리즘-2가 더 좋은 알고리즘이다.