알고리즘 기초 정리 정확성과 효율성

알고리즘

컴퓨팅은 입력을 받아 그 입력을 처리한 후 출력하는 과정입니다.

알고리즘은 입력에서 받은 자료를 출력형태로 만드는 처리 과정을 뜻합니다.

즉, 알고리즘이란 입력값을 출력값의 형태로 바꾸기 위해 어떤 명령들이 수행되어야 하는지에 대한 규칙들의 순서적 나열입니다. 

이런 알고리즘 순서 나열에 따라 종류도 달라지고 출력값에 도달하는 시간도 달라지게 됩니다.

정확한 알고리즘(정확성)

알고리즘은 입력을 출력으로 바꾸기 위해 컴퓨터가 따르는 일련의 절차입니다.

알고리즘은 우리 일상생활 언어로도 표현할 수 있습니다.

예를 들면,

(예시1)국어사전에서 '이발소'를 찾는 일을 한다고 합시다. 

여기서 하나의 방법으로 첫 페이지를 펼 처서 '이발소'가 없다면 다음페이지로 넘어갑니다. 다음 페이지에서도 '이발소'가 없다면 또 다음 페이지로 넘어갑니다. 이러한 방식을 통해 '이발소'를 찾을 때까지 이것을 반복합니다. 

이 알고리즘은 정확합니다. '이발소'가 국어사전에 있다면 이 알고리즘을 사용한 사람은 '이발소'를 찾는데는 성공할 것입니다.

위 알고리즘의 예시는 정확성은 뛰어나지만 효율성이 뛰어나지는 않습니다.

만약 위 예시와 다르게 한 번에 두페이지씩 넘긴다면 좀 더 효율성은 좋아지나 정확성이 떨어질 수 있습니다.

효율적인 알고리즘(효율성)

효율성은 작업을 완료하기까지 얼마나 시간과 노력을 덜 들일 수 있는지에 대한 척도입니다.

위 예시에 대해 더 직관적이고 효율적인 알고리즘이 뭐가 있을지 생각해봅시다.

(예시 2) 이번에는 국어사전의 가운데를 펼쳐 '이발소'를 찾아봅시다. 만약 페이지에 '이발소'가 있다면 알고리즘은 끝이 납니다. 없다면 국어사전은 자음과 모음의 조합순으로 정렬이 되어있으므로 '이발소'가 현재페이지의 앞에 있는지 뒤에 있는지에 대해 알 수 있습니다. 그리고 남은 앞 혹은 뒷부분의 절반을 또 펼쳐보며 위의 행동을 반복합니다. 마지막 한 페이지가 남았을 때는 '이발소'가 있다면 발견할 수 있게 됩니다.

이 알고리즘은 (예시 1)의 알고리즘보다 더 효율적입니다. 

 

출처:cs50