Java 시간 복잡도 (Big O)

좋은 프로그램 알고리즘이란?

• 처리 효율이 높은 알고리즘 => 시간 복잡도
• 신뢰성이 높은 알고리즘
• 일반적으로 적용이 가능한 알고리즘
• 확장성이 있는 알고리즘
• 이해하기 쉬운 알고리즘
• 이식성이 높은 알고리즘
  
  

시간 복잡도 O(n) 표기법

1. O(1) => 처리 횟수가 변하지 않고 항상 일정

   int func(int[] n) {
       if (n.length < 3)
           return 0;
   
       int a = n[0];
       a += n[1];
       a += n[2];
   
       return a;
   }

2. O(n) => n개가 증가하면 처리 횟수도 n번 증가

   int sum(int[] n) {
       int s = 0;
       for (int i : n){
       	s += i;
       }
       return a;
   }

3. O(n^2) => n이 1이 들어오면 1번x1번씩 반복, 2가 들어오면 2번x2번씩 반복

     void bubbleSort(int[] n){
         for (int i = 0; i < n.length; i++) {
            for (int j = 0; j < n.length; j++){
               if (n[i] < n[j]) {
                  int temp = n[j];
                  n[j] = n[i];
                  n[i] = temp;
               }
            }
         }
         return a;
   }

4. O(logn) => n이 들어올 때, 루프 안의 변수(처리 횟수)가 절반씩 줄고 있다.

   int sum(int[] n) {
       int sum = 0;
       int max = n.length;
       while (max > 0) {
           sim += n[max - 1];
           max /= 2;
       }
       return sum;
   }

그렇다면 다음 시간 복잡도는 어떻게 될까?

int sum3(int[] n) {
    int s = 0;
    for (int i: n) {
        s += i;
        for (int j=0; j < 10; j++) {
            s += j;
        }
    }
    return s;
}

밖의 for문은 n번, 안의 for문은 고정적으로 10번씩 돌고 있으므로, 처리 횟수는 n에 비례해서 증가한다.

따라서, 시간복잡도는 O(n)이다.
(n이 무한대로 증가하면 앞의 계수는 별 영향을 주지 못하기 때문에 생략한다.)