본질적인 관점#

알고리즘은 본질적으로 주어진 입력(input)에 대해 출력(output)을 반환하는 계산 절차(computational procedure)다.
주어진 입력에 대해, 특정 출력값이 나오도록 연산들을 순서대로 나열한 거라고 이해하면 됨.

기능적인 관점#

어떤 입력에 대해 특정 출력을 요구하는 문제를 계산 문제(computational problem)라고 함.
따라서 알고리즘은 기능적인 관점에서 이러한 계산 문제를 푸는 도구로 볼 수 있는 것.

알고리즘을 공부할 때#

두 가지 관점에서의 정의를 정리하면 알고리즘은 문제에 대한 풀이 절차다.

보통 알고리즘을 공부할 때 절차(procedure)에 집중하게 되는데
이 절차가 어떤 문제를 위한 것인지 또한 중요하게 생각해야 한다.

지금 내가 쓰는 알고리즘이 어떤 문제에 대한 풀이인지 기억하자는 거다.

정확성 (Correctness)#

주어진 입력에 대해 올바른 출력을 반환하는가.

당연한 소리 같지만, 알고리즘이 모든 입력에 대해 정확하게 동작한다는 걸 어떻게 증명할 것인가는 별개의 문제다.
대표적인 증명 도구로 루프 불변식(Loop Invariant)이 있는데, 이건 삽입 정렬 포스팅에서 자세히 다룬다.

효율성 (Efficiency)#

정확한 출력을 내더라도, 시간이 너무 오래 걸리거나 메모리를 너무 많이 쓰면 쓸모가 없다.

같은 문제를 푸는 알고리즘이 여러 개 있을 때, 어떤 게 더 효율적인지 비교할 수 있어야 한다.
이게 알고리즘 분석(Analysis)의 핵심이다.

시간 복잡도 (Time Complexity)#

알고리즘이 얼마나 빠른가. 단, 여기서 “빠르다”는 실제 실행 시간(초)이 아니다.

실행 시간은 하드웨어, 언어, 컴파일러 등에 따라 달라지기 때문에 기계 독립적인 척도가 필요하다.
그래서 입력 크기 n에 따른 연산 횟수를 기준으로 삼는다.

공간 복잡도 (Space Complexity)#

알고리즘이 메모리를 얼마나 쓰는가.

시간 복잡도와 같은 방식으로, 입력 크기 n에 따른 메모리 사용량으로 측정한다.

보통 시간 복잡도를 더 중요하게 따지는데, 메모리는 늘릴 수 있어도 시간은 되돌릴 수 없기 때문이다.
물론 메모리 제약이 빡빡한 상황에서는 공간 복잡도도 중요해진다.

Big-O (O) — 상한#

$O(g(n))$: 최악의 경우에도 $g(n)$보다는 빠르다 (이보다 느려지진 않는다)

상한만 알아도 충분한 경우가 있다. “이 알고리즘은 아무리 느려도 $O(n^2)$이다” — 이것만으로도 쓸지 말지 판단할 수 있으니까.

Big-Omega (Ω) — 하한#

$\Omega(g(n))$: 아무리 빨라도 $g(n)$보다는 느리다 (이보다 빨라질 수 없다)

하한이 정해진 경우, 더 최적화할 여지가 있는지 판단할 수 있다.

Big-Theta (Θ) — 딱 그 증가율#

$\Theta(g(n))$: 정확히 $g(n)$의 속도로 증가한다

O로 상한을 잡고, Ω로 하한을 잡고, 양쪽을 좁혀갔을 때 둘이 만나는 지점이 Θ다.
가장 정확한 표현이기 때문에 보통 복잡도를 말할 때는 Θ를 쓰는 게 맞지만, 관습적으로 O를 많이 쓴다.

주요 복잡도 클래스#

n이 커질수록 클래스 간 차이는 극적으로 벌어진다.