O(log n) 시간 복잡도란 무엇인가?

시간 복잡도란 무엇인가?

시간 복잡도는 입력(n)을 기반으로 알고리즘이 실행(O)되는 데 걸리는 시간을 설명한다.

시간 복잡도는 꽤나 직관적이다.

 

예를 들어서 O(1)의 시간 복잡도를 가지는 알고리즘이 있다면 이는 입력에 상관없이 실행하는데 항상 동일한 양의 시간이 걸린다. O(n)의 시간 복잡도를 가지는 알고리즘이라면 입력값이 커지면 커질수록 시간도 그에 맞춰서 일정한 속도(선형 진행)로 커진다는 것을 의미한다. O(n^2)의 시간 복잡도를 가지는 알고리즘이라면 입력값이 커지면 커질수록 걸리는 시간이 기하급수적으로 증가할 것이다.

 

빅-오(Big-O) 표기법

 

Log(logarithm)란 무엇인가?

로그란 간단하게 말하자면 지수를 다른 방법으로 표현한 것이다.

(*로그에 대해서는 아래의 글을 참고해 주길 바란다.)

 

로그(log)란 무엇인가?

 

코드로 표현하기

코드를 작성할 때 로그를 어떻게 사용할 수 있을까?

가장 일반적인 O(log n)의 시간 복잡도를 가지는 알고리즘 중 하나인 이진 탐색(binary search)을 살펴보도록 하자.

기본적으로 해당 알고리즘은 정렬된 배열을 절반씩 나누면서 원하는 값을 찾아나간다.

 

def binary_search(list1, low, high, n):
   if low <= high:
   mid = (low + high) // 2
   if list1[mid] == n:
      return mid
   elif list1[mid] > n:
      return binary_search(list1, low, mid — 1, n)
   else:
      return binary_search(list1, mid + 1, high, n)
   else:
      return -1

 

 

우리는 해당 배열에서 12를 찾아야 한다.

 

[1, 3, 5, 8, 12, 13, 15, 16, 18, 20, 22, 30, 40, 50, 55, 67]

 

일단은 배열의 가운데부터 시작해 보도록 하자. 이 경우 가운데는 index 7번이다. index 7번은 16의 값을 가지고 있다. 16은 우리가 찾는 값 12보다 크기 때문에 0 - 6까지의 배열만 남기고 모두 버린다.

 

[1, 3, 5, 8, 12, 13, 15, 16, 18, 20, 22, 30, 40, 50, 55, 67]

 

이제 남은 배열의 가운데인 index 3의 값을 가져온다. index 3의 값은 8이다. 8은 12보다 작기 때문에 4 - 6까지의 배열만 남기고 모두 버린다.

 

[1, 3, 5, 8, 12, 13, 15, 16, 18, 20, 22, 30, 40, 50, 55, 67]

 

남은 배열의 가운데인 index 5의 값을 가져온다. 13은 12보다 크므로 우리가 원하는 값인 index 4를 찾을 수 있다.

 

[1, 3, 5, 8, 12, 13, 15, 16, 18, 20, 22, 30, 40, 50, 55, 67]

 

index 4는 우리가 찾고 있던 값을 가지고 있고 알고리즘은 완료되었다.

 

이 전체 프로세스는 16개의 요소의 배열에 대한 4번의 작업이 필요했다. 이를 대수적으로 표현하면 다음과 같다.

 

16 * (1/2)^4 = 1

 

16개의 요소가 있고 각 반복은 그 숫자를 반으로 나누거나 1/2를 곱하기 때문이다. 이 모든 것은 결국 1개의 요소를 얻기 위해 총 4번 발생했다. 그렇다면 우리는 이를 어떻게 시간복잡도로 표현할 수 있을까?

 

우선 n 은 알고리즘에 주어지는 입력값이다. 그리고 위의 경우에 대입해 보면 16개의 요소가 n에 해당하게 된다.

16을 n으로 바꿔보자.

 

n * (1/2)^4 = 1

 

그리고 x는 밑을 올리는 지수로 표현된다. 이 경우에는 반복되는 4의 값이 x에 해당한다.

 

n * (1/2)^x = 1

 

괄호를 정리하면 이렇게 정리가 가능하다.

 

n * 1/2^x = 1

 

n * 1 은 n과 같다.

 

n/2^x = 1

 

양변에 2^x를 곱해준다.

 

2^x * n/2^x = 2^x

 

결과적으로 

 

n = 2^x

 

다시 이를 로그로 표현하면 다음과 같다.

 

(n = 2^x or 2^x = n) = (x = log_2 n)

 

그러므로 우리는 이진 탐색트리의 시간 복잡도가 O(log_2 n) 임을 증명하였다. 다른 알고리즘과 시간 복잡도를 비교할 때 밑은 중요하지 않아서 보통의 경우는 O(log n)로 표현을 대신한다.

 

정리하면

알고리즘에 대해서 공부하다 보면 여러 시간 복잡도를 가진 알고리즘에 대해서 공부하는데 단순히 이 알고리즘은 O(n)의 시간복잡도를 가지고 있다고 외우는 게 아니라 이렇게 직접 유도해 보면 기억에도 더 남고 면접에서도 할 이야기가 생길 거 같다는 생각이 들었다.

 

출처

So what is O(log n) Time Complexity Anyway?