00. 시간복잡도

시간복잡도

• 알고리즘의 시간복잡도는 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것.

• 알고리즘의 최적화를 위해 필요하다.

• 알고리즘의 시간복잡도는 주로 빅-오 표기법을 사용하여 나타낸다.

• 빅-오 표기법은 계수와 낮은 차수의 항을 제외시켜 간소화한다.

• 상수 시간(Constant time)

  • 알고리즘이 입력 크기에 구애받지 않는 값에 의해서 한정된다면, 상수 시간이라고 말 할 수 있다.
  • 예를 들어, 단 하나의 연산이 어떤 배열에서의 요소 위치를 알아내는 것을 수행한다고 할 때, 이 요소의 접근하는 것은 상수 시간이 걸린다.

• 선형 시간(Linear time)

  • T(n) = O(n)
  • 수행시간이 입력 크기에 따라 선형적으로 증가한다.
  • 예를 들어, 리스트의 모든 요소를 더하는 알고리즘은 리스트의 길이에 비례하는 시간을 요구한다/

• 로그 시간(Logarithmic time)

  • T(n) = O(log n) 일 때, 로그 시간이 걸린다고 말할 수 있다.
  • 컴퓨터가 이진수 시스템을 사용하기 때문에, 밑을 대부분 2로 사용한다.
  • 로그 시간이 걸리는 알고리즘은 이진트리에서의 연산에서나 또는 이진 탐색에서 찾아볼 수 있다.
  • 예를 들어, 문자열을 절반으로 쪼개어 그 오른쪽의 문자열을 다시 또 절반으로 쪼개고, 이를 반복하는 알고리즘으로 생각할 수 있다.

• 다항 시간(Polynomial time)

  • T(n) = O(n^k) 와 같이, 입력 크기에 어떤 다항 표현의 상한을 가지고 수행되는 알고리즘.
  • 예를 들어, 정수 n에 대한 선택 정렬 알고리즘이 상수 A에 대해서 An&2개의 연산을 수행한다. O(n^2)

• 시간복잡도의 크기에 따른 증가속도의 그래프이다.