Połączona złożoność czasu

Istnieje pojedynczo powiązana lista i podwójnie powiązana lista. Istnieją inne powiązane typy listy, ale w tym artykule zajmują się tylko pojedyncze i podwójne typy.

Pojedynczo powiązana lista

Poniższy schemat pokazuje pojedynczo powiązaną listę trzech elementów:

Każdy element ma dwie części. Pierwsza część ma dane. Druga część ma wskaźnik, który wskazuje następny element. Drugi i trzeci elementy są podobne do pierwszego. Ostatni element ma zerowy wskaźnik. Z listą pojedynczo połączoną, Traversing może pójść tylko w jednym kierunku: kierunek do przodu.

Elementy połączonej listy nie są adresowane według referencji (indeksy w nawiasach kwadratowych), wszystko jest równe. Dostęp do nich iteratory (wskaźniki). W przypadku pojedynczo powiązanej listy iterator musi zacząć od początku i przejść od elementu po elemencie, aby dotrzeć do zamierzonego elementu.

Podwójnie połączona lista

Poniższy schemat pokazuje podwójnie połączoną listę trzech elementów:

Tutaj każdy element ma trzy części. Pierwsza część ma wskaźnik, który wskazuje na poprzedni element. Druga część ma dane. Trzecia część ma wskaźnik, który wskazuje następny element. Pierwsza część pierwszego elementu ma wskaźnik, który wskazuje na null. Trzecia część ostatniego elementu ma wskaźnik, który wskazuje na null. Z listą podwójnie połączoną, przejście może pójść w dowolnym kierunku: kierunek do przodu lub do tyłu.

Elementy linkowanej listy nie są adresowane przez referencje (indeksy w nawiasach kwadratowych). Dostęp do nich iteratory (wskaźniki). W przypadku podwójnie połączonej listy iterator może poruszać się w dowolnym kierunku, ale musi zacząć od obu stron. Ruch nie może rozpocząć oficjalnie z listy.

Celem tego artykułu jest określenie tego, co jest znane jako złożoność czasu dla powiązanej listy.

Złożoność czasu ogólnie

Złożoność czasu to względny czas wykonywania jakiegoś kodu. Złożoność czasu może być również postrzegana jako liczba głównych operacji kodu.

Stały czas

Mówi się, że jedna główna operacja, taka jak wstawka lub usunięcie. Jest napisane jako:
O (1)

gdzie 1 oznacza stały czas lub działanie występujące raz. Wykorzystuje to notację Big-O, która zaczyna się od O w górach, a następnie nawiasów. Wewnątrz nawiasów znajduje się liczba głównych operacji dla zadania.

Czas liniowy

Czytanie tablicy od początku- jeden element po drugim poszukiwaniu konkretnego elementu- jest określany jako wyszukiwanie liniowe.

Element szukany można znaleźć gdzieś na środku, a poszukiwanie się skończy. To wciąż jest wyszukiwanie liniowe. Złożoność czasu dla wyszukiwania liniowego jest napisana jako:
NA)

gdzie n jest maksymalną możliwą liczbą operacji.

Połączone listy główne operacje

Badawczy
W przypadku pojedynczo połączonej listy, aby przejść od jednego elementu do następnego, kod musi użyć wskaźnika bieżącego elementu, co wskazuje na następny element. Tak nie jest w przypadku tablic. Aby uzyskać podwójnie połączoną listę, aby przejść od jednego elementu do następnego, kod musi użyć wskaźnika bieżącego elementu, który wskazuje na następny element. Tak nie jest w przypadku tablic. Aby uzyskać podwójnie połączoną listę, aby przejść od jednego elementu do poprzedniego, kod musi użyć wskaźnika bieżącego elementu, który wskazuje na poprzedni element. Tak nie jest w przypadku tablic.

Usunięcie
Po usunięciu bieżącego elementu, wskaźnik poprzedniego elementu, który wskazywał na niego, musi zostać skierowany do następnego elementu. Następnie wskaźnik następnego elementu wskazywał na niego, aby wskazać poprzedni element.

Wprowadzenie
Po włożeniu bieżącego elementu, wskaźnik poprzedniego elementu, który wskazywał na następny element, musi zostać skierowany na bieżący element. Wskaźnik następnego elementu, który wskazywał na poprzedni element, musi zostać skierowany do bieżącego elementu.

Przedni wskaźnik bieżącego elementu musi zostać skierowany na nowy następny element. Tylna wskaźnik bieżącego elementu musi zostać wskazany na nowy poprzedni element.

Złożoność czasu dla połączonej listy

Mówiąc o złożoności czasu dla połączonej listy, to złożoność czasu w przypadku wyszukiwania, wstawienia i usuwania, o których mówi się. To nie jest złożoność czasu na budowanie powiązanej listy, o której mówi się. Złożoność czasu w budowaniu linkowanej listy to inny problem.

Badawczy
Aby pojedynczo połączona jest wyszukiwanie konkretnego elementu (danych), kod wyszukiwania musi skanować element listy według elementu- od początku. Aby podwójnie połączona lista wyszukała konkretny element, kod wyszukiwania musi zeskanować element listy według elementu- od początku. Lub zeskanuj listę, element według elementu, od końca. Złożoność czasu wyszukiwania połączonej listy (pojedynczo lub podwójnie) to:
NA)

gdzie n jest liczbą elementów na liście. Nie ma znaczenia, czy element został znaleziony, gdzieś na liście.

Wprowadzenie
Wstawienie jest uważane za jedną główną operację. Aby wstawić element na połączoną listę, wyszukiwanie musi odbyć się, aby osiągnąć pozycję, w celu wprowadzenia. Złożoność czasu wyszukiwania wynosi O (n). Złożoność czasu dla wkładania wynosi O (1). Tak więc złożoność czasu dla wstawienia na połączonej liście wynosi O (N + 1). Dla uproszczenia złożoność czasu w celu wstawienia elementu, do połączonej listy, jest napisana jako:
NA)

Usunięcie
Usunięcie jest uważane za jedną główną operację. Aby usunąć element na połączonej liście, wyszukiwanie musi mieć miejsce, aby osiągnąć pozycję do usunięcia. Złożoność czasu wyszukiwania wynosi O (n). Złożoność czasu dla działania usuwania jest O (1). Tak więc złożoność czasu do usunięcia na połączonej liście jest O (N + 1). Dla uproszczenia złożoność czasu dla usunięcia elementu, poza linkowaną listą, jest napisana jako:
NA)

Budowanie połączonej listy w C

Aby zbudować podwójnie połączoną listę w C, użyj obiektu struct. Pierwszy członek danych powinien mieć wskaźnik, który wskazuje na poprzednią strukturę. Trzeci członek danych powinien mieć wskaźnik, który wskazuje następną strukturę. Środkowy element danych powinien mieć dane. Pierwszy element danych pierwszego struktury powinien wskazać null. Trzeci członek danych ostatniej struktury powinien również wskazać null.

W przypadku pojedynczo połączonej listy pomiń pierwszego członka danych.

Wniosek

Złożoność czasu wyszukiwania listy powiązanej to:
NA)

Dla uproszczenia złożoność czasu dla wstawienia elementu do połączonej listy jest:
NA)
a nie o (1).

Dla uproszczenia złożoność czasu dla usunięcia elementu, poza połączoną listą, wynosi:
NA)
a nie o (1).