Jaka jest złożoność mapy/zestawu :: wstawić, jeśli podałeś poprawną wskazówkę iteratora?

Question

Czy to O (1) lub O (logN), ale o mniejszym współczynniku?

Jeśli nie jest to określone, chciałbym przynajmniej znać odpowiedź na podstawie rozsądnego przypuszczenia, że ​​mapa/zestaw jest zaimplementowana przy użyciu drzewa czerwono-czarnego lub AVL. Ogólny algorytm, aby wstawić element, myślę, że jest coś takiego:

• znaleźć odpowiednie miejsce - O (logn)
• zrobić rzeczywiste wprowadzenie -
• przywrócić równowagę drzewa w razie potrzeby -?

Jeśli teraz dostarczyć właściwą wskazówkę iteracyjnej, następnie pierwszy etap staje O (1). Czy inne kroki są również O (1) lub O (logN)?

Answer 1

Standard nie określa, w jaki sposób kontenery mają zostać wdrożone, więc nie można liczyć na drzewo RB lub AVL. W praktyce ... złożoność ograniczeń jest taka, że ​​nie znam żadnych innych implementacji, które pasowałyby do rachunku. Ale w ograniczeniach złożoności, że znajdziesz odpowiedź: “ logarytmiczne w ogóle, ale amortyzowane stałą , jeśli t jest włożona tuż przed p. ” Więc jeśli wskazówka jest poprawna , implementacja musi być taka, że ​​wstawienie jest O (1).

Answer 2

Pierwszy standard nigdy nie powiedział dokładnie, jakiego rodzaju struktura danych używa do wdrożenia zestawu. To tylko złożoność operacji na nich, które pomagają nam skierować się w kierunku pewnego rodzaju zrównoważonego drzewka binarnego wyszukiwania.

Tak, jeśli podasz poprawną wskazówkę do wstawienia przez wstawienie prawego iteratora, wszystkie kroki zostaną zamortyzowane jako O (1) jako krok 2 i 3 i nie będą zależne od niczego.

Answer 3

• znaleźć odpowiednie miejsce - O (logn)
• zrobić rzeczywiste wprowadzenie - O (1), bez względu na to czy jest to AVL lub RB drzewo
• zrównoważenia drzewa, jeśli to konieczne - Nie znam dokładnej notacji BIG-O dla drzewa AVL, ale dla drzewa RB jest to O (1).

Przy wskazówce dotyczącej iteratora nie ma to wpływu na krok nr 2 (wstawienie) i krok nr 3 (rebalans). Dostarczając iteratora, wykonujesz sam krok 1 ("znajdź właściwe miejsce"), ogólna złożoność jest taka sama.