시간 복잡도

시간 복잡도 유형

빅오메가 표기법 : 최선일 때 연산 횟수를 나타낸 표기법

빅 세타 : 보통일 때 연산 횟수를 나타낸 표기법

빅오 표기법 : 최악일 때 연산 횟수를 나타낸 표기법

보통 코테, 실무에서는 빅오 표기법을 사용한다. why?

입력크기가 매우 작거나 할 때는 최선의 경우가 중요할 수 도 있지만 , 실무에서는 입력크기가 커서 최악의 경우에도 효율적으로 작동하는게 중요함으로 빅오표기법에 따라 알고리즘을 선택하는게 좋다.

코테에서 고려해야 할 점

1.) 연산 횟수

코딩테스트 문제에서 시간제한 2초

1초당 연산횟수 1억번을 기준으로 생각한다.

연산 횟수 = 알고리즘 시간 복잡도 * 데이터의 수(크기)

(여기서 데이터의 크기는 최악일 때(가장 크기가 클 때) 를 기준으로 한다.)

2.) 상수, 중첩될 때

예를들어 for문을 하나 사용하여 시간 복잡도가 n이라고 가정하면 n이든 2n,3n,4n이든 시간의 차이는 크지 않아서

앞의 2,3,4 같은 상수는 제외하고 계산한다.

for문이 중첩되어 시간복잡도가 n의제곱 이면 아래 n,2n,3n,4n으로 오더라도 시간에 크게 차이가 안나는 것으로 가정하여 시간복잡도를 n의제곱으로 생각한다.

결론

1.알맞은 알고리즘 선택하기

2. 비효율적인 로직 찾아서 효율적으로 바꾸기

예시

이진 탐색 : O(log n)
단일 for문 : O(n)
퀵 정렬, 합병 정렬 : O(n log n)
이중 for문, 버블 정렬, 삽입 정렬 :O(n^2)

ex) 합배열 사용해서 시간 복잡도 줄인다. o(n) -> o(1)