시간복잡도

실행시간이란?

실행시간이란 프로그램이 시작되어 모든 코드를 실행하고 종료되기까지 걸리는 실제 시간이다.

코드는 CPU가 한 줄씩 순차적으로 처리하며, 이 과정을 통해 실행시간이 결정된다. 하지만 실행시간은 다음과 같은 여러 요소에 의해 영향을 받는다...

• 시스템 부하: 백그라운드에서 실행 중인 다른 프로그램
• I/O 대기 시간: 디스크, 네트워크 등 외부 자원 접근 시간
• 하드웨어 성능: CPU 속도, 메모리 크기 등
• 운영체제 스케줄링: CPU를 어떤 프로세스에 언제 할당할지 결정

같은 코드를 같은 컴퓨터에서 여러 번 실행해도 실행시간은 조금씩 달라질 수 있다. 하지만 입력값의 크기 변화에 따라 실행시간이 어떻게 달라지는지는 예측 가능하다.

예를 들어, 반복문의 반복 횟수가 증가하면 실행시간도 그에 비례해 증가한다.

public class ExecutionTimeExample {
    public static void main(String[] args) {
        int sum = 0;
        for (int i = 0; i < 1_000_000_000; i++) {
            sum += 1;
        }
        System.out.println("Sum: " + sum);
    }
}

위 코드처럼 반복문이 10억 번 실행되면, 단순한 연산이라도 실행시간은 몇 초 이상 걸릴 수 있다.

시간복잡도란?

시간복잡도는 실행시간이 입력값의 크기 nn에 따라 어떻게 증가하는지를 수학적으로 표현한 것이다.

int sum = 0;
for (int i = 1; i < n; i++) {
    sum += i;
}

 

이 코드는 입력값 n에 따라 n−1 번 반복되므로, 실행시간은 n에 비례한다.

 

즉, 시간복잡도는 입력값 n의 함수로 나타낼 수 있으며, 이 함수가 입력에 따라 얼마나 빠르게 커지는지를 파악하는 것이 핵심이다.

점근 표기법 (Big-O)

시간복잡도를 간단하게 표현하기 위해 점근 표기법(Big-O)을 사용한다.

• 최고차항만 남기고 나머지 항은 생략
• 계수는 제거

 

주요 시간복잡도 예시

• O(1): 입력 크기와 무관 (상수 시간)
• O(log⁡n): 이진 탐색
• O(n): 선형 탐색
• O(nlog⁡n): 병합 정렬, 퀵 정렬 평균
• O(n^2): 이중 반복문
• O(2^n): 재귀적 완전탐색
• O(n!): 순열 생성 등

시간복잡도 크기 비교

n! > 2^n > n^3 > n^2 > n log n > n > log n > 1

예시를 통한 시간복잡도 분석

상수 시간 - O(1)

System.out.println("Hello");

반복 횟수와 무관하게 일정한 시간만 소요된다

선형 시간 - O(n)

for (int i = 0; i < n; i++) {
    System.out.println("Hello");
}

입력값 n에 비례하여 실행시간이 증가한다.

이차 시간 - O(n^2)

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        System.out.println("Hello");
    }
}

입력값이 커질수록 실행시간은 제곱에 비례하여 증가한다.

서로 다른 입력 크기 - O(nm)

for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        System.out.println("Hello");
    }
}

두 개의 입력값 nn과 mm이 독립적인 경우, 시간복잡도는 O(nm)이다.

시간복잡도는 최악의 경우(Worst Case) 기준

실제 실행시간은 입력에 따라 달라지지만, 시간복잡도 분석은 일반적으로 최악의 경우(Worst Case)를 기준으로 합니다.

예시: 선형 탐색

public boolean linearSearch(int[] array, int target) {
    for (int element : array) {
        if (element == target) return true;
    }
    return false;
}

• Best case: 첫 번째 요소에서 찾은 경우 → O(1)
• Worst case: 마지막 또는 존재하지 않는 경우 → O(n)
• Average case: 대략 절반 정도 확인 → O(n)

평균을 계산하는 것이 복잡한 경우가 많기 때문에, 일반적으로 최악의 시간복잡도를 사용하여 알고리즘의 성능을 평가한다.