[CS /Data Structure] 시간복잡도란?

---

[Version]
⦁ 2024.03.16 / [CS /Data Structure] 시간복잡도란?

 

시간복잡도(Time Complexity)와 공간복잡도(Space Complexity)란?

시간복잡도(Time Complexity)

• 시간복잡도는 알고리즘의 수행 시간을 평가하는 지표이다. 알고리즘의 입력 크기에 따라 수행되는 연산의 횟수나 실행 시간의 증가율을 나타낸다.
• 보통 알고리즘의 입력 크기 N에 대해 최악의 경우를 가정하여 표기한다.
• 빅오 표기법을 사용하여 나타낸다.

공간복잡도(Space Complexity)

• 공간복잡도는 알고리즘이 수행되는 데 필요한 메모리 공간의 양을 나타내는 지표이다. 알고리즘이 실행되는 동안 필요한 추가적인 메모리의 양을 고려하여 나타낸다.
• 빅오 표기법을 사용하여 나타낸다.

시간복잡도와 공간복잡도는 알고리즘의 효율성을 판단하는 데 중요한 지표이며, 두 가지를 함께 고려하여 최적의 알고리즘을 선택해야 한다.

---

시간복잡도(Time Complexity)

시간복잡도는 알고리즘의 수행 시간을 분석할 때 사용되며, 기본 연산의 실행 횟수를 기준으로 한다. 이때 기본 연산은 입출력, 산술 연산, 제어 연산등이 있다.

 

최선의 경우

• 알고리즘이 최상의 상황에서 실행될 때 걸리는 시간, 알고리즘이 어떤 경우에도 최적으로 동작할 때를 가정한다.
• 빅 오메가 표기법을 사용하여 나타낸다.

최악의 경우 (알고리즘의 성능 평가시 사용)

• 알고리즘이 최악의 상황에서 실행될 때 걸리는 시간, 일반적으로 알고리즘의 성능을 평가하는데 사용되는 지표
• 빅 오 표기법을 사용하여 나타낸다.

평균적인 경우

• 알고리즘이 여러 상황에서 실행될 때 평균적인 실행 시간을 나타낸다.
• 빅 세타 표기법을 사용하여 나타낸다.

시간복잡도 예시

시간복잡도는 입력 크기에 따라 알고리즘이 소요하는 시간의 증가율을 나타낸다. 예시를 통해 알아보자.

int func(int n) {
  int sum = 0;             // 대입연산 1회
  int i = 0;               // 대입연산 1회
   
  for(i = 0; i < n; i++) { // 반복문 n+1회
    sum += i;              // 덧셈 연산 n회
  }
  for(i = 0; i < n; i++) { // 반복문 n+1회
    sum += i;              // 덧셈 연산 n회   
  }
  return sum;              // 리턴 1회
}

1. 변수 선언 및 초기화
   • 대입 연산을 통해 변수 sum과 i를 초기화 한다.따라서 대입 연산이 각각 1회씩 발생하므로 시간복잡도는 O(1)이다.
2. 첫 번째 반복문
   • 첫 번째 반복문에서 i가 0부터 n-1까지 총 n번 반복된다. 각 반복에서는 sum += i가 수행되며, 덧셈 연산이 n회 발생한다. 따라서 첫 번째 반복문의 시간복잡도는 O(n)이다.
3. 두 번째 반복문
   • 두 번째 반복문에서도 첫 번째 반복문과 마찬가지로 i가 0부터 n-1까지 총 n번 반복된다. 마찬가지로 sum += i가 수행되며 덧셈 연산이 n회 발생한다. 따라서 두 번째 반복문의 시간복잡도도 O(n)이다.

전체 알고리즘의 시간복잡도는 각 단계의 시간 복잡도 중 가장 큰 값을 따라가게 되므로 해당 알고리즘의 시간복잡도는  O(n)이다.

---

시간복잡도 표기

상수 시간(Constant time)

• 시간복잡도: O(1)
• 상수 시간복잡도는 입력 크기에 상관없이 알고리즘이 일정한 시간만큼 실행된다. 즉, 입력의 크기가 커져도 실행 시간에 변화가 없다.

void func(int n) {
    System.out.println(n);
}

상수 시간복잡도는 입력 크기에 관계없이 항상 일정한 실행 시간을 갖는다. 위 함수에서는 출력 함수가 상수 시간에 실행되므로, 입력 크기에 상관없이 항상 같은 시간이 소요된다.

로그 시간(Logarithmic time)

• 시간복잡도: O(logN)
• 설명: 로그 시간복잡도는 입력 크기에 대해 로그 함수에 비례하는 시간이 소요된다. 대표적으로 이진 탐색과 같은 알고리즘이 이에 해당한다.

int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target)
            return mid;
        else if (arr[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return -1; // 타겟이 배열에 없을 경우
}

이진 탐색은 정렬된 배열에서 특정 값을 찾는데 사용된다. 각 반복마다 배열의 크기를 절반으로 줄여나가기 때문에 입력 크기가 입력 크기가 증가할수록 실행 시간이 로그에 비례하여 증가한다.

선형 시간(Linear time)

• 시간복잡도: O(n)
• 선형 시간복잡도는 입력 크기에 비례하여 실행 시간이 증가된다. 입력의 크기에 따라 실행 시간이 선형적으로 증가된다.

int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target)
            return i; // 타겟을 찾았을 때 해당 인덱스 반환
    }
    return -1; // 타겟이 배열에 없을 경우
}

선형 시간복잡도는 배열을 처음부터 끝까지 순회하며 특정 값을 찾는다. 배열의 크기에 비례하여 실행 시간이 선형적으로 증가하므로 선형 시간복잡도를 갖는다.

2차 시간(Quadratic time)

• 시간복잡도: O(n^2)
• 2차 시간복잡도는 입력 크기의 제곱에 비례하여 실행 시간이 증가한다. 주로 중첩된 반복문이 이에 해당한다.

void printPairs(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr.length; j++) {
            System.out.println("(" + arr[i] + ", " + arr[j] + ")");
        }
    }
}

이중 반복문을 사용하여 모든 요소 쌍을 출력한다. 이러한 경우 배열의 크기가 증가함에 따라 실행 시간이 제곱이 비례하여 증가하므로 O(n^2)의 시간 복잡도를 갖는다.

지수 시간(Exponential time)

• 시간복잡도: O(2^n)
• 지수 시간복잡도는 입력 크기의 지수에 비례하여 실행 시간이 증가한다. 주로 재귀적인 구조를 갖는 알고리즘이 이에 해당한다.

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

피보나치 수를 재귀적으로 계산하는 경우 각 호출마다 두 번의 재귀 호출이 이루어지므로 지수 시간복잡도를 갖는다. 이 경우 입력의 크기에 따라 실행 시간이 기하급수적으로 늘어나기 때문에 매우 비효율적이다.