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
14
A
Odpowiedz
14
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.
Powiązane problemy
- 1. Złożoność wyszukiwania Lucene
- 2. Złożoność czasowa wyszukiwania binarnego dla nieposortowanej tablicy
- 3. Wyszukiwanie tekstu MongoDB i wiele słów wyszukiwania
- 4. Złożoność środowiska wykonawczego tabeli haszów (wstawianie, wyszukiwanie i usuwanie)
- 5. Wyszukiwanie DataGridview: wyświetla tylko wynik wyszukiwania i ukrywa inne wiersze?
- 6. Operacja błędu wyszukiwania elastycznego [wyszukiwanie] i język [groovy] jest wyłączony?
- 7. Wyszukiwanie topologiczne i pierwsze wyszukiwanie zakresu
- 8. Różnica między „złożoność” metrykę i „złożoność/metoda” metryki
- 9. C++ - złożoność nieuporządkowanej mapy
- 10. Różne struktury danych i Złożoność
- 11. Rozszerzanie wyszukiwania i indeksowania sadu
- 12. Wyszukiwanie pełnotekstowe MySQL i SOUNDEX
- 13. `złożoność złożoności
- 14. Złożoność algorytmu
- 15. Złożoność algorytmu
- 16. Zaszyfrowane pola i wyszukiwanie pełnotekstowe, najlepsze podejście?
- 17. Indeksowanie i wyszukiwanie plików Python
- 18. Jaka jest złożoność pamięci std :: sort() i std :: sort_heap()?
- 19. Wyszukiwanie zaawansowane przy użyciu wyszukiwania w trybie hibernacji
- 20. CRM 2011 Wyszukiwanie zaawansowane - Pobierz XML - import do poprawionego wyszukiwania
- 21. stwierdzenia wcześniejszego powrotu i Złożoność cykliczna
- 22. Złożoność cykliczna z warunkami złożonymi i zwarciem
- 23. Wyszukiwanie i usuwanie Atom.io jest możliwe?
- 24. wyszukiwania ikona wewnątrz pola wyszukiwania
- 25. wyszukiwanie i zastąpić bez zużywania co szukasz
- 26. Obliczeniowa złożoność kawałka kodu
- 27. Złożoność przestrzenna algorytmu rekursywnego
- 28. Złożoność operatorów porównania
- 29. Złożoność czasu zabawy()?
- 30. Złożoność czasowa funkcji permutacji
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