1. Algorithms
1) Algorithms
1> Problem : Instance들의 모임
2> Parameter : 문제에 variable들 (아직 specific value를 할당 받지 못한 상태)
3> Instance : parameter에 specific value를 할당 받은 상태
4> Solution : 주어진 instance에 대한 answer
5> Algorithm : 문제를 해결하기 위한 step-by-step 단계
2) algorithm에 대한 정확한 정의
1> algorithm
a finite set of instructions that, if followed, accomplishes a particular task.
(particular task를 할 수 있는 집합)
2> algorithm이 만족해야하는 조건
- input : 0개 이상 있어야한다. (밖에서)
- output : 최소 1개 있어야 한다.
- Definiteness : Each instruction is clear and un-ambiguous
- Finiteness : If we trace out the instructions of an algorithm, then for all cases the algorithm terminates after a finite number of steps
- Effictiveness : 기초적이며 구현 가능해야 한다.
Every instruction must be basic enough to be carried out, in principle, by a person using only pencil and paper It is not enough that each operation be definite it also must be feasible
3) Algorithm Description
알고리즘을 묘사하는 방법
1> Natural Language (글로 묘사) : Must be definite
- 글로 쓰는 게 원칙이고 이를 보충하려고 flow chart 혹은 pseud code를 쓴다.
- 예시
2> Graphic Representation
flow chart
3> Pseudo-Language
4) The Importance of Developing Efficient Algorithms
1> 예시 : Sequential Search (N) vs Binary Search (logN)
2> 예시 : The Fibonacci Sequence
T(n) : n번째 fibonacci 항을 구할 때 호출되는 항들
3> The Fibonacci Sequence Thm 증명
4> iterative fibonacci와 recursion fibonacci의 비교
iterative fibonacci는 저장하면서 항을 구하기 때문에 더 빠르다.
5) Execution times for algorithms with various f(n)
=> n이 10^9이고 f(n)=n이면 1초이다.
'알고리즘 > 알고리즘_학교' 카테고리의 다른 글
| 4-1강 - Euler's path(cycle) 1 (개념 정리 및 구현 아이디어) (0) | 2020.10.09 |
|---|---|
| 3-2강 - 자료구조 & C, C++ programming 2 (Linked List management, Stack & Queue) (0) | 2020.10.03 |
| 3-1강 - 자료구조 & C, C++ programming 1 (call by reference, dynamic allocation) (0) | 2020.10.03 |
| 1-2강 - Introduction (Graph Problem) (0) | 2020.09.03 |
| 1-1강 - Introduction (Euler' Graph) (0) | 2020.09.02 |
