알고리즘 과 빅오 표기법

알고리즘이란?

알고리즘 이란 요리에 비유하자면 조리법에 해당함.

즉 문제를 해결하기 위한 방법이며, 이것을 구체적으로 표현한 것이 프로그램이다.

 

알고리즘이 추상적 이라면, 프로그램은 구체적이다.

알고리즘은 구현과 무관하게 추상적으로 기술되는 반면에, 프로그램은 구현 환경과 연관되어 기술된다.

 

알고리즘의 정확성

알고리즘은 기본적으로 정확성을 지녀야 한다.

 

알고리즘 오류

문법적 오류

 단순히 구문상의 오류. C 문법에서 ;(세미콜론)을 붙이지 않았다던가...

 

의미상의 오류

 구현하고자 하는 의미를 잘못 해석한 경우. 또는 문법에 대한 잘못된 이해로 작성된 알고리즘

 

논리적 오류

 프로그램의 정확성을 해치는 가장 심각한 오류

 

 

프로그램의 정확성 증명

샘플 테스트

프로그램에 오류가 있음을 증명할 수는 있으나, 프로그램에 오류가 없음을 증명 할 수는 없다.

오류가 생길만한 입력이 들어오지 않았을 수 있기 때문이다.

 

분할 정복

전체 알고리즘을 단계 별로 잘라서, 각 부분알고리즘을 나눈 뒤에 각 단언이 옳음을 증명.

 

 

알고리즘의 효율

공간적 효율성과 시간적 효율성 두 가지 측면에서 고려됨.

하지만 요즘 같이 하드웨어 성능 상 큰 차이가 나지 않는 한, 시간적 효율성이 더욱 강조된다.

이 효율성을 다르게 표현한 것이 바로 복잡도 (Complexity) 이다.

알고리즘의 시간적 효율성을 나타내기 위해, 개략적인 분석을 사용한다.

따라서 데이터의 입력 크기를 통해서 분석을 할 수 밖에 없는데, 

이때 데이터의 크기를 N 으로 표현한다.

void Display(Nptr  pHead) {        Nptr  Temp = pHead;          while( NULL != Temp )       {                   pritnf("%d" , Temp->Data );                   Temp = Temp->pNext;          } }

 

위 코드는 연결형 리스트를 순회하며 출력하는 코드이다.

리스트 안에 데이터의 개수를 N 이라고 표현 할 수 있다.

그렇다면 할당하는 과정은 총 N+1 회 일어나며, 비교 과정이 N 회, 출력함수 호출이 총 N회이다.

따라서 할당 한 번에 걸리는 시간을 a 라고 하고, 비교과정에 걸리는 시간이 b 라고 하며, 출력한번

에 걸리는 시간이 c 라고 한다면, 위 함수의 시간 복잡도를 N에관해 표현 했을 때, 다음과 같다.

 

하지만 알고리즘의 시간적 효율을 말할 때는 N에 관한 1차 방정식만을 밝히고 계수들은 전부 무시된다.

 

알고리즘의 시간효율을 계산할 때 고려하는 것이 또 있다. 매번 최선의 상황을 기대하기 어렵기 때문에

최악의 경우를 가정해서 계산한다.

이러한 제반 조건을 전제로 사용하는 수학적 기호가 바로 빅 오 표기법이다.

따라서 위 시간복잡도  는  이다.

빅 오 표기법으로 계산하기

#define MAX 90000     for i = 1000 to N-2000             for j = 2 to MAX             do {                        read();                    write();             }

, 선형시간 알고리즘( N 에 정비례 )

 

for (int i = 1; i < N: ++i) {     for (int j = 2; j < N - 1; ++j)     {         Read();         write();     } }

, 제곱시간 알고리즘( 에 비례 )

 

 

for int i = N - 10000 to N {     read();     write() }

 , 상수시간 알고리즘

 

 

if (x == 1){     for int i = 1 to N     {         read();         write()     } }else{     a = 20;     read(); }

 , 선형시간 알고리즘( N 에 정비례 )

 

 - by Raimondo