알고리즘....

알고리즘이란 주어진 문제를 해결하기 위한 잘 정의도니 동작들의 유한 집합이다.


알고리즘에는 우선 주어지는 문제가 있고 이 문제를 해결하기 위한 순서적ㅇ니 동작들이 있다. 이 동작들은 또한 자료 구조를 필요로한다. 

알고리즘을 개발하는데 가장 먼저 선행되어야 할 것은 바로 주어진 문제를 잘  이해하는 것이다. 주어지는 문제는 문제 그 자체만이 아니라 문제가 주어지는 상황도 포함이 된다. 문제가 주어지는 상황은 문제를 해결하는 데 이용할 수 있는 자원들을 포함하고 있고, 문제를 해결하는데에 제한이 되는 요소들도 포함할 수 있다. 이러한 문제를 잘 이해하고 난 후에야 알고리즘을 생각할 수 있다. - 알고리즘을 가장 적절히 한글로 표현한다면 방법이 될 것이다.

두 정수의 곱셈 에 대한 알고리즘   a la russe

1. 두 개의 정수를 첫번째 위치, 두번째 위치에 써둔다. 만일 첫번째 수가 홀수면 두번째 수를 세번째 위치에 또 쓴다.
2. 첫번째 수를 2로 나누고(나머지는 버린다.) 두번째 수에 2를 곱한다. 만약 첫번째 수가 홀수이면 두번째 수를 세번째 위치에 쓰고 짝수이면 세번째 위치를 비워둔다.
3.위의 1과2의 과정을 첫번째 위치의 수가 1이 될때 까지 반복한다.
4. 세번째 위치에 있는 수들을 모두 더한다. 이 더한 결과가 바로 두 정수의 곱의 결과이다.

-ex
45          37                     37
22          74                     -
11          148                     148
5            296                    296
2             592                   -
1             1184                  + 1184
                                   -------------
                                     1665
계산을 하기 위해서는 더 많은 종이가 필요하겠지만 a la russe 알고리즘은 기본적인 동작이 매우 간단하다.
a la russe 알고리즘의 기본동작-
1. 정수를 2로 나눈다.(이것은 C언어의 >>연산자로 간단하게 구현된다.)
2. 정수를 2로 곱한다.(이거도 C언어의 <<연산자로 간단하게 구현이 된다.)
3. 두 정수를 더한다.

- 이 세가지 간단한 기본동작으로 두 정수의 곱셈이 이루어 지기 떄문에 사람의 입장에서는 불편하지만
컴퓨터의 입장에서는 오히려 간편하다. 이 두 가지 알고리즘,  어느것이 낫다고 할수 없다...
주어진 상황에 따라 다르기 떄문에 ^^;;

알고리즘의 분석

하나의 문제에 대해서  많은 알고리즘이 존재한다면 어떠한 알고리즘을 선택할 것인가 하는 문제가 생긴다-
알고리즘의 선택은 상황에 의존하는 것이지만 그래도 객관적인 알고리즘의 비교 분석이 필요하다.

- 알고리즘의 분석은 이러한 알고리즘의 객관적인 비교 분석을 경험적으로 혹은 수학적으로 한 것이다.

경험적 분석은 흔히 쉽게 알고리즘을 프로그래밍 언어로 구현 한뒤에 이를 실행 시켜 보앗 실행 시간ㅇ르 비교해 보는것이다. 이것은 쉽게 납득될 만한 신빙성 있는 자료를 제공하며 수학적인 지식이 필요없다는 장점이 있다. 경험적 분석에 의해서도 수학적 분석과 마찬가지로 수식을 이끌어 낼 수 있는데 이것은 처리하는 자료의 수를 다르게 하여 그 함수 관계를 유추하는 것에서 가능하다.

수학적 분석은 알고리즘ㅇ르 프로그래밍 언어로 구현함이 없이 단지 알고리즘 자체만을 가지고 수학적 분석을 하는 것이다. 이 수학적 분석은 소프트웨어 공학의 주요한 부분이 될 정도로 어렵고 깊은 분야이다... 수학적 분석은 알고리즘을 프로그래밍하는 과정이 없기 떄문에 프로그래밍 하는 과정에서 같은 알고리즘이더라도 프로그래머의 능력에 따라 나타날 수 있는 성능의 편차를 없앨 수 있다는 장점이 있다.

알고리즘 분석은 세단계로 나누어 실행할 수 있다.

첫번째 단계는 알고리즘ㅇ르 판단할 수 있는 입력 자료를 결정하는 것이다.
여러가지 종류의 임의의 자료를 같은 알고리즘에 대해 계속 적용시키다 보면 어느 정도의 실행 시간의 범위가 정해진다. 이범위의 상한(근사적인 최악의 경우)은 알고리즘의 수행 시간이 상한을 넘지 않는다는 것을 보증한다. 임의의 입력을 이용하여 알고리즘의 평균 수행시간(근사적인 평균적인 경우)을 구할 수도 있다.

두번째 단계는 알고리즘을 구성하는 동작들을 추상적이고 기본적인 동작들로 분해하여 그 동작들의 수행 시간을 계산하여 보는 것이다.
예를 들어 정렬 알고리즘을 생각한다면 정렬 알고리즘은 기본적인 동작들로 '비교와 교환'이 있다. 이 비교와 교환에 대한 CPU의 동작 시간을 구하여 조합하여 보면 알고리즘이 수행하는 데 피료한 시간을 구할 수 있다.

세번째 단계는 수학적인 알고리즘 분석을 행하는 것이다.
 최악의 경우를 이용한 수행시간의 상한을 결정하는 것은 수학적으로 별로 어려운 것은 아니지만 평균적인 경루를 수학적으로 결정하는 것은 매우 어려운 일이다.

알고리즘 분석은 원하는 정도의 결과가 나올 때까지 분석하고 ,측정하고 개선시키는 과정의 반복이다.