글 읽기 - 시간복잡도에 대해 질문이 있습니다

(追記) (追記ここまで)

시간복잡도에 대해 질문이 있습니다

11478번 - 서로 다른 부분 문자열의 개수

ryukangin 1년 전 0

시간복잡도에 대해 궁금해서 글을 쓰게 되었습니다.

문제에서 문자열의 길이는 1000이하라고 되어있고 시간제한은 1초입니다.

제가 짠 코드에서 만약 길이가 1000인 문자가 들어오면 적어도 10억번은 실행될것같은데요.
그렇게 되면 1초만에 못끝내지 않나요? 왜 정답이 되었는 지 궁금합니다. 단순히 테스트 케이스에 길이가 1000인 문자가 없었던 것일까요...

일단 제출후 실행시간은 496ms가 나왔습니다.

이 제출란에 있는 시간도 궁금한 것이 있는데 여기 나와있는 실행시간은 각각의 테스트케이스 실행시간의 평균인가요?

질문정리)

1. 길이가 1000인 문자열이 들어오면 시간초과가 되야하는것이 아닌가?

2. 제출란에서 정답이었을 때 나오는 시간은 각 실행시간의 평균인지? (아니면 테스트 케이스중 제일 오래걸린시간?)

#include <bits/stdc++.h>
using namespace std;
set<string> s;
int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	string str,sub;
	cin >> str;
	int leng = str.length();
	for (int i = 0; i < leng; i++) {//length = 1000
		for (int j = 1; j <= leng-i; j++) {//length = 1000
			sub = str.substr(i, j);//length = 1000
			s.insert(sub);//lgn
		}
	}
	cout << s.size();//O(1)
}

skuru 1년 전 1

1.(削除)
작성하신 코드의 시간복잡도는 O(N³)처럼 보입니다만, 좀 더 고려해볼 사항이 있습니다. (削除ここまで)

(削除) i, j에 따라 substr의 길이가 달라질 수 있습니다. 길이가 1인 경우가 2N번, 2인 경우가 2(N-1)번, 3인 경우가 2(N-3)번, ...
따라서 모두 합하면 N(N+1)이고 O(N²)이 됩니다. (削除ここまで)

제가 잘못 생각했네요. 아래 분 답변을 보시면 될 것 같습니다.

2. 제일 오래걸린시간입니다.

djm03178 1년 전 2

@skuru 세제곱이 맞습니다. 문자열의 개수에 길이를 곱하는 걸 깜빡하신 듯 하네요. 제곱이면 496ms씩이나 안 나옵니다.

zenith82114 1년 전 1

최대 크기 또는 최대에 근접하는 크기의 테스트 케이스가 적어도 하나는 있는 것이 당연하며, 수행 시간은 전체 케이스 중 최댓값으로 표시됩니다. 채점 정보

$$\sum_{i=0}^{n-1} \sum_{j=1}^{n-i} j = \frac{1}{6}(n^3 + 3n^2 + 2n)$$

으로, n=1000에 대하여 총 연산량은 1.7억 정도이며 많은 언어에서 1초 이내로 커버됩니다.

djm03178 1년 전 1

세제곱이기는 하지만 set을 제외하면 상수가 작아 부분문자열들을 뽑는 것 자체는 충분히 빠릅니다. 하지만 set 때문에 최악의 경우는 세제곱 로그가 될 수도 있어 보이는데, 이건 데이터가 약하지 않은지 확인해봐야할 듯 합니다. 다만 길이가 1000인 걸 아무거나 넣는다고 시간 초과가 날 정도로 느린 코드는 아닙니다.