Leela Krishna
Leela Krishna

Volg

Apr 1, 2019 · 4 min lezen

in snelle programmeertaal…

Deel -1:

Waarom de structuur van de Gegevens?

bij het maken van moderne apps wordt veel van de theorie die inherent is aan algoritmen vaak over het hoofd gezien. Voor oplossingen die relatief kleine hoeveelheden gegevens verbruiken, kunnen beslissingen over specifieke technieken of ontwerppatronen niet belangrijk zijn als gewoon dingen aan het werk krijgen. Maar naarmate het publiek groeit, zullen de gegevens groeien. Veel van wat grote tech bedrijven succesvol is erfgenaam vermogen om grote hoeveelheden data te interpreteren. Het maken van zin van gegevens stelt gebruikers in staat om verbinding te maken, te delen, transacties te voltooien, en beslissingen te nemen.

→ Datastructuren :

  • Fundamentele(Basis -) gegevens structuren

Stack, Queue, Sorteer-Algoritmen

  • Bomen

Bomen & Binaire Bomen, Binair Zoeken, Heap Heap Sort, Priority Queue

  • Grafieken

Grafieken, Adjacency Lijst, Dijkstra ‘ s Algoritme, Prim ‘ s Algoritme

→ Big-O-Notatie :

Asymptotische analyse is het proces van het beschrijven van de efficiëntie van algoritmen, en het is vaak uitgedrukt in een gemeenschappelijke indeling bekend als Big-O-Notatie.

  • Tijdscomplexiteit :

de tijd die nodig is om het algoritme(functie) te voltooien naarmate de invoergrootte(n) groter wordt.

  • complexiteit van de ruimte:

de hoeveelheid geheugen (ruimte) die nodig is voor het uitvoeren van een algoritme(functie).

beide kunnen worden uitgedrukt in Big O-notatie.

  • meest voorkomende tijd complexiteiten :

→ constante tijd (O(1)) :-

een constante tijd algoritme is die dezelfde looptijd heeft, ongeacht de invoer. De grote O-notatie hiervoor is O (1).

→ lineaire tijd (O (n)) :-

een lineair tijdalgoritme is waarvan de snelheid afhankelijk is van de invoergrootte. Met andere woorden, het wordt minder efficiënt naarmate de invoergrootte(n) groeit.

→ kwadratische tijd (O (n2)) :-

het verwijst naar een algoritme dat tijd kost om de proportionele aan het kwadraat van de invoergrootte. Het loopt snel uit de hand als de invoergrootte toeneemt.

→ logaritmische tijd (o(log n)) :-

een gemeenschappelijk algoritme met o(log n) tijdcomplexiteit is binaire zoekopdracht waarvan de recursieve relatie T(n/2) + O(1) is, d.w.z. op elk volgend niveau van de boom verdeelt u probleem in de helft en doet u constante hoeveelheid extra werk.

→ Quasilineaire tijd (o (n log n)) :-

van een algoritme wordt gezegd dat het in quasilineaire tijd (ook wel log-lineaire tijd genoemd) draait als T(N) = o(n log^K n) voor enige positieve constante k; linearitmische tijd is het geval k = 1.

voorbeeld :

datastructuur is een systematische manier om gegevens te organiseren om ze efficiënt te gebruiken. De volgende voorwaarden zijn de basisvoorwaarden van een gegevensstructuur.

  • Interface-elke gegevensstructuur heeft een interface. Interface vertegenwoordigt de reeks bewerkingen die een gegevensstructuur ondersteunt. Een interface biedt alleen de lijst van ondersteunde operaties, het type parameters dat ze kunnen accepteren en het type retourneren van deze operaties.
  • implementatie-implementatie biedt de interne weergave van een gegevensstructuur. Implementatie biedt ook de definitie van de algoritmen die worden gebruikt in de operaties van de gegevensstructuur.

→ kenmerken van een gegevensstructuur :

  • correctheid-de implementatie van de gegevensstructuur moet de interface correct implementeren.
  • tijdscomplexiteit-de looptijd of de uitvoeringstijd van bewerkingen van de gegevensstructuur moet zo klein mogelijk zijn.
  • Ruimtecomplexiteit-geheugengebruik van een datastructuuroperatie moet zo weinig mogelijk zijn.

→ behoefte aan gegevensstructuur:

aangezien toepassingen complex en gegevensrijk worden, zijn er drie veel voorkomende problemen waarmee toepassingen nu-a-days worden geconfronteerd.

  1. zoeken naar gegevens-overweeg een inventaris van 1 miljoen(106) items van een winkel. Als de toepassing is om een item te zoeken, moet het zoeken naar een item in 1 miljoen(106) items elke keer vertragen het zoeken. Naarmate de gegevens groeien, zal het zoeken langzamer worden.
  2. processorsnelheid-processorsnelheid hoewel zeer hoog, daalt beperkt als de gegevens groeien tot miljard records.
  3. meerdere verzoeken – omdat duizenden gebruikers tegelijkertijd gegevens kunnen zoeken op een webserver, mislukt zelfs de snelle server tijdens het zoeken naar de gegevens.

om bovengenoemde problemen op te lossen, komen gegevensstructuren te hulp. Gegevens kunnen zo in een gegevensstructuur worden georganiseerd dat niet alle items hoeven te worden doorzocht en dat de benodigde gegevens vrijwel direct kunnen worden doorzocht.

→ laten we een stapel wrapper in swift bekijken :

we maken een wrapper rond de array van swift, waar we de array gebruiken als een opslagstructuur. Arrays geven constante tijd(O (1)) inserties en deleties wanneer ze worden uitgevoerd vanaf het einde van de array.

het is FIFO → First In First Out Data.

voorbeelden in iOS : UINavigation Stack, Undo functionaliteiten, enz.

Geef een antwoord

Het e-mailadres wordt niet gepubliceerd.