시간복잡도(Time complexity)와 공간복잡도(Space complexity)

복잡도(complexity)

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

 

시간복잡도(Time Complexity)

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

 

*빅오(Big-O)표기법 : worst case

 빅오메가 : 최선

 빅 세타 : 중간

 

O(1)	상수 시간
O(logN)	로그 시간
O(N)	선형 시간
O(NlogN)	로그 선형 시간
O(N^2)	이차시간
O(2^N)	지수시간

 

지수시간에서 상수시간으로 갈수록 복잡도가 낮아진다.

 

https://theassyrianblog.wordpress.com/programming/o-data-structure-complexities/

 

 

공간복잡도(Space Complexity)

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

빅오표기법을 통해 나타냄.

일반적으로 메모리 사용량 기준은 MB 단위

int[a] = new int [1000];  //4byte가 1000개  //4kb
int[][] a = new int[1000][1000]  //4byte가 백만개   //4MB

 

 

---

    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문 사용
        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);
    }