trie를 만드는 데 얼마나 걸리나요

trie를 검색 할 시간이 O (N) 인 문학에 많은 정보가 있습니다. 여기서 N은 패턴의 길이입니다.trie를 만드는 데 얼마나 걸리나요

그러나 나무를 만드는 데는 어느 정도 시간이 걸립니다. 나에게 총 Y 문자가있는 X 단어가 있다고 가정 해 보겠습니다.

그러면 O (Y)는 시간입니다 (각 문자를 삽입해야하기 때문에). 이 평가가 정확합니까 (보통 올바르지 않습니다)

2011-01-13 user560871

삽입 시간 x 삽입 할 요소. 내 머리 꼭대기에서 O (nlogn). – leppie

틀린입니다. 트라이를 작성하고 트라이를 검색하는 것은 두 가지 다른 알고리즘입니다. 하나는 트라이를 구축하지 않고 검색 한 다음 전체 데이터 구조를 폐기합니다.

2011-01-13 04:43:41 ryebr3ad

trie는 여러 번 사용해야한다는 것이 옳습니다. 그러나 OP가 잘못되었다고 주장하므로 답변이 잘못되었습니다. – maaartinus

그럼 O (Y)는

물론 (우리는 각 문자를 삽입하기 때문에), 각 입력 문자를 처리 할 수 있고, 기존의 지점을 따르거나 새로운를 삽입하거나 시간입니다 숯.

각 입력 문자를 살펴 봐야하기 때문에 O (Y)보다 빠를 수 없습니다. 정렬이나 다른 작업을 수행하면 속도가 느려질 수 있습니다.

2011-01-29 10:23:21 maaartinus

답변