nopanderer   3년 전

어떤 부분이 문제일까요 ㅠㅠ 고수분들 부탁드립니다.

mixnuts   3년 전

1. 위 코드에서 B, P 연산의 시간 복잡도는?
> 문자열 길이를 $L$이라고 했을 때, $O(L)$.

2. 그렇다면 위 코드의 시간 복잡도는?
> 쿼리 수를 $Q$, 중간 연산 과정에서 문자열 길이의 최대를 $L$이라 하면,
> 최악의 경우, B/P연산만 반복해서 들어올 수 있으므로 $O(LQ)$.

3. $O(LQ)$는 대략 어느정도?
> $L = 10^5$, $Q = 5 \times 10^5$ 이므로 $5 \times 10^{10}$.
> 컴퓨터가 대략 1초에 $2 \times 10^{8}$번 처리하므로 위 소스는 250초는 걸리겠군요.

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