[자료구조] 알고리즘 복잡도

1. 복잡도 (Complexity)

• 알고리즘 성능을 나타내는 척도
• 시간 복잡도 (Time Complexity)
  • 알고리즘의 필요 연산 횟수
• 공간 복잡도 (Space Complexity)
  • 알고리즘의 필요 메모리

• 시간 복잡도와 공간 복잡도는 Trade-off 관계
  • 일반적으로 메모리를 많이 사용하면 시간을 줄일 수 있다.

2. 시간 복잡도 (Time Complexity)

• 어떤 문제를 해결하기 위한 알고리즘의 필요 연산 횟수
• 빅오(Big-O) 표기법을 통해 나타냄
  • 빅오(Big-O) 표기법: 최악의 경우
  • 빅오메가 표기법: 최선의 경우
  • 빅세타 표기법: 중간의 경우

3. 공간 복잡도 (Space Complexity)

• 어떤 문제를 해결하기 위한 알고리즘의 필요 메모리 사용량
• 빅오 표기법을 통해 나타냄
  • 일반적으로 메모리 사용량 기준은 MB 단위
  • int[] a = new int[1000]; // 4byte = 4x1000 = 4KB
  • int[][] a = new int[1000][1000]; // 4MB

4. 코드

// 시간 복잡도
// 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 = 0; i < 2; i++) {
	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)
// 피보나치 재귀
// 1, 1, 2, 3, 5, 8, ...

// 공간 복잡도
// O(N)
// 피보나치 재귀

// O(1)
int result = 1;
for (int i = 1; i <= n; i++) {
	result *= i;
}