Te dwa wydają się bardzo podobne i mają prawie identyczną strukturę. Co za różnica? Jakie są zawiłości czasowe dla różnych operacji każdego z
Ile różnych maksymalnych stert istnieje dla listy nnn liczb całkowitych? Przykład: lista [1, 2, 3, 4] Maksymalna kupa może być 4 3 2 1: 4 / \ 3 2 / 1 lub 4 2 3 1: 4 / \ 2 3
W wielu dyskusjach na temat sterty binarnej zwykle tylko klawisz zmniejszania jest wymieniony jako obsługiwana operacja dla sterty min. Na przykład rozdział 6.1 CLR i ta strona Wikipedii . Dlaczego zwykle nie jest wyświetlany klucz zwiększenia dla min-sterty? Wyobrażam sobie, że można to zrobić w O...
Najprawdopodobniej pytanie to zostało zadane wcześniej. Pochodzi z problemu CLRS (2nd Ed) 6.5-8 - Podaj algorytm czasu O(nlgk)O(nlgk)O(n \lg k) , aby połączyć kkk sortowanych list w jedną posortowaną listę, gdzie nnn jest całkowitą liczbą elementów na wszystkich listach wejściowych. (Wskazówka:...
Potrzebuję pomocy w określeniu funkcji potencjalnej dla stosu maksymalnego, aby wyciąg maksymalny został zakończony w czasie zamortyzowanym . Powinienem dodać, że nie rozumiem potencjalnie tej metody.O ( 1 )O(1)O(1) Wiem, że funkcja wstawiania powinna „płacić” więcej, aby zmniejszyć koszt...
Randomizowane zgrzewalne stosy mają operację „łączenie”, której następnie używamy do zdefiniowania wszystkich innych operacji, w tym wstawiania. Pytanie brzmi: jaka jest oczekiwana wysokość tego drzewa nnn węzły? Twierdzenie 1 Gambina i Malinkowskiego, Randomized Meldable Priority Queues...