Wyszukiwanie w strukturze danych: objaśnienie różnych metod wyszukiwania
Opublikowany: 2021-05-03Sieć komunikacyjna się rozrasta, więc ludzie korzystają z internetu! Firmy przechodzą na rozwiązania cyfrowe w celu efektywnego zarządzania. Ilość danych generowanych w Internecie rośnie, a tym samym zbiory danych stają się coraz bardziej złożone. Niezbędne jest dokładne i efektywne organizowanie, zarządzanie, dostęp i analizowanie danych, struktura danych jest najbardziej pomocną techniką, a artykuł skupia się na tym samym!
Spis treści
Struktura danych
W informatyce struktury danych są podstawą abstrakcyjnych typów danych (ADT), gdzie ADT są logiczną formą typu danych. Fizyczny układ typu danych jest zaimplementowany za pomocą struktury danych. Różne typy struktur danych są używane dla różnych rodzajów aplikacji; niektóre specjalizują się w konkretnych zadaniach.
Struktura danych to zbiór wartości danych i relacji między nimi, operacji i funkcji mających zastosowanie do danych. Pomaga w organizacji, zarządzaniu i przechowywaniu danych w określonym formacie. Dzięki temu użytkownicy mogą mieć łatwy dostęp i efektywnie modyfikować dane.
Struktury danych pomagają zarządzać dużymi ilościami danych, takimi jak ogromne bazy danych. Wydajne algorytmy budowane są w oparciu o wydajne struktury danych. Oprócz wydajnego przechowywania, struktury danych są również odpowiedzialne za wydajne pobieranie informacji z przechowywanej pamięci. Zawiera tablicę, listę połączoną, wskaźnik, wyszukiwanie, stos, wykres, kolejkę, strukturę, programy, sortowanie i tak dalej.
Artykuł obejmuje koncepcję wyszukiwania w strukturze danych i jej metody. Wyjaśniono szczegółowo dwa przykłady algorytmów, aby jasno zrozumieć tę koncepcję. Aby zdobyć dalszą wiedzę, umiejętności i doświadczenie, dostępne są kursy online dotyczące struktury danych, wymienione na końcu artykułu.
Co to jest wyszukiwanie w strukturze danych?
Proces wyszukiwania żądanych informacji ze zbioru elementów przechowywanych w postaci elementów w pamięci komputera określany jest mianem „przeszukiwania w strukturze danych”. Te zestawy elementów mają różne formy, takie jak tablica, drzewo, wykres lub lista połączona. Innym sposobem zdefiniowania wyszukiwania w strukturze danych jest zlokalizowanie pożądanego elementu o określonej charakterystyce w zbiorze pozycji.
Metody wyszukiwania
Wyszukiwanie w strukturze danych można wykonać, implementując algorytmy wyszukiwania w celu sprawdzenia lub pobrania elementu z dowolnej formy przechowywanej struktury danych. Algorytmy te są klasyfikowane na podstawie rodzaju operacji wyszukiwania, takich jak:
- Wyszukiwanie sekwencyjne
Tablica lub lista elementów jest przeszukiwana sekwencyjnie podczas sprawdzania każdego składnika zestawu.
Na przykład wyszukiwanie liniowe.
- Wyszukiwanie interwałowe
Algorytmy zaprojektowane wprost do wyszukiwania w posortowanych strukturach danych są uwzględniane w wyszukiwaniu przedziałowym. Wydajność tych algorytmów jest znacznie lepsza niż algorytmów wyszukiwania liniowego.
Na przykład wyszukiwanie binarne, wyszukiwanie logarytmiczne.
Metody te są badane na podstawie czasu potrzebnego algorytmowi na wyszukanie elementu pasującego do szukanego elementu w zbiorach danych i są podawane przez,
- Najlepszy możliwy czas
- Średni czas
- Czas najgorszego przypadku
Główne obawy dotyczą najgorszych czasów, które prowadzą do gwarantowanych przewidywań wydajności algorytmu, a także są łatwe do obliczenia w porównaniu ze średnimi czasami.
Aby zilustrować przykłady i koncepcje w tym artykule, uwzględniono „n” elementów w zbiorze danych w dowolnym formacie danych. Operacje dominujące służą do uproszczenia analizy i porównania algorytmów. W przypadku wyszukiwania w strukturze danych, porównanie jest operacją dominującą, oznaczaną przez O() i wymawianą jako „duże-Oh” lub „Oh”.
W strukturze danych istnieje wiele algorytmów wyszukiwania, takich jak wyszukiwanie liniowe, wyszukiwanie binarne, wyszukiwanie interpolacyjne, wyszukiwanie z przeskokiem, wyszukiwanie wykładnicze, wyszukiwanie Fibonacciego, wyszukiwanie podlist, wszechobecne wyszukiwanie binarne, nieograniczone wyszukiwanie binarne, funkcja rekurencyjna do wyszukiwania podciągów i program rekurencyjny aby wyszukać element liniowo w podanej tablicy. Artykuł ogranicza się do algorytmów wyszukiwania liniowego i binarnego oraz zasad ich działania.
Uzyskajmy szczegółowy wgląd w wyszukiwanie liniowe i wyszukiwanie binarne w strukturze danych.
Wyszukiwanie liniowe
Algorytm wyszukiwania liniowego przeszukuje sekwencyjnie wszystkie elementy w tablicy. Najlepszy czas wykonania to jeden, natomiast najgorszy czas wykonania to n, gdzie n to całkowita liczba pozycji w tablicy wyszukiwania.
Jest to najprostszy algorytm wyszukiwania w strukturze danych i sprawdza każdy element w zestawie elementów, aż do dopasowania elementu wyszukiwania do końca zbierania danych. Gdy dane są nieposortowane, preferowany jest algorytm wyszukiwania liniowego.
Wyszukiwanie liniowe ma pewną złożoność, jak podano poniżej:
- Złożoność przestrzeni
Złożoność przestrzeni dla wyszukiwania liniowego wynosi O(n), ponieważ nie wykorzystuje żadnej dodatkowej przestrzeni, gdzie n jest liczbą elementów w tablicy.
- Złożoność czasu
*Złożoność najlepszego przypadku = O(1) występuje, gdy element wyszukiwania jest obecny w pierwszym elemencie w tablicy wyszukiwania.
*Złożoność najgorszego przypadku = O(n) występuje, gdy element wyszukiwania nie występuje w zbiorze elementów lub tablicy.
*Średnia złożoność = O(n) jest określana, gdy element jest obecny gdzieś w tablicy wyszukiwania.
Przykład,
Weźmy podaną poniżej tablicę elementów:
45, 78, 12, 67, 08, 51, 39, 26
Aby znaleźć „51” w tablicy 8 elementów podanych powyżej, algorytm wyszukiwania liniowego będzie sprawdzać każdy element sekwencyjnie, aż jego wskaźnik wskaże 51 w przestrzeni pamięci. Potrzeba czasu O(6), aby znaleźć 51 w tablicy. Aby znaleźć 12, w powyższej tablicy, potrzeba O(3), podczas gdy dla 26, potrzeba czasu O(8).
Wyszukiwanie binarne
Algorytm ten znajduje określone elementy, porównując najbardziej środkowe elementy w zbiorze danych. Gdy nastąpi dopasowanie, zwraca indeks elementu. Gdy środkowy element jest większy niż element, szuka środkowego elementu lewej podtablicy. W przeciwieństwie do tego, jeśli środkowy element jest mniejszy niż element wyszukiwania, eksploruje środek elementu w prawej podtablicy. Kontynuuje wyszukiwanie elementu, dopóki go nie znajdzie lub dopóki rozmiar podtablic nie osiągnie zera.
Wyszukiwanie binarne wymaga uporządkowanej kolejności elementów. Jest szybszy niż algorytm wyszukiwania liniowego. Działa na zasadzie dziel i zwycięża.
Złożoność wykonania = O(log n)
Algorytm wyszukiwania binarnego ma złożoność, jak podano poniżej:
- Złożoność najgorszego przypadku = O (n log n)
- Średnia złożoność = O (n log n)
- Złożoność najlepszego przypadku = O (1)
Przykład,
Weźmy posortowany algorytm składający się z 08 elementów:
08, 12, 26, 39, 45, 51, 67, 78
Aby znaleźć 51 w tablicy powyższych elementów,
Algorytm podzieli tablicę na dwie tablice, 08, 12, 26, 39 i 45, 51, 67, 78
Ponieważ 51 jest większe niż 39, rozpocznie wyszukiwanie elementów po prawej stronie tablicy.
Będzie dalej dzielił na dwie takie jak 45, 51 i 67, 78
Ponieważ 51 jest mniejsze niż 67, rozpocznie wyszukiwanie na lewo od tej podtablicy.
Ta podtablica jest ponownie podzielona na dwie jako 45 i 51.
Ponieważ 51 jest liczbą pasującą do elementu wyszukiwania, zwróci swój numer indeksu tego elementu w tablicy.
Wynika stąd, że element wyszukiwania 51 znajduje się na szóstej pozycji w tablicy.
Wyszukiwanie binarne skraca czas do połowy, ponieważ liczba porównań jest znacznie zmniejszona niż algorytm wyszukiwania liniowego.
Przeczytaj: Rodzaje struktur danych w Pythonie
Wyszukiwanie interpolacyjne
Jest to ulepszony wariant algorytmu wyszukiwania binarnego i działa na pozycji sondowania elementu wyszukiwania. Podobnie jak algorytmy wyszukiwania binarnego, działa wydajnie tylko przy zbieraniu posortowanych danych.
Najgorszy czas wykonania = O(n)
Gdy położenie elementu docelowego jest znane w zbiorze danych, używane jest wyszukiwanie interpolacyjne. Aby znaleźć numer w książce telefonicznej, jeśli ktoś chce przeszukać numer telefonu Moniki, zamiast używać wyszukiwania liniowego lub binarnego, można bezpośrednio przeszukać pamięć w przestrzeni pamięci, gdzie nazwy zaczynają się od 'M'.
Wniosek
Wyszukiwanie w strukturach danych polega na znalezieniu danego elementu w tablicy 'n' elementów. Istnieją dwie kategorie, a mianowicie. Wyszukiwanie sekwencyjne i interwałowe w wyszukiwaniu. Prawie wszystkie algorytmy wyszukiwania opierają się na jednej z tych dwóch kategorii. Wyszukiwanie liniowe i binarne to dwa proste i łatwe do zaimplementowania algorytmy, w których binarny działa szybciej niż algorytmy liniowe.
Chociaż wyszukiwanie liniowe jest najprostsze, sprawdza każdy element, dopóki nie znajdzie dopasowania do elementu wyszukiwania, dzięki czemu jest wydajne, gdy zbieranie danych nie jest prawidłowo posortowane. Ale jeśli zbiór danych jest posortowany, a długość tablicy jest znaczna, wyszukiwanie binarne jest szybsze.
Struktura danych jest istotną częścią programowania komputerowego podczas pracy z zestawami danych. Programiści i programiści muszą stale aktualizować i podnosić swoje umiejętności dzięki podstawom i aktualizacjom technik programowania komputerowego. Programiści zajmujący się strukturą danych powinni często wybierać kursy.
Jeśli chcesz dowiedzieć się więcej o data science, sprawdź program Executive PG w dziedzinie Data Science IIIT-B i upGrad, który jest stworzony dla pracujących profesjonalistów i oferuje ponad 10 studiów przypadków i projektów, praktyczne warsztaty praktyczne, mentoring z ekspertami z branży, Indywidualnie z mentorami branżowymi, ponad 400 godzin nauki i pomocy w pracy z najlepszymi firmami.
