W notacji Big-O dla struktur drzewa: Dlaczego niektóre źródła odnoszą się do O (logN), a niektóre do O (h)? - algorytm, struktury danych, drzewo, big-o, drzewo binarne-wyszukiwania

W badaniu złożoności dowolnego algorytmu przechodzącego przez binarne drzewo wyszukiwania widzę dwa różne sposoby wyrażania tego samego:

Wersja 1: Algorytm przejścia w najgorszym przypadku porównuje jeden raz na wysokość drzewa; dlatego złożoność jest O(h).

Wersja 2: Algorytm przejścia w najgorszym przypadku porównuje jeden raz na wysokość drzewa; dlatego złożoność jest O(logN).

Wydaje mi się, że ta sama logika działa, ale używają jej również różni autorzy logN lub h. Czy ktoś może mi wyjaśnić, dlaczego tak się dzieje?

Odpowiedzi:

Jeśli twoje drzewo binarne jest zbalansowane, więc każdy węzeł ma dokładnie dwa węzły potomne, wtedy liczba węzłów w drzewie będzie dokładnie równa N = 2^h - 1, więc wysokość jest logarytmem liczby elementów (i podobnie dla każdego kompletnego ndrzewo).

Jednak dowolne, nieskrępowane drzewo może wyglądać zupełnie inaczej; na przykład może mieć jeden węzeł na każdym poziomie, więc N = h w tym wypadku. Wysokość jest więc miarą bardziej ogólną, ponieważ odnosi się do rzeczywistych porównań, ale przy dodatkowym założeniu równowagi można wyrazić wysokość jako logarytm liczby elementów.

Prawidłowa wartość dla najgorszego przypadkuwyszukiwanie to drzewo O (h), gdzie h jest wysokością drzewa. Jeśli używasz zbalansowanego drzewa wyszukiwania (takiego, w którym wysokość drzewa to O (log n)), to czas wyszukiwania jest najgorszy z przypadków O (log n). Powiedział, że nie wszystkie drzewa są zrównoważone. Na przykład tutaj jest drzewo o wysokości n - 1:

1

2

3

...

n

Tutaj h = O (n), więc wyszukiwanie to O (n). Prawidłowe jest powiedzenie, że czas wyszukiwania jest również w tym przypadku O (h), ale h ≠ O (log n) i błędem byłoby twierdzenie, że czas wyszukiwania był równy O (log n).

W skrócie, O (h) jest prawidłową granicą. O (log n) jest poprawną oprawą w zbalansowanym drzewie wyszukiwania, gdy wysokość wynosi co najwyżej O (log n), ale nie wszystkie drzewa mają czas wyszukiwania O (log n), ponieważ mogą być niezrównoważone.

Mam nadzieję że to pomoże!

O (h) będzie odnosić się do drzewa binarnego, które jest sortowane, ale nie zrównoważone

O (logn) będzie odnosić się do drzewa, które jest posortowane i zbalansowane

To dwa sposoby na powiedzenie tego samego, ponieważ średnie zrównoważone drzewo binarne o wysokości "h" będzie miało około 2 ^ h węzłów.

W zależności od kontekstu, wysokość lub liczba węzłów może być bardziej odpowiednia, a więc to, co zobaczysz, będzie się odwoływać.

ponieważ (h) osiem zrównoważonego drzewa zmienia się jak log (N) umber elementów