평균성능으로 해야한다고 한다. 왜냐하면, 일반적인 확률 원칙을 적용해야하기 때문이다.
그 대표적인 예로 Quick sort이며, 무작위 알고리즘으로, 평균성능(Average-case analysis)을 가지고 판단해야 한다고 한다.
Big O 표기법 기반으로 시간의 복잡도를 알수 있으며, 이에 관련된 기본 규칙이 존재한다.
를 표시를 해준다.
시간의 복잡도는 Big O 표기법 기준으로 나온 값을 말하며, Big O표기값과 동일하다고 생각하며 되겠다 하지만 아래와 같은 몇가지 규칙이 존재한다.
상위 표로 알수 있는 것은 O표기법의 시간의 복잡도를 알수 있다.
입력이 N번 Loop 작업이 3개가 있을 경우 이를 표시하면 O(3N), 이지만, 임의 상수 c는 아래와 같이 표시한다. ( T(n) =n 작업이 3개 이므로, c는 3)
더할 때에는 가장 큰것을 선택한다.
곱을 할 경우, 좀더 간결하게 적용가능. 바깥 루프가 O(N1) 이고, 이를 T1이라고 하고,
예를 들면, 작업 A, B, C가 존재 한다고 하고 각각의 작업, 즉 Program의 Big O 표기법을 이용하여, Time Complexity를 측정을 해보자.
O(10) : 항상 10번 반복하는 작업 존재. 이 작업이 1개 존재 할 경우,
int i=0;
int test=0;
// 1번째 작업 , 항상 동일
for (i=0;i< 10; i++)
test++;
위 전체작업을 표시 하면 아래와 같지만, 위의
기본규칙 1, 2, 3 정리하면 아래와 같이 정리된다.
- 전체 작업 A , B, C 가 존재하며 이 작업을 규칙을 사용하여 간소화해보자.
- 작업 C는 기본규칙의 1번의 동일 작업이다.
- 기본규칙 3번에 의해 MAX값만 사용 ( 간소화)
- 기본규칙 2번에 의해 앞에 상수는 의미가 없어진다.
O(3N^2 + 10N + 10) = O(3N^2) = O(N^2) 와 거의 동일
이 규칙에서 핵심이 되는 기본규칙 3번의 원리를 분석하고 넘어가겠다.
위와 같이 되는 이유를
개별작업시간과 전체작업시간을
백분율로 계산을 해보자.
(개별작업시간/전체작업시간) * 100
여기서 개별작업시간을 간단히 백분율로 분석을 해보자.
- 작업 A 실행시간 = O(3N^2) / O(3N^2 + 10N + 10) * 100 = 73.2%
- 작업 B 실행시간 = O(10N) / O(3N^2 + 10N + 10) * 100 = 24.4%
- 작업 C 실행시간 = O(10) / O(3N^2 + 10N + 10) * 100 = 2.4%
- 작업 A 실행시간 = O(3N^2) / O(3N^2 + 10N + 10) * 100 = 96.7%
- 작업 B 실행시간 = O(10N) / O(3N^2 + 10N + 10) * 100 = 3.2%
- 작업 C 실행시간 = O(10) / O(3N^2 + 10N + 10) * 100 = 0.1% 이하
위와 같이 N이 증가 할수록 작업 A에 시간의 복잡도가
최대값인 작업 A에만 편중이 되는 것을 확인 할수 있다.
N 값에 증가 값에 따라 N의 복잡도가 N^2에 편중이 되므로, 다른 것들은 거의 무의미 해지기 때문에 이 규칙이 적용이된다.
O(3N^2 + 10N + 10) = O(3N^2) =
O(N^2) 와 작업 A 거의동일
위와 같이 일반 작업처럼
기본공식 3 통해 단순화 시킬수 있겠지만, 위와 같이 N이 증가할 경우를 고려했기 때문에 단순화하여 가능하지만,
만약 정확한 비교와 다른 오차를 생각 한다면, 예를 들면 N의 값이 정해져 있다고 하고, 다항식의 늘어날 경우,
다른 작업 값도 무시할수는 없을 것이다.
2.3 시간복잡도 2번째 예제 (수열)
C로 구현한 알고리즘에서 삽입정렬을 보다가, 오랜만에 보니, 일반수학에 대해 잊어버려서
n + (n -1) + (n -2) + ... 1 합의 계산을 구하는 공식을 아래와 같이 적음
아래공식은 위의 합을 구할려면, 일반적인 규칙을 찾아야 하며,
- 가장 끝수와 가장 첫수를 더하면 항상 (n+1) 동일
- 위의 합의 전체 반복은 N이며, 2개짝으로 했기에, 2로 나눈다.
n (n+1)/2 : 1, 2, 3, 4, 5, .... n 의 합
아래에 예제에 적용
https://ko.wikipedia.org/wiki/%EC%88%98%EC%97%B4
아래의 예제는 원래 C로 구현한 알고리즘의 삽입정렬이지만, 간단하게 이해하기 쉽도록 표기
자세한내용은 책을 참조.
int SimpleTest ( int size)
{
int i=0,j=0;
int test=0;
for(i=1; i< size; i++)
{
j= i-1;
while(j>=0){
test ++;
j--;
}
}
return 0;
}
상위를 소스를 분석하여, 시간복잡도를 계산해보면, 바깥루프는 반복횟수가 (n-1) 안쪽 루프는 바깥루프의 의존적이다.
이제 바깥루프와 안쪽루프에 실제 값을 넣어 i, j에 i=1, j=0 부터 넣어 봤을때,
안쪽루프의
계산되는 부분(test++) 의 안쪽루프의 계산되는 부분의 반복횟수를이 직접 보자.
n : 바깥루프의 반복횟수, size
i j 반복횟수(계산되는부분)
1 0 1
2 1 2
3 2 3
4 3 4
5 4 5
(n-1) (n-2) (n-1)
안쪽루프의 계산되는 반복횟수를 분석을 해보면 1, 2, 3, 4 5 ,6 ~ (n-1) 증가되는 것을 알 수 있으며,
이는 수열과 동일구조이며
이것을 시간의 복잡도로 표시하면, 1 ~ (n-1) 합으로 표시가 가능하게되어진다.
수열의 합공식을 적용하면,
(n-1)n/2 을 해주면 된다.
이를 간소화 하면, O((n^2)/2- n/2) 표시가 가능하며, 이는 O(n^2)와 동일하게 된다.
참조: C로 구현한 알고리즘
https://en.wikipedia.org/wiki/Time_complexity
2.4 시간복잡도 3번째 예제 (재귀함수 or LOOP )
Loop와 사칙연산인 더하기/빼기/곱하기/나누기가 만날 경우의 각각의 규칙을 생각해보자.
N : N=2 이상의 변수
X : Loop의 최종 목표값 or 초기 값
- Loop 와 + N 일경우, 곱하기로 변하지만, 반복횟수 X/N
- Loop 와 - N 일경우, 나누기로 변하지만, 반복횟수 X/N
- Loop 와 * N 일경우, 지수로 변하지만, 반복횟수 LogNX
- Loop 와 / N 일경우, 로그로 변하지만, 반복횟수 LogNX
반복횟수가 동일한 이유는 Loop 는 무한이 아니라 유한으로 동작하며, 이를 Loop를 반복횟수 구하는 작업은 동일하다.
수열과 같이 증가 와 감수되는 규칙을 알고 배열 순서가 바뀌는 것을 알면 되겠다.
값을 대입을 해보고 간단히 분석해보고 계산하자
우선 재귀들의 구성을 보면, input값에는 return value의 영향을 받지 않는다.
그래서 input 중심으로 분석한다.
개별 함수의 Time Complexity 계산을 해보자.
T(n)으로 표시해도 좋다.
검증을 원하면, 전역변수를 넣어 count를 해서 점검을 해보자.
아래에서 재귀에서 O(1)은 재귀의 종료조건을 말하고, 이는 반복횟수에도 포함도 가능
Input n=5, 반복횟수 : n+1
Input 5, 4, 3, 2, 1, 0: -1
O(1) not working
O(n) = O(1) + O(n) =
O(n) or
O(n+1)
상위 규칙을 적용하면, O(n) 겠지만, 정확히 하기 위해서 O(n+1)
static int cnt=0;
int recursiveFun1(int n)
{
cnt++;
if (n <= 0)
return 1; // +1
else
return 1 + recursiveFun1(n-1); //N
}
int loopFun1(int n)
{
int i;
for(i=n;i >0; i-=1 )
{
cnt++; //N
}
return 1;
}
Input n=15, 반복횟수 : n/5+1 = 4
Input 15 10 5, 0: -1
O(1) not working
O(n) = O(n)/5 + O(1) =
1/5* O(n) + O(1) =
O(n)
static int cnt=0;
int recursiveFun2(int n)
{
cnt++;
if (n <= 0)
return 1; //+1
else
return 1 + recursiveFun2(n-5); //N/5
}
int loopFun2(int n)
{
int i;
for(i=n;i > 0; i-=5 ) //N/5
{
cnt++;
}
return 1;
}
Input n=125, 반복횟수 : Log5(n+1) + 1 = 5
Input 125, 25, 5, 1 , 0
O(1) not working
반복횟수가 n+1 가 되는 이유는 5^0 = 1 도 포함해야 하기 때문
O(n) = O(Log5(N+1)) + O(1) =
O(Log5(N+1))
static int cnt=0;
int recursiveFun3(int n)
{
cnt++;
if (n <= 0)
return 1; // +1
else
return 1 + recursiveFun3(n/5); //Log5N
}
int loopFun3(int n)
{
int i;
for(i=n;i > 0; i/=5 ) //Log5N
{
cnt++;
}
return 1;
}
- 재귀 함수-D (재귀의 확장성 과 등비수열 )
아래의 첫번째 함수와 재귀함수-A와 동일한 형태이지만, 2번째함수는 연속 2번 재귀호출하여 점점 2배씩로 확장하면서 커지는 구조이다.
재귀의 확장성을 알기위해서 등비수열과의 연관성도 알아두고, 어떻게 확장이 되어가는지 정확한 이해를 하자.
예를 들면, 재귀함수의 전체 반복횟수를 알아보기위해, 이 구조를 완전 2진 트리라고 생각하자.
시작조건 N=5 입력
종료조건 (N==0 이면 종료)
전체 반복횟수 (N+1) = 6 번
- 002 번 재귀호출 (처음호출)
- 004 번 재귀호출
- 008 번 재귀호출
- 016 번 재귀호출
- 032 번 재귀호출
- 001 번 재귀호출 ( 64개 중에 종료조건이 맞아 종료)
상위 형태는 등비수열의 형태이며, 이를 3배씩 변경하면 그 효과 역시 동일하다.
물론 위의 조건이 약간씩 상이하게 변경이 될 수 있지만, 그 근본은 동일하다고 생각한다.
- 등비수열의 구조 와 합의 공식
- 등비수열구조 : Sn = a + ar + ar^2 + ar^3 .. + ar^(n-1)
- 합의공식 : a(1-r^n) / (1-r)
- 1st 함수 분석
재귀함수-A 와 아래 첫번째 재귀함수는 동일한 구조이며, 이를 다시 한번보자.
Input n=5, 반복횟수 : n+1
Input 5, 4, 3, 2, 1, 0: -1
O(1) not working
O(n) = O(1) + O(n) or
O(n+1)
- 2nd 함수 분석
두번째 재귀 함수호출수는 반복횟수 동일하지만 함수가 2배식 확장되어, 함수 종료 조건은 한번만 실행되어진다.
n=5 일 경우 , 반복횟수 : n+1
2^1 + 2^2 + 2^3 + 2^4 + 2^5 + 1 = 63
O(1)
n은 감소하면서 두번식 확장하면서 커진다.
합의 공식 대입: (1-2^6)/(1-2) = -63/-1 = 63 (r=2 , a=1 , n+1 대입)
n=10 일 경우 , 반복횟수 : n+1
2^1 + 2^2 + 2^3 + 2^4 + 2^5 ... 2^10 + 1 = 2047
합의 공식 대입: (1-2^11)/(1-2) = -2047/-1 = 2047 (r=2 , a=1 , n+1 대입)
이공식을 다음과 같이 변경 가능하다.
O(n) =
O(2^(n+1)) - 1
N 대신 2^(N+1)를 넣고 첫번째 재귀함수와 동일하게 반복횟수는 n+1 이다.
n을 5을 넣으면, 함수 호출수는 2^(n+1) -1 = 64 - 1번 = 63
n을 10을 넣으면 함수 호출수는 2^(n+1) -1 = 2048 -1 번 = 2047
- 3rd 함수 분석
세번째 재귀 함수호출수는 반복횟수 동일하지만 함수가 3배식 확장되어, 함수 종료 조건은 한번만 실행되어진다. .
n=5 일 경우 , 반복횟수 : n+1
3^1 + 3^2 + 3^3 + 3^4 + 3^5 + 1 = 364
O(1)
n은 감소하면서 3배식 확장하면서 커진다.
합의 공식 대입: (1-3^6)/(1-3) = -728/-2 = 364 (r=2 , a=1 , n+1 대입)
상위 공식을 아래와 같이 변경 가능하다.
O(n) =
O(3^(n+1) - 1 ) / 2
n=5 ( 3^(5+1) - 1 ) / 2 = 364
n=10 ( 3^(10+1) - 1 ) / 2 = 88573
- 4th 함수 분석
네번째 재귀 함수호출수는 반복횟수 동일하지만 함수가 4배식 확장되어, 함수 종료 조건은 한번만 실행되어진다.
상위와 같은 등비수열의 합이며, 동일하게 아래와 같이 일반화하여 쉽게 구할수 있다.
O(n) =
O(4^(n+1) -1 ) / 3
n=5 (4^(5+1 ) -1) / 3 = 1365
n=10 (4^(10+1) -1) / 3 = 1398101
static int cnt=0; // 전역변수로 한번 점검해보자
void recursiveFun4_1(int n, int m, int o)
{
cnt++;
if (n <= 0){
return 1;
}else{
recursiveFun4_1(n-1, m+1, o); // 동일한 함수를 1번 호출 1배식 확장
}
}
void recursiveFun4_2(int n, int m, int o)
{
cnt++;
if (n <= 0){
return 1;
}else{
recursiveFun4_2(n-1, m+1, o); // 동일한 함수를 2번 호출하여 2배식 확장
recursiveFun4_2(n-1, m, o+1);
}
}
void recursiveFun4_3(int n, int m, int o)
{
cnt++;
if (n <= 0){
return 1;
}else{
recursiveFun4_3(n-1, m+1, o); // 동일한 함수를 2번 호출하여 3배식 확장
recursiveFun4_3(n-1, m, o+1);
recursiveFun4_3(n-1, m, o+1);
}
}
void recursiveFun4_4(int n, int m, int o)
{
cnt++;
if (n <= 0){
return 1;
}else{
recursiveFun4_3(n-1, m+1, o); // 동일한 함수를 2번 호출하여 4배식 확장
recursiveFun4_3(n-1, m, o+1);
recursiveFun4_3(n-1, m, o+1);
recursiveFun4_3(n-1, m, o+1);
}
}
기본적으로 재귀함수-B 와 동일 하지만, 안에 다른 작업이 포함이 되어있어 이를 계산해보자.
다시 재귀함수-B를 보자
Input n=15, 반복횟수 : n/5+1 = 4
Input 15 10 5, 0
work_1 8 (7.5) 5 3(2.5) 1 = 17
아래의 소스를 동작해보면 cnt 16 으로 마지막 0 에서 cnt는 동작이 안됨 (n=0)
O(n) = O(n)/5 + O(1) =
O(n/5)+1 안에 다른 작업이 반복이 된다.
static int cnt=0; // 전역변수로 한번 점검해보자
int recursiveFun5(int n)
{
int i;
for (i = 0; i < n; i += 2) { //work_1
cnt++;
}
if (n <= 0)
return 1;
else
return 1 + recursiveFun5(n-5);
}
http://stackoverflow.com/questions/13467674/determining-complexity-for-recursive-functions-big-o-notation
2.5 시간복잡도 4번째 예제
Big O 표기법이라는 것이 기본규칙을 사용하여 일반화하여 구성을 하면 정확한 측정은 힘들어진다.
하지만 기본규칙은 항상 모든 알고리즘에서 빠른 계산과 쉬운 계산을 목표로 생각으로 구성을 해야겠다.
x = n
while ( x > 0 ) {
x = x - 1
}
n=5
input: 5 ,4 ,3 ,2 ,1
O(n)
x = n
while ( x > 0 ) {
x = x / 2
}
n=8
input: 8 , 4 , 2 , 1
O(logN)
x = n
while ( x > 0 ) {
y = n
while ( y > 0 ) {
y = y - 1
}
x = x - 1
}
n=5
input : (5,4,3,2,1) , (5,4,3,2,1) , (5,4,3,2,1), (5,4,3,2,1) , (5,4,3,2,1)
O(N^2);
x = n
while ( x > 0 ) {
y = n
while ( y > 0 ) {
y = y / 2
}
x = x - 1
}
n=4
input : (4,2,1) , (4,2,1) , (4,2,1), (4,2,1) : O(LogN) 을 O(n) 반복
O(NLogN);
x = n
while ( x > 0 ) {
y = x
while ( y > 0 ) {
y = y / 2
}
x = x - 1
}
n=4
input : (4,2,1) , (3,1) , (2,1), (1) : O(LogN) 을 O(n)반복
O(NLogN);
x = n
while ( x > 0 ) {
y = n
while ( y > 0 ) {
y = y - 1
}
x = x / 2
}
n=4
input : (4,3,2,1) , (4,3,2,1) , (4,3,2,1) : O(n)을 LogN 만큼 반복.
O(NLogN);
x = n
while ( x > 0 ) {
y = x
while ( y > 0 ) {
y = y - 1
}
x = x / 2
}
n=4
input : (4,3,2,1) , (2,1) , (1) : O(n)을 O(LogN)만큼 반복 ( O(n)의 값이 적용 )
O(NLogN);
x = n
while ( x > 0 ) {
y = n
while ( y > 0 ) {
y = y / 2
}
x = x / 2
}
n=4
input : (4,2,1) , (4,2,1) , (4,2,1) : O(LogN)을 O(LogN)만큼 반복 (두번째 LogN은 동일)
O(LogLogN);
x = n
while ( x > 0 ) {
y = x
while ( y > 0 ) {
y = y / 2
}
x = x / 2
}
n=4
input : (4,2,1) , (2,1) , (1) : : O(LogN)을 O(LogN)만큼 반복 (두번째는 LogN는 감소)
O(LogLogN);
https://www.quora.com/How-can-we-check-for-the-complexity-log-n-and-n-log-n-for-an-algorithm
3. O 표기법의 주요 함수 내용 정리
기본적으로, O표기법으로 알아내는 법은 Input을 넣어 대입하고 어떻게 동작이 되는지를 파악을 해보면 된다고 생각한다.
그리고 그 변화에 규칙성이 알아내어 규칙성을 찾아 일반적인 함수를 적용 할수 있다면 적용하는 것이다.
여기서 이산수학의 필요성이 필요한 것 같다.
(사실 고등학교 수학지식이면 충분한 것 같다)
3.1 일반적인 O 표기법
- O(1) : 항상 일정한 시간을 갖는것을 의미한다.
아래와 같이 반복 routine이 있다 할지라도, 100 * 200에서 항상 동일하게 끝난다.
아래는 항상 일정한 시간을 갖는 routine이다.
아래 작업을 두개의 일정한 값을 유지하는 작업이 2개 ( if 와 for 반복문)
O(c)+O(1) = O(1) C는 100 * 200
int index = 5;
int item = list[index];
if (condition true) then
perform some operation that runs in constant time
else
perform some other operation that runs in constant time
for i = 1 to 100
for j = 1 to 200
perform some operation that runs in constant time
3.2 일반적인 반복 O 표기법
- O(N) : n은 보통 n번의 반복이며, for or while loop로 생각하면되겠다.
int index = 5;
int item = list[index];
for i = 1 to n
perform some operation that runs in n time
- O(N^2): n번을 반복을 하고 다시 n번을 반복 이중반복이라고 생각하면되겠다.
int index = 5;
int item = list[index];
for i = 1 to n
for j = 1 to n
perform some operation that runs in n * n time
- O(N^3): 쉽게 3중반복이라고 생각하면되겠다.
위와 동일 하며, 반복문이 하나 더 추가 될 뿐이다.
3.3 2의 지수 O 표기법
- O(2^N): 2의 지수이며, input data set이 두배로 확장되는 것을 의미한다.
재귀함수로 2번의 재귀함수를 사용하여, 매번 input data set이 두배로 확장
int Fibonacci(int number)
{
if (number <= 1) return number;
return Fibonacci(number - 2) + Fibonacci(number - 1);
}
아래의 피보나치 수열을 계산과정을 보면 2의 지수 형태로 진행이 되는 것을 알 수 있다.
예를 들면, number를 5를 넣으면, 두번을 매번 재귀를 매번 호출하고,
재귀된 함수도 1 값이 될때 까지 2번씩 반복이 된다.
이는 2의 지수 함수 동일하다.
아래의 예제를 보면 쉽게 이해가 간다.
https://ko.wikipedia.org/wiki/%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95
3.4 Binary Log 함수 O 표기법
O표기법에서 사용하는 일반적인 Log의 아래값은 2이며, Log 함수의 기본적인 성질을 알아두자.
b^V = M 일 때 Logb(M) = V 된다.
b^0 = 1 이를 Logb(1) = 0 변환하면 Log Rule 1번
쉽게 생각하면 b의
지수의 값을 구하려는 함수라고 생각하면 된다.
현재 O 표기법에서는 b의 값은 2이다,
고등학교때, 그냥 Log하면 Log b는 10인 걸로 기억을 하는데 처음 혼동이 되어서 간단히 적어본다.
- logb1 = 0 , Logb(b) = b;
- logb(mn) = logb(m) + logb(n)
- logb(m/n) = logb(m) – logb(n)
- logb(m^n) = n · logb(m)
4번 규칙처럼 Log 함수에서 M의 지수를 사용할 경우, N * logb(M) 변환이 가능하다.
아래내용은 로그함수의 기본정의 규칙을 정리 다시 복습 해보자.
기본로그함수내용
https://en.wikipedia.org/wiki/Logarithm
https://en.wikipedia.org/wiki/Binary_logarithm
로그관련 기본공식
http://mathbang.net/597
http://www.purplemath.com/modules/logrules.htm
- O(logN) : log는 2를 말하며, 보통 binary search or Binomial heap 말한다.
원리는 둘 중 하나를 선택하여, 지속적으로 찾아가고 호출하는 방식을 말한다.
Binary Search 와 Binary Traversal은 다르며, Binary Search인 경우는
보통 현재 노드를 비교하여, 저장될 노드를 비교하여 찾아가는 구조이기에,
둘중 하나만 선택하여 찾아 호출하는 구조
n/b^3 의 의미 부터 파악해보면, layer가 내려갈 수록 1/b씩 곱하는것이다.
이 전체를 순회를 한다고 가정하면, 마지막 layer에 도착하기 위해서는 n/b^3의 확률이 걸린다. N=8이다.
- O(NlogN) : log는 2를 말하며, LogN에 N번의 반복을 하는 것 같다.
LogN과 기본 원리와 비슷하지만, 아래와 같이 모든 Tree를 순회를 하게되면,
더 할 수 있겠다. 그리고, Log에서 덧셈을 곳셈으로 변환하고, 그 곳셈에서 나온값을
N의 지수가 나오기때문에 아래와 같이 간단히 정리를 할 수 있겠다.
= (log n+log(n-1)+...+log 2)
= (log n+log(n-1)+...+log 2)+(log n+log(n-1)+...+log 2)
= O(n*log n)
https://ko.wikipedia.org/wiki/%ED%9E%99_%EC%A0%95%EB%A0%AC
https://en.wikipedia.org/wiki/Heapsort
https://www.quora.com/How-can-we-check-for-the-complexity-log-n-and-n-log-n-for-an-algorithm
; Using a constant-size 
![{\displaystyle L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/40715162d91a34daf9bcfed5f41d8e336417f803)
