Post

시간 복잡도(Time complexity)

알고리즘 시간 복잡도 정리

Posted
By
19 min read

TOC

◼︎ 시간 복잡도(Time Complexity)

알고리즘의 시간 복잡도는 어떤 알고리즘이 문제를 해결하는 데 얼마나 많은 시간이 필요한지를 나타내는 척도이다.

시간 복잡도는 보통 빅 오(Big O) 표기법을 사용하여 표현한다.

◼︎︎ Big-O 표기법

‘n이 커질 때 알고리즘의 단계가 얼마만큼 증가하는가’

Big-O 표기법은 점근 표기법 중 하나인데, 알고리즘의 수행 시간을 대략적으로 나타내는 방법이다.

표기법설명
O(Big O)알고리즘 성능이 최악인 경우(수행 시간의 상한)
Ω(Big Omega)알고리즘의 성능이 최선인 경우(수행 시간의 하한)
Θ(Big Theta)알고리즘이 처리해야 하는 수행 시간의 상한과 하한을 동시에 나타냄

► Big-O 알고리즘 실행 시간

상수시간 → 지수 시간으로 갈수록 알고리즘은 더 많은 시간이 걸린다.

► 상수 시간 O(1)

상수 시간(constant time)은 입력 데이터의 크기와 무관하게 알고리즘이 일정한 시간 동안 실행된다는 것을 의미한다. 즉, 입력 데이터의 크기가 커지더라도 처리 시간은 변하지 않는다.

자바로 이를 표현하면

1
2
3
4
5
6
7
8
9
10

public class Main {
    public static void main(String[] args) {
        int n = 5;
        System.out.println(isOdd(n));
    }

    public static boolean isOdd(int n) {
        return n % 2 == 1;
    }
}

여기서 isOdd 함수는 주어진 숫자 n이 홀수인지 판별한다. 함수의 실행 시간은 입력 n의 크기에 관계 없이 항상 일정하다. 입력값이 9천조가 되더라도 실행 시간은 동일하므로, isOdd 함수는 상수 실행시간을 갖는다.

따라서 가장 효율적인 알고리즘이라고 할 수 있다.

► O(n)

선형 시간(linear time)은 입력 데이터의 크기에 비례하여 알고리즘이 실행되는 시간이 증가하는 것을 의미한다. 즉, 데이터의 크기가 n이면 알고리즘의 실행 시간도 n에 비례하여 증가한다.

선형 시간을 가지는 알고리즘의 대표적인 예는 선형 검색 알고리즘이 있다. 이 알고리즘은 데이터 집합의 모든 원소를 처음부터 끝까지 순차적으로 검색하는 방식이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public class Main {
    public static void main(String[] args) {
        int arr[] = {10, 20, 80, 30, 60, 50, 110, 100, 130, 170};
        int x = 110;
        int result = linearSearch(arr, x);
        if (result == -1)
            System.out.println("원소가 존재하지 않습니다.");
        else
            System.out.println("원소 찾음 " + " 인덱스 " + result);
    }

    public static int linearSearch(int arr[], int x)
    {
        int n = arr.length;
        for(int i = 0; i < n; i++)
        {
            if(arr[i] == x)
                return i;
        }
        return -1;
    }
}

여기서 linearSearch 함수는 주어진 배열에서 주어진 숫자 x를 찾는다. 배열의 크기가 n이라면, 이 함수는 최악의 경우 n의 시간 복잡도를 갖는다.

즉, 데이터가 증가함에 따라 비례해서 처리 시간도 같이 증가하기 때문에 직선으로 표현된다.

► O(n²)

2차 시간 복잡도, 제곱 시간 복잡도

제곱 시간(quadratic time)은 입력 데이터의 크기에 따라 알고리즘이 실행되는 시간이 제곱 수준으로 증가하는 것을 의미한다. 즉, 입력 데이터의 크기가 n이면 알고리즘의 실행 시간도 n의 제곱에 비례하여 증가한다.

제곱 시간을 가지는 알고리즘의 대표적인 예는 버블 정렬(bubble sort) 알고리즘이 있다. 이 알고리즘은 배열의 모든 원소를 비교하며 정렬하는 방식이다.

1
2
3
4
5
6
7
8
9
10
11

public static void bubbleSort(int arr[]) {
    int n = arr.length;
    for (int i = 0; i < n-1; i++)
        for (int j = 0; j < n-i-1; j++)
            if (arr[j] > arr[j+1]) {
                // swap arr[j+1] and arr[j]
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
}

여기서 bubbleSort 함수는 주어진 배열을 버블 정렬 방식으로 정렬한다. 배열의 크기가 n이라면, 이 함수는 최악의 경우 n^2의 시간 복잡도를 갖는다.

즉, 데이터가 증가함에 따라 처리 시간이 제곱으로 증가하기 때문에 시간 복잡도가 크다고 할 수 있다.

버블 정렬은

두 개의 인접한 요소를 비교하여 정렬하는 방식을 사용하는데, 이러한 비교를 한 쌍씩 모든 요소에 대해 수행하며, 이 작업을 요소가 모두 정렬될 때까지 반복한다. 따라서, 데이터가 n개일 때, 버블정렬은 최악의 경우 n번의 비교를 n번 반복하게 된다. 이는 총 n*n, 즉 n^2의 연산을 의미하며, 이로 인해 버블정렬의 시간 복잡도는 O(n²)가 된다.

시간 복잡도는 알고리즘의 작동 방식을 이해해야 한다..

공부하다보니, 이해는 되는데, 약간 뇌를 얻어맞은 것 같다.

알고리즘이 어떤 작업을 수행하는지, 그 작업이 어떻게 연산의 수에 영향을 미치는지를 이해하면 시간 복잡도를 이해할 수 있다.

예를 들어, 일부 알고리즘은 입력 데이터의 모든 요소를 개별적으로 검사하므로 그 시간 복잡도는 O(n)이 된다. 다른 알고리즘은 입력 데이터를 반으로 나누는 작업을 반복하므로 그 시간 복잡도는 O(log n)이 된다.

► O(nm)

O(nm) 시간 복잡도는 알고리즘이 두 입력 데이터의 크기(n과 m)에 비례하여 시간이 증가하는 것이다. 이는 주로 두 데이터 집합 간의 중첩된 작업(예를 들어, 중첩 반복문)을 수행할 때이다.

예를 들면, 두 개의 배열에 속한 각 원소의 쌍을 비교하는 작업이 있다. 첫 번째 배열에 n개의 원소가 있고, 두 번째 배열에 m개의 원소가 있다면, 이 작업은 n * m 번의 비교를 필요로 한다. 따라서 이 작업의 시간 복잡도는 O(nm)이 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

public class Main {
    public static void main(String[] args) {
        int arr1[] = {1, 2, 3, 4, 5};
        int arr2[] = {6, 7, 8, 9, 10};
        int n = arr1.length;
        int m = arr2.length;
        compareArrays(arr1, arr2, n, m);
    }

    public static void compareArrays(int arr1[], int arr2[], int n, int m)
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                System.out.println("Comparing " + arr1[i] + " and " + arr2[j]);
            }
        }
    }
}

여기서 compareArrays 함수는 두 배열의 원소들을 비교한다. 첫 번째 배열의 크기가 n이고, 두 번째 배열의 크기가 m이라면, 이 함수는 최악의 경우 n * m의 시간 복잡도를 갖게 된다.

► O(n log n)

선형 로그 시간

O(n log n) 시간 복잡도는 알고리즘이 입력 데이터의 크기 n에 대해 n배의 로그 시간이 걸리는 것을 의미한다. 즉, 로그 시간으로 실행되는 알고리즘 O(log n)을 n번 반복하는 형태를 말한다.

이러한 시간 복잡도를 가지는 알고리즘의 대표적인 예는 병합 정렬(merge sort) 및 퀵 정렬(quick sort) 이다. 병합 정렬은 분할 정복(divide and conquer) 방법을 사용한 정렬 알고리즘인데, 주어진 데이터를 절반으로 나눈 뒤, 각각을 정렬하고 이를 다시 병합(merge)하는 과정을 반복한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

void mergeSort(int arr[], int l, int r)
{
    if (l < r) {
        // 중간 지점을 찾는다
        int m = (l+r)/2;

        // 첫 번째와 두 번째 반쪽을 정렬한다
        mergeSort(arr, l, m);
        mergeSort(arr , m+1, r);

        // 정렬된 두 반쪽을 병합한다
        merge(arr, l, m, r);
    }
}

여기서 mergeSort 함수는 주어진 배열을 병합 정렬 방식으로 정렬한다. 배열의 크기가 n이라면, 이 함수는 최악의 경우 n log n의 시간 복잡도를 갖는다.

즉, 데이터가 증가함에 따라 처리 시간이 데이터 크기 n과 그에 대한 로그 시간의 곱만큼 증가한다. 이는 상수 시간 O(1), 선형 시간 O(n), 제곱 시간 O(n²)보다 효율적인 알고리즘이며, 큰 데이터를 처리할 때 자주 사용된다.

로그 함수

로그 함수의 가장 중요한 특성 중 하나는 “n개의 요소를 반으로 계속 나누어 하나의 요소가 남을 때까지 필요한 스텝(step)의 수”를 측정한다는 것이다.

로그 함수를 더 쉽게 정리해보자면

‘책 찾기’를 예로 들 수 있다. 책장에 정렬된 책들이 있을 때, 특정 책을 찾으려면 어떻게 해야 할까?

한 권씩 차례로 확인한다면, 이는 선형 검색에 해당하며, 시간 복잡도는 O(n)을 갖는다.

하지만 책을 반으로 나누어 가운데 책부터 확인하고, 찾으려는 책이 그 책보다 앞에 있다면 앞쪽의 책을, 뒤에 있다면 뒤쪽의 책을 다시 반으로 나누어 검색한다면, 이는 이진 검색에 해당하며, 시간 복잡도는 O(log n)이다. 이처럼 로그 함수는 ‘반으로 나누기’라는 개념을 기반으로 한다.

O(n log n)과 O(log n)의 차이

여기서 궁금했던 점은, O(n log n)의 시간 복잡도를 갖는 병합 정렬이나 퀵 정렬이 O(log n)의 시간 복잡도를 갖는 이진 탐색보다 시간이 왜 더 오래 걸리는 것이며 그 이유.

이진 탐색이 한 번의 검색을 수행할 때마다 범위를 반으로 줄이는 반면, 병합 정렬이나 퀵 정렬은 각각의 정렬 과정에서 모든 요소를 다루기 때문이다. 따라서 이는 데이터의 크기 n에 대해 로그 시간이 n번 필요하므로, 전체 시간 복잡도는 O(n log n)이 된다.

다시 말해, 이진 탐색은 ‘찾기‘에 최적화된 알고리즘이고, 병합 정렬과 퀵 정렬은 ‘정렬’에 최적화된 알고리즘이다.

► O(log n)

로그 시간(logarithmic time)은 입력 데이터의 크기에 비해 알고리즘이 실행되는 시간이 로그 수준으로 증가하는 것을 의미한다. 즉, 입력 데이터의 크기가 커져도 처리 시간은 로그 수준으로만 증가한다.

자바로 이를 표현하면, 이진 검색 알고리즘이 대표적이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

public class Main {
    public static void main(String[] args) {
        int arr[] = {2, 3, 4, 10, 40};
        int n = arr.length;
        int x = 10;
        int result = binarySearch(arr, 0, n - 1, x);
        if (result == -1)
            System.out.println("원소가 존재하지 않습니다.");
        else
            System.out.println("원소 찾음 " + " 인덱스 " + result);
    }

    public static int binarySearch(int arr[], int l, int r, int x)
    {
        if (r >= l) {
            int mid = l + (r - l) / 2;

            // 중앙값이 찾는 값이면 중앙값 반환
            if (arr[mid] == x)
                return mid;

            // 중앙값이 찾는 값보다 크면 왼쪽 하위 배열에서 검색
            if (arr[mid] > x)
                return binarySearch(arr, l, mid - 1, x);

            // 중앙값이 찾는 값보다 작으면 오른쪽 하위 배열에서 검색
            return binarySearch(arr, mid + 1, r, x);
        }

        // 원소가 존재하지 않음
        return -1;
    }
}

여기서 binarySearch 함수는 주어진 정렬된 배열에서 주어진 숫자 x를 찾는다. 배열의 크기가 n이라면, 이 함수는 최악의 경우 log(n)의 시간 복잡도를 갖는다.

고등학생 때 배웠던 로그랑 지수 배웠던 거 다시 뇌 가동하기…

로그

로그는 ‘거듭제곱 횟수’를 나타낸다.

  • b는 밑, c는 지수, a는 진수

예를 들어 log2(8)은 “2를 몇 번 곱해야 8이 되는가?” 인데, 여기서는 2를 세 번 곱해야 8이 되니, log2(8)은 3이 된다.

그래서 로그와 알고리즘 시간 복잡도가 무슨 관계가 있는건가

이진 탐색을 예로 들자. 이진 탐색은 정렬된 리스트에서 특정 값을 찾는 알고리즘인데, 매 단계마다 리스트를 반으로 나눠서 찾고자 하는 값이 어느 쪽에 있는지 판단한다.

리스트의 원소가 n개일 때 최대 log(n)번만에 값을 찾을 수 있다. 왜냐하면 매번 리스트를 반으로 나누는 것은 곧 2의 거듭제곱으로 원소의 수를 줄이는 것이기 때문이다. 그래서 시간 복잡도는 O(log n)으로 표현된다.

Reference

https://m.hanbit.co.kr/media/channel/view.html?cms_code=CMS7965376216 https://ko.khanacademy.org/math/algebra2/x2ec2f6f830c9fb89:logs/x2ec2f6f830c9fb89:log-intro/a/intro-to-logarithms

Algorithms
Algorithms 알고리즘
This post is licensed under CC BY 4.0 by the author.