해당 포스팅은 알고리즘에 대한 첫 포스팅이므로 알고리즘에 대한 이론을 다루는 포스팅 입니다.
대학교 강의(단국대학교) 수업을 강의 한후 작성한 포스팅이고 ,해당 포스팅에선 예시코드를 제시하지 않았습니다.
Problems and solutions의 문제.
- a problem will normally have many usually infinitely many instances
문제는 보통 많은 무한한 인스턴스(경우 문제 예)를 가지고 있다.
problem P f:D->R
P is solved if there is an algorithm to compute f
P is unsolved if there is no algorithm to compute f
P unsolvable if it how been proved that there can be no algorithm to compare f
what is an algorithm?
- must work correctly on every Instance of the problem
- a finite sequence of instructions such that.
1. each instruction is definite and effective
2.output is collect
3. an execution of the instructions should terminate.(매우 중요)
->이 3가지 조건을 만족해야 알고리즘이다.
Necessary conditions
1. inputt : 0 or more(1,2,3,4....etc)
2. output : 1 or more.
3. definiteness : deterministic , not ambiguous
4. firiteness - 당장 메모리도 무한이 아니니까.
5. effectiveness
*Steps involved in writing a program to solve a given problem.
1. problem formulation.
2. specification : mathmatic modeling (수학적 모델을 쓰는게 정답이지.. 보통 그림으로 설명을 많이 해서 쉽게 배우지만 응용이 안되는거죠)
3. design of the solution -> algorithm design
4. implementation - os,language,data structure
5. testing & debugging
6. documentation - 메뉴얼
7 evaluation of the solution(analysis) 평가
*Analyzing Algorithm (complexity of Algorithm)
-given a problem , once we have an algorithm
-how do we compare this algorithm with others?
=> the rate of growth of the time or space
required to solve larger and larger instance of the problem
the size of the problem - > input size(n)
the size of the problem - > input size ( size는 예를들어 웹 사이트에 접속하는 사람의 수.)
Algorithm A 는 꾸준한 성과를 보이는 알고리즘이다.
하지만 Algorithm B는 처음에는 성능이 좋지 않다가, 많은 input이 들어오는 상황에서는 좋은 퍼포먼스를 발휘한다.
대부분 기업이나 회사에서 , 요구사항에 맞춰 개발을 하다보면, 내가 개발한 프로그램에서, 사용자가 얼마나 접속할지는 잘 모르는 것이다.
하지만 보통 많은 테스트를 거치지 못하기 때문에, 배포 이후 패치를 진행하는 것이다.
* Complexity : 복잡도 - 복잡도가 제일 어려운 개념이다.
1. space complexity : A function that. maps problem size(x축의 size를 주면) into space(이론적의 메모리) required to solve the problem
2. time complexity : A function that maps problem size into time required to solve the problem.
e.g sorting problem - > 이것의 이해도가 Data structure를 얼마나 이해 했느냐를 알 수 있다.
Asymptotic Time Complexity (기사 시험 단골 문제) : 점근 시간 복잡도
limiting behavior of the complexity of size increases
입력 데이터 수를 n이라고 하고 시간 복잡도를 표현할 때 n이 무한히 큰 경우로 국한 시킨다. 입력 크기(n)를 무한히 크다고 가정한 후 함수 값을 비교해 보면 logn<n<nlogn<n²<n³<n!<2ⁿ 이다. 따라서 logn의 복잡도를 가진 알고리즘이 다른 알고리즘에 비해 효율성이 좋다고 할 수 있다.
( Big Oh notation -빅오 표기법 / Ω(Omega) notation / Θ(theta) notation / little oh notation / ω(little omega) notation 이 있다.)
(참고자료 : http://daisuki_.blog.me/140099551701 )