빅오표기법

what is Big-O?

• Mathmatical notation that describes algorithm efficiency
• 시간과 공간의 복잡도 표현 가능
• 알고리즘의 실제 러닝타임을 표시하는 게 아니라, 데이터나 사용자의 증가에 따른 알고리즘의 성능을 예측하는 것이 목적. 상수와 같은 경우 1이 된다.

1. O(1) 알고리즘

        public boolean f(int[] n){	
		return(n[0] == 0)? true : false;		
	}

• 데이터가 증가함에 따라 성능의 변함이 없음

2. O(n) 알고리즘

	public void f(int[] n){
	        for(int i =0; i<n.length; i++){
		        System.out.println(i);		
         	}
        }

• 입력 데이터의 크기에 비례해서 처리시간도 증가.
• n이 하나 늘어날 때마다 처리가 한번씩 늘어남.
• 언제나 데이터와 시간이 같은 비율로 증가하므로 그래프를 그리면 직선형

3. O(n²) 알고리즘

	public void f(int[] n){
	        for(int i =0; i<n.length; i++){
                       for(int j =0; j<n.length; j++){
		              System.out.println(i+j);		
                       }
         	}
        }

• n개의 데이터를 받으면 첫번째 루프에서 n번 반복, 각 각의 elements에서 n번씩 반복.
• 데이터가 커질수록 처리시간의 부담도 상승. 데이터가 증가할수록 수직에 가까운 모양

4. O(nm) 알고리즘

	public void f(int[] n, int[] m){
	        for(int i =0; i<n.length; i++){
                       for(int j =0; j<m.length; j++){
		              System.out.println(i+j);		
                       }
         	}
        }

• m을 n만큼 반복. 데이터가 증가할수록 수직에 가까운 모양

5. O(n³) 알고리즘

	public void f(int[] n, int[] m){
	        for(int i=0; i<n.length; i++){
                       for(int j=0; j<n.length; j++){
                              for(int k=0; k<n.length; k++){
		                      System.out.println(i+j+k);		
                              }
                       }
         	}
        }

• n³은 n²을 n만큼 반복하므로, 정육면체가 될 것.
• 데이터에 증가에 따른 처리시간이 급격하게 증가

6. O(2ⁿ) Fibonacci 재귀함수를 이용한 피보나치수열

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

• 1 1 2 3 5 8 13 21 ...
• 재귀호출을 통해 함수를 호출할 때마다 직전의 숫자와 직전전의 숫자가 필요.
• n²,n³ 보다 데이터의 증가에 따라 훨씬 더 시간복잡도가 급격히 증가

7. O(log n)

	public int search(int[] arr, int target) {

		int first = 0;
		int last = arr.length;
		int mid;

		while (first <= last) {

			mid = (first + last) / 2;
			if (target == arr[mid]) {
				return mid;
			} else {
				if (target < arr[mid])
					last = mid - 1;
				else
					first = mid + 1;
			}
		}
		return -1;
	}

• 대표적인 경우는 이진검색(가운데 값을 찾아 키값과 비교 - 반복)

• 한번씩 진행될 때 마다 확인해야할 데이터의 양이 절반씩 줄어듦

• 여기서 로그2가 생략되어 표현됨 O(log2n). 컴퓨터에서는 바이너리만 거의 쓰기 때문에 2를 생략

8. O(sqrt(n))

9. Big O 표기법에서는 상수는 과감하게 버린다.

• Drop Constant
• WHY? 실제 알고리즘의 러닝타임이 아니라, 장기적으로 데이터의 증감에 따른 처리시간의 증가율을 알고자하는 것.
• 상수는 고정된 숫자이므로, 언제나 고정된 상수만큼 영향을 미침.
• 증가하지 않는 숫자는 신경쓰지 않겠다.
• O(2n) -> O(n).둘은 동일
• O(n²+n²) -> O(n²). 차원이 증가하지 않는 한 동일한 시공간복잡도를 가진다.