시간복잡도

복잡도는 시간복잡도와 공간복잡도로 나뉘어지는데 먼저 시간 복잡도에 대해 알아봅시다.

 

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

 

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

그래서 시간복잡도를 설명할 때는 시간이 아니라 어떤 알고맂므이 주어진 입력 크기를 기반으로 어떤 로직이 몇번 반복했는가를 중점으로 설명합니다. 

 

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

for(int i = 0; i < 10; i++) // 10번
{
	for(int j = 0; j < n; j++) // n번
    {
    	for(int k = 0; k < n; k++) //n번
        {
        	if(true)
            { cout << i << '\n'; } // 단순한 로직
        }
    }
}

// 10 * n ^ 2

위와 같은 로직이 반복되는 횟수는 

 

10 * n * n, 즉 10 n^2 

 

이것이 바로 시작복잡도입니다.

 

빅오표기법 (Big-O Notation)

앞의 코드는 다음과 같은 시간복잡도를 갖는다고 했습니다. 

10n^2 

이를 빅오 표기법으로 나타내면 다음과 같습니다. 

 

O(n^2)

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

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

 

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

10n^2 + n

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

 

n도 신경써야 하지 않나요? 라고 생각할 수 있지만 입력 크기가 커질 때의 연산이 커지는 것이 무엇인지 다시 생각해봅시다.

예를 들어 ndl 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 순입니다. 

빅오 표기법 그래프

2^n -> 2 4 8 16 32

n! -> 1 2 6 24 120

n -> 1 2 3 4 5

이 예시와 같이 복합도에 가장 영향이 큰 항만을 표기하는 방법입니다.

 

상수시간 시간복잡도 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};

 

예시로 확인하는 상수시간 시간복잡도

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;
}

위 코드가 몇번이나 반복되는지 디버깅을 통해 확실하게 알아봅시다. 

#include <bits/stdc++.h>
using namespace std; 

int n, cnt ;
int main()
{
	cin >> n;
    int a = 0;
    for(int i = 0; i < n; i++)
    {
    	for(int j =0; j < i; j++)
        {
        	a += i + j;
            cnt++;
        }
    }
    cout << a << '\n';
    cout << " cnt : " << cnt << '\n';
    return 0;
}

n = 3, 4, 5, 6 

cnt = 3, 6, 10, 15  

i = 1 일 때 j  = 0

i  = 2, j = 0, 1 

i  = 3, j = 0, 1, 2

i  = 4, j = 0, 1, 2, 3

이를 노트에 그려보면 

 

 

j 는 선이 그어진 값 미만까지 가질 수 있습니다. 

 

잠시 사각형의 넓이를 생각해봅시다. 

위와 같이 점의 갯수가 아닌 너비라고 생각했을 때 사각형을 이루는 점의 갯수를 너비처럼 구할 수 있습니다. 

즉 위 코드의 시간복잡도는 사각형의 절반이기 때문에 n^2 의 절반, 즉 1/2n^2 인데, i 주대각 성분이 빠진 i 미만이기 때문에 1/2(n^2 - n) 의 시간복잡도를 갖습니다. 

 

이를 빅오표기법으로 표기하자면 가장 영향이 큰 n^2항만 남아  시간복잡도 O(n^2) 를 갖는다고 할 수 있습니다.

 

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

 

#include <bits/stdc++.h>
using namespace std;
int N, M;

void solve(int N, int M)
{
	int a = 1;
    for(int i = 0; i < N; i++)
    {
    	a*= i;
    }
    for(int j = 0; j < M; j++)
    {
    	a *= j; 
    }
    cout << a << "\n";
}

int main()
{
	cin >> N >> M;
    solve(N, M);
    return 0;
}

 

입력값이 두 개 들어와도 당황하지 않고 나열한다고 생각하면 됩니다. 

중첩되지 않고 나열되어 있으면 N + M 라고 판단합니다. 

만약 2중 for문이라면 N * M 로 판단합니다. 

만약 중첩과 나열이 겹쳐져 있다면 N^2 + N + M^2 + M 반복횟수를 갖는다면 빅오 표기법의 표기방식은 N^2 + M^2 가 됩니다.

 

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

#include <bits/stdc++.h>
using namespace std;

int n, a[1004]; 
int go(int l, int r)
{
	if(l == r)
    	return a[l];
        int mid = (l + r) / 2;
        int sum = go(l, mid) + go(mid + 1, r);
        return sum;
}

int main()
{
	cin >> n;
    for(int i = 1; i <= n; i++)
    {
    	a[i - 1] = i;
    }
    int sum = go(0, n-1);
    cout << sum << '\n';
    return 0;
}
// 입력 10

// 출력 45

시간복잡도는 단순히 몇 번 반복되느냐를 판단해 식으로 만들고 빅오로 표기하는 방식입니다. 

재귀함수가 몇 번 호출되는지가 이 코드의 시간복잡도를 결정할 것 입니다.

아래처럼 디버깅하기 위한 코드를 추가하면서 직접 확인해봅시다.

#include <bits/stdc++.h>
using namespace std;

int n, a[1004], cnt; 
int go(int l, int r)
{
	cnt++;
	if(l == r)
    	return a[l];
        int mid = (l + r) / 2;
        int sum = go(l, mid) + go(mid + 1, r);
        return sum;
}

int main()
{
	cin >> n;
    for(int i = 1; i <= n; i++)
    {
    	a[i - 1] = i;
    }
    int sum = go(0, n-1);
    cout << sum << '\n';
    cout << "cnt : " << cnt << "\n";
    return 0;
}
// 입력 10

// 출력 45

n이 10일 때  cnt 는 19가 나옵니다. 

n이 5일 때 cnt 는 9가 나옵니다. 직접 손으로 그려서 재귀함수를 표현해보겠습니다. 

위 이미지처럼 2n-1 을 추론할 수 있고 빅오표기법으로 오더N, 즉 O(n)이라는 시간복잡도를 갖는 걸 알 수 있습니다.

 

디버깅을 이용해 어림잡는 방법이 아니라, 점화식을 만들고 시간복잡도를 계산하는 방식은 어렵지만 이 방법에 대해 정리해보고자 합니다.

이 방법은 코딩테스트나 알고리즘에 무조건적으로 구해야하는 것이 아니라 필요에 따라 어림잡아 계산할지 판단해야합니다. 

 

예를 들어 n 이 4일 때 함수가 몇 번 호출되는지 판단합니다. 이미지를 첨부하겠습니다.

다음 포스팅에서 예제코드를 통해 시간복잡도를 계산하는 방법을 이어 작성하겠습니다.