blpoms   4년 전

예전에 입력크기와 시간복잡도에 관한 글을 본거 같은데 어디서 봤는지 못찾겠습니다 ㅠㅠ

예를 들어 시간제한 1초를 기준으로 N=1000이면 O(N^2)로 풀어야되고 N = 5000이면 O(NlogN)으로 풀어야되고 N=???일때 O(N^2logN) ...

이런 글을 BOJ에서 본거 같은데 어디서 봤는지 기억이 안납니다.

블로그 글에서 찾아봤는데 못찾겠습니다(블로그에서 본거 같은데...).

혹시 이런 글 보신 분 계십니까...??

djm03178   4년 전

그런 게 특별히 정해져 있는 것은 아니고, 정해에 비해 매우 넉넉한 제한을 주는 경우 등도 있어서 N 제한만 보고 판단하기는 어렵습니다. 그보다는 N 제한에 따라 최대 어느 정도까지는 생각해볼 수 있는지를 감을 잡으시는 게 좋습니다.

대개의 경우 단순하게 계산한 값이 1억 이하로 나온다면 1초 안에 실행될 수 있는 시간복잡도라고 생각하시면 됩니다.

댓글을 작성하려면 로그인해야 합니다.