kolejka złożoność

0

Witam,
mam takie zadanie i za cholere nie wiem jakie są prawidłowe odpowiedzi.

Implementujemy kolejkę. Jaką złożoność będą miały operacje dodania i usunięcia z kolejki, jeśli wykorzystamy do tego następujące struktury danych? (zauważ, że możemy użyć klucza numeru porządkowego wstawianego elementu oraz pamiętać numer pierwszego i ostatniego wstawionego elementu. Tablica hashowana ma optymalnie dobraną funkcję haszującą.

Operacja | Tablica | Hash Tab | Lista dwukierunkowa | Drzewo Binarne | Kopiec binarny MIN
Wstaw | | | | |
Usuń | | | | |

pytanie jest o pesymistyczną opcję.
Pomoże ktoś ?

0

A z czym konkretnie masz problem? Bo mam wrażenie że żebrzesz o gotowca...

0

@Shalom bo Wy tam, wysoko, to byście liczyli, a widać że chłopak ma problem, taką zagadkę można nawet powiedzieć.
I rozwiązanie jest banalne, mianowicie

pytanie jest o pesymistyczną opcję.

pesymistyczne opcje dla wszystkich struktur: **zadziałają **

/#szachmat #aterazdajciebana

0

Operacja | Tablica | Hash tablica | Lista dwukierunkowa | drzewo binarne | kopiec binarny MIN

Wstaw | O(1) | O(n) | O(1) | O(logn) | O(logn)

Usuń | O(1) | O(n) | O(n) | O(logn) | O(logn)

nie jestem pewien co do odpowiedzi.
czego nie wiem ?
np. tego czy jak wstawiam do tablicy (kolejki) w indeks 0, następnie wstawiam 2 element to czy muszę przesuwać element id[0] w "prawo" i tak dalej przez co rośnie złożoność obliczeniowa do O(n) czy źle myślę.

1
  1. To jest kolejka FIFO czy LIFO? Bo to sporo zmienia. Zakładam że mówimy tu o FIFO.
  2. Wstawianie na początek tablicy ma pesymistycznie O(n) bo musisz wszystko przesuwać albo przepisać do nowej lokalizacji przy realokacji pamięci.
  3. Z tablicą hashującą to jest trochę trudniejsza kwestia, bo czym jest pesymistyczny przypadek dla optymalnie dobranej funkcji hashującej? Pesymistycznie ładujemy wszystko pod ten sam indeks i mamy O(n), ale optymalna funkcja hashująca nie powinna dopuścic do takiej sytuacji i czas powinien być O(1).
  4. Usuwaine z hashmapy jest w czasie O(1) albo O(n) tak samo jak w punkcie powyżej. To zależy czy zakładamy że wszystko poleciało na ten sam hash czy nie.
  5. Usuwanie z końca listy to O(1) jeśli zakładamy że pamiętamy zarówno początek jak i koniec listy.
0

nie wiem czy istnieje kolejki LIFO, mówię tutaj o FIFO.
a w drzewach myślę dobrze czy nie bardzo ?

dzięki bardzo .

0

Jeśli to drzewo zrównoważone to O(logn) na szukanie elementu i O(logn) na równoważenie więc dodawanie i usuwanie masz w O(logn).

1 użytkowników online, w tym zalogowanych: 0, gości: 1