시간복잡도

개념

시간복잡도(Time Complexity)는 알고리즘이 실행되는 데 걸리는 시간을 입력 크기 N에 대해 표현한 것인데 코딩 테스트에서는 실제 실행 시간이 아니라 입력 크기가 증가할 때 연산 횟수가 얼마나 증가하는지를 기준으로 알고리즘의 효율성을 판단합니다.

대표적인 시간복잡도

복잡도	의미	예시
$O(1)$	상수 시간	배열 인덱스 접근
$O(\log N)$	로그 시간	이진 탐색
$O(N)$	선형 시간	배열 순회
$O(N \log N)$	로그 선형	정렬
$O(N^2)$	이중 반복문	브루트포스
$O(2^N)$	지수 시간	부분집합 탐색

예시

$O(1)$

배열의 특정 인덱스에 접근하는 연산은 입력 크기와 관계없이 항상 동일한 시간이 걸립니다.

Java

int value = arr[5];

Python

value = arr[5]

JavaScript

let value = arr[5];

$O(\log N)$

이진 탐색은 탐색 범위를 절반씩 줄여가며 탐색합니다.

Java

while(left <= right){
    int mid = (left + right) / 2;
    if(arr[mid] == target) break;
    else if(arr[mid] < target) left = mid + 1;
    else right = mid - 1;
}

Python

while left <= right:
    mid = (left + right) // 2
    if arr[mid] == target:
        break
    elif arr[mid] < target:
        left = mid + 1
    else:
        right = mid - 1

JavaScript

while(left <= right){
    let mid = Math.floor((left + right) / 2);
    if(arr[mid] === target) break;
    else if(arr[mid] < target) left = mid + 1;
    else right = mid - 1;
}

$O(N)$

배열을 처음부터 끝까지 한 번 순회하는 경우입니다.

Java

for(int i = 0; i < n; i++){
    System.out.println(arr[i]);
}

Python

for i in range(n):
    print(arr[i])

JavaScript

for(let i = 0; i < n; i++){
    console.log(arr[i]);
}

$O(N \log N)$

대표적으로 정렬 알고리즘이 있습니다.

Java

Arrays.sort(arr);

Python

arr.sort()

JavaScript

arr.sort((a,b) => a - b);

$O(N^2)$

이중 반복문이 있는 경우입니다.

Java

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

Python

for i in range(n):
    for j in range(n):
        print(i, j)

JavaScript

for(let i = 0; i < n; i++){
    for(let j = 0; j < n; j++){
        console.log(i, j);
    }
}

$O(2^N)$

모든 부분집합을 탐색하는 경우입니다.

Java

void dfs(int depth){
    if(depth == n) return;

    dfs(depth + 1);
    dfs(depth + 1);
}

Python

def dfs(depth):
    if depth == n:
        return

    dfs(depth + 1)
    dfs(depth + 1)

JavaScript

function dfs(depth){
    if(depth === n) return;

    dfs(depth + 1);
    dfs(depth + 1);
}