Struktury danych i algorytmy (DSA) odnoszą się do badania metod organizacji i przechowywania danych oraz projektowania procedur (algorytmów) rozwiązywania problemów, które działają na tych strukturach danych. DSA to jedna z najważniejszych umiejętności, którą musi posiadać każdy student informatyki. Często można zauważyć, że osoby posiadające dobrą wiedzę na temat tych technologii są lepszymi programistami niż inni i dlatego przechodzą wywiady z niemal każdym gigantem technologicznym. Ten Poradnik DSA ma na celu pomóc Ci szybko i łatwo nauczyć się struktur danych i algorytmów (DSA).

Spis treści

• Pełny formularz DSA
• Co to jest DSA?
• Jak nauczyć się DSA?
• Strunowy
• Połączone listy
• Matryca/Siatka
• Stos
• Kolejka
• Sterta
• Haszysz
• Drzewo
• Wykres

• Algorytm wyszukiwania
• Algorytm sortowania
• Algorytm dziel i zwyciężaj
• Chciwe algorytmy
• Rekurencja
• Algorytm cofania
• Programowanie dynamiczne
• Algorytmy wykresów:
• Wyszukiwanie wzorców
• Algorytmy matematyczne
• Algorytmy geometryczne
• Algorytmy bitowe
• Randomizowane algorytmy
• Algorytm rozgałęziony i związany

Pełny formularz DSA

Termin DSA oznacza Struktury danych i algorytmy , w kontekście informatyki.

Co to jest DSA?

Struktury danych i algorytmy (DSA) odnoszą się do badania metod organizacji i przechowywania danych oraz projektowania procedur (algorytmów) rozwiązywania problemów, które działają na tych strukturach danych.

Jak nauczyć się DSA?

Pierwszą i najważniejszą rzeczą jest podzielenie całej procedury na małe części, które należy wykonać sekwencyjnie. Cały proces nauki DSA od podstaw można podzielić na 5 części:

1. Naucz się przynajmniej jednego języka programowania (zostawiamy to Twojemu wyborowi).
2. Poznaj struktury danych
3. Naucz się algorytmów
4. Dowiedz się o złożoności czasu i przestrzeni
5. Ćwicz problemy dotyczące DSA

Jak nauczyć się DSA?

Mamy nadzieję, że nauczyłeś się wybranego języka programowania, przejdźmy do następnego kroku, aby nauczyć się DSA w tym samouczku DSA.

Nadchodzi najważniejszy i najbardziej oczekiwany etap planu uczenia się struktury danych i algorytmu – etap, w którym rozpoczynasz naukę o DSA. Tematyka DSA składa się z dwóch części:

• Struktury danych
• Algorytmy

Chociaż są to dwie różne rzeczy, są ze sobą ściśle powiązane i bardzo ważne jest, aby podążać właściwą drogą, aby nauczyć się ich najskuteczniej. Jeśli nie wiesz, którego uczyć się najpierw, zalecamy zapoznanie się z naszą szczegółową analizą na ten temat: Tutaj prześledziliśmy proces uczenia się struktury danych, a następnie najbardziej powiązane i najważniejsze algorytmy wykorzystywane przez tę strukturę danych.

Poznaj struktury danych

Struktury danych to podstawowe komponenty, które pomagają organizować i efektywnie przechowywać dane w pamięci komputera. Umożliwiają efektywne zarządzanie danymi i manipulowanie nimi, umożliwiając szybszy dostęp, operacje wstawiania i usuwania. Typowe struktury danych obejmują tablice, listy połączone, stosy, kolejki, drzewa i wykresy , z których każdy służy konkretnym celom w oparciu o wymagania danego problemu. Zrozumienie struktur danych ma fundamentalne znaczenie dla projektowania wydajnych algorytmów i optymalizacji wydajności oprogramowania.

Szyk to liniowa struktura danych przechowująca zbiór elementów tego samego typu danych. Elementom przydzielana jest ciągła pamięć, co pozwala na stały dostęp. Każdy element ma unikalny numer indeksu.

• Operacje na tablicy:
  • Przejście : Iteracja po elementach tablicy.
  • Wprowadzenie : Dodanie elementu do tablicy o określonym indeksie.
  • Usunięcie : Usuwanie elementu z tablicy o określonym indeksie.
  • Badawczy : Znajdowanie elementu w tablicy według jego wartości lub indeksu.
• Rodzaje tablic :
  • Tablica jednowymiarowa : Prosta tablica z jednym wymiarem.
  • Tablica wielowymiarowa : Tablica o wielu wymiarach, taka jak macierz.
• Zastosowania tablicy :
  • Przechowywanie danych w sposób sekwencyjny
  • Implementowanie kolejek, stosów i innych struktur danych
  • Reprezentowanie macierzy i tabel
• Powiązane tematy dotyczące tablicy:
  • Samouczek dotyczący tablic
  • 50 najważniejszych problemów z kodowaniem tablicowym podczas rozmów kwalifikacyjnych
  • Ćwicz problemy na tablicach

2. Sznurek

A strunowy to ciąg znaków, zwykle używany do reprezentowania tekstu. Uważa się, że jest to typ danych umożliwiający manipulację i przetwarzanie danych tekstowych w programach komputerowych.

• Operacje na ciągach :
  • Powiązanie : Łączenie dwóch ciągów znaków.
  • Porównanie : Porównywanie leksykograficzne dwóch ciągów znaków.
  • Podciąg ekstrakcja : Wyodrębnianie podciągu z ciągu.
  • Szukaj : Wyszukiwanie podciągu w ciągu.
  • Modyfikacja : Zmiana lub zamiana znaków w ciągu.
• Zastosowania ciągu :
  • Przetwarzanie tekstu
  • Dopasowanie wzoru
  • Walidacji danych
  • Zarządzania bazami danych
• Powiązane posty:
  • Poradnik dotyczący sznurków
  • 50 najważniejszych problemów z kodowaniem ciągów podczas rozmów kwalifikacyjnych
  • Ćwicz problemy na sznurku

3. Połączone listy

A połączona lista to liniowa struktura danych, która przechowuje dane w węzłach połączonych wskaźnikami. W przeciwieństwie do tablic, listy połączone nie są przechowywane w sąsiadujących lokalizacjach pamięci.

• Charakterystyka listy połączonej:
  • Dynamiczny : Rozmiar list połączonych można łatwo zmieniać, dodając lub usuwając węzły.
  • Nieciągłe : Węzły są przechowywane w losowych lokalizacjach pamięci i połączone wskaźnikami.
  • Dostęp sekwencyjny : Dostęp do węzłów można uzyskać tylko sekwencyjnie, zaczynając od początku listy.
• Operacje na liście połączonej:
  • kreacja : Tworzenie nowej połączonej listy lub dodanie nowego węzła do istniejącej listy.
  • Przejście : Iteracja po liście i uzyskiwanie dostępu do każdego węzła.
  • Wprowadzenie : Dodanie nowego węzła w określonej pozycji na liście.
  • Usunięcie : Usuwanie węzła z listy.
  • Szukaj : Znalezienie węzła o określonej wartości na liście.
• Rodzaje list połączonych :
  • Lista pojedynczo połączona : Każdy węzeł wskazuje następny węzeł na liście.
  • Lista podwójnie połączona : Każdy węzeł wskazuje zarówno następny, jak i poprzedni węzeł na liście.
  • Okrągła lista połączona : Ostatni węzeł wskazuje z powrotem na pierwszy węzeł, tworząc okrągłą pętlę.
• Zastosowania listy połączonej :
  • Listy połączone są używane w różnych aplikacjach, w tym:
  • Implementacja kolejek i stosów
  • Reprezentowanie wykresów i drzew
  • Utrzymanie uporządkowanych danych
  • Zarządzanie pamięcią
• Powiązane tematy:
  • Samouczek dotyczący listy połączonych
  • 50 najważniejszych problemów na połączonej liście do rozmów kwalifikacyjnych
  • Ćwicz problemy dotyczące list połączonych

4. Matryca/Siatka

A matryca to dwuwymiarowa tablica elementów ułożonych w wierszach i kolumnach. Jest reprezentowany jako prostokątna siatka, w której każdy element znajduje się na przecięciu wiersza i kolumny.

• Kluczowe idee:
  • Wydziwianie : Poziome linie elementów macierzy.
  • Kolumny : Pionowe linie elementów macierzy.
  • Wymiary : Liczba wierszy i kolumn w macierzy (np. macierz 3×4 ma 3 wiersze i 4 kolumny).
  • Element Dostęp : Dostęp do elementów można uzyskać za pomocą indeksów wierszy i kolumn (np. M[2][3] odnosi się do elementu w wierszu 2 i kolumnie 3).
• Zastosowania macierzy/siatki :
  • Przetwarzanie obrazu
  • Analiza danych
  • Problemy z optymalizacją
• Powiązane posty:
  • Poradnik dotyczący macierzy/siatki
  • 50 najważniejszych problemów w matrycy/siatce podczas rozmów kwalifikacyjnych
  • Ćwicz problemy na macierzy/siatce

5. Stos

Stos to liniowa struktura danych, która charakteryzuje się określoną kolejnością wykonywania operacji. Kolejność może być LIFO (ostatni na wejściu, pierwszy na wyjściu) Lub FILO (pierwsze weszło, ostatnie wyszło) . LIFO oznacza, że ​​element wstawiany jako ostatni wychodzi jako pierwszy i WIERSZ oznacza, że ​​element wstawiany jako pierwszy wychodzi jako ostatni.

• Operacja na stosie :
  • Naciskać : Dodaje element na górę stosu
  • Muzyka pop : Usuwa i zwraca element na górze stosu
  • Zerkać : Zwraca element na szczycie stosu bez jego usuwania
  • Rozmiar : Zwraca liczbę elementów na stosie
  • Jest pusty : Sprawdza, czy stos jest pusty
• Zastosowania stosu :
  • Wywołania funkcji
  • Ocena wyrażeń
  • Cofanie się
  • Operacje cofania/ponawiania
• Powiązane tematy na stosie:
  • Samouczek dotyczący stosu
  • 50 najważniejszych problemów na stosie podczas rozmów kwalifikacyjnych
  • Ćwicz problemy na stosie

6. Kolejka

A Kolejka Struktura danych to podstawowe pojęcie w informatyce wykorzystywane do przechowywania danych i zarządzania nimi w określonej kolejności. Kieruje się zasadą Pierwsi weszli, pierwsi wyszli ( FIFO ), gdzie pierwszy element dodany do kolejki jest pierwszym, który zostanie usunięty

• Operacja w kolejce :
  • Kolejkuj : Dodaje element na końcu kolejki
  • Odpowiednio : Usuwa element z przodu kolejki
  • Zerkać : pobiera przedni element bez jego usuwania
  • Jest pusty : Sprawdza, czy kolejka jest pusta
  • Jest pełna : Sprawdza, czy kolejka jest pełna
• Typ kolejki :
  • Okrągła kolejka : Ostatni element łączy się z pierwszym elementem
  • Kolejka dwustronna (Deque) : Operacje można wykonywać z obu końców
  • Kolejka priorytetowa : Elementy są rozmieszczone według priorytetu
• Zastosowania kolejki :
  • Planowanie pracy
  • Kolejkowanie wiadomości
  • Modelowanie symulacyjne
  • Buforowanie danych
• Powiązane tematy:
  • Poradnik dotyczący kolejki
  • 50 najważniejszych problemów w kolejce na rozmowy kwalifikacyjne
  • Ćwicz problemy w kolejce

7. Sterta

A Sterta jest kompletną binarną strukturą danych drzewa, która spełnia właściwość sterty: dla każdego węzła wartość jego dzieci jest mniejsza lub równa jego własnej wartości. Do implementacji zwykle używa się stert kolejki priorytetowe , gdzie najmniejszy (lub największy) element zawsze znajduje się w korzeniu drzewa.

• Operacje na stercie :
  • Wstawić : Dodaje nowy element do sterty, zachowując właściwości sterty.
  • Ekstrakt-Maks./Wyciąg-Min : Usuwa element główny i restrukturyzuje stertę.
  • Klawisz zwiększania/zmniejszania : Aktualizuje wartość węzła i restrukturyzuje stertę.
• Rodzaje sterty :
  • Maksymalny stos : Węzeł główny ma maksymalną wartość wśród swoich dzieci.
  • Min-Sterta : Węzeł główny ma minimalną wartość wśród swoich dzieci.
• Zastosowania sterty :
  • Kolejki priorytetowe
  • Sortowanie
  • Algorytmy grafowe (np. algorytm Dijkstry)
• Powiązane posty:
  • Samouczek dotyczący sterty
  • 50 najważniejszych problemów na stosie podczas rozmów kwalifikacyjnych
  • Ćwicz problemy na stercie

8. Haszysz

Haszowanie to technika, która generuje wynik o stałym rozmiarze (wartość skrótu) z danych wejściowych o zmiennym rozmiarze za pomocą wzorów matematycznych zwanych funkcje skrótu . Haszowanie służy do określenia indeksu lub lokalizacji przechowywania elementu w strukturze danych, co pozwala na wydajne pobieranie i wstawianie.

• Kluczowe idee:
  • Funkcja skrótu : Funkcja matematyczna, która odwzorowuje dane wejściowe na wartość skrótu.
  • Tabela mieszająca : Struktura danych przechowująca pary klucz-wartość, gdzie klucz jest wartością skrótu, a wartością są rzeczywiste dane.
  • Kolizja : Gdy dwa różne klucze dają tę samą wartość skrótu.
• Rodzaje funkcji skrótu :
  • Metoda podziału : Dzieli dane wejściowe przez stałą, a resztę wykorzystuje jako wartość skrótu.
  • Plac Środkowy Metoda: Podnosi dane wejściowe do kwadratu i przyjmuje środkowe cyfry jako wartość skrótu.
  • Metoda składania : Dzieli dane wejściowe na bloki o równej wielkości i dodaje je do siebie, aby uzyskać wartość skrótu.
  • Metoda mnożenia : Mnoży dane wejściowe przez stałą i przyjmuje część ułamkową jako wartość skrótu.

• Techniki rozwiązywania kolizji :
  • Oddzielne łańcuchy (otwarte mieszanie) : Przechowuje kolidujące elementy na połączonej liście z odpowiednią wartością skrótu.
  • Otwarte adresowanie (zamknięte haszowanie) : Używa różnych strategii, aby znaleźć alternatywną lokalizację kolidujących elementów w tabeli skrótów.
• Zastosowania haszowania :
  • Efektywne przechowywanie i odzyskiwanie danych w bazach danych i systemach plików.
  • Weryfikacja haseł i podpisów cyfrowych.
  • Dystrybucja żądań na wiele serwerów.
  • Generowanie bezpiecznych skrótów dla integralności danych i uwierzytelniania.
• Powiązane posty:
  • Poradnik dotyczący hasha
  • Ćwicz problemy dotyczące haszowania

9. Drzewo

A drzewo to nieliniowa hierarchiczna struktura danych składająca się z węzłów połączonych krawędziami, z górnym węzłem zwanym korzeniem i węzłami posiadającymi węzły podrzędne. Jest stosowany w informatyce do efektywnego organizowania danych.

zaczyna się od Javy

• Przejście przez drzewo : Metody przechodzenia przez drzewo służą do odwiedzania i przetwarzania węzłów w drzewiastej strukturze danych. Trzy popularne metody przechodzenia to:
  • W celu : Odwiedź lewe poddrzewo, bieżący węzeł, a następnie prawe poddrzewo.
  • Przed Sprzedaż : Odwiedź bieżący węzeł, lewe poddrzewo, a następnie prawe poddrzewo.
  • Po zamówieniu : Odwiedź lewe poddrzewo, prawe poddrzewo, a następnie bieżący węzeł.
• Klasyfikacje drzew:
  • Klasyfikacje Drzewa odnoszą się do grupowania drzew w oparciu o pewne cechy lub kryteria. Może to obejmować kategoryzację drzew na podstawie ich współczynnika równowagi, stopnia węzłów, właściwości porządkowych itp. Poniżej znajduje się kilka ważnych klasyfikacji drzew.

• Zastosowania drzew:
  • Systemy plików
  • Bazy danych
  • Dokumenty XML
  • Sztuczna inteligencja
• Powiązane posty:
  • Poradnik dotyczący drzewa
  • 50 najważniejszych problemów z kodowaniem drzew
  • Ćwicz problemy na drzewie

10. Wykres

A Wykres to nieliniowa struktura danych składająca się ze skończonego zestawu wierzchołków (lub węzłów) i zestawu krawędzi łączących parę węzłów.

• Przejścia wykresu:
  • Wyszukiwanie wszerz (BFS) : Odwiedza węzły poziom po poziomie.
  • Wyszukiwanie w głąb (DFS) : Odwiedza węzły rekurencyjnie, eksplorując jedną gałąź na raz.
• Zastosowania grafów :
  • Portale społecznościowe
  • Mapy i nawigacja
  • Planowanie
  • Eksploracja danych
• Powiązane posty:
  • Reprezentacja wykresu
  • Rodzaje wykresów
  • Poradnik dotyczący wykresów
  • Ćwicz problemy na wykresie

Naucz się algorytmów

Po wyjaśnieniu pojęć Struktury danych , teraz czas rozpocząć podróż przez Algorytmy . W zależności od rodzaju natury i zastosowania algorytmy są pogrupowane w kilka kategorii, jak pokazano poniżej:

1. Algorytm wyszukiwania

Algorytmy wyszukiwania służą do lokalizowania określonych danych w większym zestawie danych. Pomaga znaleźć w danych obecność wartości docelowej. Istnieją różne typy algorytmów wyszukiwania, każdy z własnym podejściem i wydajnością.

• Najpopularniejsze algorytmy wyszukiwania:
  • Wyszukiwanie liniowe : Przeszukiwanie iteracyjne od jednego końca do drugiego.
  • Wyszukiwanie binarne : Wyszukiwanie typu „dziel i zwyciężaj” w posortowanej tablicy, zmniejszając o połowę przestrzeń poszukiwań przy każdej iteracji.
  • Wyszukiwanie trójskładnikowe : Przeszukiwanie typu „dziel i zwyciężaj” w posortowanej tablicy, dzieląc przestrzeń poszukiwań na trzy części w każdej iteracji.
• Inne algorytmy wyszukiwania:
  • Przeskocz wyszukiwanie
  • Wyszukiwanie interpolacyjne
  • Wyszukiwanie wykładnicze
• Powiązane tematy:
  • Ćwicz problemy dotyczące algorytmu wyszukiwania

2. Algorytm sortowania

Algorytmy sortowania służą do porządkowania elementów listy w określonej kolejności, np. numerycznej lub alfabetycznej. Porządkuje elementy w sposób systematyczny, ułatwiając wyszukiwanie i dostęp do poszczególnych elementów.

Istnieje wiele różnych typów algorytmów sortowania. Niektóre powszechnie stosowane algorytmy to:

Powiązane tematy:

• Samouczek algorytmu sortowania
• Najczęściej sortowane pytania i problemy podczas rozmowy kwalifikacyjnej
• Przećwicz zadania dotyczące algorytmu sortowania

3. Algorytm dziel i zwyciężaj

Dziel i rządź algorytmy stosują rekurencyjną strategię rozwiązywania problemów, dzieląc je na mniejsze podproblemy, rozwiązując te podproblemy i łącząc rozwiązania w celu uzyskania rozwiązania końcowego.

Kroki:

1. Dzielić : Podziel problem na mniejsze, niezależne podproblemy.
2. Podbić : Rekurencyjnie rozwiązuj każdy podproblem.
3. Łączyć : Połącz rozwiązania podproblemów, aby uzyskać rozwiązanie końcowe.

Przykłady:

• Sortowanie przez scalanie: Dzieli tablicę na dwie połowy, sortuje każdą połowę rekurencyjnie i łączy posortowane połówki.
• Szybkie sortowanie: wybiera element przestawny, dzieli tablicę na dwie podtablice w oparciu o przestawną i rekursywnie sortuje każdą podtablicę.
• Wyszukiwanie binarne: Dzieli przestrzeń poszukiwań na pół, aż do znalezienia elementu docelowego lub wyczerpania przestrzeni poszukiwań.

Powiązane artykuły:

• Poradnik Dziel i rządź
• Ćwicz problemy z algorytmem „Dziel i zwyciężaj”.

4. Chciwe algorytmy

Jak sama nazwa wskazuje, algorytm ten buduje rozwiązanie po kawałku i wybiera następny element, który daje najbardziej oczywistą i natychmiastową korzyść, tj. który jest najbardziej optymalnym wyborem w tym momencie. Zatem problemy, w których wybór lokalnie optymalnych rozwiązań prowadzi również do rozwiązań globalnych, najlepiej pasują do Greedy.

Oto kilka ważnych problemów zachłannych algorytmów:

Powiązane artykuły:

• Poradnik dotyczący algorytmu zachłannego
• Ćwicz problemy z algorytmem Greedy'ego

5. Rekurencja

Rekurencja to technika programowania, w której funkcja wywołuje samą siebie w ramach swojej własnej definicji. Zwykle stosuje się go do rozwiązywania problemów, które można podzielić na mniejsze wystąpienia tego samego problemu. Na przykład: Wieże Hanoi (TOH) , Obliczenia czynnikowe I Ciąg Fibonacciego itp.

10 z 40

Kroki :

• Obudowa podstawowa : Zdefiniuj warunek, który zatrzymuje wywołania rekurencyjne i zapewnia rozwiązanie.
• Przypadek rekurencyjny : Zdefiniuj kroki, aby podzielić problem na mniejsze instancje i wykonać wywołania rekurencyjne.
• Powrót : Zwróć rozwiązanie z wywołań rekurencyjnych i połącz je, aby rozwiązać pierwotny problem.

Cechą, która sprawia, że ​​rekurencja jest jednym z najczęściej używanych algorytmów, jest to, że stanowi ona podstawę dla wielu innych algorytmów, takich jak Przejścia przez drzewa , Przejścia wykresu , Algorytmy dziel i zwyciężaj I Algorytmy cofania .

Powiązane tematy:

• Poradnik dotyczący rekurencji
• Funkcje rekurencyjne
• Rekurencja ogona
• 50 najważniejszych problemów związanych z algorytmem rekurencji w rozmowie kwalifikacyjnej
• Ćwicz problemy dotyczące algorytmu rekurencji

6. Algorytm cofania

Jak wspomniano wcześniej, Cofanie się algorytm wywodzi się z algorytmu rekurencji, z możliwością przywrócenia, jeśli rozwiązanie rekurencyjne zawiedzie, tj. w przypadku niepowodzenia rozwiązania program śledzi moment, w którym zawiodło i buduje na innym rozwiązaniu. Zasadniczo wypróbowuje wszystkie możliwe rozwiązania i znajduje właściwe.

Niektóre ważne i najczęstsze problemy algorytmów cofania, które należy rozwiązać przed kontynuowaniem, to:

Powiązany artykuł:

• Poradnik cofania się
• Ćwicz problemy dotyczące algorytmu wycofywania się

7. Programowanie dynamiczne

Programowanie dynamiczne to metoda stosowana w matematyce i informatyce do rozwiązywania złożonych problemów poprzez rozbicie ich na prostsze podproblemy. Rozwiązując każdy podproblem tylko raz i przechowując wyniki, pozwala uniknąć zbędnych obliczeń, co prowadzi do bardziej wydajnych rozwiązań szerokiego zakresu problemów.

Kluczowe idee:

• Optymalna podbudowa : Optymalne rozwiązanie problemu można zbudować z optymalnych rozwiązań jego podproblemów.
• Nakładające się podproblemy : Podproblemy często powtarzają się w większym problemie, co prowadzi do zbędnych obliczeń.
• Zapamiętywanie / Tabulacja : Przechowywanie rozwiązań podproblemów w celu uniknięcia ponownego obliczania.

Niektóre ważne i najczęstsze problemy algorytmów programowania dynamicznego, które należy rozwiązać przed kontynuowaniem, to:

Powiązane artykuły:

• Tabulacja a zapamiętywanie
• Jak rozwiązać problem programowania dynamicznego?
• Samouczek programowania dynamicznego
• 50 najważniejszych problemów z kodowaniem w programowaniu dynamicznym podczas rozmów kwalifikacyjnych
• Ćwicz problemy dotyczące algorytmu programowania dynamicznego

8. Algorytmy grafowe :

Algorytmy grafowe w strukturach danych i algorytmach (DSA) to zbiór technik i metod stosowanych do rozwiązywania problemów związanych z grafami, które są zbiorem węzłów i krawędzi. Algorytmy te służą do wykonywania różnych operacji na wykresach, np szukanie, przemierzanie, znajdowanie najkrótszej ścieżki i ustalanie łączność . Są niezbędne do rozwiązywania szerokiego zakresu problemów świata rzeczywistego, w tym routingu sieciowego, analizy sieci społecznościowych i alokacji zasobów.

Powiązane tematy:

• Poradnik dotyczący wykresów
• 50 najważniejszych problemów z kodowaniem wykresów podczas wywiadów
• Ćwicz problem dotyczący algorytmów grafowych

9 . Wyszukiwanie wzorców

Wyszukiwanie wzorców to podstawowa technika w DSA używana do wyszukiwania wystąpień określonego wzorca w danym tekście.

Poniżej znajduje się kilka standardowych algorytmów wyszukiwania wzorców:

Powiązane tematy:

• Samouczek wyszukiwania wzorców
• Ćwicz zadanie na Wyszukiwanie wzorców

10 . Algorytmy matematyczne

Algorytmy matematyczne to klasa algorytmów rozwiązujących problemy związane z pojęciami matematycznymi. Są szeroko stosowane w różnych dziedzinach, w tym w grafice komputerowej, analizie numerycznej, optymalizacji i kryptografii.

Powiązane tematy:

• Ćwicz problem dotyczący algorytmu matematycznego

11. Algorytmy geometryczne

Algorytmy geometryczne to klasa algorytmów rozwiązujących problemy związane z geometrią. Algorytmy geometryczne są niezbędne do rozwiązywania szerokiego zakresu problemów w informatyce, takich jak:

Powiązane tematy:

• Ćwicz zadanie dotyczące algorytmów geometrycznych

12. Algorytmy bitowe

Algorytmy bitowe to algorytmy działające na pojedynczych bitach liczb. Algorytmy te manipulują binarną reprezentacją liczb w celu wykonywania takich zadań, jak manipulowanie bitami, bitowe operacje logiczne (AND, OR, XOR), przesuwanie bitów , I ustawienie Lub czyszczenie określonych bitów w ramach liczby. Algorytmy bitowe są powszechnie stosowane w Zadania związane z programowaniem niskiego poziomu, kryptografią i optymalizacją gdzie wymagana jest wydajna manipulacja pojedynczymi bitami.

Powiązane tematy:

• Samouczek algorytmów bitowych
• Ćwicz zadanie dotyczące algorytmów bitowych

13. Algorytmy losowe

Algorytmy randomizowane to algorytmy wykorzystujące losowość do rozwiązywania problemów. Wykorzystują losowe dane wejściowe, aby osiągnąć swoje cele, często prowadząc do prostszych lub bardziej wydajnych rozwiązań.

Rodzaje algorytmów losowych:

1 milion ile 0

• Las Vegas : Zawsze daje poprawny wynik, ale czas działania jest losowy.
• Monte Carlo : Może dawać nieprawidłowy wynik z małym prawdopodobieństwem, ale czas działania jest zwykle krótszy.

Ważne algorytmy wykorzystujące algorytmy randomizacji:

14. Algorytm rozgałęziony i związany

The Algorytm rozgałęziony i związany jest metodą stosowaną w problemach optymalizacji kombinatorycznej w celu systematycznego poszukiwania najlepszego rozwiązania. Działa poprzez podzielenie problemu na mniejsze podproblemy lub gałęzie, a następnie wyeliminowanie niektórych gałęzi w oparciu o granice optymalnego rozwiązania. Proces ten trwa do momentu znalezienia najlepszego rozwiązania lub zbadania wszystkich gałęzi.

Standardowe problemy dotyczące algorytmu rozgałęzionego i powiązanego:

Powiązane tematy:

• Samouczek algorytmu rozgałęziania i wiązania

Dowiedz się o złożonościach

W strukturach danych i algorytmach (DSA) głównym celem jest skuteczne i wydajne rozwiązywanie problemów. Aby określić efektywność programu, przyglądamy się dwóm typom złożoności:

1. Złożoność czasu : Mówi nam, ile czasu zajmuje wykonanie naszego kodu.
2. Złożoność przestrzeni : Mówi nam, ile pamięci wykorzystuje nasz kod.

Notacja asymptotyczna :

Aby porównać efektywność algorytmów, używamy notacji asymptotycznej, narzędzia matematycznego służącego do estymacji czas oparte na rozmiar wejściowy bez uruchamiania kodu. Koncentruje się na liczbie podstawowych operacji w programie.

Najczęściej stosowaną notacją do analizy kodu jest Notacja dużego O , określając górny limit czasu działania lub zużycia pamięci w odniesieniu do rozmiaru wejściowego.

Powiązane tematy:

• Zrozumienie złożoności czasu na prostych przykładach
• Złożoność czasowa różnych struktur danych
• Jak analizować pętle do analizy złożoności algorytmów
• Ćwicz pytania dotyczące analizy złożoności czasu

Ściągawki do rozwiązywania problemów praktycznych:

Wyselekcjonowane listy problemów z poniższych artykułów:

• Mapa drogowa DSA autorstwa Sandeepa Jaina
• ARKUSZ SDE – kompletny przewodnik dotyczący przygotowania SDE
• Arkusz główny techcodeview.com – lista wszystkich ściągawek