[알고리즘 개념] 시간복잡도란?

알고리즘의 시간복잡도(Time Complexity)

• 알고리즘이 입력의 크기에 따라 실행 시간이 어떻게 증가하는지를 나타내는 개념이다.
• 알고리즘의 시간복잡도는 보통 Big O 표기법을 사용하여 나타냅니다.

 

 

Big O 표기법

• 시간복잡도를 나타내는 방법 중 하나로, 알고리즘의 실행 시간이 입력의 크기에 대해 상한을 나타내는 표기법이다.
• 다음 복잡도는 차수가 낮은 순서이다.

1. O(1) : 상수 시간 복잡도

입력 크기에 관계없이 항상 일정한 실행 시간을 가집니다.

 

2. O(log n) : 로그 시간 복잡도

입력 크기가 증가함에 따라 실행 시간이 로그 함수로 증가한다. 이진 탐색과 같은 알고리즘에 해당한다.

 

3. O(n) : 선형 시간 복잡도

입력 크기에 비례하여 실행 시간이 증가한다. 선형 탐색과 같은 알고리즘이 여기에 해당한다.

 

4. O(n log n) : 선형로그 시간 복잡도

입력 크기에 비례하여 실행 시간이 n과 로그 n의 곱으로 증가한다. 합병 정렬과 퀵 정렬과 같은 일부 정렬 알고리즘이 여기에 해당한다.

 

5. O(n^2) : 제곱 시간 복잡도

입력 크기에 비례하여 실행 시간이 n의 제곱으로 증가한다. 버블 정렬과 삽입 정렬과 같은 일부 정렬 알고리즘이 여기에 해당한다.

 

6. O(n!) : 펙토리얼 복잡도

n의 팩토리얼은 1부터 n까지의 양의 정수를 모두 곱한 값을 의미한다. 펙토리얼 연산은 입력 크기 n에 대해 매우 빠르게 증가하기 때문에 매우 비효율적이다.

 

 

시간복잡도를 근거로 제한 조건을 파악하는 방법

1. 문제의 크기(N)를 파악하기

문제에서 입력으로 주어지는 데이터의 크기를 확인한다. 입력 크기가 주어지지 않은 경우, 문제에서 시간제한을 주로 어느 정도로 설정하였는지를 확인하는 것이 도움이 된다.

2. 반복문 개수 세기

주어진 알고리즘에서 반복문이 몇 번 실행되는지 확인한다.

3. 연산 복잡도 계산

주어진 알고리즘이 수행하는 주요 연산의 복잡도를 계산하는데 대표적으로 O(1), O(log N), O(N), O(N^2) 등의 시간복잡도가 있다.

4. 최악의 경우 계산

주로 알고리즘의 최악의 경우 시간복잡도를 파악한다. 이를 통해 알고리즘이 어떤 경우에도 시간 내에 해결이 가능한지 판단할 수 있다.

5. 반복문 안의 중첩과 계산 복잡도

반복문이 중첩되는 경우, 각 반복문의 복잡도를 합산하여 총 복잡도를 계산한다.

6. 재귀 알고리즘 복잡도

재귀 함수를 사용하는 알고리즘의 경우, 재귀 호출 횟수와 각 호출의 복잡도를 파악하여 총 복잡도를 계산한다.