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

Big-O notation : 자료구조나 알고리즘에서 성능 측정에 가장 중요한 지표

빅오 식의 규모 : O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) 

/* N을 입력받아 1~N의 합을 구하는 코드 */

import java.util.Scanner;

public class Hap {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int a = input.nextInt();
        int sum = 0;

        for (int i=1; i<=a; i++) {
            sum = i + sum;
        }

        System.out.println(sum);
    }
}

이 소스 코드의 시간복잡도를 빅오 표기법으로 나타내보자. 먼저, 컴퓨터는 기본적인 사칙연산에 대해선 빠른 시간 안에 처리할 수 있으므로, O(1)로 표기할 수 있다. 따라서 굵직한 연산을 세보면 다음과 같다!

- for 문이 한 번 돌아가는 데에, i<=a인지 비교하는 연산 한 번, sum에 i를 더하는 연산 한 번, i를 1 증가시키는 연산 한 번 이렇게 최소 3개의 연산이 필요하다. 반복문을 처음 들어오거나 나갈 때의 추가적인 연산은 싹 다 제외시키더라도 for 문은 최소 3N번의 연산을 한다. 따라서 3N을 빅오 표기법으로 나타내면 O(N)이 된다. (앞의 계수는 값이 커지면 의미가 없다!). 

 

아래의 소스 코드는 1~N 더하는 공식을 구현한 코드이다.

/* N을 입력받아 1~N의 합을 구하는 코드 */
/ * 공식을 이용해보자 */
import java.util.Scanner;

public class Hap {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int a = input.nextInt();
        int sum = a * (a + 1) / 2;

        System.out.println(sum);
    }
}

위 코드에서 for문을 한 줄의 식으로 대체하였다. 이 줄은 대입을 제외하면 덧셈 한번, 곱셉 한 번, 나눗셈 한 번, N에 상관없이 3번의 연산이 이루어진다. 즉, O(1)의 시간 복잡도가 측정이 된 것이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int a = Integer.parseInt(br.readLine());
        int sum = a * (a + 1) / 2;

        System.out.println(sum);
    }
}

* 번외 : Scanner와 BufferedReader를 사용했을 때 처리 시간 차이

다시 본문으로 돌아와 시간 복잡도의 제한에서 풀 수 있을지 가늠해보는 방법이 있다. 먼저 컴퓨터의 연산 속도를 생각해보면 된다. 컴퓨터는 1초에 가장 간단한 연산을 1억번 정도 한다고 생각하면 된다. 만약 시간 복잡도가 O(NM)이라고 했을 시, N=1000, M=10000이라면 천만이라는 숫자는 1초안에 연산이 가능하다. 하지만 숫자가 커져서 N=100000, M=10000 이라고 한다면 O(NM)의 연산으로는 힘들것이다. 따라서, O(NlogM)의 성능의 알고리즘을 사용한다면 넉넉하게 연산이 가능하다.

 

이처럼, 알고리즘 연산 횟수의 계수를 줄이기보단 그 차수를 줄여버리는 게 주어진 상황에서 문제를 해결할 수 있는 방법이 될 것이다.

---

다음으로 공간복잡도 라는 것이 있다. 시간 복잡도는 실행시간을 측정하는 용도인 반면, 공간복잡도는 필요한 메모리를 측정한다. 예시로 배열 A를 입력ㅂ다아 그 중 X보다 작은 수만 원래 순서대로 출력하는 코드를 작성해보자.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int cnt = Integer.parseInt(br.readLine());
        int number = Integer.parseInt(br.readLine());

        int[] arr = new int[cnt];

        for (int i=0; i<arr.length; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }

        for (int j=0; j<arr.length; j++){
            if (arr[j] < number){
                System.out.print(arr[j]);
                System.out.print(" ");
            } else {
                continue;
            }
        }
    }
}

위 코드의 시간 복잡도는 O(N)이며, 공간 복잡도 역시 N개의 값을 저장해야 하므로 O(N)이 된다. 하지만 배열을 꼭 저장했다가 나중에 다시 보면서 하지 말고, 입력하자마자 처리해도 된다는 것을 안다. 따라서, 하나씩 입력받다가 X보다 작은 것을 StringBuiler에 append 시키면 배열도 사용하지 않고 문제를 풀 수 있다. 이 경우 공간 복잡도는 O(1)이 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        int n = Integer.parseInt(st.nextToken());
        int x = Integer.parseInt(st.nextToken());
        
        StringBuilder sb = new StringBuilder();
        
        for (int i=0; i < n; i++) {
            int value = Integer.parseInt(st.nextToken());
            
            if (value < x){
                sb.append(value).append(' ');
            }
        }
        System.out.println(sb);
    }
}

공간 복잡도의 대부분 경우 시간복잡도보다 우선순위가 밀린다고 한다. 메모리가 현대엔 넘쳐나기 때문..하지만 시간복잡도의 향상은 중요하다. 그 이유는 컴퓨터의 연산속도는 메모리가 늘어나는 속도만큼 성능이 개선되지 않았기 때문이다. 알고리즘의 시간복잡도를 줄이는 것은 굉장히 중요한 이슈이다. 

---

어쩐지 백준을 통해 알고리즘을 풀다보면, 시간초과는 본 적이 있어도 메모리 초과라는 메시지를 본 적이 거의 없는 것 같다.  앞으로 코딩할 때 시간과 메모리를 고려한 알고리즘을 작성할 수 있는 실력자가 되어야겠다..