algospot.com :: 질문과 답변: suffix array를 써서 최장공통부분문자열을 구하는 복잡도.

suffix array를 써서 최장공통부분문자열을 구하는 복잡도.

김우현

실제 정렬하는데 드는 복잡도는 O( N*logN * '두 element를 비교하는데 걸리는 시간')
이 대략 걸립니다. 보통은 int형을 정렬하기 때문에 O( N*logN * 1) 로 간주하는거죠.
문자열은 대소관계를 비교하는데 O(N) 시간이 걸리기 때문에
O(N * logN * N) => O(N^2 * logN) 이 걸리게 됩니다.

14년 전 link
상욱

아하아하!!!!!!!! 그렇군요!! 감사합니다. ^^
문자열의 배열을 정렬하니까!!!

14년 전 link
Dynamical

정렬방식을 개선한다면 O(n log n)에 할수도 있죠.

14년 전 link
Being

Dynamical님은 ICPC 안하시나요..

14년 전 link
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.

상욱: http://algospot.com/zbxe/?document_srl=5108
위의 에디토리얼을 보면.
4번 해법이 Suffix Array를 사용하는 해법이잖아요.
근데 이것의 복잡도가 O(n^2logn)인게 이해가 안되요. ㅜㅜ
정렬에 드는 시간은 O(nlogn) 아닌가요?
정렬은 한 번만 하면 되니까.
총 복잡도는 O(n^2 + nlogn) 이니까.
결과적인 복잡도는 O(n^2) 이 된다고 생각하는데...
O(n^2logn)이 되려면. 정렬을 n번 해야 하는데.
아무리 생각해도 정렬은 한 번만 하는게 아닌가... 생각이 들어서요.
덧, 그리고 여기 RSS가 접속이 안 되요. ㅜㅜ

[이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

14년 전