[알고리즘] 알고리즘이 뭐지?

안녕하세요? 코딩충입니다. 

블로그 활동을 하다가 생각해보니 알고리즘이 뭔지 설명한 적이 없는 것 같아서 이렇게 중간에 포스팅을 올립니다.

1.알고리즘이란?

 -어떤 문제를 해결하기 위한 동작들의 모임 

 -유한하다(시간적으로 공간적으로)

 -작동이 일어나게 내재하는 단계적 집합

 -연산, 데이터 진행 또는 자동화된 추론을 수행 

결론(정리): 알고리즘이란 문제를 해결하기 위한 유한성을 가지고 끝이 있는 동작(단계)들의 집합이다.

2.알고리즘의 필수 조건

-입력 : 외부에서 제공되는 자료가 0개 이상 존재해야 합니다. 

-출력 : 모든 입력에 대한 출력이 같으면 안됩니다.

-명확성 : 수행 과정은 명확하고 모호하지 않은 명령어로 구성되어야 합니다. 

-유한성 : 알고리즘의 명령어들은 끝이 있는 계산을 수행한 후에 종료해야 합니다.

-실행 가능성 : 모든 과정은 명백하게 실행 가능한 것이어야 한다.

결론(정리): (입력, 출력 제외) 끝이 있고 명확하며 실행 가능해야 한다.

3. 알고리즘의 판단 기준

-정확성 : 입력에 대해서 유한 시간내에 올바른 답을 산출하는가?

-작업량 : 알고리즘에서 수행되는 가장 중요한 연산들의 작업량의 합이 어떠한가? 너무 크지는 않는가?

-기억 장소 사용량 : 기억 장소 사용량이 어떠한가? 너무 많지는 않은가?

-최적성 : 그 알고리즘보다 더 적은 작업량으로 수행하는 알고리즘은 없는가?

결론(정리): 적은 메모리 양으로 빠르게 정확하게 할 수록 좋다.

(보통 정확성이 제일 중요하고 작업량과 기억 장소 사용량이 두번째로 중요하다)

4.시간복잡도(작업량과 동일한 의미이다)

시간복잡도의 형태에는 O(N), O(N²), O(N³), O(2ⁿ), O(n!), O(log N), O(N log N) 등 다양한 형태가 존재한다.

참고자료: 위키피디아

CONTENT & DESIGN BY 코딩충