[알고리즘] 시간 복잡도(Time Complexity)란? (Big-O 표기법)

 

 

 

1. 시간복잡도란? 

 

• 시간 복잡도(Time Complexity)란 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것|
  
  
• 시간 복잡도란 크기 n의 모든 입력에 대해 걸리는 최대의 시간(최악의 경우)
  
  
• 명칭이 시간 복잡도라 헷갈릴 수 있지만 시간 복잡도는 시간 개념이 아니라 알고리즘이 실행될 때 동작하는 모든 연산의 횟수가 몇번인지 세는 것
  
  
• 알고리즘의 성능 평가 유형엔 최선, 평균, 최악이 있는데, 이 중 최악의 경우로 알고리즘의 성능을 평가한다. 그 이유는 알고리즘이 복잡해질 수록 평균 성능을 구하기 어렵기도 하며, 나머지 경우 모두 최악의 경우보다는 빠르므로 최악의 경우가 앞선 두 경우를 모두 포함할 수 있기 때문이다. 

 

 

2. Big-O Notation(Big-O 표기법)

 

• Big-O 표기법이란 알고리즘의 효율성을 표기해주는 표기법 이다.
  
  
• 알고리즘의 효율성을 상한선 기준으로 표시한다.
  : 상한선을 기준으로 하여 모든 경우의 수를 포함한다. 최악의 경우로 알고리즘의 성능을 평가하여 알고리즘의 모든 경우의 수를 포괄하는 것이다. 착각하기 쉬운 점은 최악의 경우로 알고리즘의 성능을 평가한다는 것은 효율성이 최악이라는 것은 아니라는 것이다. 모든 경우의 수를 포괄하기 위한 방법일 뿐이다. 
  
  
• 영향력 없는 계수와 낮은 차수의 항은 무시한다.
  : 가장 영향력이 큰 항(차수가 제일 높은 항) 외에 나머지는 무시한다.
  ex) O(2N²+N) = O(N²)

• 상수는 무시한다.
  : Big-O 표기법은 데이터의 입력값의 크기에 따라 영향을 받기 때문에 상수는 무시되거나 1로 통일한다.
    ex) O(N+2) = O(N) / O(7) = O(1)

• Big-O 함수의 성능 비교 :  (빠름) O(1) < O(logN) < O(N) < O(NlogN) < O(N²) < O(2ⁿ) (느림)

 

 

▼  상수  시간 / 함수 :  O(1) 

     -  입력 자료의 수(n)과 상관 없이 언제나 일정한 실행 시간을 갖는 알고리즘 표현 

     -  예시 :  입력 자료와 연관된 연산 없이 탐색, 출력, 반환하는 경우

 

▼  선형  시간 / 함수 :  O(n)

     -  입력 자료의 수(n)에 비례해서 실행 시간을 갖는 알고리즘을 표현 

     -  예시 : n번의 반복문 루프를 도는 경우

 

▼  2차  시간 / 함수 :  O(n²)

     - 예시 : 입력 자료의 수(n)에 대한 이중 for문, 삽입정렬, 저품정렬, 선택정렬 , 면적

     - cf ) O(nm) : 입력 자료의 수(n, m)에 대한 이중 for문으로 n²와는 다름. 

 

▼  3차  시간 / 함수 : O(n³)

     -  예시 : 입력 자료의 수(n)에 대한 삼중 for문, n×n 행렬 두 개의 무식한 곱셈, 편상 관계 계산, 큐빅 

 

▼  지수  시간 / 함수 : O(2ⁿ)

     -  예시: 피보나치 수열

 

▼  로그 시간 / 함수 : O(logn) 

     -  예시 : 이진 검색, 퀵 정렬, 병합 정렬, 힙 정렬

 

 

 

3.  알고리즘 문제 풀기 전 대략적 계산 방법

 

• 일반적으로 1억번 연산이 1초정도 걸리므로 문제를 풀 때 가능한 연산의 횟수는 시간 제한 초수 * 1억이다.
• 다시 말해서 내 알고리즘 코드에서 최악의 경우일 때, 위에서 계산한 가능 연산 횟수를 초과하지 않으면 된다.
• 문제에서 주어지는 최대 입력 데이터 수를 보고 대략적으로 가능한 시간복잡도를 파악하여 구상한다. 

 

데이터 수	시간복잡도	연산 횟수
10⁸	n, logn	1억번의 연산
10⁶	nlogn	1억번의 연산
10⁴	n²	1억번의 연산
500	n³	1억번의 연산
20	n!, 2ⁿ	1억번의 연산