🌹 정리 by 장미(https://velog.io/@newbiekim/)

프로그램을 만들 때 우리는 다양한 알고리즘을 사용한다.

예를 들어, 정수를 오름차순으로 정렬하는 프로그램을 만든다고 가정하면 버블 정렬, 삽입 정렬, 퀵 정렬 등 여러 가지 알고리즘을 사용할 수 있다.

결과는 같지만 어떤 알고리즘을 쓰느냐에 따라서 과정이 달라진다. 즉, 알고리즘마다 성능도 제각각 다르다.

이 때 우리는 가장 좋은 성능을 발휘하는 알고리즘을 사용하고 싶을 것이다. 아니, 사용해야 한다.

가장 좋은 알고리즘을 고르기 위해선 효율성을 따져야 한다.

1. 시간적 효율성 → 이 알고리즘이 얼마나 빠른지 → 시간 복잡도
2. 공간적 효율성 → 이 알고리즘이 메모리를 얼마나 차지하는지 → 공간 복잡도

같은 데이터를 입력해도, 알고리즘마다 수행하는 시간이 다르고 차지하는 공간이 다르다.

보통은 공간 복잡도보다 시간 복잡도를 더 우선시한다. (기술력이 점점 좋아져서 메모리의 성능이 좋아지고 있기 때문에 우리는 시간 복잡도를 더 우선으로 고려하면 된다.)

알고리즘의 속도는 입력 데이터가 n개일 때 CPU의 연산 횟수로 판단한다. (알고리즘의 속도에 영향을 미치는 것은 여러 이유가 있겠지만 가장 큰 원인은 연산 횟수이다.)

→ 입력 데이터의 양이 다르다면 당연히 데이터가 많은 쪽이 더 오래 걸린다. 그러므로 데이터는 똑같이 n이라 가정하고 연산 횟수로 비교한다.