tkdgur7234   3년 전

시간 복잡도는 배웠는데 이게 1초라고 되어있으니 어떻게 계산하는지 모르겠습니다.

sdpr   3년 전

대충 500이면 O(N^3) (즉, 3중)정도까지, 1000이면 시간이 2초면 O(N^3)까지, 2000이상이면 O(N^2)정도, 10000이면 O(NlogN)정도..?

절대 맹신하면 안되지만, 대충 시간복잡도에 최대값을 넣었을 때 1초당 1억이 넘지 않는걸 선으로 합니다.

단, 진짜 시간복잡도에 넣었는데 4억정도 나오는 반면 시간초과가 나지 않는 경우가 있습니다. 연산의 복잡도를 고려해서 시간복잡도를 적당히 고려해보세요.

tkdgur7234   3년 전

500이 1초인가요? 500, 1000이 뭘 의미하는 건가요? 제가 잘 몰라서요 ㅜ

sdpr   3년 전

데이터의 크기입니다. 막 보다보면 '노드의 개수가 N개', '수열의 크기가 N', 이런식으로 데이터의 크기를 줘요.

반복하는 요소에 대해서, 시간복잡도에 대입했을 때 1억을 넘지 않게 하는 것이 일반적인 선이라는 의미였습니다.

ex. 문제 내용 자체는 간단해보이는 14898번: 서로 다른 수와 쿼리 2 (acmicpc.net) 이 문제를 예로 들어봅시다.

이 문제를 순수하게 반복문으로만 짠다면 O(NQ)의 시간복잡도가 나옵니다. 이는 N이 100만, Q가 100만이므로 10^12가 되어 무조건 시간초과를 받게됩니다.

하지만 시간복잡도에 관여하는 N과 Q가 충분히 작다면, 예를들어 N이 10000이고 Q가 1000이었다면 둘을 곱해 천만이므로, 1억을 넘지 않습니다. 이정도 N과 Q라면 반복문으로 구현을 해도 문제가 없다는 의미입니다.

tlsdydaud1   3년 전

500, 1000 등은 문제에 나온 변수들(위 댓글에서는 N)의 제한을 의미하고, 그렇게 해서 나온 1억은 연산 횟수를 의미합니다. 그러니까 위 댓글의 의미는 '제출한 코드를 실행했을 때 연산의 총 횟수가 1억 이하이면 일반적으로 실행 시간이 1초를 넘지 않는다.' 정도가 됩니다.

tkdgur7234   3년 전

다들 감사합니다!

완벽히 이해됐습니다

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