알고리즘 - 시간복잡도

개요

• 알고리즘이 수행되는 데 걸리는 시간을 입력크기 n에 대한 함수로 나타낸 것
• 즉, 입력이 커질수록 처리 시간이 얼마나 늘어나는 지를 분석하는 방식

사용하는 이유

• 여러개의 알고리즘이 동일한 문제를 해결할 수 있다 하더라도, 입력크기 n의 값에 따라 성능에 크게 차이가 날 수 있다.
• 시간복잡도를 통해 어떤 알고리즘이 더 효율적인 지 비교할 수 있다.

시간 복잡도 표기 방법

• Big-Ω: 최선의 경우 성능을 나타낸다.
  • 가장 빠를 때의 성능
  • 실제로는 잘 쓰이지 않는다.
• Big-Θ: 정확한 시간 복잡도
  • 최선과 최악의 시간이 같을 때 사용한다.
  • 정확한 성능을 나타낼 수 있다.
• Big-O: 최악의 경우 성능을 나타낸다.
  • 가장 많이 쓰이는 표기법
  • 입력값n이 가장 불리한 상황에서 얼마나 오래 걸리는지를 분석
  • 성능 보장을 위해 중요하다.

시간 복잡도 종류

시간복잡도 이름 예시 의미

O(1)	상수 시간	배열의 특정 인덱스 접근	입력 크기에 상관없이 항상 일정한 시간 소요
O(log n)	로그 시간	이진 탐색	매우 빠름(입력 2배 증가 시 연산 1 증가)
O(n)	선형 시간	배열 한 번 순회	입력 크기에 비례하여 시간 소요
O(n log n)	로그-선형 시간	병합 정렬, 퀵 정렬	효율적인 정렬
O(n²)	이차 시간	버블 정렬, 이중 루프	입력이 커지면 급격히 느려짐
O(2ⁿ)	지수 시간	파보나치 재귀	매우 비효율적
O(n!)	팩토리얼 시간	모든 순열 탐색(완전 탐색)	현실적으로 사용이 어려움

실무에서의 기준

• 1,000 이하: O(n²) 도 괜찮음
• 10,000 ~ 100,000: O(n log n) 이하 권장
• 1,000,000 이상: O(n) 또는 O(log n)

시간 복잡도 분석

1. 입력 크기 n 정의
2. 주요 연산 횟수 세기
3. 중첩 반복문 고려
4. 가장 영향 큰 항만 남기고 단순화