[TIL] 복잡도

학습 목표

복잡도과 정렬의 개념에 대해서 이해한다

복잡도

시간 복잡도 Time Complexity 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석 
공간 복잡도 Sapce Complexity 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석 

시간 복잡도

Big-O 표기법 - Worst Case 을 기준으로 표기

특정 크기의 입력 n 을 기준으로 실행하는 연산의 횟수

O(1) 상수 시간 Contant time ; 입력 크기 ( n ) 에 상관 없이 일정한 연산을 수행하는 시간 복잡도

public void constantTime(int n){
	System.out.println("cool");
}

 

O(log2 n) 로그 시간 Logarithmic time ; n 이 커지면 연산 횟수가 log2 n 에 비례해서 증가

+ 단순 순환 (O(n)) 이 아닌 1/2 씩 경우의 수를 줄여 나가며 탐색하는 알고리즘을 이용할 때 사용하는 방법

BTS (Binary Search Tree) 의 경우 

public void LogarithmicTime(int n){
    for(int i = 0; i <= n; i*2){
    	System.out.println("cool");
    }
}

 

O(n) 선형 시간 Linear time ; n 이 커지면 연산 횟수가 n 에 비례해서 증가

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

 

O(n^2) 2차 시간 Quadratic time ;  n 이 커지면 연산 횟수가 n^2 에 비례

public void QuadraTime(int n){
    for(int i = 0; i <= n; i++){
    	for(int j = 0; j <= n; j++){
        	System.out.println("cool");
        }
    }
}

 

O(2^n) 지수 시간 expotential time ; n 이 커지면 연산 횟수가 2^n 에 비례

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

 

 

출처 https://thkim-study.tistory.com/29

시간 복잡도를 줄이는 방법

반복문의 숫자를 줄이자
적절한 자료 구조 사용
적절한 알고리즘 이용 

 

공간 복잡도

Space Complexity

작성한 프로그램이 얼마나 많은 메모리를 차지하는지 분석하는 방법

프로그램 실행과 완료에 얼마나 많은 공간 (메모리) 가 필요한지를 나타낸다

빅오 표기법의 특징

1. 상수항 무시
   빅오 표기법은 n 이 충분히 크다고 가정하고 있고, 알고리즘의 효율성은 n 의 크기에 영향을 받으므로
   상수항 같은 사소한 부분은 무시한다
   -> O(2n) 은 O(n) 으로 간주
2. 영향력 없는 항 무시
   빅오 표기법은 n 의 크기에 영향을 받으므로 가장 영향력이 큰 항 이외에 영향력이 없는 항은 무시한다
   -> O(n^2 + 2n + 1) 은 O(n^2) 으로 간주

 

정렬

은 아래 페이지에 정리했다

DO IT 알고리즘입문 CH06

 

참고한 블로그 

https://dev-cool.tistory.com/19

https://choijying21.tistory.com/entry/Java-데이터-타입-Long-long-int의-차이-어떤걸-써야할까

https://velog.io/@welloff_jj/Complexity-and-Big-O-notation