시간 복잡도란?

📌 시간 복잡도란?

알고리즘이 문제를 해결하기 위한 시간(연산)의 횟수를 말한다.
알고리즘을 평가할 때는 2가지를 사용한다.

• 수행시간에 해당하는 것이 시간 복잡도 Time Complexity
• 메모리 사용량에 해당하는 것이 공간 복잡도 Space Complexity

📌 빅-오 표기법(Big-O)이란?

연산 횟수를 카운팅 할 때는 3가지를 사용한다.

• 최선의 경우 Best Case
• 최악의 경우 Worst Case
• 평균적인 경우 Average Case

알고리즘이 복잡해 질수록 평균적인 경우는 구하기가 매우 어려워 지므로 알고리즘의 성능을 파악할 때는 최악의 경우로 판단한다. 이 때 최악의 경우를 계산하는 방식을 빅-오(Big-O) 표기법이라고 한다.

• O(1) (Constant)
  프로그램에서 1라인이 실행되는 경우, 1이라고 표현

• O(log₂ n) (Logarithmic)
  입력 데이터의 크기가 커질수록 처리 시간이 로그(log: 지수 함수의 역함수) 만큼 짧아지는 경우, 이진 탐색이 대표적이며, 재귀가 순기능으로 이루어지는 경우도 해당된다.

• O(n) (Linear)
  입력 데이터의 크기에 비례해 처리 시간이 증가할 경우, 1차원 for문 즉, 반복문이 N번만큼 반복할 경우

• O(n log₂ n) (Linear-Logarithmic)
  데이터가 많아질수록 처리시간이 로그(log) 배만큼 더 늘어나는 알고리즘, 정렬 알고리즘 중 병합 정렬, 퀵 정렬이 대표적

• O(n²) (quadratic)
  데이터가 많아질수록 처리시간이 급수적으로 늘어나는 경우, 이중 루프가 대표적

• O(2ⁿ) (Exponential)
  데이터량이 많아질수록 처리시간이 기하급수적으로 늘어나는 경우, 피보나치 수열과 재귀가 역기능을 할 경우가 대표적

(n이란 입력되는 데이터를 의미)