복잡도

: 알고리즘 성능을 나타내는 척도

• 시간 복잡도 : 알고리즘의 필요 연산 횟수
• 공간 복잡도 : 알고리즘의 필요 메모리

→ 시간 복잡도와 공간 복잡도는 Trade-off 관계 ( 반비례 관계 )

시간 복잡도

: 빅오 표기법을 통해 나타냄 → 최악의 경우

예시

//O(1)
System.out.println("hello");

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

//O(N)
for(int i = 1;i<2; i++){
		System.out.println("hello");
}

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

//O(N^2)
for(int i = 1;i<2; i++){
	for(int i = 1;i<2; i++){
			System.out.println("hello");
	}
}

//O(2^N)
//피보나치 재귀
System.out.println(fibonacci(6));

공간 복잡도

• 빅오 표기법을 통해 나타냄
• 일반적으로 메모리 사용량 기준은 MB 단위
• int[] a = new int[1000]; // 4KB
• int[][] a = new int[1000][1000]; // 4MB