해당 포스팅은 알고리즘에 대한 첫 포스팅이므로 알고리즘에 대한 이론을 다루는 포스팅 입니다.

대학교 강의(단국대학교) 수업을 강의 한후 작성한 포스팅이고 ,해당 포스팅에선 예시코드를 제시하지 않았습니다.



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 )

 

+ Recent posts