Złożoność pesymistyczna algorytmów

Cześć, tak się złożyło, że ostatnimi czasy zainteresowały mnie algorytmy i struktury danych. Od około dwóch tygodni analizuję stos, drzewa listy itp. Zainteresowałem się żłożonościami pesymistycznymi dla niektórych algorytmów. Około połowę operacji uzupełniłem samodzielnie.

Proszę o sprawdzenie, czy to co uzupełniłem jest poprawne oraz o pomoc w uzupełnieniu brakujących wartości :D

Operacja/Algorytm | Tablica nieuporządkowana | Stos | Lista jednokierunkowa | Lista dwukierunkowa | Kopiec binarny | Kopiec dwumianowy | Kopiec Fibonacciego | Drzewo AVL | Drzewo czerwono-czarne
---------------- | --
Wstawienie klucza | O(1) | O(1) | O(1) lub O(n) | O(1) | O(log n) | O(log n) | O(1) | O(log n) | O(log n)
Usunięcie klucza | O(1) | O(1) | O(n) | O(n) | O(log n) | O(log n) | O(n) | - | -
Modyfikacja klucza | O(1) | - | O(n) | O(n) | - | - | - | - | -
Następnik klucza | - | - | O(1) | O(1) | - | - | - | - | -
Poprzednik klucza | - | - | O(n) | O(1) | - | - | - | - | -
Maksimum | O(n) | - | - | - | - | - | - | - | -
Minimum | O(n) | - | - | - | O(1) | O(log n) | O(n) | - | -

1. Usunięcie lub modyfikacja klucza w tablicy uporządkowanej nie jest O(1) — jako że musisz najpierw ten klucz tam odnaleźć.
2. Podobnie dla usuwania klucza z listy dwukierunkowej i dla modyfikacji w obu listach.
3. Następnik klucza na liście jednokierunkowej to tylko jedna operacja.
4. Znalezienie minimum w kopcu Fibonacciego jest stałe tylko w sensie amortyzowanym.
5. Wstawienie klucza do drzewa AWŁ to czas pseudostały (tzn. O(log(n))).

Być może są inne błędy, ale te rzuciły mi się w oczy przed wypiciem kawy.

Swoją drogą, bardziej po polsku byłoby pisać o „drzewie AWŁ”, bo jego autorzy to Adelson-Wielskij i Łandis, nie ma się co silić na anglicyzmy… Przy czym zdaję sobie sprawę z tego, że chyba tylko ja tak piszę o tej strukturze danych… I tak się cieszę, że nie pisze się o „drzewie АВЛ”.

Dzięki.

1. W tablicy uporządkowanej nie jest stała, to masz rację, ale tutaj mam tablicę nieuporządkowaną więc raczej jest dobrze.
2. Rozumiem, że w kopcu Fibonacciego w takim razie powinno być O(n)?

Rosyjki to fajny język, ale klawiatura uboga więc odpada :(

Poprawiłem tabelkę w poście

W obu tych sytuacjach, zależy, co chcesz zapisać. W pierwszej, pytanie czy chcesz się, na przykład, dostać do ósmego elementu — wtedy jest tak, jak piszesz, że dostęp jest natychmiastowy, czy może dostać do elementu zawierającego "kopytko" — a wtedy musisz przeszukać tablicę, bo nie wiesz, gdzie to jest. W drugiej, jeśli Cię faktycznie interesuje pesymistyczny niezamortyzowany przypadek, to tak. Ale zazwyczaj (nie zawsze! Istotnym wyjątkiem są np. systemy czasu rzeczywistego) bardziej obchodzi nas czas zamortyzowany.

Trochę to wszystko pomieszane, ale co zrobić :D Gdzieś wyczytałem, że najistotniejsza jest pesymistyczna złożoność. Ktoś by mógł mi wytłumaczyć pozostałe przypadki?

Zastanawianie się, czy istotniejsza jest złożoność pesymistyczna, czy średnia, czy może jeszcze inna, jest tak, jak zastanawianie się, czy lepsze w samochodzie jest przyspieszenie, czy prędkość maksymalna — w różnych warunkach różne rzeczy się liczą. Typowo najbardziej obchodzi nas złożoność średnia, bo wolimy, żeby program się wykonywał co do zasady szybciej, nawet jeśli przez to sporadycznie może się wykonywać wolniej. Przez co jednym z najbardziej popularnych algorytmów sortujących jest quicksort, o paskudnej złożoności pesymistycznej O(n²).

A co do pozostałych:

• W tablicach nieuporządkowanych raczej nie ma co mówić o poprzednikach/następnikach. Jeśli chodzi o zmienną bezpośrednio mniejszą/większą, to z jednej strony można to zrobić, wyznaczając wszystkie elementy mniejsze (O(n)) a potem biorąc ich maksimum (O(n)), więc ostatecznie szukana złożoność jest ≤ O(n), a z drugiej, potencjalnie taka wartość może być na przeciwnym końcu tablicy, więc musimy ją przejrzeć całą, zatem złożoność ≥ O(n), stąd ostatecznie jest równa O(n).
• W stosie, żeby zmodyfikować klucz, musimy się do niego dostać, a że dostawać się możemy tylko do wartości na górze, to złożoność ≥ O(n) (musimy, w najgorszym przypadku, zdjąć wszystko ze stosu). Z drugiej strony, możemy zawsze pościągać wszystko ze stosu i wrzucić jak leci w tablicę nieuporządkowaną (O(n)), a potem przeszukać w O(n) tamtą, zatem ostatecznie złożoność modyfikacji to O(n).
• Następnik na stosie to O(1) — po prostu ściągasz kolejną wartość. Poprzednik podobnie — wrzucasz sobie ściągnięte wartości po jednej do bufora, patrzysz na wartość na szczycie, i jak w końcu będzie taka, jak chciałeś, to bierzesz bufor.

Spróbuj teraz sam kilka kolejnych.

Zwróć uwagę, że ja rozumiem „modyfikację klucza” jako procedurę mającą znaleźć klucz, zmienić go i przywrócić odpowiedni stan strukturze, natomiast w każdym pozostałym przypadku wychodzę od już znanego położenia elementu. Dlaczego tak? Głównie po to, by różniło się to istotnie od usuwania klucza. Ale jeśli chcesz, mogę przyjąć inną umowę.

Sposób w jaki rozumiesz modyfikację klucza jest jak najbardziej trafny.

1. Stos: maksimum i minimum wynosi O(n) ponieważ tą wartość trzeba najpierw znaleźć.
2. Lista jednokierunkowa i dwukierunkowa: maksimum i minimum tak samo jak w stosie. Wartość trzeba znaleźć.
3. Kopiec binarny: modyfikacja klucza wynosi O(log n), klucz trzeba znaleźć, wyciągnąć, zmienić wartość i wstawić ponownie. Następnik i poprzednik klucza to O(n) ponieważ trzeba przejść przez każdy element w kopcu i sprawdzić, czy jest on następnikiem bądź poprzednikiem. Maksimum to O(1), zawsze jest na początku kopca.

Na razie tyle, przeanalizuję teraz reszte algorytmów i uzupełnie brakujące. Althorion prosiłbym Cię o sprawdzenie mojego rozumowania :D

Ad 1.: Tak, ale jakby to było kolokwium, to bym Ci pewnie kazał to szerzej uzasadnić — dlaczego nie da się szybciej? Jednym zdaniem wystarczy, to jest dosyć oczywiste.
Ad 2.: Tak.
Ad 3.: Tutaj argumentacja, że nie da się szybciej zmodyfikować, jest już trochę trudniejsza, więc warto nad tym chwilę posiedzieć. Następnik i poprzednik nawet jeszcze bardziej. Maksimum dobrze.

Ale w każdym razie w kopcu binarnym poprawnie wartości zostały uzupełnione? Pomyślę wieczorkiem nad innym uzasadnieniem. Tymczasem mam kolejne rozwiązania.

1. Kopiec dwumianowy: Modyfikacja klucza to O(log n), żeby zmienić wartość należy znaleźć ją w kopcu, zdjąć, zmodyfikować i włożyć, prawdopodobnie do innego drzewa. W najgorszym wypadku trzeba będzie przelecieć przez kilkaset drzew. Następnik i poprzednik klucza to O(log n), wartość musimy najpierw znaleźć, tak samo jak w przypadku modyfikacji, trzeba będzie przelecieć przez kilkaset drzew. To chyba jeden z najbardziej nie opłacalnych algorytmów.
2. Kopiec Fibonacciego: Modyfikacja klucza to O(log n), ta sama zasada co w dwumianowym. Następnik i poprzednik to O(log n), tak samo co w dwumianowym. Maksimum to O(n), trzeba tylko przelecieć przez wszystkie drzewa i znaleźć.

Co ciekawe, z tego co się dowiedziałem to kopiec Fibonacciego to ten samo co dwumianowy, tyle że kopiec Fibonacciego wykorzystuje trochę inne wzory co do rozmiaru poddrzewa.

Te chyba były najtrudniejsze. Proszę o sprawdzenie.

Odświeżam wątek

Hej,

Szukałem tego dobre 3 dni, aż w końcu w notatkach u siebie na uczelni znalazłem coś takiego. Mam nadzieję, że pomoże :)

Pozdrawiam