[알고리즘] 시간 복잡도 'Time Complexity'

시간복잡도

시간 복잡도

시간 복잡도란 알고리즘이 문제를 해결하기 위한 시간(연산)의 횟수를 말한다.

 

알고리즘을 평가하는데 있어 수행시간과 메모리 사용량을 평가기준으로 두는데, 수행시간에 해당하는 것이 "시간 복잡도(Time Complexity)" / 메모리 사용량에 해당하는 것이 "공간 복잡도(Space Complexity)" 이다.

 

연산 횟수를 카운팅 할 때 3가지 경우가 있다.

 

1. 최선의 경우 Best Case

2. 최악의 경우 Worst Case

3. 평균적인 경우 Average Case

 

평균적인 경우가 가장 이상적으로 보이겠지만 알고리즘이 복잡해질수록 평균적인 경우는 구하기가 매우 어려워진다.

그러므로, 최악의 경우로 알고리즘의 성능을 파악한다.

 

2-1 Program Step 에서 Elementary Operation 이란?

- 프로그램의 진행 정도를 나타내는 기본 단위이다.

 

1. 대입연산

2. 덧셈 / 뺄셈 / 곱셈 / 나눗셈

3. 비교구문

4. 함수호출

 

즉, 알고리즘의 실행 순서를 따라가며 Elementary Operation이 일어나는 수를 측정한다.

 

2-2 어떻게 카운팅할까?

1. 전역변수를 이용하여 Elementary Operation을 카운팅한다.

2. 각 실행문 별로 Step수와 실행 횟수를 분석한다.

 

2-2-1 전역변수를 이용하여 Elementary Operation을 카운팅

[JavaScript]

let count = 0;
function sum(list, n) {
  let tempSum = 0; // 대입연산
 
  for (let i = 0; i < n; i++) {
    count++;   // loop 한번 돌 때마다
    tempSum += list[i];
    count++;  // 대입연산
  }
  count++;  // for loop 끝날 때 한번
  count++;  // return 수행
  return tempSum;
}
 

 

2-2-2 각 실행문 별로 Step 수와 실행 횟수를 분석한다.

주어진 프로그램 2개의 성능 비교 및 분석

• 프로그램 P1의 성능 : C1 * n² + C2 *n
• 프로그램 P2의 성능 : C3 * n

 

C1, C2, C3에 따라서 대소 비교 결과가 다름

어떤 C1, C2, C3에 대해서도 C1 * n² > C3 * n 을 만족하는 n은 존재함.

 

n이 작으면 프로그램 P1의 성능이 더 좋을 수 있다.

n이 충분히 크면 항상 프로그램 P2의 성능이 좋다 (P1에는 제곱이 있기 때문에)

 

작은 경우 모두 성능이 좋으므로 문제될 것은 없다.

따라서 n이 큰 경우의 처리가 중요하다.

 

 

📚 참고

feel5ny.github.io/2017/12/09/CS_01/

알고리즘과 시간 복잡도