*시간 복잡도(Time Complexity) 는 알고리즘의 절대적인 실행 시간을 나타내는 것이 아닌 알고리즘을 수행하는데 연산들이 몇 번 이루어지는 지를 숫자로 표기합니다.*
여기서 연산의 종류는 산술, 대입, 비교, 이동을 말합니다.
그런데 연산의 실행 횟수는 보편적으로 그 값이 변하지 않는 상수가 아니라 입력한 데이터의 개수를 나타내는 n에 따라 변하게 됩니다.
연산의 개수를 입력한 데이터의 개수 n의 함수로 나타낸 것을 시간 복잡도 함수라고 말하며, 수식으로는 T(n) 이라고 표기합니다.
양의 정수 n을 n번 더하는 계산을 진행한다고 가정해봅시다.
n X n 을 계산하는 것과 n개를 n번 더한 것을 계산하는 등 여러 방법이 있습니다.
/* Case 1 */
let sum = n * n; // 대입 1, 곱셈 1
/* Case 2 */
let sum = 0; // 대입 1
for(let i = 1; i <= n; i++) {
sum = sum + n; // 대입 n, 덧셈 n
}
/* Case 3 */
let sum = 0; // 대입 1
for(let i = 1; i <= n; i++) { // A
for(let j = 1; j <= n; j++) { // B
sum = sum + 1; // A : 대입 n, 덧셈 n
// B : 대입 n, 덧셈 n
}
}
위 3개의 알고리즘의 연산 횟수를 비교해보면 아래와 같이 나타낼 수 있습니다.
(간단하게 확인하기 위해 루프 제어 연산은 제외합니다.)
| 연산 종류 | Case 1 | Case 2 | Case 3 |
|---|---|---|---|
| 대입 연산 | 1 | n + 1 | n * n + 1 |
| 덧셈 연산 | n | n * n | |
| 곱셈 연산 | 1 | ||
| 나눗셈 연산 | |||
| 전체 연산 횟수 | 2 | 2n + 1 | $2n^2 + 1$ |
곱셈 연산은 덧셈 연산보다 시간이 더 소요되지만 동일하다고 가정할 경우라도 위 3개의 알고리즘을 비교할 수 있습니다.
하나의 연산이 t만큼의 시간이 필요하다고 가정한다면
*Case 1의 경우는 2t 만큼의 시간이 필요하고*
*Case 2의 경우는 (2n + 1)t 만큼의 시간, 마지막으로*