빅오 표기법

빅오 : 알고리즘의 성능을 수학적으로 표현하는 표기법

 

알고리즘의

시간 복잡도

공간복잡도 표현가능

 

end point

알고리즘의 데이터나 사용자의 증가율에 따른 알고리즘의 성능을 예측

 

O(1) :오원

입력데이터의 크기에 상관없이 일정한 시간이 걸리는 알고리즘 표현

    public boolean oOne(int[] n) {
        if(n[0] == 0) {
            return true;
        }else {
            return false;
        }
    }

 

O(n) : 오엔

입력 데이터의 크기에 비례해서 처리시간이 늘어나는 알고리즘 표현

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

O(n2): 오엔스퀘어

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

 

O(nM) : 오엔엠

public void oNM(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);
            }
            
        }
    }

 

O(n3) :

    public void oN3(int[] n) {
        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);
                }
            }
            
        }
    }

 

O(2n)

피보나치

    public int o2N(int n, int[] r) {
        
        if(n <= 0) return 0;
        
        else if(n==1) return r[n] = 1;
        
        else return r[n] = o2N(n-1,r) + o2N(n-2,r);
        
    }

 

O(log n) : 오로그엔(이진검색)

한번 처리가 진행될때마다 검색해야하는 데이터량이 절반씩 줄어드는 알고리즘

    public int oLogN(int k, int[] arr, int s, int e) {
        
        if( s > e ) return -1;
        
        int m = (s+e) /2;
        
        if(arr[m] == k) return m;
        
        else if (arr[m] > k) return oLogN(k,arr,s,m-1);
        
        else return oLogN(k,arr,s,m+1);
        
    }