[알고리즘] 시간 복잡도(Time complexity)

 

 

시간복잡도(Time complexity)는 문제를 해결하는데 걸리는 수행 시간과 입력 데이터의 함수 관계를 분석하는 개념으로, 입력 데이터의 크기가 커질 때, 알고리즘이 얼마나 효율적인지 평가할 수 있다.

 

시간 복잡도는 주로 빅오 표기법(Big-O Notation)으로 표현되며, 알고리즘의 수행 시간은 동일 크기의 다양한 입력 데이터에 의해 달라질 수 있기 때문에, 가장 많이 쓰이는 최악의 시간 복잡도의 알고리즘 시간을 T(n)이라고 했을 때, 이것은 크기 n의 모든 입력 데이터에 대해 걸리는 최대의 시간으로 정의할 수 있다. 그 수치가 작을 수록 효율적인 알고리즘을 의미한다.

 

 

시간 복잡도에는 빅오(Big-O) 외에도 빅오메가(Big-Omega), 빅세타(Big-Theta)라는 개념도 존재한다.

빅오는 최악의 경우를 나타내는 표기법으로 입력 크기 n이 커질 때, 최대 얼마만큼의 시간이 걸릴 수 있는지를 분석한다.

빅오메가는 최선의 경우를 나타내는 표기법으로 입력 크기 n이 커질 때, 최소 얼마만큼의 시간이 걸릴 수 있는지를 분석한다.

빅세타는 알고리즘의 평균적인 실행 시간을 나타내며, 빅오와 빅오메가의 결합으로 볼 수 있다. 입력 크기 n에 대해 알고리즘의 수행 시간이 특정 범위 내에서 변동하는것을 나타낸다.

 

 

빅오 시간복잡도

 

함수	이름	시간복잡도	설명	예시
O(1)	상수	상수 시간(Constant Time)	입력 크기에 상관없이 항상 동일한 시간이 걸리는 경우	배열의 특정 원소에 접근할 때
O(logn)	로그	로그 시간(Logarithmic Time)	입력 크기가 커질수록 시간이 천천히 증가하는 경우	이진 탐색 (Binary Search)
O(n)	선형	선형 시간(Linear Time)	입력 크기에 비례하여 시간이 증가하는 경우	선형 탐색 (Linear Search)
O(nlogn)	로그 선형	선형 로그 시간(Linearithmic Time)	선형적으로 증가하는데, 추가적으로 로그 요소가 포함된 경우 주로 효율적인 정렬 알고리즘	병합 정렬 (Merge Sort) 퀵 정렬 (Quick Sort)
O(n^2)	이차	이차 시간(Quadratic Time)	입력 크기에 제곱에 비례하여 시간이 증가하는 경우 주로 중첩된 반복문	버블 정렬 (Bubble Sort) 선택 정렬 (Selection Sort)
O(2^n)	지수	지수 시간(Exponential Time)	입력 크기가 커질수록 처리 시간이 지수적으로 증가하는 경우	피보나치 수열 계산(재귀 방식)
O(n!)	계승	팩토리얼 시간(Factorial Time)	입력 크기 n에 대해 n 팩토리얼의 시간이 걸리는 경우 모든 가능한 경우의 수를 다 시도해야하는 경우	외판원 문제 (Travelling Salesman Problem)

 

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O(n!)

 

오른쪽으로 갈수록 시간 복잡도가 큰 알고리즘으로 수행시간이 길다고 할 수 있다.

 

n의 값이 작을 때는 알고리즘 사이에 큰 차이가 없지만 n의 값이 커지면 커질수록 복잡한 알고리즘은 수행 시간이 급격히 길어지게 되며 이는 성능과 직결된다.

 

 

---

 

 

1. O(1)

입력 크기(n)에 상관없이 일정한 연산을 수행한다.

public int str(int[] s) {
    return s[0];
}

public int str(s) {
    System.out.println(s);
}

 

 

 

2. O(logn)

입력 크기(N)가 커질 때 연산 횟수가 logN에 비례해서 증가한다. 실행을 반복할 때마다 알고리즘의 탐색 범위를 1/2로 줄여 나가는 이진 탐색과 같은 알고리즘에서 볼 수 있습니다.

// 이진 탐색 함수
public int binarySearch(int[] array, int target) {
    int left = 0;                  // 왼쪽 인덱스
    int right = array.length - 1;  // 오른쪽 인덱스

    while (left <= right) {
        int mid = left + (right - left) / 2; // 중간 인덱스 계산

        // 목표 값을 찾은 경우
        if (array[mid] == target) {
            return mid; // 목표 값의 인덱스를 반환
        }
        // 목표 값이 중간 값보다 큰 경우, 오른쪽 절반 탐색
        if (array[mid] < target) {
            left = mid + 1;
        }
        // 목표 값이 중간 값보다 작은 경우, 왼쪽 절반 탐색
        else {
            right = mid - 1;
        }
    }
    // 값이 배열에 없는 경우 -1 반환
    return -1;
}

 

 

 

3. O(n)

입력 크기(n)가 커질 때 연산 횟수가 n에 비례해서 증가한다. 탐색할 데이터가 많아질수록 수행 시간이 입력 크기 n에 비례하여 증가한다.

// 선형 탐색 함수
public static int linearSearch(int[] array, int target) {
    // 배열의 모든 원소를 순차적으로 탐색
    for (int i = 0; i < array.length; i++) {
        // 목표 값을 찾으면 해당 인덱스를 반환
        if (array[i] == target) {
            return i;
        }
    }
    // 배열에서 목표 값을 찾지 못한 경우 -1 반환
    return -1;
}

 

 

 

4. O(nlogn)

로그 시간 복잡도와 선형 시간 복잡도를 곱한 만큼 증가한다. 

 

선형 로그 시간 알고리즘은 보통 데이터 세트를 작은 부분으로 나누고, 이들을 독립적으로 처리하는 형태를 취합니다. 병합 정렬과 같은 효율적인 정렬 알고리즘은 대부분 선형 로그 시간 복잡도를 따릅니다.

 

 

 

5. O(n^2)

입력 크기(n)가 커질 때 연산 횟수가 n^2 에 비례해서 증가한다.

public void solution(int n) {
	for(i=0; i < n; i++) {
		for(j=0; j < n; j++) {
			...
		}
	}
}

 

 

 

6. O(2^n)

입력 크기가 커질 때 연산수가 2^n 에 비례해서 증가한다.

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

 

 

 

7. O(n!)

입력 크기 n에 대해 모든 가능한 경우의 수 n를 다 시도한다.

public static int factorial(int num) {
    if (num == 1){
        return 1;
    }else{
        return num * factorial(num - 1);
    }
}

 

 

---

 

 

자료구조와 시간복잡도 관계

 

 

 

 

링크.

https://www.bigocheatsheet.com/

Big-O Algorithm Complexity Cheat Sheet (Know Thy Complexities!) @ericdrowell