프로그래밍에서 알고리즘의 성능을 분석하는 중요한 요소 중 하나는 알고리즘의 복잡도입니다. 알고리즘의 복잡도를 이해하는 것은 효율적인 코드를 작성하는 데 매우 중요합니다.

1. 알고리즘 복잡도란?

알고리즘 복잡도는 알고리즘이 얼마나 많은 자원(시간 및 공간)을 사용하는지를 나타냅니다. 이는 일반적으로 알고리즘의 실행 시간과 메모리 사용량을 의미합니다.

2. 시간 복잡도(Time Complexity)?

시간 복잡도는 알고리즘이 실행되는 데 걸리는 시간의 양을 나타냅니다. 이는 일반적으로 빅오(Big-O)표기법으로 표현됩니다.

예를 들어, 정렬 알고리즘의 시간 복잡도는 정렬되는 요소의 개수에 따라 달라집니다. 일반적으로 더 많은 요소를 정렬하는 데 더 많은 시간이 소요됩니다.

3. 공간 복잡도(Space Complexity)란?

공간 복잡도는 알고리즘이 실행되는 데 필요한 메모리의 양을 나타냅니다. 이는 입력 크기와 관계없이 알고리즘이 사용하는 메모리 양을 나타냅니다.

예를 들어, 배열을 정렬하는 알고리즘의 공간 복잡도는 보통 배열의 크기와 관련이 있습니다. 더 많은 요소를 정렬하는 데 더 많은 메모리가 필요할 수 있습니다.

int[] a = new int[1000]; // 4KB
int[][] b = new int[1000][1000] // 4MB

4. 자바 코드 예시

public class Main {
    static int fibonacci(int n) {
        if (n < 3) {
            return 1;
        }
        return fibonacci(n - 2) + fibonacci(n - 1);
    }

    static int factorial(int n) {
        if (n < 1) {
            return 1;
        }
        return n * factorial(n - 1);
    }

    public static void main(String[] args) {

//      1. 시간 복잡도
        System.out.println("== 시간 복잡도 ==");

//      O(1)
        System.out.println("== O(1) ==");
        System.out.println("hello");

//      O(logN)
        System.out.println("== O(logN) ==");
        for (int i = 1; i < 16; i*=2) {
            System.out.println("hello");
        }

//      O(N)
        System.out.println("== O(N) ==");
        for (int i = 0; i < 2; i++) {
            System.out.println("hello");
        }

//      O(NlogN)
        System.out.println("== O(NlogN) ==");
        for (int i = 0; i < 2; i++) {
            for (int j = 1; j < 8; j*=2) {
                System.out.println("hello");
            }
        }

//      O(N^2)
        System.out.println("== O(N^2) ==");
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                System.out.print("hello ");
            }
            System.out.println();
        }

//      O(2^N)
        System.out.println("== O(2^N) ==");
//      피보나치 재귀
//      1, 1, 2, 3, 5, 8, 13, ...
        System.out.println(fibonacci(6));


//      2. 공간 복잡도
        System.out.println("== 공간 복잡도 ==");
//      O(N)
        System.out.println("== O(N) ==");
        int n = 3;
        System.out.println(factorial(n));

//      O(1)
        System.out.println("== O(1) ==");
        int result = 1;
        for (int i = 1; i <= n; i++) {
            result *= i;
        }
        System.out.println(result);
    }
}