이산수학 알고리즘

수학적인 알고리즘의 의미 기반?

 

알고리즘

주어진 문제에 대해 그 문제를 해결하기 위한 방법을 순차적으로 나열한 것

 

알고리즘 특징

1) 입력을 가진다

2) 출력을 가진다

3) 유한 시간 내에 종료 돼야 한다.

4) 각각의 중간과정이 명확하게 서술되어야 한다.

5) 여러 입력값에 대해 적용 가능해야 한다.

 

알고리즘 표현 방법

- 순서도

- 의사 코드

- 실제 언어를 사용햇 표현

 

순서도

 

의사코드

 

알고리즘의 분석 기준

- 정확도

- 코드 복잡도

- 공간 복잡도

- 시간 복잡도

 

공간 복잡도는 기술의 발달로 하드웨어의 비용이 많이 줄어들어 비교적 덜 중요해짐

따라서 정확도와 시간 복잡도가 주로 알고리즘에서 제일 중요한 요소로 여겨진다.

 

시간복잡도 표기법

Big O , qlr-dh vyrlqjqdlfkrh qnfmsek.

g(n)에 들어가는 함수는 1, logn, n, nlogn, n^2 ...

 

---

재귀적 알고리즘

 

재귀적 함수란 함수가 자기 자신을 스스로 호출하는 함수

재귀적 알고리즘이란 재귀적 함수를 포함한 알고리즘

 

재귀적인 문제를 해결하기 위해서는 초기조건이 필요하다

초기조건이 엉망이면 무한적으로 코드가 실행되버리는 무한 루프에 빠질 수 있다.

 

계속 순환하는데 이러한 계산을 위해 자료구조 중에 stack이 사용된다.

재귀적 함수에 의한 stack의 크기가 부족할 때 생기는 것이 stack overflow이다.

 

같은 결과를 내는 코드지만 재귀법을 사용하는 경우와 반복문을 사용하는 경우에 실행 시간과 컴퓨터에서 사용하는 기억 장소 사용량 등이 매우 다르다.

일반적으로 재귀법은 반복법보다 프로그램의 구성이 간단하지만 실행시간이나 메모리를 더 많이 사용한다는 단점이 있다.

재귀법을 사용한 프로그램과 반복법을 사용한 프로그램 사이에는 동등한 대체법이 존재할 수 있으니, 케이스에 맞게 쓸 수 있다.