빅 오 표기법(Big-O Notation), 알고리즘의 효율을 알려줘

컴퓨터 프로그램을 만들 때 가장 중요한 것은 2가지이다. 얼마나 빠른가 와 얼마나 적은 공간을 차지하는가. 아무리 좋은 프로그램이라도 너무 느리면 소용이 없고, 아무리 좋은 프로그램이라도 너무 크면 소용이 없다. 게임이 아무리 재밌어도 한 번 키는데 1시간이 걸리고, 용량이 2TB라고 해 보자. 그 게임을 사용할 사람은 없을 것이다. 이런 극단적인 예시가 아니라도, 프로그램을 최대한 빠르고 용량을 적게 차지하게 하는 건 중요하다. 이런 효율을 측정해 주는 방법 중 하나가 바로 빅 오 표기법이다.

 

---

Big-O가 뭘까?

Big-O 표기법은, 쉽게 말해 컴퓨터 프로그램의 효율성을 최악을 가장하고 측정해 주는 것이다. BIg-O 표기법에서는, 데이터가 말도 안 되게 커질때의 효율을 측정한다. 사실, 데이터가 적으면 어떤 알고리즘을 쓰던 효율에 크게 차이가 없다. 알고리즘이 의미가 있을 때는 데이터가 점점 커질 때이기 때문에, Big-O가 효율성을 측정하는데 자주 씌는 것이다.

 

프로그램의 효율성을 측정하는 방법은 크게 빅오, 빅오메가, 빅 세타가 있는데, 각각의 특징은 다음과 같다.

 

	Big-O(빅오)	Big-Ω(빅오메가)	Big-Θ(빅세타)
기준	상한선	하한선	상한선과 하한선 사이

 

Big-O는 흔히 O(n), O(log n)과 같이 나타내는데, O 안에 있는 공식이 함수의 형태와 같기 때문에 그래프로 직관적으로 복잡도를 표시하는 경우가 많다.

 

 

위의 그래프와 같이 복잡도를 표시할 때는, x 축이 데이터의 크기이고, y 축이 데이터를 처리하는데 걸리는 시간이다. 즉, 이 그래프는, 데이터가 늘어나면 비슷한 비율로 처리하는 시간도 늘어난다는 뜻이다. 예를 들어, 10개의 데이터를 처리하는데 걸리는 시간이 10초라면, 100개의 데이터를 처리하는 데는 100초가 걸리는 식이다.

---

Big-O 법칙

Big-O 표기법은 데이터가 엄청 클 때를 가정하고 있기 때문에, 사소한 영향은 무시하고 최대한 간단히 나타내는 경향이 있다. 물론, 이는 모두 엄밀한 수학적 정의에 의해 유도된 것이지만, 실제로 Big-O 표기법을 사용할때는 다음과 같은 2가지 법칙만 알아도 크게 상관없다.

 

1. 상수 무시

Big-O 에서는 상수는 기본적으로 무시한다. 따라서, 아래와 같은 공식이 성립한다.

 

O(n + c) = O(n)

O(cn) = O(n)

 

이런 공식이 성립하는 이유는 아래의 그래프를 보면 알 수 있다.

 

 

위의 그래프에서 데이터가 작을 때는 시간 차이가 꽤 나지만, 데이터가 커지면 커질수록 상수항의 사소한 시간 차이는 의미가 없어진다. 예를 들어, 데이터가 1일 때는 시간 차이가 1초와 1.2초지만, 데이터가 100일 때는 100초와 100.2초이다. 1초가 걸릴 때는 1초와 1.2초는 무려 20%나 시간이 더 걸리는 것이지만, 100초가 걸릴 때는 100.2초는 0.002% 정도만 더 걸릴 뿐이다. 이는 무시해도 될만한 차이이다.

 

2. 지배적인 변수만 고려

비슷한 이유로, Big-O 표기법에서는 지배적인 변수만 고려한다. 아래와 같은 예를 보면, n^2항 외에도 n항이 있지만, n항이 미치는 영향은 적기 때문에 무시한다.

 

O(n^2 + n) = O(n^2)

 

---

가장 흔한 Big-O

Big-O 표기법은, 정말 다양한 형태가 있을 수 있지만, 대표적으로 씌이는 것은 다음과 같다. 위에서도 언급했다시피, x 축은 데이터의 개수이고, y 축은 복잡도이기 때문에, x 축이 커질수록 y 축도 커지면 안 좋은 알고리즘이고, x 축이 커져도 y 축이 조금만 커 질수록 좋은 알고리즘이다.

 

O(1)

 

O(log(n))

O(n)

O(n log(n))

O(n^2)

O(n^3)

 

위의 그래프를 보면 어느정도 유추할 수 있듯이, 가장 선호되는 효율성은 아래와 같다.

O(1) < O( log n) < O(n) < O(n log n) < O(n^2) < O(n^3)

이를 아래와 같이 한 그래프에 나타내면 다음과 같다.

 

---

Big-O 예시

Big O 표기법은 컴퓨터가 코드를 실행할 때의 효율성을 측정하는 것이기 때문에 코딩을 할 때 쓰는 다양한 문법들도 각자 효율성이 있다. 그중 가장 대표적인 것들을 알아보자.

 

1. 기본적인 연산

덧셈, 뺄셈, 곱셈, 나눗셈 비교 등의 기본적인 연산은 모두 O(1)이다. 이런 연산은 데이터가 커진다고 딱히 해야할 연산도 많아지지는 않기 때문이다.

2. if 문

if 문의 복잡도도 O(1)이다. if 문의 본질은 사실 비교 연산자이기 때문에, if 문이 O(1)인건 어쩌면 당연해 보인다.

3. for 루프

for 루프의 복잡도는 O(n)이다. for 루프는 데이터를 처음부터 끝까지 훑는 것이기 때문에, 데이터가 많아질수록 시간이 오래 걸린다. 특이한 것은, for 루프는 안에 어떤 복잡도를 가진 코드가 있느냐에 따라 복잡도가 달라진다. 예를 들어, for 루프 안에 또 다른 for 루프가 있을 경우 for 루프는 각 데이터마다 for 루프를 돌아야 한다. 첫 번째 for 루프에서도 O(n)을, 두 번째 for 루프에서도 O(n)을 즉, O(n)을 n번 돌아야 하기 때문에 for 루프 안의 for 루프의 복잡도는 O(n * n), 즉 O(n^2)이 된다.

 

for i in data:
    for j in data:
        print("Hello")

---

유명한 알고리즘의 복잡도

알고리즘을 처음 배울때 가장 먼저 배우는 정렬과 탐색 알고리즘 일부의 시간 복잡도는 아래와 같다. 

 

알고리즘 이름	최선	평균	최악
퀵 정렬	O(n log n)	O(n log n)	O(n^2)
삽입 정렬	O(n)	O(n^2)	O(n^2)
선택 정렬	O(n^2)	O(n^2)	O(n^2)
거품 정렬	O(n)	O(n^2)	O(n^2)
선형 탐색	O(1)	O(n)	O(n)
이진 탐색	O(1)	O(log n)	O(log n)
해시 탐색	O(1)	O(1)	O(n)

 

알고리즘의 복잡도를 알아내는 방법은, 알고리즘을 구현한 코드를 보고 Big-O 표기법에서 예시로 든 복잡도를 적용시키는 방법이 대표적이다. 예를 들어, 선형 탐색은 처음부터 차례대로 찾고자 하는 데이터가 나올 때까지 검색하고 찾고자 하는 데이터가 나오거나 끝까지 모두 검색하면 끝나는 코드이다. 이를 간단히 구현해 보면 다음과 같다.

 

func linear_search(data, target):
    for i in data:
        if i is target:
        	return true
    return false

 

위의 코드를 분석해보면 다음과 같다. 우선, for 루프를 썼으니 기본적으로 O(n)이 됐다. 그리고, for 루프 안에 있는 코드는 곱하기로 처리되기 때문에 if 문의 효율성을 O(n)에 곱하면 된다. if 문은 O(1) 이기 때문에 위의 코드는 O(1 * n)이 되고, 이는 O(n)과 같다.  그렇기 때문에 선형 탐색의 시간 복잡도는 O(n)이다.

 

나머지 알고리즘도 이런식으로 분석할 수 있다. 더 자세한 건 알고리즘을 다룬 여기서(예정) 찾아볼 수 있다.

---