95924

95924



Dostęp do elementu: jeżeli element jest umieszczony na końcu listy, to aby do niego dotrzeć, trzeba przejrzeć wszystkie pozostałe n-1 elementów - O(n).

Wyszukanie:

Wyszukanie elementu: jak wyżej _ O(n).

Wstawienie:

Wstawienie elementu: należy utworzyć nową komórkę 0(1), wypełnić wartość pola danych 0(1), pole wskaŁnika wypełnić wartością głowy 0(1), a wartość głowy wypełnić wartością wskazującą na nowy element 0(1) _ całkowity czas omawianej operacji wynosi zatem 0(1).

Usunięcie:

Usunięcie elementu: wartość wska1nika elementu poprzedzającego należy wypełnić wartością wskazującą na element następny 0(n) (trzeba ten wska-Anik znale1ć!) i usunąć z pamięci dany element 0(1) _ 0(n).

Lista dwukierunkowa Budowa:

każdy element, oprócz wartości i wska1nika na następny element zawiera też wskaAnik na element poprzedzający , a oprócz głowy zawiera też (choć nie jest to konieczne) tzw. ogon, czyli wskaxnik na ostatni element struktury.

Złożoność obliczeniowa Wyszukanie:

skraca operacje wyszukiwania elementu w najgorszym wypadku o połowę , jednak z punktu widzenia efektywności to nadal jest złożoność tego samego rzędu (0(n/2) = 0(n)).

Wstawienie:

Skraca w najgorszym wypadku o połowę , jednak z punktu widzenia efektywności to nadal jest złożoność tego samego rzędu (0(n/2) = O(n)).

Usunięcie:

Skraca w najgorszym wypadku o połowę , jednak z punktu widzenia efektywności to nadal jest złożoność tego samego rzędu (0(n/2) = 0(n)).

Lista cykliczna Budowa:

wskaźnik ostatniego elementu wskazuje na pierwszy element Złożoność obliczeniowa

jak wyżej

Lista samoorganizująca się Opis:

elementy w strukturze są uporządkowane niemalejąco lub nierosnąco (względem wartości pól danych).

Cechy charakterystyczne:

Korzyści pojawiają się w niektórych szczególnych sytuacjach (gdy np. interesuj ąnas głównie maksymalne / minimalne elementy).

Złożoność obliczeniowa Wstawienie:



Wyszukiwarka

Podobne podstrony:
92 (70) CHARAKTERYSTYKA OGÓLNA Rozdzielacz zapłonu silnika 1,6 jest umieszczony na końcu wału rozrzą
139 jamach ? treścią pytanie jest umieszczone na końcu historyjki. Zanim dziecko ".„lituje 5ię
Tw. 5 (Weie rstr assa): Jeżeli funkcja f jest ciągła na przedziale domkniętym <a; b> to 1"
19 Funkcje zespolone. Twierdzenie 4.2. Jeżeli funkcja f jest ciągła na krzywej gładkiej C, to I f(z)
Jeżeli książka jest tłumaczeniem, na końcu notki w nawiasie dodajemy informacje o tłumaczach: Guilfo
Elementy układu zasilaniaSterownik pompy paliwa J538 Sterownik jest umieszczony na pokrywie elektryc
Wybierz dwa spośród elementów graficznych umieszczonych na torbie. Dla każdego z nich: •
img249 2 22 Część I. Wprowadzenie do ekonomii 7. Jeżeli cenowa elastyczność popytu na dobro EcP = -0
skanuj0032 (36) 98 98 li Jeżeli ktoś jest przemądrzały albo zanadto krytyczny, to psuje zabawę”. W s
KALIGRAFIA MAŁYCH LITER I CYFR (12) V Drobne elementy liter dopisuj na końcu. mż£i& RE
KALIGRAFIA WIELKICH LITER (07) Drobne elementy liter dopisuj na końcu.
W rezystorach warstwowych materiał rezystywny jest umieszczony na podłożu w postaci warstwy. Rezysto
Sposób podłączania oscyloskopu do źródła napięcia jest przedstawiony na rys 3. Można to zrobić przy
z4b 11.    Sekcja finałły umieszczana na końcu obsługi wyjątków: a)    
1. Wstęp. Ze względu na dostępność literatury projekt ten omówiony jest jedynie na podstawie szaty
Slajd23 System GLOBALSTAR 56 satelitów systemu Globalstar jest umieszczonych na niskiej orbicie geos

więcej podobnych podstron