알고리즘 = 문제를 해결하는 단계적 절차 또는 방법


◆알고리즘의 특성


-정확성 : 알고리즘은 주어진 입력에 대해 올바른 해를 주어야 한다.

-수행성 : 알고리즘의 각 단계는 컴퓨터에서 수행이 가능하여야 한다.

-유한성 : 알고리즘은 일정한 시간 내에 종료되어야 한다.

-효율성 : 알고리즘은 효율적일수록 그 가치가 높아진다.



알고리즘의 표현 방법 


말로 표현 :

ex)첫 카드의 숫자를 읽고...

다음 카드의 


의사 코드 : 프로그래밍 언어와 유사

ex)



여러가지 알고리즘

#해결방식에 의한 알고리즘 분류
-분할 정복 알고리즘
-그리디 알고리즘
-동적 계획 알고리즘
-근사 알고리즘
-백트래킹 기법
-분기 한정 기법
-기타 등등



문제를 해결하는 방식은 문제의 속성과 밀접한 관계가 있으므로, 문제에 따라 알고리즘을 사용해야함


#문제에 기반한 알고리즘

-정렬 알고리즘

-그래프 알고리즘

-기하 알고리즘

-기타 등등


알고리즘의 효율성 표현


#시간복잡도와 공간복잡도 → 주로 시간복잡도가 사용됨.


시간을 측정하기 위해 컴퓨터를 사용할 수가 없음(측정하는 컴퓨터의 모든 조건이 같아야 하므로 평가가 어려움)

때문에 → 알고리즘이 수행하는 기본적인 연산 횟수를 입력 크기에 대한 함수로 표현.


#복잡도를 표현하는 세가지 방법

-최악의 경우 

-평균의 경우

-최선의 경우


#복잡도의 점근적 표기


위에서 말했듯이 연산 횟수를 입력 크기에 대한 함수로 표현하는데 이를 단순하게 표현하기 위해 점근적 표기법을 사용한다.


점근적 표기의 세가지

-빅오 표기법

-빅 오메가 표기법

-빅 세타 표기법


※ 점근적 표기법은 따로 책을 보시면서 공부하는게 도움이 될듯 싶습니다.


+ Recent posts