시간 복잡도와 빅 오 표기법 공부 - O(n), O(1), O(n^2), O(log n)에 대하여

계산 복잡도와 시간 복잡도: 어떤 알고리즘이 문제를 풀기 위해 해야하는 계산이 얼마나 복잡한지를 나타낸 정도를 '계산 복잡도'라고 한다. 계산 복잡도는 '시간 복잡도'와 '공간 복잡도'로 나눌 수 있다. 

 

빅 오 표기법: 계산 복잡도를 표현하는 방법에는 여러가지가 있는데, 그 중 '빅 오 표기법'을 주로 사용한다. 

 

이 글에선 시간복잡도와 빅 오 표기법을 공부할 예정이다.

 

 

알고리즘이 빠르다, 느리다는 시간으로 표현하지 않는다. 다시말해, 초, 분, 시간으로 표현하지 않는다는 말이다. 왜나하면 같은 알고리즘이라도 하드웨어의 차이로 인해 수행시간이 달라지기 때문이다. 문서 작업용 노트북의 처리속도와 게이밍 컴퓨터의 처리속도가 같을 수는 없다.

 

따라서 알고리즘의 스피드는 곧 '알고리즘이 완료까지 걸리는 절차의 수'를 의미한다.

 

 

첫 번째로 O(n)에 대해 알아보자. 이는 문제를 해결하기 위한 단계의 수와 입력값n이 1 : 1관계를 가진다는 것을 의미한다. 예를 들어 for문을 이용한 '1부터 n까지의 합을 구하는 함수'가 있다고 해보자. 이 함수는 n의 값으로 100을 집어넣는다면 for문이 100번 돌면서 한번 돌때마다 합계인 sum변수에 1을 더하는 구조일 것이다.

 

그렇다면 이 함수는 입력값, 입력 크기 n에 대해서 덧셈을 n번 해야한다. 이때 필요한 계산 횟수가 입력 크기에 '정비례'하는데 이를 O(n)이라고 표현한다.

 

이제 만약에 함수에 for문이 두개 있다고 가정해보자. 방금 전 가정한 함수보다 절차가 두 배로 늘어버렸다. 입력 크기와 단계가 1:1인 상황에서 1:2인 상황이 되어버렸다. 이럴때는 이론적으로는 O(2n)을 써야하나 과연 그럴까? 그렇지 않다. 빅 오 표기법은 디테일엔 관심이 없다. 빅 오 표기법은 알고리즘에서 필요한 계산 횟수를 정확한 숫자로 표현하는 것이 아니라, 입력 크기와 계산 횟수간의 관계를 표현한다.

 

중요한 것은 이 함수가 인풋의 크기에 따라서 어떻게 작동하는지 대략 파악하는 것이다. O(n)이든 O(2n)이든 의미하는 바는 똑같다. 입력값과 알고리즘의 절차의 수가 정비례한다는 것이다. 

 

이를 '선형 시간'이라고 표현하기도 한다.

 

 

두 번째로 O(1)에 대해 알아보자. O(1)의 의미는 입력값의 크기와 상관없이 끝내는데 동일한 숫자의 절차가 필요한 알고리즘을 의미한다.

 

예를 들어 '1부터 n까지의 합을 구하는 함수'를 가우스 공식을 이용해서 만든다면 절차는 'return n * (n + 1) // 2' 한 단계만 존재할 것이다. 입력값n의 크기가 10이든 100이든 한 단계의 절차만 거쳐서 결과를 도출할 것이다.

 

그렇다면 만약 함수가 거치는 절차가 2개라면 어떻게 될까? O(2)가 될까?

 

아니, 그렇지 않다. 여전히 O(1)으로 표시한다. 상술했듯이 빅 오 표기법은 입력 크기와 계산 횟수간의 관계를 표현한다. O(1)이 주목하는 점은 입력 크기n과 필요한 계산 횟수가 무관하다는 점이다. 즉, 입력크기가 커져도 계산 시간이 더 늘어나지 않는다면 모두 O(1)로 표기한다.

 

이를 '상수 시간'이라고 표현하기도 한다.

 

O(n)과 비교하면, 입력 크기가 큰 문제를 풀 때는 보통 O(1)인 알고리즘이 훨씬 더 빠를것이다.

 

 

세 번째로 O(n^2)에 대해 알아보자. O(n^2)는 문제를 해결하기 위한 단계의 수가 입력값n의 제곱이라는 의미를 가진다. 입력값n이 10이라면 100개의 단계가 필요하다는 말이다.

 

보통 반복문 안에 반복문이 있는 경우, 예를 들자면 for문 안에 for문이 들어있는 상황일 때 그렇다. 예를 들어 입력값n만큼 반복하는 반복문의 안에 똑같이 n만큼 반복하는 반복문이 있다고 해보자. 10개의 데이터는 100개의 단계가 되고 20개의 데이터는 400개의 단계가 되는 것이다.

 

O(n)과 비교하면 O(n)이 더 효율적이라고 평가받고 선호된다.

 

이를 '2차 시간'이라고 표현하기도 한다.

 

 

마지막으로 O(log n)에 대해 알아보자. O(log n)은 이진검색 알고리즘을 설명할 때 주로 쓰인다. O(log n)을 설명하기 위해 필요한 사전지식부터 먼저 간단히 설명하고 나서 O(log n)을 설명하려 한다.

 

O(log n)을 설명하기 이전에 먼저 이진검색을 간단히 알아보자. 이진검색 알고리즘에서 입력값n은 이진검색할 배열의 길이이다. 이진검색에서는 n이 10에서 20으로 두배가 늘어도 절차는 3단계에서 4단계로 1단계만 증가한다. 왜냐하면 이진검색은 각 단계마다 입력받은 배열을 중간점을 기준으로 절반으로 나눠서 검색하기 때문이다.

 

이진검색은 이렇게 입력받은 배열을 각 단계마다 반으로 나누면서 탐색하고, 검색 도중에 검색값을 찾지 못한다면 최후에 한 개의 배열이 남을 때까지 입력값을 반으로 나누며 검색을 진행한다.

 

로그에 대해서도 간단히 알아보자. 지수와 로그는 정반대이다. 먼저 지수에 대해서, '2^n = 32'일 때 'n'은 무엇일까?라는 문제는 본질적으로 '2를 몇번 곱해야 32가 될까?'를 묻는 문제이다.

 

그리고 반대로 'n = log 32'일 때 'n'은 무엇인가? (로그의 밑은 2이다)' 라는 문제는 본질적으로 '32를 몇번 나눠야 1이 될까?'를 묻는 문제이다. 정답은 n=5이다. 32 - 16 - 8 - 4 - 2 - 1. 총 5번의 단계를 거쳐서 32는 1이 된다.

 

다시 이진검색을 보자. 이진 검색은 매 단계마다 입력받은 배열을 중간을 기준으로 반으로 나누고 시작한다. 때문에 입력값이 두배가 되어도 단계는 1만 증가한다. 한번만 더 나누면 되니까. 정리하자면, 내가 하고싶은 말은 이진탐색과 log는 공통적으로 입력값 n을 반으로 나누고 나눠서 1로 만드는 절차를 가진다는 것이다. 때문에 주로 이진탐색과 같은 정렬 알고리즘의 속도를 O(log n)으로 표현한다. 원리가 같으니까.

 

O(log n)은 보통 정렬 알고리즘에서 많이 쓰이고 log의 밑은 표시하지 않는다. 보통 O(n)보단 빠르고 O(1)보단 느리다.

 

이 방식에 약점이 있다면 이진검색은 정렬되지 않은 배열에는 사용일 불가능하다는 점이다.

 

O(log n)을 '로그 시간'이라고 표현하기도 한다.