Big-O 표기법

Big - O?

• 알고리즘의 성능을 수학적으로 표현해주는 표기법
• 시간 복잡도와 공간 복잡도를 표현할 수 있음
• 데이터나 사용자의 증가율에 따른 알고리즘의 성능을 예측하는 것이 목표

 

시간 복잡도 = 얼마나 시간이 오래 걸리는지

공간 복잡도 = 얼마나 메모리는 차지하는지

 

Big - O 표기법의 성능

 

1. O(1)
2. O(log n)
3. O(n)
4. O(n log n)
5. O(n²)
6. O(n³)
7. O(2n)
8. O(n!)

1~8까지 데이터의 증가에 따른 수행시간 비교하였습니다. 아래 내용은 해당 영상을 참고하여 정리하였습니다.

 

O(1) // constant time

 

입력 데이터의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘을 표현할 때 사용합니다. n개의 데이터가 얼마나 큰지와 상관없이 언제나 일정한 속도로 결과를 반환합니다. 위의 그래프와 같이 가로축이 데이터의 크기고 세로축이 처리시간이라고 할 때, 데이터가 증가함에 따라 성능의 변화가 없습니다.

 

O(n) // linear time

 

입력 데이터의 크기와 비례해서 처리시간이 걸리는 알고리즘을 표현할 때 사용합니다. n개의 테이터를 받으면 n번 루프를 돌읍니다. n이 하나가 늘어날 때 마다 처리가 하나씩 늘어나서 n의 크기의 만큼 처리시간이 걸리게 됩니다. 데이터와 시간이 같은 비율로 증가하기 때문에, 그래프는 위와 같이 직선으로 표현됩니다.

 

O(n²) // quadratic time

 

n개의 데이터를 돌면서 그 안에서 n으로 루프를 또 돌릴 때 n²가 됩니다. 처음에는 조금씩 상승하다 데이터가 증가할 수 록 그래프가 수직 상승합니다.

 

위와같이 n개의 데이터를 받으면 첫번째 루프에서 n번 돌면서, 각각의 엘리먼트에서 n번씩 또 돌읍니다. 처리 횟수가 n을 가로 세로 길이로 가지는 면적만큼 된다고 볼 수 있습니다. n이 1개씩 증가할 때 마다 가로 한줄, 세로 한줄이 1개씩 증가하니 데이터가 커질수록 처리시간의 부담도 증가합니다.

 

O(nm) // quadratic time

 

 

nm도 n²와 마찮가지로 데이터가 증가할수록 그래프가 점점 수직에 가까운 모양이 됩니다. 위의 n²과 유사하나 n을 n번큼 돌리는 것이 아니라, n개의 데이터를 m만큼 돌리는 것 입니다. 

 

 

n은 엄청 크고 m은 작을 수 있기 때문에 Big - O 표기법에도 다르게 표기해줘야합니다.

 

O(n³) // Polynomial / cubic time

 

n³는 n²과 비슷한 그래프 모양을 보이지만, 데이터가 증가할 때 마다 가로 x 세로 x 높이까지 증가하니, 데이터가 증가함에 따라 더 급격하게 처리 시간이 늘어납니다.

 

n²에 n을 한번 더 돌리면 n³이 됩니다. n을 가지고 루프를 3중으로 돌린 것 입니다. O(n)은 가로만 있는 직선이고 O(n²)은 가로 세로가 있는 면적이라고 하면, n³은 n²을 n만큼 더 돌리니 큐빅 형태로 표현할 수 있습니다.

 

O(2n) // exponential time

 

O(2n)은 n²이나 n³보다 데이터가 증가함에 따라 늘어나는 시간이 더 급격하게 증가함을 볼 수 있습니다. 데이터가 늘어날 때 마다 아래와같이 증가하기 때문입니다.

 

 

매번 함수가 호출될 때 마다 2번씩 호출을 합니다. 2번씩 호출된 트리 모양의 구조를 트리 모양의 높이 만큼 반복합니다. 피보나치의 개념 떠오르시면 이해할 수 있습니다.

 

 

n²과 2n은 헷갈리게 생겼는데 둘은 상이한 알고리즘입니다. 피보나치 수열에 대해 설명드리겠습니다. 피보니치 수열은 n-2번째와 n-1번째 숫자를 더합니다. 3번째 값은 0과 1을 더한 1이고 4번째값은 1과 1을 더한 2입니다. 5번째는 1과 2를더한 5 이런식으로 진행이 됩니다. (0, 1, 1, 2, 3, 5, 8, 13, 21...)

 

위와같이 그림으로 직관적으로 이해하자면, 1부터 시작해서 한 면을 기준으로 정사각형을 만드는 것입니다. 1과 1이 붙어서 직사각형이 됩니다. 큰 면이 2임으로 2를 기준으로 정사각형을 하나 더 붙여줍니다. 그러면 늘어난 면이 3이되는데 또 그 면을 기준으로 정사각형 3을 만들어주고, 늘어난 5의 면을 기준으로 5를 만들어주고, 늘어난 8을 또 붙여줍니다. 

 

위와같이 기하학의 황금비율, 피보나치의 나선형이 그려지게 됩니다.

 

O(log n) // binary search

 

 

log n은 한번 검색할 때 마다 데이터의 절반은 검색 영역에서 제외시키기 때문에 순차 검색에 비교해서 속도가 현저하게 빠릅니다. 위의 그래프를 보면 O(log n)이 O(n)보다도 훨씬 적은시간에 많은 데이터를 처리할 수 있습니다. 데이터의 절반을 검색 영역에서 제외한다는 말이 이해가 어려울 수 있는데 아래 내용을 보시면 이해할 수 있습니다.

 

 

log n의 대표적인 알고리즘은 2진 검색입니다. 위와같이 정렬된 배열 안에서 key값인 6을 찾는다고 가정합니다. 정렬이 된 배열 안에서 2진검색을 하려면 우선 가운데 값을 찾아서 키값과 비교합니다. 가운데 값인 5보다 key값인 6이 더 크니까 6~9사이에 있는 데이터 안에서 찾으면 됩니다. 그러면 앞에있는 데이터인 1~5안에서는 찾지 않습니다. 6~9사이에 있는 데이터 중에서 다시 중간값을 찾아서 key값과 비교합니다. 한번씩 검색할때마다 검색해야 하는 데이터의 양이 절반씩 줄게 됩니다.

 

 

여기까지 Big - O 표기법의 몇가지 대표되는 알고리즘에 대해 알아보았습니다. Big - O표기법에서 중요한 것 한가지를 짚고 마무리하겠습니다. Big - O에서 상수는 과감하게 버립니다. 실제 알고리즘의 러닝타임을 측정하기 위해 만들어진 것이 아니라, 장기적으로 데이터가 증가함에 따른 처리시간의 증가율을 예측하기 위해서 만들어진 표기법이기 때문입니다. O(2n) => O(n)으로 표기합니다. ( O(2n²) => O(n²)  2n² 제곱도 상수를 버리는 것이 동일합니다.) 상수는 고정된 숫자니까, 증가율에 영향을 미칠 때 언제나 고정된 상수 만큼씩만 영향을 미치기 때문에, 증가하지 않는 숫자는 신경쓰지 않는 것 입니다.