[Algorithm - Big O Notation] 연산 갯수 세기 및 시간 복잡도 시각화하기 (2/4)

연산 갯수 세기

코드가 실행될 때 걸리는 정확한 시간을 초로 측정하는 것보다는 컴퓨터가 처리하는 연산 갯수를 세면된다. 단순하게 만들어서 이 알고리즘은 실핼될때 연산은 5번해야하고 어떤 알고리즘은 7번해야 한다면, 컴퓨터의 사양과는 상관없이 시간은 항상 연산의 갯수에 달려 있을 것이다. 연산이 빠른편이었던 두번째 코드의 연산 갯수를 살펴보자. 

 

연산의 갯수 3개

 

 

 

곱하기, 더하기, 나누기 총 3개의 연산이 있는 것을 알 수 있다. n이 2든 1억이든 계산은 딱 3번만 이루어 진다. 이것을 첫번째 코드를 살펴보자.

 

 

 

for문안에 위치한 '+'는 루프문안에 있기 때문에 n이 5라면 연산이 5번 이루어지게 된다. n이 20이라면 20번 연산이 이루어진다. n이 1억이라면 1억의 연산이 생기게 된다. 여기에 '='도 연산자이기 때문에 더 추가된다. 또한, '++' 또한 더하기 1을 한다는 의미로 연산자이다. 이외에도 많은 연산자가 존재하게 된다. 만약, n이 10이라면 연산 50개에 for문 밖에 있는 2개를 더하여 총 52개의 연산을 하게된다.

 

중요한 것은 연산의 갯수를 일일이 세는 것이 아니라 전체적인 추세를 보는 것이다. 두번째 코드의 경우 n이 커질수록 연산의 갯수도 비례적으로 늘어난다. 

 

 

시간 복잡도 시각화하기

https://rithmschool.github.io/function-timer-demo/

Big O Introduction

 

상기 링크로 들어가면 함수를 실행하는데 얼마나 시간이 오래 걸리는지 보여주는 위젯이 있다. n의 값을 입력하고 Plot 버튼을 클릭하면 n이 커지면서 어떤 현상이 보이는지 확인할 수 있다.

 

두번째 코드- y축은 Microseconds이다.

 

 

첫번째 코드

 

첫번째와 두번째 코드 그래프 비교 (회색이 두번째 코드 그래프)

 

 

 

전체적인 추세를 보면 따라가기 쉬운 선이 하나 있다. 이는 n이 커질수록 시간이 비례하게 늘어 난다는 의미이다. 두번째 코드의 경우 n의 값이 얼마이든 연산의 갯수가 항상 동일하기 때문에 시간이 거의 똑같이 걸리게 된다. 위 아래로 조금의 변동 사항은 있었지만 큰 차이는 없었다.