Problem dynamiczny (algorytmy)

Problemy dynamiczne w teorii złożoności obliczeniowej to problemy wyrażone w kategoriach zmieniających się danych wejściowych. W najbardziej ogólnej formie problem z tej kategorii jest zwykle przedstawiany w następujący sposób:

Biorąc pod uwagę klasę obiektów wejściowych, znajdź wydajne algorytmy i struktury danych, które odpowiedzą na określone zapytanie dotyczące zestawu obiektów wejściowych za każdym razem, gdy dane wejściowe zostaną zmodyfikowane, tj. obiekty zostaną wstawione lub usunięte.

Problemy tej klasy mają następujące miary złożoności:

Przestrzeń – ilość miejsca w pamięci wymaganego do przechowywania struktury danych;
Czas inicjalizacji – czas potrzebny na wstępne zbudowanie struktury danych;
Czas wstawienia – czas potrzebny na aktualizację struktury danych po dodaniu jeszcze jednego elementu wejściowego;
Czas usunięcia – czas potrzebny na aktualizację struktury danych po usunięciu elementu wejściowego;
Czas zapytania – czas potrzebny na udzielenie odpowiedzi na zapytanie;
Inne operacje specyficzne dla danego problemu

Ogólny zestaw obliczeń dla problemu dynamicznego nazywany jest algorytmem dynamicznym .

Wiele problemów algorytmicznych wyrażonych w kategoriach ustalonych danych wejściowych (zwanych w tym kontekście problemami statycznymi i rozwiązywanymi przez algorytmy statyczne ) ma znaczące wersje dynamiczne.

Przypadki specjalne

Algorytmy przyrostowe lub algorytmy online to algorytmy, w których dozwolone jest tylko dodawanie elementów, prawdopodobnie zaczynając od pustych/trywialnych danych wejściowych.

Algorytmy dekrementalne to algorytmy, w których dozwolone jest tylko usuwanie elementów, począwszy od inicjalizacji pełnej struktury danych.

Jeśli dozwolone jest zarówno dodawanie, jak i usuwanie, algorytm jest czasami nazywany w pełni dynamicznym .

Przykłady

Element maksymalny

Zadanie statyczne: Dla zbioru N liczb znajdź największą.

Problem można rozwiązać w czasie O(N).

Problem dynamiczny: Dla początkowego zbioru N liczb, dynamicznie utrzymuj maksymalną liczbę, gdy dozwolone jest wstawianie i usuwanie.

Dobrze znanym rozwiązaniem tego problemu jest samobalansujące się drzewo wyszukiwania binarnego . Zajmuje miejsce O(N), może być początkowo skonstruowany w czasie O(N log N) i zapewnia czasy wstawiania, usuwania i zapytania w O(log N).

Problem utrzymania kolejki priorytetowej: Jest to uproszczona wersja tego dynamicznego problemu, w którym należy usunąć tylko element maksymalny. Ta wersja może zawierać prostsze struktury danych.

Wykresy

Biorąc pod uwagę graf, zachowaj jego parametry, takie jak łączność, maksymalny stopień, najkrótsze ścieżki itp., Kiedy dozwolone jest wstawianie i usuwanie jego krawędzi.

Zobacz też