Leela Krishna
Leela Krishna

Follow

Apr 1, 2019 · 4 min czytać

w języku programowania swift …

część -1:

dlaczego struktury danych?

podczas tworzenia nowoczesnych aplikacji często pomija się wiele teorii związanych z algorytmami. W przypadku rozwiązań, które zużywają stosunkowo małe ilości danych, decyzje dotyczące konkretnych technik lub wzorców projektowych mogą nie być ważne, jak tylko doprowadzenie rzeczy do działania. Jednak wraz ze wzrostem liczby odbiorców dane będą rosły. Wiele z tego, co duże firmy technologiczne odnoszą sukcesy, to zdolność do interpretacji ogromnych ilości danych. Zrozumienie danych pozwala użytkownikom łączyć się, udostępniać, realizować transakcje i podejmować decyzje.

→ Struktury Danych :

  • podstawowe(elementarne) struktury danych

stosy, kolejki, algorytmy sortowania

  • drzewa

drzewa & drzewa binarne, Wyszukiwanie binarne, sterta, sortowanie sterty, Kolejka priorytetów

  • wykresy

wykresy, lista Adjacencji, algorytm Dijkstry, algorytm prima

→ notacja Big O :

Analiza asymptotyczna jest procesem opisywania wydajności algorytmów i jest zwykle wyrażana we wspólnym formacie znanym jako notacja Big O.

  • Złożoność Czasowa :

Ilość czasu na ukończenie algorytmu(funkcji) wraz ze wzrostem jego wielkości wejściowej(n).

  • złożoność przestrzeni :

Ilość pamięci(miejsca) potrzebna do uruchomienia algorytmu (funkcji).

obie te wartości można wyrazić w notacji Big O.

  • najczęstsze zawiłości czasowe:

→ czas stały (O(1)) :-

algorytm czasu stałego jest taki sam, niezależnie od jego wejścia. Duży zapis O to jest O (1).

→ czas liniowy (O (n)) :-

algorytm czasu liniowego polega na tym, że jego prędkość zależy od jego wielkości wejściowej. Innymi słowy, staje się mniej wydajny w miarę wzrostu jego wielkości wejściowej(n).

→ czas kwadratowy (O (n2)) :-

odnosi się do algorytmu, który wymaga czasu do proporcjonalnego do kwadratu wielkości wejściowej. Szybko wymyka się spod kontroli, gdy zwiększa się jego rozmiar wejściowy.

→ czas logarytmiczny (o (log N)) :-

wspólnym algorytmem o (log N) złożoności czasowej jest Wyszukiwanie binarne, którego relacja rekurencyjna to T (n/2) + O (1) tzn. na każdym kolejnym poziomie drzewa dzielisz problem na pół i wykonujesz stałą ilość dodatkowej pracy.

→ czas Quasilinear (o (n log N)) :-

mówi się, że algorytm działa w czasie quasilinearnym (zwanym również czasem log-liniowym), jeśli T(N) = O(N log^k n) dla pewnej dodatniej stałej K; czas liniowy to przypadek k = 1.

przykład :

Struktura danych to systematyczny sposób organizowania danych w celu ich efektywnego wykorzystania. Poniższe warunki są podstawowymi warunkami struktury danych.

  • interfejs − każda struktura danych ma interfejs. Interfejs reprezentuje zestaw operacji obsługiwanych przez strukturę danych. Interfejs dostarcza tylko listę obsługiwanych operacji, Typ parametrów, które mogą zaakceptować i typ zwracania tych operacji.
  • implementacja-implementacja zapewnia wewnętrzną reprezentację struktury danych. Implementacja dostarcza również definicji algorytmów wykorzystywanych w operacjach struktury danych.

→ charakterystyka struktury danych:

  • poprawność-implementacja struktury danych powinna poprawnie implementować swój interfejs.
  • złożoność czasowa − czas trwania lub czas wykonania operacji struktury danych musi być jak najmniejszy.
  • złożoność przestrzeni − wykorzystanie pamięci operacji struktury danych powinno być jak najmniejsze.

→ potrzeba struktury danych:

ponieważ aplikacje stają się coraz bardziej złożone i bogate w dane, istnieją trzy typowe problemy, z którymi borykają się teraz aplikacje.

  1. wyszukiwanie danych-weź pod uwagę zapasy 1 miliona(106) pozycji sklepu. Jeśli aplikacja ma przeszukiwać dany artykuł, musi przeszukiwać go w 1 milionie(106) elementów za każdym razem, gdy wyszukiwanie spowalnia. Wraz ze wzrostem ilości danych wyszukiwanie będzie wolniejsze.
  2. procesor Speed − Prędkość procesora, choć jest bardzo wysoka, spada ograniczona, jeśli dane rosną do miliardów rekordów.
  3. wiele żądań-ponieważ tysiące użytkowników może przeszukiwać dane jednocześnie na serwerze WWW, nawet szybki serwer nie działa podczas przeszukiwania danych.

aby rozwiązać wyżej wymienione problemy, na ratunek przychodzą struktury danych. Dane mogą być zorganizowane w strukturę danych w taki sposób, że wszystkie elementy nie muszą być przeszukiwane, a wymagane dane mogą być przeszukiwane niemal natychmiast.

→ zobaczmy wrapper stosu w języku swift:

tworzymy wrapper wokół tablicy Swifta, gdzie używamy tablicy jako struktury pamięci masowej. Tablice dają stałe wstawianie i usuwanie w czasie (O(1)), gdy są wykonywane od końca tablicy.

jest to FIFO → pierwsze w pierwszym wyjściu danych.

przykłady w iOS : Stos UINavigation, funkcje cofania itp.

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany.