알고리즘. 시간복잡도와 Big-O 표기법 알아보기

1 분 소요

🌟 Big-O 표기법Permalink

알고리즘의 복잡도에는 시간 복잡도와 공간 복잡도가 있다.

시간 복잡도는 문제를 해결하는데 걸리는 시간과 입력의 함수 관계고, 공간 복잡도는 메모리 크기다. 알고리즘에서는 시간 복잡도가 더 중요!

이때 시간 복잡도를 나타내는 방법으로 Big-O 표기법을 사용한다.

빅 오 표기법은 최악의 실행 시간을 표기하고, 다른 표기법으로는 최상의 실행 시간을 표기하는 Big-Ω 빅 오메가 표기법, 평균 실행 시간을 표기하는 Big-θ 빅 세타 표기법이 있다.

가장 사용하기 편한 게 빅 오 표기법이라 빅 오 표기법으로 시간 복잡도를 나타낸다.

Big-O 표기법으로 나타내는 방법

printf("Hello, World");

int arr[] = {1, 2, 3};
printf(arr[0]);

값이 크거나 작아도 즉시 출력할 수 있으므로 이런 건 O(1)의 시간 복잡도를 가진다.

for(int i = 0; i < n; i++)
{
    //...
}

이런 건 n의 크기에 따라 실행 시간이 증가해서 O(N)이라고 표기한다.

for(int i = 0; i < n; i++)
{
    for(int j = 0; j < m; j++)
    {
        //...
    }
}

이건 반복문이 두 번 있는 경우!

이건 입력 크기에 따라 처리 시간이 증가하는 정렬 알고리즘에서 많이 사용된다고 함!

이건 기하급수적 복잡도라고 불리며, 가장 느린 시간을 나타낸다. 피보나치 수열이 이 시간 족잡도를 가지고 있으며, 뭘 할 때마다 두 배로 실행 시간이 늘어난다고 보면 됨!

n / 2나, n에 m이나 다른 미지수가 더해져도 그대로 n이라고 나타냄. 왜냐면 스케일이 커질 수록 n 앞의 숫자는 의미가 없기 때문!

Chulgil.Lee