시간복잡도

복잡도

-> 만들어낸 알고리즘을 직접 구현해보지 않아도 대략적인 시간을 미리 파악할 수 있다.
즉, 어떤 알고즘을 사용할지 검토할 때 비교하기 편하다.

알고리즘 A의 계산시간 T(N)이 대략 P(N)에 비례하면
T(N) = O(P(N)) 으로
알고리즘 A의 복잡도는 O(P(N))이라 한다.

ex) T(N) = 3N^2+5N+100일때 T(N) = O(T(N^2))

복잡도 종류

1. 지수시간 - N이 증가함에 따라 계산시간이 급격하게 늘어남.
   O(N!), O(2^n)
2. 다항시간
   O(N^d),O(N^2),O(N^3) & 다항식은 아니지만 다항 시간이 필요한 계산량 O(NlogN),O(N*sqrt(N))
3. 상수시간 - 문제 크기에 의존하지 않는 상수시간 이내에 처리가 끝남
   O(1)

복잡하지만 빠른 알고리즘만 추구하면 안된다.
풀고싶은 문제의 크기에 따라 적절한 시간 복잡도를 가진 알고리즘을 판별하는것이 중요!
O(2^n)은 지수시간 알고리즘으로 N<=20정도의 문제 크기가 작은 범위라면 쓸만하다.

복잡도 표기법

란다우 빅오 표기법

• 계산시간 상한을 평가
  점근적 상한성으로 아무리 최악의 시간 복잡도여도 비교 함수보다 같거나 좋다.
  T(N) = O(N^2)은 O(N^3),O(N^100)으로 전부 성립한다.

오메가 표기법

• 계산시간 하한을 평가
  아무리 좋은 상황이어도 비교함수보다 같거나 나쁘다.
  T(N) = Ω(NlogN)

세타 표기법

• 점근적 상한&하한의 교집합. 평균 범위
  T(N) = O(P(N)) 및 T(N) = Ω(P(N))이면 T(N) = Θ(P(N))