W czysto funkcjonalnych najgorszych przypadkach sortowanych list o stałym czasie, Brodal i in. prezentuj czysto funkcjonalne zrównoważone drzewa z konkatenatem O (1) i wstawiaj, usuwaj i znajduj O (lg n). Struktura danych jest nieco skomplikowana.
Czy istnieje prostsze zrównoważone drzewo wyszukiwania z konkatenacją O (1), funkcjonalne czy nie?
Odpowiedzi:
Możesz w prosty sposób utworzyć strukturę danych z zamortyzowanym czasem konkatenacji O (1) , po prostu wstawiając wszystko od jednego drzewa do drugiego po konkatenacji (która ma koszt O (n log n), dokładnie taki sam, jak użyto do konstruowania tego drzewa w pierwsze miejsce, więc całkowity czas to wciąż O (n log n)), ale to oszustwo.
W najgorszym przypadku O (1) autorzy twierdzą, że był to otwarty problem dla dowolnej struktury danych, więc nie sądzę, że znajdziesz łatwą odpowiedź.
Pobrałem wspomniany artykuł, który odpowiada „nie”, przynajmniej w momencie publikacji artykułu. To z dwóch powodów:
dokument jest wymagany do prawidłowego przeglądu powiązanych prac i robią to we wstępie, wraz ze streszczeniem na ryc. 1, które mówi „nie”. Przynajmniej jeśli został opublikowany na renomowanej konferencji, ale tak to wygląda (Brodal jest cytowany kilka razy w „Czysto funkcjonalnych strukturach danych” C. Okasaki, odniesienie na ten temat).
Wspominają jednak w tekście o algorytmie z czasem wyszukiwania O (log n log log n) i konkatenacją w czasie O (1), naszkicowanym w pracy K&T z STOC '96. To może być dla ciebie interesujące.
Punkt 1. zapewnia również, że możesz po prostu poszukać dokumentów powołujących się na ten, aby znaleźć późniejsze wyniki, musieliby to zacytować.
Gdyby pytanie miało praktyczne znaczenie (ale tak nie powinno być), uważam, że stałe czynniki są ważniejsze niż różnica między O (1) a O (log N) (jak omówiono we wstępie do algorytmów Sedgewicka), więc musisz po prostu znaleźć testy porównawcze dla przypadku użycia aplikacji.