Co to jest złożoność tworzenia trie listy słów i co to jest złożoność wyszukiwania innego zestawu słów w tym trie? Czy powinienem używać trie do wyszukiwania ciągów, kiedy mam hashtable?Złożoność wyszukiwania i wyszukiwanie
Złożoność tworzenia Trie jest O(W*L), gdzie W jest liczba słów i L jest średnia długość słowa: trzeba wykonać L wyszukiwań przeciętnie dla każdego W słów w zestawie.
To samo dotyczy wyszukiwania słów później: wykonujesz L kroków dla każdego ze słów W.
Wstawienia i wyszukiwania skrótów mają tę samą złożoność: dla każdego słowa należy sprawdzić równość, która ma wartość O(L), dla ogólnej złożoności O(W*L).
Jeśli chcesz wyszukać całe wyrazy, tablica skrótów jest łatwiejsza. Jednak nie można wyszukiwać słów za pomocą ich prefiksu za pomocą tabeli mieszania; Jeśli wyszukiwania oparte na prefiksach nie są dla ciebie interesujące, użyj tabeli mieszania; w przeciwnym razie użyj trie.
Jeśli szukam całego słowa w hashtable, potrzebuję dobrej funkcji skrótu i powinniśmy być ostrożni przy definiowaniu funkcji skrótu. Popraw mnie jeśli się mylę ... – Varun
@var Z powodu powszechnego używania ciągów znaków jako kluczy tabel hash, wymyślono bardzo dobre funkcje haszowania dla łańcuchów. Szybkie wyszukiwanie w Internecie dałoby ci pół tuzina doskonałych sugestii. Chciałbym użyć tego, którego używa Microsoft, lub tego, który jest wbudowany w łańcuchy Java, ponieważ zostały one zoptymalizowane. – dasblinkenlight