3307664465

Zmniejszenie złożoności opiera się na dwóch obserwacjach:

I.    „Once a leaf always a leaf” - na krawędziach do liści można dodawać znak bez zastanowienia.

II.    Jeśli w drzewie jest już jakiś sufiks, to wszystkie jego sufiksy też są już w drzewie, czyli jeśli w danej iteracji wykorzystano regułę 3 do rozszerzenia j, to można ją zastosować (czyli nic nie robić) dla wszystkich dalszych rozszerzeń w danej iteracji

Złożoność 0(m)

Zbuduj 11.

Dla i=1 do m-1

Dla j takiego, że jL <j< jR

Znajdź ścieżkę od korzenia zaetykietowaną S/...I Dodaj znak S,vi na koniec ścieżki jL - w iteracji I to indeks ostatniego dodanego liścia jR - w iteracji I to pierwszy indeks j taki, że Sj...j₊i jest już w drzewie Wywołań pętli jest 2m; to, co jest wykonywane, da się zrobić w stałym czasie.

-3-

Wyszukiwarka

Podobne podstrony:
WYKŁAD 2 TERMODYNAMIKA Termodynamika opiera się na czterech obserwacjach fenomenologicznych zwa
Image (23) 692NICHOLAS J. WHEELER, ALEX J. BELLAMY opiera się na dwóch podstawowych twierdzeniach. P
Sztuki plastyczne w XIX wieku.Architektura zdominowana przez historyzm opierała się na dwóch nurtach
Metoda BCG (Boston Consulting Group) opiera się na dwóch czynnikach: •    tempie wzro
58075 Zdjęcie185 (2) Projektowanie statyczne i dynamiczne hydraulicznych układów automatyki opiera&n
edukacyjna powinno opierać się na następujących aspektach: (i) złożoność, (ii) specjalizacja, (iii)
037 LITERATURA DO ZABYTKËW TEL 601979100 tylna opiera się na strzemieniu opartym na dwóch sprężynach
2. Funkcjonalna opiera się na koncepcji istnienia dwóch układów masy towarowej: początkowego (sfera
2. Wnioskowanie a contrario (z przeciwieństwa) - opiera się na porównaniu istotnych cech dwóch stanó
00091 Ostatni etap IV opiera się na zbudowaniu macierzy XG. Jest to macierz obserwacji zmiennych ob
28 TADEUSZ KOWALSKI Opierając się na wcześniej opisanych tendencjach i obserwacjach związanych z
00091 Ostatni etap IV opiera się na zbudowaniu macierzy XG. Jest to macierz obserwacji zmiennych ob
85 Z RUCHU NAUKOWEGO. pierwszy rzut oka. Thomsen zabrał się do pracy, opierając się na owych dwóch w

więcej podobnych podstron