[C언어]알고리즘 (Time Complexity)시간 복잡도와 빅오 표기법

우선, Algorithm 알고리즘 이란?

 어떤 문제를 해결하고자, 구현하고자 하기 전에, 문제의 해결을 위한 절차 또는 단계를 명시적이고, 논리적으로 표현한 것을 알고리즘이라고 합니다. 

 

 (추상적으로 표현된 알고리즘은 특정한 프로그래밍 언어로만 작성된 것이 아니기에 다른 언어를 사용하는 프로그래머들이 자신이 알고있는 언어를 통해 알고리즘의 해답을 구현할 수 있습니다.)

 

 문제를 해결하기 위한 방안으로 여러 알고리즘이 있을 것인데,, 이중에서 가장 좋은 알고리즘. 효율적인 알고리즘을 판별하기 위한 대표적인 알고리즘의 성능 분석 방법은 시간복잡도와 공간복잡도입니다.

---

시간 복잡도

 알고리즘을 프로그램으로 수행되는데(실행->완료시점)까지 사용된 총 저장공간을 분석하는 방법은 공간복잡도이고,

알고리즘이 수행되는데 실행된 명령문의 실행 빈도수를 계산한 방법이 시간 복잡도입니다.

 한 문제에 대한 여러 알고리즘 중 최적의 알고리즘을 효율적으로 측정하기 위해 시간 복잡도를 사용합니다. 

 

 시간 복잡도를 구할때 가장 중요한 것은 지정문, 조건문, 반복문 을 하나의 단위 시간을 갖는 기본 명령문으로 취급해 입력 크기 n에 대한 실행 빈도 함수를 구해야 하는 것입니다.

 

---

• 예를들어 아래의 문장에서

int x=0;		//1회
for(int i=0;i<n;i++){	//n+1회
	x++;		//n회
}
(for문은 i==n-1일때 x++이후 i==n일때 i<n에 의해서 포문에서 벗어남으로 한번 더 실행됩니다.)

 

실행 빈도 함수T(n) = 2n+2회입니다.

 

• 두번째 예제에서는

int sum=0;				//1회
for(int i=0;i<n;i++){			//n+2회
	for(int j=0;j<n;j++){		//n+2회
    	sum+=i+j;			//n+1회
    }
}

실행 빈도 함수는 안쪽 for문부터 바깥for문까지 T(n)= (n+2+n+2)*(n+2)+1회 임을 알 수 있습니다.

 

알고리즘의 실행 시간은 n에 따라 정해집니다. 

---

 

점근적 분석? 차수 표기법 ??

 시간복잡도는 실행 빈도함수에서 입력 크기 n에 대한 실행 시간의 증가율만 분석하는 점근적 분석을 사용합니다. why? 입력크기 n의 값이 높아지면 높아질수록, 1000 이나 10000의 숫자는 턱없이 작은 수가 되기 때문입니다. 따라서 실행 빈도 함수의 상수항과, 계수는 무시하고, n이 가장 큰 하나의 항(=최고차항)에 대해서 차수 표기법으로 시간 복잡도를 표기합니다.

 

• 빅-오 표기법, 빅-오메가 표기법, 빅-세타 표기법

시간 복잡도를 3가지의 방법으로 표기를 할 수 있는데 그중 대표적인 방법은 빅-오 표기법입니다. (맨 처음 들었을때는 정말 무서워 보이는 괴물로 느껴졌었습니다..Big-Oh Notatio ) 

 

• 빅-오 표기법 정의 

함수 f(n)과 g(n)이 주어졌을 때, 모든 n>=n[0]에 대하여 |f(n)|<=c*|g(n)|을 만족하는 상수 c와 n[0]이 존재하면,
f(n)=O(g(n))이다.

말 그대로, 함수값에서 계수는 생략하고, O의 오른쪽 괄호 안에 표시를 하는 방법입니다. 위의 표기법을 사용하여 아까 처음의 예제에서 구했던 실행 빈도함수 T(n)=2n+2에 대한 빅 오 표기법을 구한다면?

T(n)=O(n) 이 되는 것입니다.

즉!!!! 최고차항을 Big Oh의 O를 따서 O(최고차항) 으로 표기하면 되는 방법입니다!!  (약간 당황하실 수도 있으시겠지만) 정답은 O(n)입니다.

 

• 마지막 예제입니다.

void Sum(int n){		
for(int i=0;i<n;i++){		//n회
	for(int j=0;j<100;j++){	//100회
    	for(int z=0;z<500;z++){//500회
        	x++;		//499회
        }
    }
}

T(n)=n+100+500+499 . T(n)의 빅 오 표기법은? = O(n) 입니다.

(최고차항을 구하는 것이 빅-오 표기법을 표기함에 있어 가장 중요한 방법임을 알 수 있습니다.)

 

알고리즘의 T(n)은 logn, n, nlogn, n^2, n^3, 2^n 등의 실행 시간 함수가 있는데,

n값이 커질 수록 실행시간 함수값의 크기는 (기하급수적으로 ..)

logn<n<nlogn<n^2<n^3<2^n의 순서로 커집니다. 실행 함수값의 크기가 커진다는 뜻은 실행시간이 느려진다는 것을 뜻합니다!!

Q> 알고리즘의 성능이 좋은 순서는?

1. O(1)  - 지수

2. logn

3.  n

4.  nlogn

5.  n^2

6.  n^3

7.  2^n

 

일반적으로는 최악의 경우를 고려한 해결책을 찾기 때문에 빅-오 표기법을 주로 사용합니다!!!

 

 

긴 글 읽어주셔서 정말 감사합니다.