시간복잡도(Time Complexity), 빅오(Big-O)표기법이란?

# 시간복잡도(Time Complexity)란?

* 알고리즘이 문제를 해결하기 위한 시간(연산)의 횟수

* INPUT N에 대하여 알고리즘이 문제를 해결하는 데에 얼마나 오랜 시간이 걸리는 지를 분석하는 것

* 최고차항의 계수만 표기하는 방법을 사용

  (N이 커질수록 낮은 차수들의 연산의 횟수는 상대적으로 작아져서 무시해도 됨)

ex) n개의 데이터에 대한 연산 횟수가 

$$2n^3-5n^2+n+1일 경우 시간 복잡도는 $$O\left(n^3\right)이다. 

최고차항의 계수 $$2와 $$-5n^2+n+1이 시간 복잡도에 영향을 안 끼치는 것은 아니나, 

전체적인 관점에서 보면 최고차항의 차수가 가장 큰 영향을 끼치고 그 외의 것들은 최고차항의 차수에 비하면 상대적으로 영향이 미미하기 때문이다.

# 알고리즘 성능 파악

1. 최선의 경우 Best Case

2. 최악의 경우 Worst Case

3. 평균적인 경우 Average Case

평균적인 경우가 가장 이상적으로 보이겠지만 알고리즘이 복잡해 질수록 평균적인 경우는 구하기가 매우 어려워 진다.

그러므로 최악의 경우로 알고리즘의 성능을 파악한다.

# 빅오(Big-O)표기법이란?

* 최악의 경우로 알고리즘의 성능을 파악하는 것

ex) Binary Search 알고리즘의 시간복잡도를 Big-O로 나타내면 O(n log n) -> Binary 알고리즘은 n개의 원소가 있을때 아무리 못해도(최악의 경우에)     n log n번 정도(대략적) 반복문을 돌리면 값을 찾을 수 있다는 의미이다.

# 시간복잡도 정리

참고로 logn은 $$\log_{2}n을 의미한다.

• $O\left(1\right)$ 과 같은 상수(Constant) 형태
• $$O\left(\log n\right) 과 같은 로그(Logarithmic) 형태
• $$O\left(n\right) 과 같은 선형
• $$O\left(n \log n\right) 과 같은 선형로그 형태
• $$O\left(n^c\right), $$O\left(n^3\right)과 같은 다차(Polynomial) 형태
• $$O\left(c^n\right), $$O\left(3^n\right)과 같은 지수(Exponential) 형태
• $$O\left(n!\right)과 같은 팩토리얼(Factorial) 형태

$$\log n

시간복잡도가 O(N^3)이상이면 시간복잡도가 기하급수적으로 늘기때문에 실행하기 힘든 프로그램

# 참고사항

* 작성한 알고리즘이 1억 번의 연산을 하면 수행시간은 1초로 가정하고 접근하는것이 일반적이다.

# 참고 사이트

https://ko.wikipedia.org/wiki/%EC%8B%9C%EA%B0%84_%EB%B3%B5%EC%9E%A1%EB%8F%84

https://namu.wiki/w/%EC%8B%9C%EA%B0%84%20%EB%B3%B5%EC%9E%A1%EB%8F%84

https://m.blog.naver.com/PostView.nhn?blogId=kks227&logNo=220769859177&proxyReferer=https%3A%2F%2Fwww.google.com%2F

https://www.youtube.com/watch?v=OVRLHJC95Gs

https://www.youtube.com/watch?v=6Iq5iMCVsXA