CS 알고리즘 시간복잡도

시간 복잡도(Time Complexity)는 알고리즘이 처리하는 작업의 양이 입력 데이터의 크기에 따라 어떻게 변화하는지를 분석한 것이다. 입력 크기가 커짐에 따라 알고리즘이 얼마나 많은 시간을 소요하는지를 나타내는 척도라고할 수 있다. 주로 사용되는 빅오 표기법(Big-O Notation)에 대해 간단히 알아본다.

 

ㅇ 빅오 표기법(Big-O Notation)

• O(1) - 상수 시간(Constant Time) (오-원)
  입력 크기와 상관없이 항상 일정한 시간이 걸리는 경우
  예 : 배열에서 특정 인덱스의 요소에 접근할 때

 

• O(log n) - 로그 시간(Logarithmic Time) (오-로그-엔)
  입력 크기가 증가할 때, 시간이 로그 단위로 증가하는 경우
  예 : 이진 탐색(Binary Search)

 

 

• O(n) - 선형 시간(Linear Time) (오-엔)
  입력 크기에 비례하여 시간이 증가하는 경우
  예 : 배열의 모든 요소를 하나씩 탐색하는 경우

 

• O(n^2) - 이차 시간(Quadratic Time) (오-엔-스퀘어)
  입력 크기에 제곱에 비례하여 시간이 증가하는 경우
  예 : 중첩된 루프(이중 for문)를 사용하는 알고리즘

 

 

• O(2^n) - 지수 시간(Exponential Time) (오-이의-엔승)
  입력 크기에 n에 대해 실행 시간이 지수적으로 증가하는 경우
  예 : 피보나치 수열을 재귀적으로 계산하는 경우

 

입력 크기 n이 커질 수록 O(1) ~ O(2^n) 더 많이 시간이 소요된다.