시간복잡도

시간복잡도

알고리즘의 시간 복잡도는 알고리즘을 실행하는 데 걸리는 시간을 입력 크기에 따라 표현한 것이다.

보통 입력 값이 적을 때에는 시간 복잡도를 깊이 있게 고민하지 않지만 실제로 방대한 양의 데이터는 수만 ~ 수억 개의 데이터를 처리해야한다. 입력값이 커짐에 따라 연산 처리 시간의 양을 최소화 하는 방법에 대한 고민이 필수적이다.

 

시간 복잡도를 이해하면, 특정 문제에 대해 작성한 알고리즘이 얼마나 효율적인지를 평가할 수 있다.

이를 통해 입력 크기가 커질 때 알고리즘이 얼마나 빨리 실행되는지, 혹은 느려지는지를 알 수 있다.

 

 

Big-O 표기법

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

빅오는 최악의 경우를 기준으로 알고리즘의 성능을 나타내며, 가장 많이 쓰이는 표기법이다.

Big-O 그래프 출처 : https://velog.io/@welloff_jj/Complexity-and-Big-O-notation

O(1)

상수 시간 복잡도라고 부른다. 입력 크기에 관계없이 알고리즘이 항상 같은 시간이 걸린다.

입력 크기에 상관없이 항상 일정한 시간이 걸리는 경우를 의미한다. 특정 연산이 한 번만 수행될 때 나타나는 복잡도이다.

바꾸어 말하면 입력값의 크기에 관계없이 출력값을 얻어내는데 걸리는 시간이 일정하다는 의미이다.

배열의 특정 인덱스에 접근하는 작업이 이에 해당한다.

입력 크기가 아무리 커져도 실행 시간이 변하지 않기 때문에 알고리즘이 매우 효율적이다.

O(log n)

로그 시간 복잡도라고 부른다. 입력 크기가 커져도 실행 시간이 느리게 증가한다.

주로 입력을 반씩 줄여 나가는 경우에 발생한다. 여기서 log n은 보통 2를 밑으로 하는 로그(이진 로그)를 의미한다.

Big-O 표기법 중 O(1) 다음으로 빠른 시간 복잡도를 가진다.

이진 탐색(Binary Search)이 대표적이다. 이진 탐색은 정렬된 배열에서 중간값을 반복적으로 확인하며 원하는 값에 접근하므로, 탐색 대상의 크기가 n, n/2, n/4로 계속 줄어든다.

 

O(n)

선형 시간 복잡도라고 부른다. 입력 크기에 비례해 실행 시간이 증가한다. 일반적으로 한 번의 루프로 모든 데이터를 순회해야 하는 알고리즘에서 나타난다. 

 입력값이 1개 있을 때 1초의 시간이 걸리고, 입력값을 100배 증가시켰을 때 처리 시간이 같은 비율로 늘어나 100초가 걸린다면 그 알고리즘은 O(n)의 시간 복잡도를 가진 알고리즘이라고 할 수 있다.

입력이 커질수록 실행 시간이 비례하여 증가한다. 하지만, O(n) 시간 복잡도는 많은 문제에서 현실적으로 적용 가능한 범위의 효율적인 복잡도로 평가된다.

 

O(n^2)

이차 시간 복잡도라고 부른다. 입력 크기에 따라 실행 시간이 제곱에 비례해 증가한다. 일반적으로 이중 for문과 같은 중첩 루프에서 발생한다.

버블 정렬(Bubble Sort), 선택 정렬(Selection Sort) 등이 이에 해당한다. 예를 들어, 두 개의 중첩된 루프가 전체 데이터를 한 번씩 확인하며 특정 조건을 체크하는 경우, 데이터 개수가 n일 때 n^2 번의 연산이 발생한다.

입력 크기가 커질수록 실행 시간이 매우 빠르게 증가하여 비효율적이다. 작은 데이터셋에서는 사용할 수 있지만, 큰 입력에서는 부적합하다.

O(n log n)

선형 로그 시간 복잡도라고 부른다. 입력 크기에 선형적이면서 로그에 비례한 시간이 걸리는 경우이다.

보통 효율적인 정렬 알고리즘에서 많이 나타난다.

병합 정렬(Merge Sort)과 퀵 정렬(Quick Sort)이 대표적이다. 이 알고리즘들은 배열을 재귀적으로 나누고 각 부분을 정렬하며, 각 분할마다 O(log n)의 단계가 필요하고, 전체 데이터 수 만큼 반복하므로 O(n log n)이 된다.

 

O(n log n) 복잡도는 정렬 문제에서 현실적으로 가장 효율적인 수준이다. 따라서 대용량 데이터를 다룰 때 자주 사용하는 알고리즘이 이 복잡도를 갖는다.

O(2^n)

지수 시간 복잡도라고 부른다. 입력 크기가 커질 때 실행 시간이 급격히 증가한다.  

피보나치 수열이 대표적인 예이다.

지수 시간 복잡도를 가진 알고리즘은 입력 크기가 조금만 증가해도 수행 시간이 빠르게 늘어나기 때문에, 일반적으로 입력 크기가 작을 때만 사용할 수 있다. 큰 입력에 대해서는 현실적으로 실행이 불가능할 정도로 시간이 오래 걸릴 수 있다.

따라서지수 시간 복잡도는 최대한 피해야 할 복잡도 중 하나이며, 더 효율적인 알고리즘을 통해 시간 복잡도를 줄이는 것이 바람직하다.

O(n!)

팩토리얼 시간 복잡도라고 부른다. 입력 크기 n에 대해 가능한 모든 순열을 고려해야 할 때 나타나는 복잡도이다.

n!은 1부터 n까지의 모든 정수를 곱한 값이므로, 값이 매우 빨리 커진다.

가장 비효율적인 시간 복잡도 중 하나이다. n이 조금만 커져도 현실적으로 해결할 수 없는 경우가 많기 때문에 보통 이런 문제는 효율적인 알고리즘(예: 백트래킹, 메모이제이션)을 적용하거나, 근사 알고리즘을 통해 최적해 대신 근사해를 찾는 방식으로 접근한다.