AiSDE Egzamin

Złożoność pesymistyczna wstawienia 100 nowych zdarzeń na listę zdarzeń symulacji zawierającą już 1000 zdarzeń wynosi:

Liczba poziomów drzewa turniejowego zawierającego 1000 elementów wynosi:

Aby skonstruować stóg składający się z n elementów, trzeba wpisać elementy do stogu i wykonać operację:

W trakcie symulacji zdarzeniowej czas symulacji zmieniamy:

Złożoność średnia sortowania prawie posortowanego ciągu n-elementowego algorytmami quicksort i przez wstawianie pozostaje w stosunku:

Złożoność średnia mierzona liczbą zamian przy sortowaniu prawie posortowanego ciągu n-elementowego algorytmami przez wstawianie i przez wybieranie pozostaje w stosunku:

Poszukując wśród n elementów k najmniejszych należy wstawić do stogu dokładnie:

Złożoności średnie znalezienia wśród n elementów k najmniejszych przy użyciu stogu i k-tego najmniejszego przy użyciu algorytmu Hoare'a są w stosunku:

Poszukując najlżejszego drzewa rozpinającego, konstruowanie drzewa:

Przy poszukiwaniu najlżejszego drzewa rozpinającego w grafie z n wierzchołkami, po k iteracjach stosunek liczby rozważanych drzew w algorytmie Kruskala i Prima wynosi:

W algorytmie znajdowania najgrubszej ścieżki od źródła, węzeł t krawędzi e=(o,t) jest cechowany z o, jeżeli (w - waga, l - etykieta):

Stosunek złożoności wyszukania w grafie o n wierzchołkach i m krawędziach najkrótszych ścieżek między wszystkimi parami wierzchołków przy użyciu algorytmu Floyda w stosunku do algorytmu Dijkstry wynosi: (Komandos zdaje się nie dostrzegać lepszych implementacji Dijkstry)

Przy wyszukiwaniu metodą interpolacyjną jednego spośród miliona elementów trzeba wykonać kroków około:

Stosunek pesymistycznej liczby kroków wymaganych do wyszukania elementu w słowniku 1000 elementów metodami przeszukiwania binarnego i drzewa AVL to:

Złożoności pesymistyczne wyszukania elementu w słowniku opartym na drzewie BST i drzewie AVL pozostają w stosunku:

W haszowaniu otwartym, przy n elementach i m możliwych wartościach kluczy wartości funkcji haszującej powinno być rzędu:

W haszowaniu zamkniętym, gdy stosujemy rehasz przy szukaniu elementu, którego nie ma w słowniku, kończymy, gdy:

Liczba wierzchołków drzewa pozycyjnego struktury słownika (nie licząc korzenia) jest równa:

W algorytmach znajdowania rozłącznych ścieżek przeplot to:

Przy znajdowaniu maksymalnego przepływu, krawędzi nieskierowanej o przepustowości 1 i przepływie 1/2 w grafie resztkowym odpowiada: