복잡도 (Complexity)

• 알고리즘의 성능을 나타내는 척도
• 시간 복잡도(Time Complexity) : 알고리즘의 필요 연산 횟수
• 공간 복잡도(Space Complexity) : 알고리즘의 필요 메모리
• 시간복잡도와 공간복잡도는 Trade-off 관계
  메모리를 많이쓰면 연산횟수를 줄일 수 있다.

시간 복잡도(Time Complexity)

• 어떤 문제를 해결하기 위한 알고리즘의 필요 연산 횟수
• 빅오(Big-O) 표기법을 통해 나타냄

빅오 표기법	설명
$O(1)$	상수 시간
$O(logn)$	로그 시간
$O(n)$	선형 시간
$O(nlogn)$	로그 선형 시간
$O(n^2)$	이차 시간
$O(2^n)$	지수 시간

$O(1)$

연산을 한번만 하는것 println 등

$O(n)$

for (int i= 0; i<2; i++){
	System.out.println("hello");
}

$O(logn)$

for (int i= 1; i<16; i*=2){
	System.out.println("hello");
}

$O(nlogn)$

for (int i= 0; i < 2; i++){
	for(int j = 1; j<8; j*=2){
		System.out.println("hello");
    }
}

$O(n^2)$

for (int i= 0; i < 2; i++){
	for(int j = 0; j<2; j++){
		System.out.println("hello");
    }
}

$O(2^n)$

public fibonacci(int n){
	if(n<3){
    	return 1;
    }
    return fibonacci(n-2)+fibonacci(n-1);
}

공간 복잡도(Space Complexity)

• 어떤 문제를 해결하기 위한 알고리즘의 필요 메모리 사용량
• 빅오 표기법을 통해 나타냄
  일반적으로 메모리 사용량 기준은 MB단위