알고리즘과 시간복잡도(Time Complexity)

시간 복잡도란 문제를 해결하는 데 걸리는 시간과 입력의 함수관계라 한다.

효율적인 알고리즘 구현 방법에 대해 고민한다면 시간 복잡도를 고려해야 하며

효율적인 알고리즘 방법을 고민한다는 것은 시간 복잡도를 고민한다고 할 수 있다.

 

알고리즘의 로직을 코드로 구현할 때 시간 복잡도를 고려한다는 것은

입력값의 변화에 따라 연산이 실행될 때, 연산 횟수에 비해 시간이 얼마나 걸리는가라는 의미이다.

효율적인 알고리즘을 구현한다는 것은 입력값이 커짐에 따라 증가하는 시간의 비율을

최소화한 알고리즘을 구현했다고 할 수 있다.

 

시간 복잡도를 표기하는 세 가지 표기법이 있다.

Big-O(빅-오) ⇒ 상한 점근

Big-Ω(빅-오메가) ⇒ 하한 점근

Big-θ(빅-세타) ⇒ 그 둘의 평균

위 세 가지 표기법은 각각 최악, 최선, 평균의 경우에 대해 나타내는 방법이다.

 

알고리즘을 평가할 때 대부분 최악의 경우를 염두에 두고 하기 때문에 주로 빅-오 표기법을

사용하여 나타낸다.

ex) n^2 + 2n -> O(n^2), 2n^4 + 3n -> O(n^4)

 

최선의 경우에는 어떤 알고리즘을 보여도 만족할 만한 결과를 얻을 수 있기 때문에

비교를 할 수가 없으며, 평균적인 상황의 경우도 어떠한 상황이 평균적인 것인지

정의하기 힘들기 때문이다.

 

 

 

 

참조)

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