접미사 배열: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
잔글 →랭크: 표 수정 |
잔글 →Manber-Myers 알고리즘: 주석 추가 |
||
136번째 줄:
접미사끼리 비교하는 횟수는 <math>\mathcal{O}(n \lg n)</math>이고, 한 쌍의 접미사의 사전 순서를 판단하는데 필요한 비교 횟수는 <math>\mathcal{O}({n})</math>이므로 총 시간 복잡도는 <math>\mathcal{O}({n}^{2} \lg n)</math>이 된다.
<!----------------------------------------------------------------------------------
문서 분리에 대한 주의
이 부분으로 인해 접미사 배열 문서의 길이가 과도하게 길어지는 감이 있습니다.
하지만 랭크와 기수 정렬은 접미사 배열을 구하는 일반적인 방식의 핵심적인 부분입니다.
특히 랭크에 대한 설명은 접미사 배열 문서에 필수적으로 포함되어야 한다고 생각합니다.
그러므로 전문적이지 않은 편집자 혹은 봇이 문서를 분리해 주지 마실 것을 부탁드리며
이 문단을 따로 문서로 만들 때 충분한 토의를 거쳐 주셨으면 좋겠습니다.
----------------------------------------------------------------------------------->
=== Manber-Myers 알고리즘 ===
{| class="infobox" style="width: 22em"
| |||