JavaScript/Basic

[JS 알고리즘&자료구조] 시간 복잡도 시각화하기

발싸믹쏘스 2023. 10. 25. 00:25

걸리는 시간도 연산의 갯수보다도 큰 그림을 보는 것이 중요하다고 앞에서 얘기했으니 이제 큰 그림을 보는 시간을 가져보려고 한다. 아래의 홈페이지에 들어가면 앞에서 예시로 들었던 addUpToFirst와 addUpToSecond 함수를 실행시키고 해당 코드들이 결과값을 뱉기까지 얼마나 시간이 걸리는지 추세를 나타내준다. 

우선 addUpToFirst 함수의 추세선을 살펴보자.

입력되는 n의 값에 따라 시간이 기하급수적으로 느는 것을 확인할 수 있다. 앞의 장에서 봤듯이 해당 로직은 n의 숫자만큼 연산의 갯수가 늘어나기 때문에 당연히 시간도 늘어나는 것을 알 수 있다. 다음으로 addUpToSecond 함수의 추세선을 보자.

n의 값으로 어떤 것이 입력되도 해당 함수는 3개의 연산만을 실행하기 때문에 시간이 거의 늘어나지 않고 0에 수렴하는 것을 볼 수 있다. 

각각의 알고리즘이 n의 숫자에 따라 어떤 추세선을 가지는지 살펴볼 수 있었다. 이제 다음으로 마침내 Big O에 대해 제대로 파헤쳐볼 시간이다.