2003번 - 수들의 합 2
우선, O(1억) 이 1초 정도에 돌아간다고 가정하겠습니다.
이중 for 문으로 모든경우를 탐색하기 때문에 시간복잡도 O(n^2) 로,
N = 10000 일때 아래의 코드는 O(1억) 의 시간복잡도로 실행된다고 생각하는데
시간제한이 0.5초인 이문제에 대해서 아래의 코드가 왜 통과가 되는지 궁금합니다.
p.s 첫번째 코드는 두번째 코드에서 가지치기를 한것인데
첫번째 40ms
두번째 52ms 에 통과가 됩니다.
서버와 컴퓨터 성능 등에 따라 약간식 다를 수도 있지만 대략 c++ 는 1초에 4억번 (또는 그 이상) 정도 연산을 합니다.
그래서 O(n^2) 를 돌리면 1억번 연산을 하게 되고, 1초에 2억번연산만 넘지 않으면 되니 통과를 하게 됩니다.
참고로 제가 알고 있는 정보가 틀릴 수도 있습니다;;
요즘 컴퓨터는 단순한 문장 루프는 10억~20억번도 돌립니다.
댓글을 작성하려면 로그인해야 합니다.
7slidemorning 4년 전
우선, O(1억) 이 1초 정도에 돌아간다고 가정하겠습니다.
이중 for 문으로 모든경우를 탐색하기 때문에 시간복잡도 O(n^2) 로,
N = 10000 일때 아래의 코드는 O(1억) 의 시간복잡도로 실행된다고 생각하는데
시간제한이 0.5초인 이문제에 대해서 아래의 코드가 왜 통과가 되는지 궁금합니다.
p.s 첫번째 코드는 두번째 코드에서 가지치기를 한것인데
첫번째 40ms
두번째 52ms 에 통과가 됩니다.