알고리즘의 속도 표기법 Big O

이 글은 전 글과 같이 유튜브 영상을 보고 작성한 글이다.

 

이번에는 어떻게 알고리즘의 속도를 전문적이고 CS적인 표현으로 나타내는지 공부해봤다.

 

알고리즘의 속도는 단순히 시간으로 표현하지 않는다.

그 이유는 각 하드웨어의 성능이 달라 실행 속도에 차이가 있을 것이기 때문이다.

 

따라서, 알고리즘의 속도는 완료까지 걸리는 절차의 수로 결정된다.

 

이전 글의 선형 검색을 예를 들어 보면, input size = N일 때 선형 검색 알고리즘은 N steps가 요구된다.

 

이 때, 선형 검색의 시간 복잡도는 O(N)을 갖는다고 한다.

 

이러한 표기 방식을 Big O notation이라고 한다.

 

또 다른 예를 들어 아래와 같은 파이썬 코드가 있다고 가정할 때,

def print_first(arr):
	print(arr[0])

배열의 크기에 상관없이 이 함수는 동일한 수의 스텝이 필요할 것이다.

 

그리고 이 함수의 시간 복잡도는 상수 시간(Constant Time)이라고 할 수 있다.

 

또, Big O 형식으로 표기하면 O(1)라고 표기한다.

 

만약, 여기에 같은 print문이 한 줄 더 있다고 해서 O(2)라고 표기할까??

 

이 질문에 대한 답은 NO이다. Big O 표기법은 input size에 따라 어떻게 이 함수가 작동하는지를 확인한다.

상수를 신경쓰지 않는다.

 

다른 시간복잡도로는 2차 시간(Quadratic Time)이 있다.

 

2차 시간은 중첩 반복(Nested Loops)이 있을 때 발생한다.

 

예를 들어, 아래와 같은 파이썬 코드가 있을 때,

def print_twice(arr):
	for n in arr:
    	for x in arr:
        	print(x, n)

배열의 각 아이템에 대해 루프를 반복해 실행한다.

 

따라서, 위 함수의 시간복잡도는 입력의 n^2이다.

 

input size가 10이라면, 함수는 100번의 절차가 필요할 것이다.

 

또 다른 시간복잡도로 로그 시간(Logarithmic Time)이 있다.

 

로그 시간은 이진 검색 알고리즘을 설명할 때 사용한다.

 

이전 글에서 설명한 이진 검색 알고리즘을 Big O notation으로 표기하면 O(log N)이 된다.

 

로그(Logarithm)는 지수(Exponent)의 정반대다.

 

지수는 곱해야 할 수를 얘기하지만 로그는 나눠야 할 수를 얘기한다.

 

따라서 입력이 2배가 되어도 검색을 위한 절차는 1만 증가했었다. 어차피 1번만 더 나누면 되기 때문이다.

 

이 때, Big O 표기법에서는 log의 밑 숫자는 쓰지 않는다.