Big-O 표기법 간단 정리

참고 : https://www.youtube.com/watch?v=6Iq5iMCVsXA
		(엔지니어대한민국) 

Big-O 표기법은 알고리즘의 성능을 수학적으로 풀어주는 표기법이다.

데이터나 사용자의 증가율에 따른 알고리즘의 성능을 예측하는 것이 목표이기에 상수는 기본적으로 1로 처리 된다.

O(1)

• 데이터의 크기에 상관 없이 언제나 일정한 시간이 걸리는 알고리즘을 말한다.

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

//배열의 크기가 얼마던 간에 일정한 속도로 데이터를 반환 한다.
//즉 , 데이터가 증가해도 성능에 변화가 없다.

o(n)

• 입력 데이터의 크기에 비례해서 처리 속도가 같이 커진다.

public int [] solution(int [] arr){
	int [] answer = new int[arr.length];
    
	for(int i=0; i < arr.length; i++){
    		answer[i] = arr[i];
	}
}

//데이터가 증가함에 따라 비례해서 시간도 같이 증가한다.
//언제나 데이터와 시간이 같은 비율로 증가하기 때문에 그래프는 직선으로 표현 가능 하다.

O(n^2)

• 쉽게 말해 같은 크기를 가진 이중 배열을 생각하면 좋을거 같다.

	public int [] solution(int n , int [][] arr){
	int [] answer = new int[n][n];
    
	for(int i=0; i < arr.length; i++){
    		for(int j=0; j < arr[i].length ; j++){
			answer[i][j] = arr[i][j];
	}
}

//데이터가 증가함에 따라 시간의 증가폭이 급격히 커진다.

O(nm)

• 위와 비슷해 보이나 , n이 커도 m이 작을 수 있기 때문에 다르다.

O(n^3)

• 3중 for문을 생각하면 쉽게 다가온다.
• n^2 보다 데이터 증가폭에 따라 더 급격하게 시간이 증가 한다.

O(2^n)

• 재귀호출을 사용한 피보나치 수열을 생각하면 된다.

	public int solution(n){
		if(n==1 || n==2) return 1;
        return n = solution(n-1) + solution(n-2);
	}
    
 //매번 함수가 호출 될떄마다 , 2번씩 호출하는 형태다.
 //트리형태로 표현되어 지는데 트리의 높이만큼 반복 한다.
 // n^3 보다 데이터 증가폭에 따라 더 급격한 시간 증가가 있다
 

O(m^n)

• 위와 같은데 한번에 2번씩 호출되는 것이 아닌 m번씩 호출되는 것.

O(log n)

• 이진 검색을 생각하면 된다.
• 한번 검색할 때마다 데이터의 절반씩 걸러진다.

주의 : 정렬이 되어있는 데이터라고 가정하고 설명한다.

	int arr [] = {1,2,3,4,5,6,7,8,9,10};
    int c = 7;
    int lt = 0;
    int rt = arr.length()-1;
    
	public int solution(int [] arr , int lt , int rt , int c){
        int temp = (lt+rt)/2;
        
        if(arr[temp] == c) return temp;
        else if(arr[temp] > c) {
        	rt = temp-1;
            return solution(arr , lt , rt , c);
       }else{
       		lt = temp+1;
            return solution(arr,lt , rt , c);
       }   
    }
    
    
//중간 값을 기준으로 절반씩 거르기 때문에 순차검색에 비해 속도가 빠르다.
//O(n)보다 데이터 증가폭에 비한 시간 증가량이 적다.

주의 : 빅오에서 상수는 과감하게 버린다.
예시로 ,

	public void solution(int arr[]){
    	for(int i=0; i <arr.length ; i++){
        	System.out.println(arr[i])
        }
        
        for(int i=0; i <arr.length ; i++){
        	System.out.println(arr[i])
        }
    }
    
  //for문이 2번 나왔다. 고로 O(2n)으로 볼 수 있다.
  //하지만 실제 빅오 표기법으로는 이러한 것도 O(n)으로 본다.
    
 //이유는 ? 처음 말했다 시피 , 알고리즘의 러닝타임을 재기위한 것이 아닌 장기적으로 데이터가 증가함에 따라 처리시간의 증가율을 예측하기 위해 만들어진 것이기 떄문이다.