Algorytmy i struktury danych Flashcards
Algorytmy i struktury danych
Przedstaw ideę metody „dziel i zwyciężaj” w konstrukcji algorytmów, podaj przykłady.
Idea metody “dziel i zwyciężaj” polega na podziale trudnego problemu na mniejsze, bardziej zarządzalne podproblemy, rozwiązaniu każdego z nich oddzielnie (często rekurencyjnie), a następnie połączeniu wyników, aby uzyskać rozwiązanie problemu głównego. Ta strategia może być stosowana w różnych kontekstach, w tym w algorytmach sortowania, obliczeń numerycznych i wielu innych.
Przykłady:
* Sortowanie przez scalanie (mergesort): Ten algorytm dzieli listę na połowy aż do uzyskania jednoelementowych list, które są naturalnie posortowane, a następnie łączy te listy w sposób, który utrzymuje porządek sortowania.
* Algorytm szybkiego potęgowania: Obliczanie a^n polegające na rekurencyjnym obliczaniu (a^(n/2))^2 dla parzystych n, co redukuje liczbę wymaganych operacji mnożenia.
Algorytmy i struktury danych
Omów strukturę grafu i sposoby jego reprezentacji.
Struktura grafu: Graf to zbiór węzłów (zwanych także wierzchołkami) oraz krawędzi, które łączą te węzły. Grafy mogą być skierowane lub nieskierowane, ważone (z przypisaną wagą do każdej krawędzi) lub nieważone.
Sposoby reprezentacji:
- Macierz sąsiedztwa: Dwuwymiarowa tablica, gdzie komórka [i][j] wskazuje na obecność (często za pomocą wartości 1) lub brak (wartość 0) krawędzi między wierzchołkami i oraz j.
- Listy sąsiedztwa: Każdy wierzchołek grafu posiada listę zawierającą wszystkie inne węzły, z którymi jest połączony.
Algorytmy i struktury danych
Przedstaw ideę algorytmu sortowania szybkiego (quicksort) oraz jego złożoność.
Idea algorytmu quicksort: Quicksort to algorytm sortowania typu “dziel i zwyciężaj”, który wybiera tzw. “pivot” (element osiowy), a następnie partycjonuje tablicę na dwa podzbiory: elementy mniejsze lub równe pivotowi i elementy większe od pivotu. Następnie algorytm rekurencyjnie sortuje oba podzbiory.
Złożoność algorytmu quicksort:
Średnia i najlepsza: O(n log n), gdzie n jest liczbą elementów do posortowania.
Najgorszy przypadek: O(n^2), co zdarza się, gdy co wybór pivotu prowadzi do najmniej równomiernego podziału (np. przy już posortowanej tablicy).
Algorytmy i struktury danych
Podaj definicję drzewa binarnych poszukiwań BST (binary search tree), wymień podstawowe operacje na BST i ich złożoność.
Drzewo binarne poszukiwań (BST) to struktura danych, która dla każdego węzła spełnia następujące warunki:
* Wszystkie węzły w lewym poddrzewie mają wartości mniejsze od wartości węzła nadrzędnego.
* Wszystkie węzły w prawym poddrzewie mają wartości większe od wartości węzła nadrzędnego.
Podstawowe operacje na BST i ich złożoność:
* Wyszukiwanie: O(log n) w przypadku zrównoważonego drzewa, O(n) w najgorszym przypadku (dla drzewa zdegenerowanego w listę).
* Wstawianie: O(log n) zrównoważone, O(n) w najgorszym przypadku.
* Usuwanie: O(log n) zrównoważone, O(n) w najgorszym przypadku.
Algorytmy i struktury danych
Przedstaw istotę techniki haszowania, cechy funkcji haszującej, sposoby rozwiązywania kolizji.
Technika haszowania (ang. hashing) to metoda mapowania danych o dowolnej długości na krótsze klucze o stałej długości, nazywane hashami. Te klucze są następnie wykorzystywane do szybkiego wyszukiwania, efektywnewykorztsanie pamięci i wstawiania i usuwania danych.
Cechy funkcji haszującej:
- Deterministyczność: Dla tej samej wartości wejściowej zawsze generuje tę samą wartość haszu.
- Efektywność: Obliczenie wartości haszu powinno być szybkie.
- Równomierne rozłożenie: Powinna minimalizować kolizje, równomiernie rozkładając wartości haszu.
Sposoby rozwiązywania kolizji:
Kolizja ma miejsce, gdy dwa różne elementy mają ten sam hash. Istnieje kilka metod rozwiązywania kolizji:
* Łańcuchowe rozwiązywanie kolizji: Stosowanie listy (łańcucha) dla każdej wartości haszu w celu przechowywania wielu elementów.
* Adresowanie otwarte: Wyszukiwanie wolnej komórki w tablicy haszującej za pomocą różnych metod, np. liniowego próbkowania lub próbkowania kwadratowego.
