시간복잡도 개요

   입력값과 연산 수행 시간의 상관관계를 나타내는 척도

 Big-O 표기법     

최악의 상황일 때 걸리는 시간을 이용해 시간복잡도를 나타내는 방법     

대부분 Big-O 표기법을 이용해 시간을 나타낸다.

상수항과 영향력이 낮은 항은 무시한다.

     

시간복잡도를 그래프로 나타낸 것이다. y축은 연산량이고 x축은 원소의 수이다.

 

아래는 예제들이다.

O(n)

O(n)

O(n*m)

 

O(n^3)

O(2^n)

O(log n)

 

O(  )  <- 이 괄호 안에 들어가는 식을 계산해서 언어에 따라서 다른데 c++ 기준 1억분의 1초 정도로 생각할 수 있다고 한다.