[알고리즘] 알고리즘이란

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

◆알고리즘의 특성

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

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

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

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

◆알고리즘의 표현 방법 

말로 표현 :

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

다음 카드의 

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

ex)

max=A[0] for i = 1to9 if(A[i]>max)max=A[i] return max

◆여러가지 알고리즘

#해결방식에 의한 알고리즘 분류

-분할 정복 알고리즘

-그리디 알고리즘

-동적 계획 알고리즘

-근사 알고리즘

-백트래킹 기법

-분기 한정 기법

-기타 등등

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

#문제에 기반한 알고리즘

-정렬 알고리즘

-그래프 알고리즘

-기하 알고리즘

-기타 등등

◆알고리즘의 효율성 표현

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

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

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

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

-최악의 경우 

-평균의 경우

-최선의 경우

#복잡도의 점근적 표기

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

점근적 표기의 세가지

-빅오 표기법

-빅 오메가 표기법

-빅 세타 표기법

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