시간 복잡도와 공간 복잡도

Big O표기법

• O(1)

int sum(int a, int b) {
  return a + b;
}

int getElement(int[] array, int index) {
    return array[index];
}

• O(N)

int findMax(int[] array) {
    int max = array[0];
    for(int i = 1; i < array.length; i++) { // O(N)
	      if (array[i] == 2) {
		       return;
	       }
        if(array[i] > max) {
            max = array[i];
        }
    }
    return max;
}


int[] findMaxAndMin(int[] array) { // O(2N) => O(N) 
    int max = array[0];
    int min = array[0];

    for(int i = 1; i < array.length; i++) { // O(N)
        if(array[i] > max) {
            max = array[i];
        }
    }
  
	  for (int i = 1; i < array.length; i++) { // O(N)
        if (array[i] < min) {
            min = array[i];
        }
    }

    return new int[]{max, min}; // 최대값과 최소값을 배열로 반환
}

• O(N^2)

boolean hasDuplicates(int[] array) { // O(N^2)
    for (int i = 0; i < array.length; i++) { // O(N)
        for (int j = i + 1; j < array.length; j++) { // O(N)
            if (array[i] == array[j]) {
                return true;
            }
        }
    }
    return false;
}

시간 복잡도

• 시간 복잡도는 알고리즘이 문제를 해결하는 데 걸리는 시간과 입력 크기(n)의 관계를 나타낸다
• 입력 크기가 커질 때 실행 시간이 어떻게 증가하는지를 분석하여 알고리즘의 효율성을 평가
• 예제: 선형 검색(Linear Search) - O(n)
  • 선형 검색은 배열의 모든 요소를 차례대로 검사하여 원하는 값을 찾는 방법
  • 최악의 경우 모든 요소를 검사해야 하므로, 시간 복잡도는 O(n)

Array<Integer> array = {1, 2, 3, ... N};

linearSearch(array, 2); // 2번의 실행
linearSearch(array, 0); // N번의 실행

public int linearSearch(int[] array, int key) {
    for(int i = 0; i < array.length; i++) {
        if(array[i] == key) {
            return i; // 원하는 값의 인덱스 반환
        }
    }
    return -1; // 값을 찾지 못한 경우
}

공간복잡도

• 공간 복잡도는 알고리즘이 문제를 해결하는 데 필요한 총 저장 공간의 양
• 이는 알고리즘의 임시 저장 공간(예: 변수, 배열)과 입력 크기에 따라 결정

O(n)

• 데이터 구조

// 공간복잡도 O(1)
int sum() {
	int result = 0; // 공간복잡도 O(1)
	for (int i=1; i<N; i++) {
		result += i; // 공간복잡도 O(1)
	}
	return result;
}

// O(N)
int[] copyArray(int[] array) {
    int[] newArray = new int[array.length]; // O(N)
    for (int i = 0; i < array.length; i++) {
        newArray[i] = array[i];
    }
    return newArray;
}

• 호출 스택

  피보나치 수열의 값을 재귀적으로 계산하는 방법은 함수 호출에 따른 호출 스택의 크기가 입력 크기 n에 비례하므로, 공간 복잡도는 O(n)

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

복잡도 분석의 중요성

시간 복잡도를 계산하는 것은 코딩 테스트 실력을 늘리는데 필수불가결한 능력

코딩테스트 문제를 풀기전에 시간 복잡도를 어림짐작함으로써 수행시간을 파악하고 이 문제에 필요한 알고리즘을 예측해야한다

• 주먹구구 법칙에 따르면, 연산 횟수가 1억을 넘어가면 수행시간이 1초가 넘는다고 예상할 수 있다

• 알고리즘 문제의 시간 제한이 1초로 주어졌다면, 알고리즘의 연산 횟수가 N 이라고 가정했을 때, O(N) 에서 N<10^8 이 되도록 알고리즘을 구현해야 시간 초과가 발생하지 않는다