[1204] 자바 - 시간복잡도(Time Complexity)

#시간복잡도

- 시간복잡도란?

• 알고리즘문제를 풀다보면 등장하는 효율성 테스트가 있다. 정확성 테스트를 통과하더라도 효율성테스트에서 떨어지는 경우가 많다. 효율성 테스트를 실패하면 '시간 초과'라는 메시지가 나온다.
  효율적인 알고리즘은 시간 복잡도가 낮은 코드를 말하는 것이다.
• 시간복잡도란 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수와 소요 시간의 비례도를 말한다.
  시간복잡도를 효율화한 코드는 이 비례도를 최소화한 코드를 말하는 것이다.

 

- Big-O 표기법

• 시간 복잡도를 표기하는 방법은 여러 가지가 있는데, Big-O 표기법이 가장 많이 사용된다.
• Big-O 표기법은 최악의 경우를 고려하는 표기법이다.
  이를 사용하는 이유는 프로그램의 실행 중 여러 연산값을 도출하는 데 걸리는 최악의 경우의 시간을 고려 할 수 있기 때문이다.
  예를 들어 어떤 프로그램이 값을 도출해내는 데 소요되는 시간의 범위가 1~100초 사이이고 100개의 값을 연산해야 한다면 Big-O표기법은 최악의 경우를 고려하여 100*100인 10000초로 계산한다. 개발자는 이를 염두에 두고 효율적인 코드를 구성하기 위한 프로그래밍을 할 수 있을 것이다.

- Big-O 표기법의 종류

1. O(1)
    ▪  O(1)은 constant complexity라고 불림.
    ▪ 입력값이 증가하더라도 시간이 늘어나지 않음.
    ▪ 즉시 출력값을 얻어낼 수 있음.
    ▪ O(1)의 시간복잡도를 가지는 알고리즘의 예시는 다음과 같다.
   

   public int O_1_algorithm(int[] arr, int idx) {
       return arr[idx];
   }
   
   String[] arr1 = new String[]{"hello", "new", "world"}
   int[] arr2 = new int[]{1,2,3};
   ind idx = 0;
   String answer = O_1_algorithm(int[] arr, int idx);
   System.out.println(answer); // hello

2. O(n)
    ▪ O(n)은 linear complexity라고 불림
    ▪ 입력값과 시간이 같은 비율로 늘어남(1개/1초 -> 100개/100초)
    ▪ O(n)의 시간복잡도를 가지는 알고리즘의 예시는 다음과 같다.
   

   public void O_n_algorithm(int n) {
       for(int i = 0; i < n; i++) {
           System.out.println(i);
       }
   }

   
   
   
3.  O(log n)
    ▪ O(log n)은 logarithmic complexity라고 불림
    ▪ Big-O 표기법 중 O(1) 다음으로 빠른 시간 복잡도를 가진다.
    ▪ 대표적인 알고리즘으로 BST(Binary Search Tree)가 있음
   
   
4. O(n^2)
    ▪ O(n^2)은 quadratic complexity라고 불림
    ▪ 입력값의 제곱의 비율로 시간이 늘어남
    ▪ n의 값과 상관없이 표기법은 같다.
    ▪ O(n^2)의 시간복잡도를 가지는 알고리즘의 예시는 다음과 같다.
   

   public void O_quadratic_algorithm(int n) {
       for (int i = 0; i < n; i++) {
           for (int j = 0; j < n; j++) {
                System.out.println(a);
           }
       }
   }
   
   public void another_O_quadratic_algorithm(int n) {
       for(int i = 0; i < n; i++) {
           for(int j = 0; j < n; j++) {
               System.out.println(1);
           }
           for(int k = 0; k < n; k++) {
               System.out.println(1);
           }
           for(int l = 0; l < n; l++) {
               System.out.println(1);
           }
       }
   }

   
    
5. O(2^n)
    ▪ O(2^n)은 exponetial complexity라고 불림
    ▪ Big-O 표기접 중 가장 느린 시간복잡도를 가진다.  ▪ 피보나치 수 알고리즘이 이 시간복잡도를 가짐

public int fibonacci(int n) {
    if (n <= 1) {
        return 1;
    }
    return fibonacci(n - 1) + fibonacci(n-2);
}