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

  • 상욱
    상욱

    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가 접속이 안 되요. ㅜㅜ

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

    10년 전
4개의 댓글이 있습니다.
  • 김우현
    김우현

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


    10년 전 link
  • 상욱
    상욱

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


    10년 전 link
  • Dynamical
    Dynamical

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


    10년 전 link
  • Being
    Being

    Dynamical님은 ICPC 안하시나요..


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