시간복잡도 big-O big-Ω big-θ 공간복잡도

시간복잡도

O(big-O)

시간의 상한을 나타낸다. 배열의 모든 값을 출력하는 알고리즘은 O(N)으로 표현할 수 있지만, 이 외에 N보다 큰 big-O 시간으로 표현할 수도 있다. 예를 들어, O(N^2), O(N^3), O(2^N)도 옳은 표현이다. 다시 말해 알고리즘의 수행 시간은 적어도 이들 중 하나보다 빠르기만 하면 된다. 따라서 big-O 시간은 알고리즘 수행 시간의 상한이 되고, 이는 '작거나 같은' 부등호와도 비슷한 관계가 있다.

Ω(big-Ω)

등가 개념 혹은 하한을 나타낸다. 배열의 모든 값을 출력하는 알고리즘은 Ω(N) 뿐만 아니라 Ω(logN) 혹은 Ω(1)로도

표현할 수 있다. 결국 해당 알고리즘은 Ω 수행시간보다 빠를 수 없게 된다.

θ(big-θ)

θ는 O와 Ω 둘 다 의미한다. 즉, 어떤 알고리즘의 수행시간이 O(N)이면서 Ω(N)이라면, 이 알고리즘의 수행시간을 θ(N)로 표현할 수 있다.

공간복잡도

공간복잡도는 시간복잡도와 평행선을 달리는 개념이다. 크기가 n인 배열을 만들고자 한다면, O(n)의 공간이 필요하다. n * n 크기의 2차원 배열을 만들고자 한다면, O(n^2)의 공간이 필요하다.

 

/*
다음 코드는 O(n) 시간과 O(n) 공간을 사용한다.
 
호출될 때마다 스택의 깊이는 깊어진다.
sum(4)
 -> sum(3)
   -> sum(2)
     -> sum(1)
       -> sum(0)
*/
int sum(int n)
{
    if (n <= 0)
    {
        return 0;
    }
    return n + sum(n - 1);
}

 

/*
0과 n 사이에서 인접한 두 원소의 합을 구하는 아래 함수.
 
이 코드는 pairSum 함수를 대락 O(n)번 호출했지만, 이 함수들이 호출 스택에 동시에 존재하지는 않으므로 O(1) 공간만 사용한다.
*/
int pairSumSequence(int n)
{
    int sum = 0;
 
    for (int i = 0; i < n; i++)
    {
        sum += pairSum(i, i + 1);
    }
 
    return sum;
}
 
int pairSum(int a, int b)
{
    return a + b;
}

예제

[ 예제 4 ]

/*
예제 4 
 
arrayA의 원소 하나당 안쪽 for 루프는 b(=arrayB.length)회 반복된다. 따라서 a(arrayA.length) 일 때 수행시간은 O(ab)가 된다.
 
서로 다른 두 개의 입력이 주어지므로 O(N^2)이라고 말하면 안된다. 두 배열의 크기를 모두 고려해야 한다.
*/
void printUnorderedPairs(int[] arrayA, int[] arrayB)
{
    for (int i = 0; i < arrayA.length; i++)
    {
        for (int j = 0; j < arrayB.length; j++)
        {
            if (arrayA[i] < arrayB[j])
            {
                System.out.println(arrayA[i] + "," + arrayB[j]);
            }
        }
    }
}

 

[ 예제 7 ]

다음 중 O(N)과 같은 것들은 무엇인가? 왜 그렇게 생각하는가?

 

• O(N+P), P < N/2 일 때
• O(2N)
• O(N+logN)
• O(N+M)

----------------------------------------

• 만약 P < N/2이라면, N이 지배적인 항이므로 O(P)는 무시해도 괜찮다.
• O(2N)에서 상수항은 무시할 수 있으므로 O(N)과 같다.
• O(N)이 O(logN)보다 지배적인 항이므로 O(logN)은 버려도 된다.
• N과 M 사이에 어떤 연관 관계도 보이지 않으므로 여기에선 두 변수 모두를 표시해줘야 한다.

따라서 마지막을 뺀 나머지는 모두 O(N)과 같다.

 

[ 예제 8 ]

여러 개의 문자열로 구성된 배열이 주어졌을 때 각각의 문자열을 먼저 정렬하고 그 다음에 전체 문자열을 사전순으로 다시 정렬하는 알고리즘이 있다고 가정하자. 이 알고리즘의 수행 시간은 어떻게 되겠는가?

 

• 가장 길이가 긴 문자열의 길이를 s라 하자
• 배열의 길이를 a라 하자.

------------------------------------------

• 각 문자열을 정렬하는 데 O(slogs)가 소요된다.
• a개의 문자열 모두를 정렬해야 하므로, 총 O(a*slogs)가 소요된다.
• 이제 전체 문자열을 사전순으로 정렬해야 한다. 문자열 두 개를 비교하는 데 O(s) 시간이 소요되고, 총 O(aloga)번을 비교해야 하므로 결론적으로는 O(a*sloga)가 소요된다.

위의 두 부분을 더해주면 전체 시간복잡도는 O(a*s(loga+logs))가 된다.

 

[ 예제 10 ]

/*
예제 10
 
이 코드에서 루프는 x=2부터 x*x=n까지 반복한다. 다시 말해서 x=√n 까지 반복한다는 뜻이다.
 
시간복잡도는 O(√n) 이다.
*/
boolean isPrime(int n)
{
    for (int x = 2; x * x <= n; x++)
    {
        if (n % x == 0)
        {
            return false;
        }
 
        return true;
    }
}

 

[ 예제 13, 15 ]

/*
예제 13
 
피보나치 수 1
 
각 호출마다 분기가 2개 존재하므로 깊이가 N일 때 수행 시간은 O(2^N)이 된다.
*/
int fib(int n)
{
    if (n <= 0)
    {
        return 0;
    }
    else if (n == 1)
    {
        return 1;
    }
    return fib(n - 1) + fib(n - 2);
}
 
/*
예제 15
 
피보나치 수 2 (캐시)
 
fib(i)를 호출할 때마다 fib(i-1)과 fib(i-2)의 계산은 이미 끝나 있고 그 값은 캐시 배열에 저장되어 있을 것이다.
따라서 단순히 캐시값을 찾아서 더한 뒤 그 결과를 캐시 배열에 다시 저장하고 반환해주기만 하면 된다. 
이 일련의 과정은 상수 시간 안에 동작한다. 상수 시간의 일을 N번 반복하므로 총 O(N)시간이 걸린다.
 
메모이제이션(memoization)이라 불리는 이 기술은 지수 시간이 걸리는 재귀 알고리즘을 최적화할 때 쓰는 흔한 방법 중 하나이다.
*/
void allFib(int n)
{
    int[] memo = new int[n + 1];
 
    for (int i = 0; i < n; i++)
    {
        System.out.println(i + ": " + fib(i, memo));
    }
}
 
int fib(int n, int[] memo)
{
    if (n <= 0)
    {
        return 0;
    }
    else if (n == 1)
    {
        return 1;
    }
    else if (memo[n] > 0)
    {
        return memo[n];
    }
 
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
 
    return memo[n];
}