시간복잡도

• 시간복잡도(Time Complexity)란?
  컴퓨터 프로그램의 입력값과 연산 수행 시간의 상관관계를 나타내는 척도이다.
  (효율성에 중점을 두고 생각하는 느낌이다.)

시간 복잡도를 표기하는 방법은 주로 Big-O 표기법을 따른다
(빅오 표기법은 시간 복잡도 최악의 경우를 고려한다.)

Big-O 표기법의 종류

• O(1)
  입력 데이터와 상관없이 일정하게 증가하는 알고리즘 시간과 요소와 일정하게 증가함.
  O(1)는 constant complexity라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않는다.

• O(n)
  linear complexity라고 부르며, 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미한다.
  

ex)O(n)=O(2n) 같은 의미이다.

• O(log n)
  가장 대표적인 알고리즘으로는 이진 검색법이 있다.(binary search)

• O(n^2)
  입력값이 증가함에 따라 실행시간이 n의 제곱만큼 계속 늘어난다.
  
  O(n^2)=O(3n^2) 같은 의미이다.

• O(2^n)
  Big-O 표기법 중 가장 느린 시간 복잡도를 가집니다.