Time Complexity (시간 복잡도)

Time Complexity (시간 복잡도)

알고리즘의 핵심은 얼마나 효율적으로 코드를 작성하는가에 있다. 이 효율성을 검증하는데에 시간 복잡도를 들 수 있다.

• 시간 복잡도는 알고리즘이 입력 크기에 따라 소요되는 시간의 증가율을 말한다.
• 즉, 알고리즘을 설계할 때, 시간 복잡도를 고려한다는 것은 알고리즘이 처리하는 데이터의 크기에 따라 실행 시간이 어떻게 증가하는지를 고려하는 것을 의미한다.
• 시간 복잡도를 고려하여 알고리즘을 설계하면 다음과 같은 장점이 있다.
  • 입력의 크기에 따라 실행 시간이 어떻게 증가하는지 사전 파악 가능
  • 실행시간 최소화 및 효율적인 문제 해결
  • 그로 인해 최적의 알고리즘 발견

Big - O 표기법

시간 복잡도를 표기하는 방법은 크게 3가지가 있다.

• Big-O(빅-오) ⇒ 상한 점근 (최악)
• Big-Ω(빅-오메가) ⇒ 하한 점근 (최선)
• Big-θ(빅-세타) ⇒ 그 둘의 평균 (평균)

 

이 3가지 방법 중 주로 Big-O표기법을 사용하는데 그 이유는 다음과 같다.

• 우리가 애플리케이션을 사용할 때 사용자 입장에서 오류 상황이 발생하지 않기 위한 노력을 한다.
• 즉, 애플리케이션을 개발함에 있어, 오류가 나는 다양한 상황들을 테스트 해야 한다.
• 또한, 최악의 경우에서 효율적으로 시간이 적게 걸린다면, 최선일 경우, 평균일 경우는 더 좋은 결과가 당연히 발생하게 된다.
• 따라서, 이러한 테스트에 있어서는 최악의 상황( Big-O )을 체크하는 것이 좋다.

 

Big-O 표기법의 종류

• O(1) : 일정한 복잡도 
• O(n) : 선형 복잡도
• O(log n) : 로그 복잡도
• O(n²) : 2차 복잡도
• O(2ⁿ) : 기하급수적 복잡도

시간복잡도 그래프

 

O(1) - 일정한 복잡도 (good)

O(1) 은 일정한 복잡도라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않는다. 즉, 크기와 상관없이 바로 출력이 가능하다는 의미이다.

• 대표 알고리즘 : 상수 시간 알고리즘

O(1)의 시간 복잡도를 가진 알고리즘

public class ArrayExample {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        int element = arr[2];
        System.out.println("배열의 세 번째 요소: " + element);
    }
}

• 이 알고리즘은 입력 값이나 데이터가 아무리 커져도 즉시 값을 조회할 수 있다.

 

O(n) - 선형 복잡도 (good)

선형 복잡도는 입력값이 증가함에 따라 시간이 같은 비율로 증가하는 것을 의미한다.

• 대표 알고리즘 : 선형 탐색 (Linear Search)

O(n)의 시간 복잡도를 가진 알고리즘

public class LinearTimeExample {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}

• 위 예시는 길이가 5인 배열 arr을 선언하고, 배열의 모든 요소를 반복문을 통해 출력한다.
• 반복문은 배열의 길이에 비례하여 실행되기 때문에 배열의 크기에 따라 수행 시간이 같은 비율로 증가하게 된다.

 

O(log n) - 로그 복잡도 (good)

O(1) 다음으로 빠른 시간복잡도이며, 입력 크기가 증가할 때마다 수행시간이 상대적으로 더 적게 증가한다.

• 대표 알고리즘 : 이진 탐색 (Binary Search)

O(log n)의 시간 복잡도를 가진 알고리즘

public class LogarithmicTimeExample {
    public static void main(String[] args) {
        int n = 16;
        int count = 0;

        while (n > 1) {
            n = n / 2;
            count++;
        }

        System.out.println("반복 횟수: " + count);
    }
}

• 위 예시는 초기값이 16인 변수 n을 반복문을 사용하여 2로 나누고, 반복횟수를 세는 변수 count를 증가시킨다. 이 과정을 n이 1보다 작아질 때까지 반복한다.
• 반복문을 돌 때, 변수 n을 2로 나눔으로써 초기값의 절반만을 탐색하므로 입력의 크기에 비해 수행 시간이 적게 증가한다.

 

O(n²) - 2차 복잡도 (bad)

입력 크기 n에 대해 2차 함수의 형태로 증가하는 알고리즘으로 다시말해, 입력 크기의 제곱에 비례하여 수행시간이 증가한다.

• 대표 알고리즘 : 이중 반복문 알고리즘

O(n²)의 시간 복잡도를 가진 알고리즘

public class QuadraticTimeExample {
    public static void main(String[] args) {
        int[] arr = {5, 2, 9, 1, 7};

        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length; j++) {
                System.out.println(arr[i] + "와(과) " + arr[j] + " 비교");
            }
        }
    }
}

• 위 예시는 길이가 5인 배열 arr의 모든 요소를 비교하는 알고리즘으로 이중 반복문을 사용하여 모든 요소의 조합을 비교하고, 각 비교 결과를 출력한다.
• 이 과정에서 배열의 요소 하나 당 배열에 있는 5개의 요소를 비교해야하니 시간 복잡도는 5² = 25가 된다.
• 이처럼, O(n²) 시간 복잡도는 입력 크기에 비례하여 급격하게 수행시간이 증가하기 때문에 효율적이지 않다.

 

O(2ⁿ) - 기하급수적 복잡도 (bad)

입력 크기에 대해 기하급수적으로 증가하는 알고리즘으로 일반적으로 매우 느리며, 입력 크기가 조금만 커져도 수행시간이 급격하게 증가한다.

• 대표 알고리즘 : 완전 탐색 (Exhaustive Search)

O(2ⁿ)의 시간 복잡도를 가진 알고리즘

public class FibonacciExample {
    public static void main(String[] args) {
        int n = 10;
        
        System.out.println("피보나치 수열의 첫 " + n + "개 항:");
        for (int i = 0; i < n; i++) {
            System.out.print(fibonacci(i) + " ");
        }
    }
    
    public static int fibonacci(int n) {
        if (n <= 1) {
            return n;
        } else {
            return fibonacci(n - 1) + fibonacci(n - 2);
        }
    }
}

• 위 예시는 피보나치 수열을 구현한 예시로, 재귀 함수를 사용하여 피보나치 수열의 n번째 항을 구한다.
• fibonacci() 메서드 내부에서는 n이 1 이하일 경우 n을 반환하고, 그 외의 경우에는 이전 두 항의 값을 재귀적으로 호출 하여 더한 값을 반환한다.
• 이처럼 재귀적인 호출을 사용하는 알고리즘의 경우, 시간복잡도가 지수적으로 증가하기 때문에 효율적이지 않다.

 

시간복잡도 도출 기준

• 상수는 시간 복잡도 계산에서 제외한다.
• 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다.

시간 복잡도를 구하는 방법

• 1개의 반복문을 사용하여 단일 요소 집합을 반복 하는 경우 : O (n)
• 컬렉션의 절반 이상을 반복 하는 경우 : O (n / 2) -> O (n)
• 2개의 다른 반복문을 사용하여 2개의 개별 콜렉션을 반복 할 경우 : O (n + m) -> O (n)
• 2개의 중첩 반복문을 사용하여 단일 컬렉션을 반복하는 경우 : O (n²)
• 2개의 중첩 반복문을 사용하여 2개의 다른 콜렉션을 반복 할 경우 : O (n m) -> O (n²)
• 컬렉션 정렬을 사용하는 경우 : O(nlog(n))

 

연산횟수를 계산하는 방법 

연산 횟수 = 알고리즘 시간복잡도 * 데이터의 크기

 

 

정렬 알고리즘의 시간복잡도 비교

 

자료구조 시간복잡도 비교

 

 

 

[참고]

https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-time-complexity-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84/

[알고리즘] Time Complexity (시간 복잡도) - 하나몬

https://velog.io/@crosstar1228/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%8B%9C%EA%B0%84%EB%B3%B5%EC%9E%A1%EB%8F%84Time-Complexity%EC%99%80-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0

[자료구조]시간복잡도(Time Complexity)와 알고리즘, 자료구조