O 표기법(Big - O Notation), 쎄타 표기법(Theta Notation), 오메가 표기법(Omega Notation)

Big - O Notation, 흔히 말하는 O표기법이란 최악, 최선의 성능중 최악의 성능에 해당한다. 최악의 성능을 평가하는 이유는 적어도 일정

정도의 성능은 보장한다는 의미이다. O 표기법은 알고리즘의 성능을 평가하기 위해 처리해야할 데이터의 양에 대한 실행시간을 수학적 

으로 계산한 방법이다시간 복잡도 함수에서 알고리즘 분석을 원활하게 하기 위해 시간 복잡도를 표기하는것을 Big -O

Notation이라고 한다.

다음과 같은 for문이 있다고 가정하자. 이 루프 제어문은 n개의 대입연산과, n+1번의 비교연산, n번의 덧셈 연산을 포함하여, 총 3n + 1

개의 연산이 생긴다. 추가적으로 루프문 내에서는 n번의 덧셈연산과, n번의 대입연산, 총 2n이 발생하여 해당 루프문은 최종적으로

5n+1 이라는 연산을 하게된다. 해당 루프문을 O표기법으로 나타내면 O(n)이 되는데, O표기법은 시간 복잡도에 기여하지 못하는 항을

생략하고 시간 복잡도를 표현하기 때문에, 기본 연산 횟수가 다항식 형태로 되어있는 경우, 해당 다항식의 최고차항만 남기고 다른 항, 

상수항을 버리게 된다. 즉 위의 식 5n + 1에서는 상수항 1을 버린 최고차항 5n만 고려하기 때문에 해당 루프문이 시간복잡도는 O(n)이

되는것이다.

O 표기법에는 다음과 같은 방법들이 존재한다.   해당 순서는 연산 수행 시간순과 동일하다

1)    O(1) : 이와 같은 성능을 갖는 알고리즘은 처리해야 할 데이터의 양과는 상관없이 항상 일정한 실행시간을 갖는 알고리즘을 의미한다.

ex) f(n) = 10

2)    O(log2N) : 이와 같은 성능을 갖는 알고리즘은 처리해야 할 데이터의 양이 증가할수록 실행 시간도 약간씩 증가하는 알고리즘을 의미한다. 실행 시간의 증가폭 자체가 logN의 그래프를 가지므로 급격하게 증가하지는 않는다. 일반적으로 효율이 좋은 검색 알고리즘의 성능이 이에 해당된다.

3)    O(N) : 이와 같은 성능을 갖는 알고리즘은 처리해야할 데이터의 양과 비례하여 실행시간도 증가하는 경우이다(ex : for문)

ex) f(n) = 99n +100

4)    O(NlogN) 처리해야할 데이터의 양에 비해 정비례보다 약간 더 증가하는 실행시간을 갖게된다. 일반적으로 효율이 좋은 정렬(sort)알고리즘의 성능이 이에 해당된다.

5)    O(N^2) : 이와 같은 알고리즘은 2중 반복문을 의미한다(중첩 for문)
이와 같은 알고리즘은 처리해야할 양이 증가하면 증가할수록 데이터의 제곱만큼의 실행시간이 소요되기 때문에 좋은 알고리즘은 아니다.

6)    O(N^3) : 이와 같은 알고리즘은 3중 반복문을 의미한다. 처리해야할 양이 세제곱만큼 증가한다(최악)

7)    O(2^n) : 이와 같은 알고리즘은 데이터의 증가에 따라 2의 n승만큼 실행 시간이 증가하는 알고리즘이다.(최악)

O표기법에는 다음과 같은 규칙들이 존재한다.

1 . 반복문은 최대 반복 횟수로 계산한다.

2 . 중첩된 반복문은 각각의 중첩문의 최대 반복횟수를 곱셈하여 계산한다.

-> 예를 들어 이중 for문이 있다고 가정을 하자.

이와 같이 2개의 for문이 중첩된 경우, 최대 반복 횟수를 곱하여, O표기법을 계산한다. 우선적으로 단일 for문의 경우에는 

최대 반복 횟수는 N이된다. 두번째 반복문도 단일 for문으로 보면 똑같이 최대 반복 횟수는 N이될것이다. 결론적으로 해당

이중 for문을 O표기법으로 표기하게 되면 O(N*N), 즉 O(N^2)가 되는것이다. 이를 응용하여 삼중 for문이 있다고 가정해

보자.

당연히 해당 for문도 각각의 for문 별로 최대 반복횟수는 N이 되기 때문에 최종적으로 O(N*N*N)이되어 O(N^3)이되는

것이다.

3 . 반복문이 떨어져 2개 이상이 잇는 경우에는 가장 큰 값으로 계산한다.

-> 다음과 같이 떨어져있는 for문 2개가 있다고 가정해보자.

우선적으로 위의 for문의 경우의 O표기법은  O(N)이 된다, 밑의 for문의 경우에는 O(N^2)가 된다. 여기서는 O(N^2)가 O(N)보다

큰 값이므로, 해당 문에서의 O표기법은 O(N^2)가 되는것이다.

      4 . if ~ else문은 알고리즘 성능에 영향을 미치지않는다.

5 . 재귀함수는 풀어서 계산한다.

-> 다음과 같은 팩토리얼을 구하는 재귀함수가 있다고 가정하자

우선 위의 규칙 4에서 if~else문은 알고리즘의 성능에 영향을 주지 않는다고 한것을 기억해야한다. 결론적으로 해당 함수에서 

봐야할것은 return iol * func(iol)부분인데, 해당 재귀 호출을 풀어쓰면 다음과 같다.

iol * func(iol -1) * func(iol -2) .......... * 1

이 되게 된다. 결론적으로 1부터 N까지의 곱셈이라는 소리가 되는데, 결론적으로 재귀호출은 N번 반복하게 되어 O표기법으로 

연산하게 되면 O(N^N)이 되는것이다.

지금부터는 O표기법을 수학적으로 접근하고, Omega Notation과 Theta Notation에 대해서도 살펴보자,

우선 O표기법부터 들어가보자. 만약 f(x)라는 함수와 g(x)라는 함수가 존재한다고 하자.

만약 g(x)의 함수에 임의의 상수 C를 곱한것에 대한 값이 f(x) 식보다 크거나 같다는 것이 참이 되면 f(x) = O(g(x))라는 식이 성립된다. 

기본적인 O표기법의 수학적 정의는 다음과 같다.

두 함수 f(x) g(x)가 있을때 모든 n>n0에 대해 |f(x)| <= c * |g(x)|를 만족하는 

2개의 상수 C와 n0가 있으면 f(n) = O(g(n))이 된다.

예시를 들어 해당 식을 증명해 보면 다음과 같다.

2x^2 + 1이라는 식을 가진 f(x)라는 함수와 x^2라는 식을 가진 g(x)라는 함수가 있다고 가정하자. 우선적으로 O표기법의 수학적 공식에

대입해 보면 2x^2+1 <= c * x^2 라는 등식으로 표현해 줄 수 있다. 우선적으로 상수 C의 값이 1일때는 당연히 안될것이고, 2일때는 f(x)

의 값에 +1이 붙게 되어 안되고, C값이 3일때는 우선적으로 크게 보면 참이라고 말할 수 있다. 하지만 O 표기법에 대한 수식은 최소한을

만족시키는 데이터의 값인 n0의 값과 상수값 두가지가 존재해야만 성립하기 때문에, n0값에 대한것도 구해주어야 한다.(표의 유도과정 

참고)

해당 두 함수 f(x) g(x)에 대한 O표기법의 결론을 내면 '상수 C의 값이 3이고, n의 값이 1보다 크거나 같을때 f(x) = O(g(x))가 성립한다고

할 수 있다.

이번에는 또다른 표기법 Big Omega라는 것에 대해 살펴보자. O표기법을 잘 이해했다면 Big Omega는 쉽다. 오메가 표기법은 그림을

보며 각자 해석해 보자.(오류 : 등호가 > 가 아닌 >= 입니다)

그 다음 세타 표기법(Big - Theta Notation)에 대해서는 이것만 기억하면 된다. 두 함수 f(x), g(x)에 대해 O표기법과 오메가 표기법에 대해

모두 참이 성립되면 두 함수는 세타 표기법에 대해 참이 성립되는 것이다.