[자료구조] 빅오 표기법(Big-O notation)이란?

 

 

빅 오 표기법(Big-O notation)의 정의

Big-O(또는 Big-Oh) notation은 알고리즘의 시간 복잡도를 나타내는 표기법이며, O(f(n))으로 나타낸다.

 

알고리즘의 시간 복잡도

알고리즘의 복잡도를 판단하는 척도로는 시간 복잡도와 공간 복잡도 두 가지가 있는데, 빅 오 표기법은 시간 복잡도를 다룬다. 

당연하게도 알고리즘은 연산이 많아질수록 그 속도가 오래 걸린다. 

따라서 시간 복잡도는 알고리즘 내 연산의 횟수와 관계가 있다. 

 

가령 아래의 코드를 보면, 바깥 루프의 1부터 n까지의 각 i에 대해서, 안쪽 루프를 i번씩 방문한다.

즉 i가 1일 때 1번, 2일 때 2번, 3일 때 3번...n일 때 n번 result++;를 방문하게 된다.

 

 

 

그런데 이 코드는  사실 루프 내에서 총 ∑i번이나 ++연산을 수행해야 하므로 굉장히 비효율적이다.

같은 내용을 수행하는 코드를 아래와 같이 작성하면 효율을 조금 늘려볼 수 있다. 

 

 

 

이제 루프 내부에서 연산을 n번 하는 코드로 발전했다.

여기에서 더 단순화시킬 수도 있다. 알다시피 1부터 n까지를 더하면 n(n+1)/2이다.

따라서 ∑i를 계산하는 코드라면 그냥 아래와 같이 나타내어도 된다.

 

 

 

이제 for문도 없고 한 번의 계산만으로 결과값을 도출해 낼 수 있게 되었다. 

시간 복잡도가 훨씬 간단한 알고리즘이다.

 

알고리즘을 작성하는 데에 있어서 중요한 부분이 이처럼 효율성을 증가시키는 것이다.

위 코드들은 n의 값이 작다면 사실 큰 차이가 없게 느껴지지만, n값이 커진다면 효율성의 차이가 커진다. 

첫 번째 코드는 n(n+1)/2번 계산을 하고, 두 번째 코드는 n번, 세 번째 코드는 1번 계산을 한다.

n값에 따른 처리 시간을 그래프로 그려 본다면 이렇다.

 

 

 

n의 값이 커짐에 따라 처리 속도가 크게 차이가 나는 것을 볼 수 있다.

 

여기에서 Big-O notation의 의미를 볼 수 있습니다. 맨 처음에 말했듯 Big-O notation은 시간 복잡도를 나타내는데, 

알고리즘 내에서 시간 복잡도라는 것은 'n값의 증가에 따라 처리 시간이 증가하는 정도'정도라고 생각해 볼 수 있다.

 

Big-O의 수학적 정의와 계산법

어떤 함수 f(n)의 Big-O notation이 O(g(n))라는 것은, 

n의 값이 일정 수준이 넘어가면(충분히 많은 아이템을 사용한다면)

그 이상의 어떤 n을 대입하여도 c*g(n)보다 결과값이 작은 상수 c가 존재한다는 뜻이다.

 

예를 들어, 어떤 함수 f(n)의 Big-O notation이 O(n)이라면, 특정 값보다 커지면 무한대까지 계속 f(n)이 c*n(c는 임의의 상수)보다 작다는 것이다. 

 

수학적으로는 아래와 같이 나타낼 수 있다.

 

 

 

 

 

알고리즘 내에서 시간 복잡도를 계산할 때에는 그 단위 연산의 횟수를 기준 함수로 한다.

이 때 단위 연산(primitive operation)이란, 정의, 단순계산, 비교, 출력 등의 가장 간단한 연산들을 말한다. 

 

다시 위의 세 알고리즘을 살펴보면,

첫 번째 코드는 정의 1번, 계산 n(n+1)/2번, 출력 1번 = 총 n(n+1)/2 + 2번의 연산을 한다.

두 번째 코드는 정의 1번, 계산 n번, 출력 1번 = 총 n + 2번의 연산을 한다.

마지막 코드는 정의 1번, 출력 1번 = 총 2번의 연산을 한다.

 

따라서 위의 각 알고리즘은 n(n+1)/2 + 2개, n+2개, 2개의 단위 연산을 한다고 볼 수 있다.

 

첫 알고리즘에서 단위 연산의 수를 T(n)이라고 할 때,

T(n) = n(n+1)/2 + 2이다. 

 

이제 빅오 표기법으로 나타내기 위해 적절한 g(n)과 c, 그리고 n0를 선택한다.

 

g(n)=n^2, c=1,  n0=3

 

이렇게 세 값을 선택하면, n0이상의 모든 수에 대해 c*n^2보다 T(n)의 값이 작다.

따라서 T(n) = O(n^2)이라고 나타낼 수 있다.

비슷하게 두번째 알고리즘은 O(n), 세 번째는 O(1)로 나타낼 수 있다.

 

잘 이해가 안 된다면 수학적인 계산법은 적당히 읽고 넘겨도 크게 문제가 되지는 않는다.

실제 알고리즘에서의 빅 오 표기는 이것보다는 포스팅 가장 끝에 있는 방법으로 간단하게 알아낸다.

 

Big-O의 표기법

위에 첫 알고리즘에서 'T(n)을 O(n^3) 또는 O(n^2+6n) 등으로 나타내면 안 되느냐' 하고 생각할 수 있겟지만, 

Big-O notation에 대해서는 표준적으로 아래와 같은 법칙들을 적용한다.

 

- f(n)이 n에 대한 d차식이면, f(n)은 O(n^d)이다.

- 가능한 가장 작은 notation을 사용하여야 한다. 

=> O(n^2)도 되고 O(n)도 된다면 가장 작은 O(n)을 사용

- 가능한 가장 간단한 표기를 사용하여야 한다. 

=> O(3n+4)도 되고 O(n)도 된다면 가장 간단한 O(n)을 사용

 

이러한 법칙들에 따라서 빅 오 표기법은,

O(1), O(logn), O(n), O(n^2), O(nlogn), O(n^3), O(2^n) 등으로 나누어 쓰게 되며,

시간 복잡도(알고리즘의 복잡도)를 비교하자면

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n)등의 순서로 복잡하다.

아무래도 같은 기능을 수행한다면 가능한 단순한 알고리즘이 가장 효율적인 알고리즘일 것이다.

 

특정 알고리즘의 시간 복잡도가 O(n)일 때, 일반적으로 '알고리즘의 런타임(runtime)이 O(n)이다', 

또는 '알고리즘의 시간 복잡도(time complexity)가 O(n)이다' 등으로 말한다.

 

알고리즘 내에서 간단하게 Big-O 계산하기

사실 일일이 primitive operation을 세는 것은 의미가 없다.

루프 밖에 있는 단순 연산들은 결국 상수항이라 제외되고,

루프 안에 여러 개의 연산이 있다고 하더라도 가장 큰 차수 외에는 각 항의 계수를 포함한 모든 것들이 무시되기 때문에

루프와 recursion 횟수만 확인하면 된다.

 

가령 n에 관련된 for loop가 두 번 있다면 n에 대한 1차식 두 개를 곱하므로,

연산의 개수에 대한 식은 n에 대한 2차식이 되고, 이는 O(n^2)이다. 

 

결국 알고리즘 내에서 Big-O notation은 루프의 차수(깊이)와 직결된다고 볼 수 있다. 

즉, n에 대한 loop가 1개라면 O(n), 두 개라면 O(n^2)이라고 할 수 있다.

 

* 그나마 눈여겨볼 만한 점은 위의 제1 알고리즘의 두 번째 루프에서 만약 j<i대신 j<m이 들어갔고 m이 아예 새로운 변수였다면, 

runtime은 O(n^2)이 아니라 O(m*n)이 된다는 것 정도이다.

 

​그리고 알고리즘 내에서 빅오 분석법을 사용할 때에는 worst-case를 가정한다.

즉, 가장 오래 걸릴 경우의 시간 복잡도를 표기한다는 것이다.

 

예를 들어, '1번째부터 n번째까지 있는 원소들 중 1번째부터 i번째까지를 바꾼다'라는 알고리즘이 있다고 하자.

그렇다면 총 연산의 횟수는 i번인데, 이 i는 1부터 n까지의 어떤 수라도 될 수 있다.

이 때 빅오 분석법을 쓰기 위해서 우리는 i가 n일 경우를 가정한다.

말이 복잡한데 간단하게 생가하면 n과 관련된 그 어떤 변수를 루프 안에 쓰더라도, 루프가 하나라면 O(n)으로 나타내면 된다는 것이다.

 

단, O(logn)이나 O(nlogn)과 같은 경우는 해당되는 알고리즘의 형태들이 조금 다른데, 

예시만 들자면 배열의 정렬(array sorting) 방법 중 힙소팅(heap sorting)과 같은 경우 O(nlogn)의 런타임으로 작동한다.

이후 여러 알고리즘들에 대해 포스팅하면서 각각의 런타임을 다룰 예정이다.

 

 

(이 글은 2017전에 네이버 블로그에서 포스팅했던 내용을 일부 수정해 이전한 내용입니다.)