[TIL] 시간 복잡도와 빅오 표기법(Big-O notation)

240724

시간 복잡도란 (Time Complexity) ?

알고리즘이 수행(연산)되는 데 필요한 시간의 양을 입력 크기 n에 대한 함수로 표현한 것이다.

그 말은 좋은 알고리즘은  입력값이 늘어나도 걸리는 시간이 덜 늘어나는 알고리즘이라는 거었다.

 

시간 복잡도가 중요한 이유

 

• 성능 : 알고리즘이 큰 입력 데이터에 대해서 어떻게 동작할지를 성능을 추측할 수 있다.
• 효율: 서로 같은 값을 얻는 알고리즘도 들이는 시간을 기준으로 더 효율적인 알고리즘을 알 수 있다. 
• 최적화: 더 빠른 알고리즘을 설계하고 최적화할 수 있는 방향을 제시한다.

 

빅오 표기법(Big-O notation)

알고리즘의 효율성을 분석하는 도구, 알고리즘이 커지는 입력 크기에 대해 얼마나 자원(시간 or 공간)을 소비하는지를 표현하는 방법이다. 빅오 표기법은 최악의 경우를 나타내며, 입력 크기 n이 무한히 커질 때 알고리즘의 성능을 나타내는 데 사용된다.

 

 

• O(1) - 상수 시간(Constant Time)
  • 입력 크기에 상관없이 항상 일정한 시간이 걸리는 알고리즘.
  • ex) 배열의 특정 인덱스에 접근하는 연산.
• O(log n) - 로그 시간(Logarithmic Time)
  • 입력 크기가 커질수록 시간이 조금씩 증가하는 알고리즘. 입력값이 클수록 효율성이 눈에 띈다.
• O(n) - 선형 시간(Linear Time)
  • 입력 크기에 비례하여 시간이 증가하는 알고리즘.
  • ex) 배열의 모든 요소를 한 번씩 확인하는 연산.
• O(n log n) - 선형 로그 시간(Linearithmic Time)
  • 로그 시간과 선형 시간이 결합된 알고리즘.
• O(n^2) - 이차 시간(Quadratic Time)
  • 입력 크기의 제곱에 비례하여 시간이 증가하는 알고리즘.
• O(2^n) - 지수 시간(Exponential Time)
  • 입력 크기에 따라 시간이 지수적으로 증가하는 알고리즘.

효율순서

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) 

 

 그래서 보통은 O(n)을 기준으로 이보다 효율이 낮은 알고리즘을 시간복잡도가 안 좋은 알고리즘이라고 하고, 

이보다 효율이 높으면 좋은 알고리즘이라고 한다.