알고리즘이란?

문제 해결을 위한 단계들을 체계적으로 명시한 것.
계산을 위한 절차들.

---

알고리즘의 5가지 중요한 특징

유한성(finiteness)

알고리즘은 단계들을 반드시 유한한 횟수로 거친 후에 종료해야 한다.

명확성(definiteness)

알고리즘의 수행 과정은 명확하고 모호하지 않은 명령어로 구성되어야 한다.

입력(input)

알고리즘은 외부에서 제공되는 자료가 0개 이상 존재 또는 그 이상의 입력들을 가진다.

출력(output)

알고리즘은 하나나 그 이상의 출력들을 가진다.
(모든 입력에 하나의 출력이 나오면 안된다.)

효과성(effectiveness)

효과적이라는 말은,
이론적으로 알고리즘의 모든 연산들이 사람이 종이와 연필을 이용해서 유한한 시간 안에 정확하게 수행할 수 있을 정도로 충분히 단순해야 한다는 의미이다.

(모든 과정은 명백하게 실행 가능(검증 가능) 한 것이어야 한다.)

---

선형시간(linear time)알고리즘

선형 알고리즘은 먼저 초기화가 필요하다.

다음으로, 각 항목을 차례로 검사하고, 항목에 대해 간단한 계산을 수행한다.

수를 세거나, 이전 값과 비교하거나, 간단한 방식으로 변환하거나 출력한다.

마지막에는 작업을 끝내기 위한 어떤 단계가 필요하다.
(ex: 평균을 계산, 합계, 가장 큰 키를 출력하는 것)

각 항목에 대한 연산에 거의 같은 시간이 걸린다면 소요되는 전체 시간은 항목의 수에 비례한다.