알고리즘의 효율성(성능)을 따질 때 기준이 되는것은 보통 '수행시간'과 '저장공간'이 됩니다.
이번에는 '수행시간'의 관점에서 효율성을 판단할 때 사용되는 점근적 표기법에 대해서 알아봅시다.
알고리즘의 효율성을 따질 때 입력의 크기가 작으면 효율성에 상관 없이 금방 수행이 끝나기 때문에
효율성을 따질 때에는 '입력의 크기가 충분히 크다'라고 가정하고 판단합니다.
점근적 표기법은 '입력의 크기가 충분이 클 때' 변수가 커짐에 따라 함수가 증가하는 비율을 표현하는 방법입니다.
예를 들어 n+10000000이라는 함수와 n^2+1이라는 함수가 있다고 생각해봅시다.
n이 작을 때에는 왼쪽의 함수가 값이 더 크겠지만, 점근적 표기법에서의 '입력이 크기가 충분히 크다'라고 가정하고
생각해봤을 때 n이 당장 10000정도만 되도 오른쪽의 함수가 더 커지는 것을 알 수 있습니다.
n이 커질수록 그 차이는 더욱 극단적으로 벌어지게 되겠죠.
다른 예로 1000000n이라는 함수와 n^2라는 함수가 있다고 생각해봅시다.
이도 마찬가지로 n이 작을 땐 왼쪽이 더 값이 크지만, n이 커질수록 왼쪽과 오른쪽 함수의 차이가 점점 벌어집니다.
이렇듯 점근적 표기법에서는 충분한 크기의 입력이 들어왔다고 가정하기 때문에 상수항이나 변수의 계수에
초점을 두는것이 아니고 입력의 크기(변수)에 중점을 두고 생각합니다.
빅-오(Big-O)
Big-O표기법은 빅-오라고 부르며, 정의는 다음과 같습니다.
O(g(n)) = {f(n) | 모든 n >= n0(충분히 큰 모든 n)에 대하여 f(n <= cg(n)인 양의 상수 c와 n0가 존재한다.Big-O표기법은 해당 알고리즘 수행시간의 상한선을 의미합니다.
즉 이 알고리즘은 적어도 해당 함수보다 더 적은 수행시간을 가진다는 것을 의미합니다.
표기법은 O(n)와 같이 사용합니다.
예를 들어 Big-O(n)이라고 표기되어 있다면, 해당 알고리즘은
입력 n에 대하여 n보다 점근적으로 가파르지 않게 증가함을 의미합니다.
중요한 점은 Big-O표기는 엄밀한 상한이 될 수도 있고, 여유 있는 상한이 될 수도 있다는 것입니다.
예를 들어 n+2라는 함수가 있다고 생각해보고, 이제 이것을 Big-O표기법으로 바꾸어봅시다.
위에서 말한 정의에 부합하면 Big-O를 만족하는 것이 됩니다.
n+2 = O(n)이라고 한 번 가정해봅시다.
그리고 정의를 만족하도록 c = 5, n = 1이라고 대입해보도록 합시다.
n+2 <= n
= 1+2 <= 5*1
= 3 <= 5이렇게 위의 정의를 만족하기 때문에 n+2는 O(n)가 된다고 말할 수 있습니다.
그런데 여기서 과연 n+2를 O(n^2)라고 말할 수 있을까요?
대답은 당연히 가능합니다. 다시 한번 증명해보도록 할까요?
n+2 = O(n^2)
c = 1, n = 3
n+2 <= n^2
= 3+2 <= 3^2
= 5 <= 9이렇게 n^2또한 위의 정의를 만족합니다.
n^2가 이를 만족하는데 n^3, n^4등등... 그 위는 당연히 만족하겠죠?
때문에 Big-O표기법이 엄밀한 상한이 될 수도 있고, 여유 있는 상한이 될 수도 있다는겁니다.
뭐, 말은 이렇게 하지만 우리는 수행 시간을 통해 효율성을 판단해야 하기 때문에 엄밀한 상한을 정해야 하겠죠?
몇 가지 문제를 풀면서 Big-O표기법에 익숙해지도록 합시다.
1. 3n^2 = O(n^2)임을 증명하라
2. 2n+3 = O(n)임을 증명하라
3. n^2/3+10 = O(n^2)임을 증명하라