알고리즘 정의

알고리즘은 주어진 문제를 풀기 위한 명령어를 단계적으로 나열한 것이라고 생각할 수 있다. 하지만 컴퓨터를 통한 문제를 해결한다는 측면에서 보면 알고리즘의 각 명령어(연산)들에 약간의 제한이 있어야 한다. 따라서 알고리즘은 다음 조건을 만족한다.

• 입출력 : 0개 이상의 외부 입력과 하나 이상의 출력이 있어야 한다.
• 명확성 : 명령은 모호하지 않고 단순 명확해야한다.
• 유한성 : 한정된 수의 단계를 거친 후에는 반드시 종료해야 한다.
• 유효성 : 모든 명령은 컴퓨터에서 수행 가능해야 한다.

정리하면 알고리즘은 "주어진 문제를 해결하기 위해 모호하지 않고 단순 명확하게, 컴퓨터가 수행 가능할 수 있는 유한한 명령들을 단계적으로 구성한 것"이라고 할 수 있다.

알고리즘 분석

정확성

유효한 입력, 유한 시간 ➡️ 정확한 결과 생성 여부 ❓
= 다양한 수학적 기법을 사용해서 이론적인 증명이 필요하다.

정해진 시간 내 정확한 결과를 생성해야 한다. 정확성 분석을 위해서는 다양한 수학적 기법을 사용하여 알고리즘이 예상한대로 수행되는지 증명해야 한다.

효율성

알고리즘 수행에 필요한 컴퓨터 자원의 양을 측정

• 메모리 양 ➡️ 공간 복잡도 (정적 공간+동적 공간)
• 수행 시간 ➡️ 시간 복잡도

효율적인 알고리즘이라는 것은 가능한 적은 메모리, 빠른 수행 시간을 갖는 알고리즘을 의미한다.

공간 복잡도

알고리즘 실행 후 완료까지 필요한 메모리의 총 양을 말한다. 알고리즘을 수행하기 위해 필요한 공간은 컴파일 과정에서 고정적으로 결정되는 정적 공간과 동적할당/함수호출 등과 같이 실행 시간에 동적으로 결정되는 공간으로 이루어진다.

시간 복잡도

• 알고리즘의 실제 수행시간 측정하는 것은 일반성 결여 (컴퓨터 속도, 프로그래밍 언어 등 변수 多)
• 따라서 시간 복잡도는 알고리즘의 단위 연산 수행 횟수 합으로 측정
• 입력 크기 n이 증가하면 수행 시간도 증가하므로 입력크기 n에 대한 함수 f(n)으로 표현
• 시간 복잡도에 영향을 미치는 영향은 입력 데이터의 크기, 데이터의 상태 등이 있음
• 평균 수행시간, 최선의 수행시간, 최악 수행시간 중 최악 수행시간이 일반적인 척도

알고리즘 실행 후 완료까지 걸리는 시간을 말한다. 하지만 알고리즘의 수행시간은 컴퓨터의 속도 등 변수가 많아 객관적인 판단이 어렵다. 따라서 알고리즘이 수행하는 기본적인 연산의 횟수로 시간 복잡도를 표현한다. 그런데 데이터 개수가 증가할 수록 수행 시간도 증가하므로 알고리즘의 수행시간을 단순히 단위 연산의 개수로 표현하기보다는 입력 크기 n에 대한 함수로 표현하는 것이 바람직하다.

또한 알고리즘의 수행 시간은 주어진 입력 데이터의 상태에 따라 영향을 받는다 예를 들어 어떤 정렬 알고리즘의 경우 데이터가 이미 정렬된 상태로 주어질 때 가장 빠른 수행 시간을 보이지만, 데이터가 무작위로 주어진 경우 가장 나쁜 성능을 보일 수도 있다. 따라서 알고리즘에 가장 적합한 상태로 데이터가 주어진다고 가정하면 수행시간이 가장 적게 걸리는 최선의 수행 시간을 계산할 수 있다.

하지만 알고리즘에 입력되는 데이터의 상태가 항상 최적이라고 가정할 수 없으므로 최선이 아닌 일반적인 상황에서의 수행 시간을 계산한 뒤 평균 값을 구하는 것이 필요하다. 하지만 평균 수행 시간을 계산하는 과정에서는 모든 경우의 입력상태와 그에 대한 각각의 수행시간을 알기 어려우므로, 최선이나 평균 수행시간이 아니라 최악의 수행시간을 알고리즘의 시간 복잡도를 평가하는 일반적인 척도로 사용한다. 즉, 어떤 입력이 주어지더라도 이것 이상의 수행시간은 걸리지 않는다는 것을 보장하는 것이다.