| [ QuizWit ] in KIDS 글 쓴 이(By): cdpark (박종대) 날 짜 (Date): 1998년02월14일(토) 18시11분47초 ROK 제 목(Title): Re: RRe: NP problem NP-hard인 경우는... S1, S2, S3, ..., Sr 개인 경우... 둘 간의 L.C.Subsequence 문제는 O(n^2) 또는 O(p log n) 타임입니다. p = S1과 S2에 있는 같은 symbol쌍의 갯수. 최악의 경우 O(n^2) Aho, Hpocroft, Ullman의 Data Structures and Algorithms에 나와 있군요. 더 좋은 것이 있는지는 모르겠습니다. -- 박.. |