26번줄의 M %= sum; 때문에, 매번 M이 절반이하로 감소되기 때문입니다.
sum < M/2 일때, M %= sum 결과는 M/2보다 작음이 자명합니다.
sum > M/2 일때, 이 역시 M %= sum 결과가 M/2보다 작습니다.
(r = M - sum * [m /sum]에서, sum>M/2이므로)
그래서 시간복잡도는 O(nlogM)입니다
31005번 - 귤나무
26번줄의 M %= sum; 때문에, 매번 M이 절반이하로 감소되기 때문입니다.
sum < M/2 일때, M %= sum 결과는 M/2보다 작음이 자명합니다.
sum > M/2 일때, 이 역시 M %= sum 결과가 M/2보다 작습니다.
(r = M - sum * [m /sum]에서, sum>M/2이므로)
그래서 시간복잡도는 O(nlogM)입니다
감사합니다!
시간 복잡도 계산도 생각할 게 많네요
댓글을 작성하려면 로그인해야 합니다.
nabina1395 1년 전
저는 곰곰이들의 요청을 순회하는 연산의 시간 복잡도가 O(N)이고,
또 최악의 경우에 매 순회마다 1개의 곰곰이들만 제거될 수 있으니 이러한 순회가 최대 N번 반복될 수 있어
시간 복잡도가 O(N^2)가 되기에 1 <= N <= 200000인 문제의 조건에 따르면 시간 초과를 받을 것이라고 생각하였는데,
매우 널널한 실행 시간으로 통과되네요. 혹시 이 코드의 시간 복잡도가 O(N^2)보다 더 낮을까요?