시간 복잡도 정리

시간 복잡도 유형

빅 오메가 : 최선일 때 연산 횟수
빅 세타 : 보통
빅 오 : 최악
--> 코딩 테스트에서의 시간 복잡도는 보통 빅 오를 사용한다.

 

연산 횟수 계산하는 법

* 제한 시간이 2초라면, 보통 2억번 이하의 연산 횟수로 문제를 해결해야 함

* 버블 정렬 시간 복잡도로 예를 들음
O(n^2) == 최대 연산 횟수^2
이런식으로 계산 했을때 제한 시간이 2초니까 최대 연산 횟수^2가 2억 번 이하면 됨

시간 복잡도 계산

* 상수는 시간복잡도 계산에서 제외

 

* 가장 많이 중첩된 반복문의 수행 횟수가 시간복잡도임

 

--> 그래서 2중 for문이 30개여도 시간 복잡도는  2중 for문 1개일 때랑 똑같음