Co mogłoby zająć więcej czasu?Tabela Big O of Hash vs. Drzewo wyszukiwania binarnego
wydrukuj wszystkie pozycje przechowywane w drzewie wyszukiwania binarnego w uporządkowanej kolejności lub wydrukuj wszystkie pozycje przechowywane w tablicy haszów w porządku posortowanym.
Wydrukowanie elementów tabeli skrótów zajmie więcej czasu w kolejności posortowanej, ponieważ tabela mieszania nigdy nie jest posortowana poprawnie? i BST jest?
Masz rację. Hashtables są sortowane według jakiejś funkcji hash, a nie według ich naturalnej kolejności sortowania, więc musisz wyodrębnić wszystkie wpisy O (N) i posortować je O (NlogN), podczas gdy możesz przejść drzewo binarne w naturalnej kolejności w O (N).
Należy jednak pamiętać, że na przykład w Javie istnieje LinkedHashSet i LinkedHashMap, które dają niektóre zalety skrótu, ale które można przemierzać w kolejności, w jakiej zostały dodane, aby można było je posortować i móc przechodzenie przez to w posortowanej kolejności, a także wyodrębnianie elementów za pomocą skrótu.
Prawidłowo, tablica skrótów nie jest "sortowana" w sposób, w jaki prawdopodobnie chcesz. Elementy w tablicach hash nie są zwykle w pełni uporządkowane, chociaż układ często jest w pewnym rodzaju w sąsiedztwie. Ale są one uporządkowane według funkcji mieszania, która jest zwykle szalenie inna dla podobnych zwrotów. Nie jest to rodzaj według jakiegokolwiek miernika, jakiego użyłby człowiek.
Jeśli główną rzeczą, którą robisz ze swoją kolekcją, jest drukowanie jej w posortowanej kolejności, najlepiej użyj jakiegoś typu BST.
Drzewo wyszukiwania binarnego jest przechowywane w taki sposób, że jeśli wykonasz pierwszą operację głębi, elementy zostaną posortowane w kolejności (zakładając, że masz funkcję porównywania). Wielkie O powracających przedmiotów znajdujących się już w drzewie byłoby Wielkim O przechodzenia przez drzewo.
Masz poprawne tabele mieszania, nie są one posortowane. W rzeczywistości, aby wyliczyć wszystko w prostym stole mieszającym, musisz sprawdzić każde wiadro, aby zobaczyć, co tam jest, wyciągnąć je, a następnie sortować to, co dostajesz. Mnóstwo pracy, aby uzyskać z tego posortowaną listę.
Prawidłowe, drukowanie posortowanych danych przechowywanych w tabeli mieszania będzie wolniejsze, ponieważ tabela mieszania nie jest posortowana. To tylko daje szybki sposób na znalezienie konkretnego przedmiotu. W "Big O Notation" mówi się, że przedmiot można znaleźć w stałym czasie, tj. O (1).
Z drugiej strony, można znaleźć pozycję w binarnym drzewie wyszukiwania w "czasie logarytmicznym" (O (log n)), ponieważ dane zostały już posortowane.
Więc jeśli chcesz wydrukować posortowaną listę, znacznie lepiej jest przechowywać dane w uporządkowanej kolejności (np. Drzewo binarne).
Enjoy,
Robert C. Cartaino
Pojawi się kilka ciekawych pytań. Czy drzewo wyszukiwania jest jeszcze szybsze, biorąc pod uwagę następujące elementy?
Sprawdź również związane względy Omiń listy vs. binarne drzewo: Skip List vs. Binary Tree