[알고리즘] 시간 복잡도

시간 복잡도

시간 복잡도(time complexity)란 가장 널리 사용되는 알고리즘의 수행 시간 기준으로, 알고리즘이 실행되는 동안 수행하는 기본적인 연산의 수를 입력의 크기에 대한 함수로 표현한 것입니다.

일반적으로 점근 표기법을 사용하여 시간 복잡도를 나타내며, O(⋯) 형태로 표기합니다. O(⋯) 안에는 입력 크기(n)에 따른 실행 횟수를 함수로 표현합니다.

 

O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2ⁿ) < O(n!) 

 

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

• 입력 크기에 상관없이 일정한 시간이 걸리는 알고리즘
• 예: 주로 수학 공식등을 이용해 답을 바로 계산해내는 문제

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

• 입력 크기가 커질수록 실행 시간이 느리게 증가
• 예: 이진 탐색(Binary Search)

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

• 입력 크기에 비례하여 실행 시간이 증가
• 예: 배열에서 특정 값을 찾는 선형 탐색(Linear Search)

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

• 입력 크기가 커질수록 실행 시간이 n과 logn의 곱에 비례하여 증가
• 예: 효율적인 정렬 알고리즘(예: 퀵 정렬, 병합 정렬, 힙 정렬)

O(n²): 이차 시간 복잡도

• 입력 크기가 커질수록 실행 시간이 n²에 비례하여 증가합니다.
• 예: 이중 루프를 사용하는 알고리즘(예: 버블 정렬, 삽입 정렬).

O(2ⁿ): 지수 시간 복잡도

• 입력 크기가 커질수록 실행 시간이 매우 빠르게 증가합니다.
• 예: 모든 부분집합을 탐색하는 알고리즘(예: 부분집합 합 문제).

O(n!): 팩토리얼 시간 복잡도

• 입력 크기가 커질수록 실행 시간이 팩토리얼에 비례하여 증가합니다.
• 예: 모든 순열을 탐색하는 알고리즘.

수행시간을 예상하는 가장 많이 사용되는 방법은 1초에 1억($10^8$)번의 연산이 수행된다고 가정하는 것 입니다.

 

 

 

출처 : 안즈 블로그, 라이 블로그, 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략