시간복잡성(Time Complexity)

시간복잡성이란??

시간복잡성이란 어떤 문제를 해결하는데 걸리는 시간과 입력의 함수관계를 의미한다.

이때 실행시간을 기준으로 잡지 않고 연산의 횟수로 기준을 잡는데 그 이유는 실행시간은 플랫폼마다 다른 실행시간이 나오기 때문이다.

 

시간복잡성 표기법

시간복잡성의 표기는 다음과 같이 3가지가 있다.

• 최상의 경우 : 오메가 표기법 (Big-Ω Notation)
• 평균의 경우 : 세타 표기법 (Big-θ Notation)
• 최악의 경우 : 빅오 표기법 (Big-O Notation)

이 중에서 가장 많이 쓰이는 것은 빅오 표기법이다.

빅오 표기법은 만약 0(log n) O(n) O(n^2) 세가지 경우가 나올 때 가장 느린 속도를 대표로 하는 것이다.

 

Big-O의 표기의 종류

Big-O에서의 시간복잡성 종류는 다음과 같다.

• O(1) – 상수 시간(constant time) : 문제를 해결하는데 오직 한 단계만 처리하는 가장 빠른 시간복잡도이다.
  ex)배열에서 특정인덱스의 값 읽기
• O(log n) – 로그 시간(logarithmic time) : 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듬.
  ex)이진트리에서 특정 값 찾기
• O(n) – 직선적 시간(liner time) : 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가짐.
  ex)일반적인 반복문이나 이를 이용한 배열, 링크드리스트의 특정 값 찾기
• O(n log n) -선형로그 시간(linerithmic time) : 문제를 해결하기 위한 단계의 수가 N*(log2N) 번만큼의 수행시간을 가진다.
•  O(n^2) –다항 시간(quadratic time) : 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱
  ex)이중for문일 경우를 예로 들 수 있다.
• O(C^n) – 지수 시간(exponential time) : 문제를 해결하기 위한 단계의 수는 주어진 상수값 C 의 n 제곱으로 최악의 시간복잡도이다.

 

자료구조별 시간복잡도

각 자료구조별 시간복잡도를 쉽게 볼 수 있는 표가 있다.

 

시간복잡도를 왜 사용할까??

시간복잡도를 왜 사용하는지에 대한 나의 생각은 바로 적절한 상황에 맞는 자료구조를 이용하기 위해서다.

각 자료구조마다 빠르거나 느리거나 하는 특징이 있기 때문에 어떠한 상황에서 어떤 자료구조를 쓸 것인지에 대한 기준을

정할 수 있다.