fibonacci

public class Chap_07 {
    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) 출력 연산 한번만 / 특정 위치에 대해 indexing
        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");
            //입력값 16에 대해 출력값 4번만 이루어 진다면 로그의 밑은 2
        }

//      O(N) N번에 대해 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++) { //N번 만큼 이루어 지고
            for (int j = 1; j < 8; j*=2) {
                System.out.println("hello"); //안쪽 for문은 N만큼 이루어 진다.
            }
        }

//      O(N^2) / N번만큼 이루어진 for문이 이중으로 있을때
        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)
//     (함수를 재귀함수로 만들어서 재귀적으로 호출 -> 함수 call stack 정보가 적층이 된다.)
//      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);
    }
    //N이 몇번이든 관계 없이 4byte integer result 하나 갖고 사용 가능
}