알고리즘 복잡도 개념과 자바로 구현해 보기

1. 복잡도

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

 

2. 시간 복잡도

    - 알고리즘의 필요 연산 횟수

시간 복잡도

 

3. 공간 복잡도

    - 알고리즘의 필요 메모리

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

 

* 시간 복잡도와 공간 복잡도는 Trade-off(모순) 관계

* 공간 복잡도 보다는 시간 복잡도를 줄이는 방법으로 구현하는게 추세이다.

 

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) {         System.out.println("== 시간 복잡도 ==");         System.out.println("== O(1) ==");         System.out.println("hello");         System.out.println("== O(logN) ==");         for (int i = 1; i < 16; i*=2) {             System.out.println("hello");         }         System.out.println("== O(N) ==");         for (int i = 0; i < 2; i++) {             System.out.println("hello");         }         System.out.println("== O(NlogN) ==");         for (int i = 0; i < 2; i++) {             for (int j = 1; j < 8; j*=2) {                 System.out.println("hello");             }         }         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();         }         System.out.println("== O(2^N) ==");         // 1, 1, 2, 3, 5, 8, 13, ...         System.out.println(fibonacci(6));         System.out.println("== 공간 복잡도 ==");         System.out.println("== O(N) ==");         int n = 3;         System.out.println(factorial(n));         System.out.println("== O(1) ==");         int result = 1;         for (int i = 1; i <= n; i++) {             result *= i;         }         System.out.println(result);     } }