복잡도(시간복잡도, 공간복잡도, Big-O 표기법)

복잡도

 

복잡도는 시간복잡도와 공간복잡도로 나뉘어지며 주로 Big-O표기법을 이용해 나타냄

 

 

시간복잡도

 

시간복잡도란 입력값에 대해 어떠한 알고리즘이 실행되는데 걸리는 시간을 의미함

하지만 코드가 실행되는데 걸리는 정확한 시간을 의미하는것이 아니고, 주요로직의 반복횟수를 중점으로 측정함

 

즉 몇초가 걸리는 코드인지 측정하는 것이 아니고, 주요 로직이 몇회 반복되냐를 측정하는 것

 

for(int i = 0; i < m; i++){
	for(int j = 0; j < m; j++){
		cout << '*';
	}
}

for(int i = 0; i < m; i++){
	for(int j = 0; j < m; j++){
		cout << '*';
	}
}

for(int k = 0; k < n; k++){
	cout << '*';

예를들어 위 코드는 첫 번째 for문에서 m²회 반복되고, 두 번째 for문에서 m²회 반복되고, 세 번째 for문에서 n회 반복되므로 총합 2m² + n회 반복된다고 할 수 있음

즉 시간복잡도가 2m² + n인 것

하지만 아래 내용에 있는 Big-O 표기법으로 나타낸다면 O(m²) 

 

 

공간복잡도

 

공간복잡도란 입력값에 대해 어떠한 알고리즘이 실행되는데 필요한 메모리 공간의 양을 의미함

정적변수부터 array나 map이나 재귀함수호출로 인한 스택 등 메모리 공간을 사용하는 경우 모두 포함해서 계산함

 

int arr[10000000];

int main()
{
	int arr2[1234];
}

위와 같은 코드가 있다면 4바이트 변수가 10,001,234개 있으므로 40,004,936(40MB) 공간복잡도라고 할 수 있음

 

즉 문제풀이에서 아래와 같이 128MB로 메모리가 제한되어 있다면?

128MB = 128,000,000이므로 int형 변수 32,000,000개까지 사용할 수 있다는 뜻이고 

int n[32000000]보다 적은 공간을 쓴다면 메모리 걱정은 없다는 뜻

또한 메모리제한보다 더 큰 메모리가 필요하다면 다른 알고리즘을 고려해야 한다는 뜻

 

공간복잡도의 Big-O표기법은 만약 N개의 int형 변수가 필요하다면 4N바이트의 변수가 필요하게 되고 

O(4N)이지만 상수는 생략하므로 그냥 O(N)이 됨

 

 

Big-O 표기법

 

같은 알고리즘을 사용해도 입력값이 달라지면 수행시간이 바뀔 수 있음

 

예를들어 정렬 알고리즘의 경우
{2, 1, 3, 4, 5} 형태의 입력이 주어진다면 2와 1만 바꾸면 끝나니 엄청 빠르다
반면 

{5, 4, 3, 2, 1} 형태의 입력이 주어진다면 상대적으로 훨씬 느려진다

위처럼 입력값에 따라 수행 시간이 달라지는데 이 중 "최악의 상황"일 때 걸리는 시간을 가정하며

또한 컴퓨터 사양이나 상황 등에 따라 결과가 매번 다를 수 있으니

정확한 시간을 측정하는 목적이 아닌 주요로직의 반복횟수에 따른 시간소요의 경향성에 대해 표기하는것이 Big-O표기법

 

Big-O표기법

- 상수항은 무시한다. 예를들어 for문안에서 if를 사용하면 O(n+1)이라고 하지 않고 상수항을 무시해서 O(n)으로 취급

- 여러번 반복해도 배수를 붙이지 않는다. 예를들어 별도의 for문이 2개 있으면 O(2n)이 아니라 그냥 O(n)으로 취급

- 영향력이 낮은 항은 무시한다. 예를들어 O(n²)인 이중for문과, 별도의 O(n)인 하나의 for문이 있을 경우 O(n²+n)이 아니라  O(n²) 취급

- 단, O(nlogn)의 경우 n이 logn보다 영향력이 크지만 logn을 무시하지 않고 nlogn으로 표기하는 듯 함

- 위처럼 간략하게 나타내는 이유는 정확한 실행 시간을 예측하는 것이 아니라 자료의 수가 증가함에 따라 소요시간이 얼마나 증가하는지 나타내기 위한 방법이기 때문

 

Big-O 표기법 예시

 

1. O(1)

상수시간 시간복잡도라고 부르며, 상수시간 시간복잡도는 입력크기와 상관없이 일정한 시간복잡도를 가지는것을 말함

 

  1) 입력과 출력(cin, cout)

  2) 단순연산( num *= 2; )

  3) 배열의 인덱스 참조( arr[0] )

  4) 간단한 if문

    if(n&1) cout << "홀수";

    else cout << "짝수";

 

위의 4번 예시 if문에서 만약 n이 홀수인 경우 한단계에 거쳐 끝나고, 짝수인 경우 두단계에 거쳐 끝나지만
이 둘의 차이는 아래 예시들에 비해 터무니없이 작은 차이라 둘 다 O(1)로 처리한다

 

2. O(n)

반복문을 이용해 n번 반복하는 것이 O(n)
n의 값에 따라 처리수가 1:1로 비례해서 늘어남

 

3. O(n²)

반복문이 두번 겹쳐져있는 이중 for문은 O(n²)가 된다

 

4. O(n³)

반복문이 세번 겹치면 O(n³)이고 몇번 겹치냐에 따라 제곱수가 늘어나는 방식

 

5. O(nm)

이중 for문이지만 밖 for문은 n회반복, 내부 for문은 m회 반복

 

6. O(2ⁿ)

피보나치 수열에서

fibonacci(n)을 호출하면 fibonacci(n-1)과 fibonacci(n-2)가 호출되므로 

호출이 2회 일어나게 되고 이게 n번 반복되므로 2의 n제곱

 

7. O(logn)

이진 탐색 기법의 경우 탐색을 해나갈수록 탐색해야 할 데이터가 절반으로 떨어져가기 때문에

O(logn)가 된다.

 

※ 시간복잡도간 비교

n! > 2ⁿ > n² > nlogn > n > logn > 1

 

※ log 계산법

logN은 밑에 10을 생략한것이며 logab = c라면 a^c = b와 같이 계산한다.
즉 N = 10000이라면 10의 몇승이 10000인가를 계산하므로 log10000은 4가 된다.

 

 

시간복잡도 계산법

 

O(n)의 대략적인 소요시간은 n의 값이 1억당 1초정도라고 한다.  
즉 n이 10^8이라면 대략적으로 1초가 걸린다고 생각하면 된다.

그러므로 문제 조건이 1초이내에 해결이라면 n의 값에 따라 아래와 같이 알고리즘을 선택할 수 있다.
n <= 20 -> O(n!) : 순열, O(2^n): 브루트포스
n <= 100 -> O(n^3) : 플로이드-와샬
n <= 1000 -> O(n^2) : 벨만 포드
n <= 10000 -> O(n)은 10000, O(nlogn)은 40000이 걸림
: 동적 프로그래밍, 이분 탐색, 다익스트라 알고리즘, 유니언 파인드, 세그먼트 트리, 투 포인터
n <= 10^8 -> O(logn) : 수학적 기믹이 필요해짐, 유클리드의 호제법

즉 문제의 입력 제한과 시간 제한을 꼭 확인하고 알고리즘을 짜기 시작해야 다 짜고나서 시간초과가 뜨는 시간낭비를 막을 수 있다.