시간 복잡도

시간 복잡도는 ‘문제를 해결하는데 걸리는 시간과 입력의 함수 관계’를 가리킨다.

• wikipidia

• 즉, 어떠한 알고리즘의 로직이 ‘얼마나 오랜 시간’이 걸리는지를 나타내는데 쓰이며, 보통 빅O 표기법으로 나타낸다.

빅오 표기법

Big-O 표기법은 상한 점근으로, 최악의 경우를 고려하는 표기법이다.

<aside> 💡 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마큼 걸리는가? 를 표기하는 방법

</aside>

• 즉, 입력 범위 n을 기준으로 해서 로직이 몇번 반복됬는지 나타내는 것이다.

시간 복잡도의 존재 이유

<aside> 💡 효율적인 코드로 개선하는데 쓰이는 척도가 되기 때문!

</aside>

위의 그래프를 보면, O($n^2$)의 시간 복잡도는 Elements 수가 증가할 수록, 시간이 엄청나게 증가하지만, O(n)은 그에 비해 그렇게 크게 증가하지 않는다.

→ 따라서 이것이 척도가 된다.

시간 복잡도 계산 방법

• 가장 영향을 많이 끼치는 항의 상수 인자를 빼고 나머지 항은 제거

Ex) $10n^2 + n$ ⇒ $n^2$