코드를 효율적으로 짜려면?

코드가 효율적인가 비교할 때, 어떤 것을 척도로 계산하게 될까? 

먼저, 단순하게 코드를 돌렸을 때 걸리는 시간으로는 측정할 수 없다. 컴퓨터 사양에 따라서 같은 코드라도 돌아가는 속도가 다를 수 있기 때문이다. 또한 같은 사양의 컴퓨터라도 깔려있는 프로그램의 정도에 따라 속도는 다양하게 차이가 날 수 있다. 

보통 인풋 크기가 커질 수록 알고리즘의 소요 시간이 커진다. 인풋 데이터의 크기를 n이라고 하면, n이 매우 큰 수라고 가정한다. 왜냐하면, n이 작을 경우에는 알고리즘

이 나쁘든 좋든 사용자가 크게 느끼지 못한다. 그래서, 보통 알고리즘의 효율성을 평가하고자 할 경우, 우리의 알고리즘이 취급하는 데이터가 상당히 크다고 가정한다. 또한, n이 커져나갈 수록 알고리즘의 시간이 어떻게 변화하는가를 통해서 알고리즘의 효율성을 평가하고자 하였다. 이때, n이 증가할 때마다의 늘어나는 시간에 대한 값이 중요한 평가 요소가 된다. 어떤 알고리즘은 기하급수적으로 늘어날 수도 있고, 어떤 알고리즘은 미미한 수준으로 변동이 없을 수도 있다. 

데이터 사이언티스트들은 알고리즘의 소요시간을 계산하기 위해서 '점근표기법(Big O notation)'를 이용해서 공통의 언어로 나타내고자 하였다. 점근표기법에 의하면, 인풋 데이터 형태의 가장 큰 차수, 계수를 무시한 형태가 소요 시간에 큰 영향을 미치게 된다. 

예를 들자면, 20n+40 을 표현하면 -> O(n) 

2n^2 + 8n + 157 을 표현하면 -> O(n^2)

5n^3+ 100n^2 + 75 -> O(n^3) 

그럼 각 표기법에 따른, 걸리는 소요 시간을 알아보도록 하자. 분석에서 많은 데이터 타입인 리스트로 생각해보자. 

인풋에 들어가는 리스트의 길이가 n이라고 할 때,

O(1)의 경우, n이 100 ->200 -> 1000 -> 10000으로 증가해도 그 소요 시간이 증가하지 않는다. 

이에 해당하는 경우로는, 리스트에 특정 요소값을 더하거나append(), 마지막 요소 값을 빼는 경우pop()에 해당한다.

O(n)의 경우, 늘어나는 만큼의 배수로 소요 시간이 증가한다. 즉, 특정 데이터의의 크기가 2배만큼 증가한다면, 시간은 2n이 된다.

자, 어떤 패턴이 이제 보일 것이다. O(n^2)의 경우? 

그렇다, n이 커질 수록 커진 만큼의 거듭제곱만큼이 시간이 증가하게 된다.

 

점근표기법으로 나타낸 시간 그래프이다.