알고리즘(Algorithm)과 복잡도

알고리즘(Algorithm)

-어떤 문제 해결을 위한 절차나 방법

 

알고리즘의 조건

• 입력
• 출력
• 명확성
• 유한성
• 효율성

 

복잡도(Complexity)

알고리즘 성능을 나타내는 척도

 

 

시간 복잡도(Time Complexity) 

알고리즘의 필요 연산 횟수

 

 

공간 복잡도(Space Complexity)

알고리즘의 필요 메모리

 

-시간 복잡도와 공간 복잡도는 Trade-off관계

 

 

시간 복잡도(Time Complexity) 

어떤 문제를 해결하기 위한 알고리즘의 필요 연산 횟수

• 알고리즘의 효율성을 평가하는 중요한 기준으로, 입력 크기 n이 커질 때 알고리즘의 수행 시간이 어떻게 증가하는지를 나타냄

빅오(Big-O) 표기법을 통해 나타냄  => 최악의 경우를 대비하여 자원을 준비해두기 위함

 

※ 빅오(Big-O)는 worst case를 의미함 -> 최악의 경우 몇 번 걸리는지 

    빅오메가 -> 최선의 경우 몇 번 걸리는지

    빅세타-> 빅오와 빅오메가의 중간 정도를 의미

 

 

• O(1): 입력 크기에 상관없이 항상 일정한 시간이 소요됨 (상수 시간)
• O(log n): 입력 크기가 커질수록 실행 시간이 천천히 증가함 (로그 시간)
• O(n): 입력 크기 n에 비례하여 실행 시간이 증가함 (선형 시간)
• O(n log n):  입력 크기 nnn에 비례하면서도 그 증가율이 log⁡n\log nlogn만큼 추가로 증가함 (선형 로그 시간)
• O(n^2): 입력 크기에 따라 실행 시간이 제곱 비례로 증가함 (이차 시간)
• O(2^n): 입력 크기 nnn이 증가할 때 실행 시간이 기하급수적으로 증가함 (지수 시간)

 

 

 

 

공간 복잡도(Space Complexity) 

어떤 문제를 해결하기 위한 알고리즘의 필요 메모리 사용량

빅오 표기법을 통해 나타냄

 -일반적으로 메모리 사용량 기준은 MB(메가바이트) 단위

 

 

// 기초 수학 - 알고리즘 복잡도

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");
        // hello

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

//      O(N)
        System.out.println("== O(N) ==");
        for (int i = 0; i < 2; i++) { //n번(=2)만큼 출력
            System.out.println("hello");
            //hello
            //hello
        }

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

//      O(N^2)
        System.out.println("== O(N^2) ==");
        for (int i = 0; i < 2; i++) { //N번 만큼 이뤄지는 for문이 2개 있을 때
            for (int j = 0; j < 2; j++) {
                System.out.print("hello ");
            }
            System.out.println();
        }
        //hello hello
        //hello hello

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


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

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