알고리즘 복잡도 측정

하나의 문제를 해결하는 여러 알고리즘이 존재할 수 있습니다. 그리고, 개발자는 성능을 평가하여 하나를 결정해야 합니다. 이때, 코드가 실행될 때 걸리는 정확한 시간을 측정하는 방법으로 속도를 비교할 수 있습니다. 하지만, 실행 시간은 기계에 의존적이며 대안으로 나온 알고리즘들이 모두 짧은 시간 내로 수행되어 비교가 어려울 수 있습니다.

이러한 경우, 직접 속도를 측정하는 것이 아닌 컴퓨터가 처리해야 하는 연산의 수를 세는 것이 나은 방법일 수 있습니다.

✔️ 시간 복잡도 (Time Complexity)

특정 입력을 기준으로 개략적인 연산의 수를 계산하여 알고리즘의 속도를 평가하는 척도로 사용합니다.

✔️ 공간 복잡도 (Space Complexity)

특정 입력을 기준으로 알고리즘의 메모리 사용량을 평가하는 척도로 사용합니다.

✔️ 빅오(Big-O) 표기법

복잡도를 표현하는 표기법 중 하나로 불필요한 상세를 무시하고 필수적인 부분에 집중하는 점근적 표기법을 따릅니다. 빅오 표기법은 O(n) 형식으로 어떤 함수의 입력 값에 따라 알고리즘의 실행 시간 및 공간 사용량이 어떻게 변하는지를 설명합니다. 빅오 표기법의 예시는 다음과 같습니다.

// n이 입력되면 n번 루프가 반복되므로, O(n)으로 표기합니다.
for (int i = 0; i < n; i++) { ... }

// 아래 루프는 O(n)으로 표기합니다. n이 무한에 가까울 수록 k가 의미가 없기 때문입니다. (상수항과 계수 무시)
int k = 5;
for (int i = 0; i < n * k; i++) { ... }

// 입력값인 n과 m이 독립적이라면 빅오는 더할 수 있습니다. O(n + m)으로 표기합니다.
for (int i = 0; i < n; i++) { ... }
for (int i = 0; i < m; i++) { ... }

// 빅오는 곱해질 수 있습니다. O(n^2)으로 표기합니다.
for (int i = 0; i < n; i++) {
  for (int j = 0; j < n * 5; j++) {}
}

// 가장 큰 항 외에는 무시할 수 있습니다. O(n^2)로 표기합니다.
for (int i = 0; i < n; i++) {}

for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j++) {}
}

Loading comments...