[자료구조] ch1 알고리즘이 아닌 예시들(examples not an algorithm)

 

* 학교 자료구조 수업을 들으며 책으로 공부한 내용들을 정리하고 있습니다.

* 교재 : Fundamentals of Data Structure in C (2nd Edition) - Ellis Horowitz, Sartaj Sahni, Susan Enderson-Freed

---

 

이전 글에서 Algorithm의 성립 조건으로 5가지 requirements를 배웠다.

더 detail한 이해를 위해 예시를 들고 해당 예시들이 알고리즘에 해당하는지 분류해보자.

(이전 글 :  https://cuffyluv.tistory.com/25)

---

복습) requirements of algorithms

1) Input(입력) : zero or more quantities that are externally supplied

외부에서 공급되는 양이 0개 이상이어야 함.

 

2) Output(출력) : at least one quantity is produced

적어도 하나 이상은 생성돼야함.

 

3) Definiteness(명확성) : clear and unambiguous instructions

분명하고 확실한 명령어들이어야 함.

 

4) Finiteness(유한성) : terminated after finite steps

유한한 단계가 끝나고 나면 제거되어야함.

 

5) Effectiveness(유효성) : instruction is basic enough to be carried out

명렁어는 수행되기에 충분히 기본적이어야 함.

---

ex1. For positive integer x, y, and z, is 2 the largest value of n that satisfies x^n + y^n = z^n

 

Input : positive integer x, y, z

Output : TRUE or FALSE (1 or 0)

Definiteness : 컴퓨터에게 '명령'을 내리는 게 아닌, 질문을 하고 있음. 이는 명확성에 어긋남

Finiteness : n을 찾고 나면 알고리즘이 종료될 것임

Effectiveness : 충분히 기본적인 명령임

Input(입력)	Output(출력)	Definiteness(명확성)	Finiteness(유한성)	Effectiveness(유효성)
O	O	X	O	O

-> 따라서 해당 문장은 알고리즘이 아님.

---

ex2. Divide 5 by 0, store it in x, and branch to statement 10.

 

Input : x

Output : branch되었음 (현상 자체가 결과)

Definiteness : 제대로 명령을 내리고 있음.

Finiteness : 분기 후에는 알고리즘이 종료될 것임

Effectiveness : 수를 0으로 나눈다는건 성립하지 않음. 즉, 수행될 수 없으므로 유효성에 어긋남.

Input(입력)	Output(출력)	Definiteness(명확성)	Finiteness(유한성)	Effectiveness(유효성)
O	O	O	O	X

-> 따라서 해당 문장은 알고리즘이 아님.