[C++/ Algorithm] 시간복잡도, 공간복잡도

#1. 시간복잡도

복잡도는 시간복잡도와 공간복잡도로 나누어지는데 먼저 시간복잡도에 대해 알아보겠습니다.

 

시간복잡도란 입력크기에 대해 어떠한 알고리즘이 실행되는데 걸리는 시간이며 주요로직의 반복횟수를 중점으로 측정됩니다.

 

아니 시간이라고?

그렇다면 시간복잡도를 측정하기 위해서 항상 시간을 재야 할까요?

만약 어떠한 로직이 있고 그 로직이 걸리는 시간을 재려면 이렇게 재야 합니다.

 

console.time("test")
let sum = 0;
for (let i = 0; i < 1000000; i++) {
	sum += 1;
}
console.timeEnd("test")

// test: 1.575ms
// java코드임

 

하지만 이러한 시간이라는 것은 컴퓨터 사양 등 여러가지 요소에 영향을 받곤 합니다.

그래서 시간복잡도를 설명할 때는 시간이 아니라 어떠한 알고리즘이 주어진 입력크기를 기반으로 로직이 몇번 반복되었는가를 중점으로 설명합니다.

 

예를 들어 다음코드는 어떠한 시간 복잡도를 가질까요?

 

for (int i = 0; i < 10; j++) { // 10번 반복
	for (int j = 0; j < n; j++) { // n번 반복
    		for (int k = 0; k < n; k++) { // n번 반복
				if (true) cout << i << "\n"; // (상수 시간복잡도의 단순 로직)
        }
    }
}



for (int i = 0; i < n; i++) {
	if (true) cout << i << "\n";
}


// 10 n ^ 2 + n 을 반복

 

10n ^ 2 + n의 시간복잡도를 가집니다.

---

#2. 빅오표기법

앞의 코드의 시간복잡도를 빅오 표기법으로 나타내면 다음과 같습니다.

 

O(n^2)

 

빅오 표기법(Big - O notation) 이란 복잡도에 가장 영향을 많이 끼치는 항의 상수인자를 빼고 나머지 항을 없애서 복잡도를 나타내는 표기법입니다.

​

참고로 다른 표기법들도 있지만 가장 많이 쓰이는 것은 빅오표기법입니다.

​

예를 들어 다음과 같은 시간복잡도에서 복잡도에 가장 많은 영향을 끼치는 항은 무엇일까요?

10 n^2 + n​

바로 n의 제곱항이고 다른 것은 그에 비해 미미하기 때문에 이것만 신경쓰면 된다는 것입니다.

​

아니, n도 신경써야 되지 않나요? 라고 생각할 수 있지만 입력크기가 커질 때의 연산이 커지는 것을 볼까요?

예를 들어 n이 1, 3, 9, 12로 증가한다고 할 때 n ^ 2은 1, 9, 81, 144로 증가하죠? n ^ 2이 월등히 크게 증가하는 것을 볼 수 있습니다.

​

​

예를 들어서 10 * n ^2 + n^ 2정도의 시간복잡도를 빅오표기법으로 표현하면 어떻게 될까요? n^2이 되게 됩니다.

​

자 다음 그림을 외워볼까요? 이를 외우고 있어야 나중에 빅오표기법을 나타낼 때 쉽게 표현할 수 있습니다.

n! > 2 ^ n > n ^2 > nlogn > n > logn > 1 순입니다.

​

 

---

상수시간 시간복잡도 O(1)

---

상수시간 시간복잡도는 입력크기와 상관없이 일정한 시간복잡도를 가지는 것을 말하며 O(1)의 시간복잡도를 씁니다.

​

예를 들어 다음과 같은 부분들이 모두 O(1)의 시간복잡도를 가집니다.

​

• 입력과 출력 

ex) cin, cout, scanf, printf

​

• 곱하기

a[2] *= 2;

이외에도 곱하기, 나누기, 나머지연산, 빼기 등은 O(1)을 가집니다.

​

• 간단한 비교 if문

if(a[2] == 2)

 

• 배열의 인덱스 참조

int a[3] = {1, 2, 3};
int b = a[2];

---

문제로 연습하는 시간복잡도

---

자 그러면 문제를 통해 배워보도록 하겠습니다.

 

Q1. 다음 코드의 시간복잡도는?

#include<bits/stdc++.h>
using namespace std; 
int n;
int main(){
	cin >> n; 
	int a = 0;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < i; j++){
			a += i + j; 
		}
	}
	cout << a << '\n';   
	return 0;
}