자료구조 & 알고리즘, 첫 강좌는 빅오 표기법 (Big-O Notation)으로 시작하려한다.
알고리즘은 수많은 방식으로 전개되고, 수많은 종류의 자원(ex: 시간, 메모리)를 요구한다.
예를 들어, 다음 곱셈을 할 때의 알고리즘을 생각해보자.
곱셈을 할 때에는, 두 수의 각 자리수를 분리하여 각각 곱한 후 더하게 된다.
1000*40+1000*5+0*40+0*5+0*40+0*5+0*40+0*5 로 계산하여 45000이라는 결과를 얻어낸다는 얘기다.
여기서는 1000이 네 자리 수, 45가 두 자리 수이므로 곱셈을 총 4*2=8번하였다.
또 하나의 예시를 살펴보자.
이 예시에서는 총 몇 번의 곱셈을 해야할까?
그렇다. 163이 세 자리 수이고, 2가 한 자리 수 이므로 3*1=3번 곱셈을 한 셈이다.
그렇다면, 이번엔 살짝 일반화해보자.
1이 n번 이어지는 수와 2가 m번 이어지는 수를 곱할때, 곱셈은 총 몇 번을 해야할까?
이런 질문들에서 나온 것이 "점근 표기법"이다.
어떤 알고리즘이 입력(혹은 주변 환경)에 따라 대강 얼마나 연산을 하는지를 예측하는 척도를 나타낸다.
점근 표기법에는 크게
1. 빅오 표기법
2. 빅세타 표기법
3. 빅오메가 표기법
으로 세 가지가 있지만, 본 글에서는 가장 많이 쓰이는 1번 빅오 표기법만 알아보도록 한다.
빅오 표기법은 상한 점근에 관한 표기법이다.
상한 점근이 무엇인지 갸웃하고 있을 지도 모르겠다.
어떤 함수 f(x)가 충분히 큰 모든 x에 대해 C*g(x)보다 작을 때, g(x)를 f(x)의 상한 점근이라고 한다.
(C는 상수)
잘 이해가 되지 않을 듯하여, 한 가지 예시를 들고 왔다.
첫 번째, f(x)=3x^2+5x-7의 상한 점근을 알아보자.
충분히 큰 수 x에 대해, x^4>x^3이다.
따라서 3x^2+5x+7<3x^2+5x^2+7x^2=15x^2이므로 f(x)는 O(x^2)이 된다.
수식으로 알아보면 어렵게 느껴질 수 있겠다는 생각이 든다.
간편히 말해서 f(x)=O(g(x))에서 g(x)는 f(x)의 최고차항이 된다고 생각하면 된다.
3x^2=O(x^2)이 되고, 3n!=O(n!)이 된다는 얘기다.
어려울 수 있지만 앞으로 알고리즘과 자료구조를 하나하나 익히다 보면 어느새 빅오 표기법이 몸에 익어 있으리라 필자는 확신한다. 걱정 말고 앞으로의 강좌를 계속해서 이어나가도록 하자.