어떻게 어떤 알고리즘이 더 좋은 알고리즘인지 판별할 수 있을까?
만약에 나와 내 친구가 0부터 N까지의 합을 구하는 함수를 작성했다고 가정해보자. 과연 나와 내 친구가 짠 함수를 어떻게 비교할 수 있을까?
내가 짠 코드
친구가 짠 코드
그리고 이 둘의 실행시간을 비교해보자 n으로는 둘다 10000을 대입하였다.
친구가 짠 코드의 실행시간이 더 짧다는 걸 알 수 있다.
하지만 코드의 효율성을 측정하기 위해서 코드의 실행시간을 가지고 비교해보는 것은 그렇게 큰 의미가 없다. 컴퓨터의 하드웨어 성능에 따라서 결과값이 달라지기 때문이다. 그래서 우리는 객관적인 지표가 필요한데, 그때 사용되는 방법이 바로 Big O 이다.
Big O
Big O 는 함수의 인풋이 커져감에 따라서 코드의 실행시간이 얼마나 상대적으로 증가하는지를 나타낸다.
내가 짠 코드는 인풋의 값 n 이 증가하면 증가할수록 연산과정이 n+1 번임을 알 수 있다. 하지만 친구가 짠 코드는 n의 값이 아무리 증가하여도 연산과정이 변하지 않음을 알 수 있다.
내가 짠 코드는 O(n), 친구가 짠 코드는 O(0) 이다.
이로써 객관적으로 친구가 짠 코드가 더 효율적인 코드인게 증명이 된 셈이다.
