[알고리즘] 시간복잡도에 대하여

미리보기 요약:

입력 크기 보고, 최대 시간복잡도 결정해서 그 아래로 코드짜기

 

 

 

서론

알고리즘을 멀쩡히 풀었는데 시간 초과가 되는 경우를 다들 한번씩 겪어볼것입니다.

그럴때 다른 푸신분들의 코드를 보면 다른 방향으로 구현이 된 경우들이 있죠.

 

열심히 맞게 풀어도 헛고생하는 여러분들을 위해, 

그러는 경우를 방지하는 방법을 말씀드리겠습니다

 

실버문제에선 거의 없는것같고

골드정도에서 종종 나옵니다

 

어디서 흘려듣던, 시간복잡도에 대해 다뤄보겠습니다.

 

이 글을 보시고 미리 습관을 들여놓으시면 좋을듯 합니다

 

 

 

 

본론

문제 풀기 전에 체크할 점

1.입력크기

2.입력크기를 보고 시간복잡도 최대치 결정

3.시간제한 체크

 

대략적인 입력크기에 따른 적절한 시간복잡도

n < 10

-> N! (백트래킹, 브루트포스)

 

n< 100

-> n의 3제곱(3중 for문)

 

n < 1000

-> N의 2제곱(dp등)

 

n < 1,000,000

-> N log N(이분탐색등)

 

n < 10,000,000

-> log N

 

 

대략 1억번 연산은 1초입니다

 

 

 

 

결론

결론은 맨 위에 요약으로 적어뒀습니다.

다들 미리 이부분을 체크하고, 어떻게 짤지 구상하는게 좋을듯합니다.

 

모두들 끝없는 공부라도 지치지말고, 오래 열정을 불태우시길 바랍니다