Leela Krishna
Leela Krishna

Følg

Apr 1, 2019 * 4 min læst

i hurtig programmeringssprog …

del -1:

hvorfor datastrukturer?

når man opretter moderne apps, overses meget af teorien, der er forbundet med algoritmer, ofte. For løsninger, der bruger relativt små mængder data, er beslutninger om specifikke teknikker eller designmønstre muligvis ikke vigtige som bare at få tingene til at fungere. Men som publikum vokser, så vil dataene. Meget af, hvad big tech virksomheder succes er arving evne til at fortolke store mængder data. At give mening om data giver brugerne mulighed for at oprette forbindelse, dele, gennemføre transaktioner og træffe beslutninger.

List Datastrukturer :

  • grundlæggende(elementære) datastrukturer

stak, kø, sorteringsalgoritmer

  • træer

træer& binære træer, binær søgning, bunke, bunke sortering, prioritetskø

  • grafer

grafer, adjacency list, Dijkstra ‘ s algoritme, Prims algoritme

kur Big O notation:

asymptotisk analyse er processen med at beskrive effektiviteten af algoritmer, og den udtrykkes almindeligvis i et fælles format kendt som Big O notation.

  • Tidskompleksitet :

mængden af tid til at fuldføre algoritmen(funktion) som dens input størrelse(n) vokser.

  • Rumkompleksitet :

den mængde hukommelse(plads), der er nødvendig for, at en algoritme (funktion) kan køre.

begge disse kan udtrykkes i stor O Notation.

  • mest almindelige Tidskompleksiteter :

→ konstant tid (O(1)) :-

en konstant tidsalgoritme er, som har den samme køretid uanset dens input. Den store O Notation for dette er O (1).

lodret lineær tid (O (n)) :-

en lineær tidsalgoritme er, hvor dens hastighed er afhængig af dens inputstørrelse. Med andre ord bliver det mindre effektivt, da dets inputstørrelse(n) vokser.

den kvadratiske tid (o (n2)) :-

det refererer til en algoritme, der tager tid til proportional med kvadratet af input størrelse. Det løber hurtigt ud af kontrol, da dens inputstørrelse øges.

den logaritmiske tid (o(log n)) :-

en fælles algoritme med o(log n) tidskompleksitet er binær søgning, hvis rekursive relation er T(n/2) + O(1) dvs.på hvert efterfølgende niveau af træet deler du problemet i halvdelen og udfører konstant mængde yderligere arbejde.

kvasilinær tid (o (n log n)) :-

en algoritme siges at køre i kvasilinær tid (også kaldet log-lineær tid) hvis T(n) = O(n log^k n) for en eller anden positiv konstant k; linearitmisk tid er tilfældet k = 1.

eksempel :

datastruktur er en systematisk måde at organisere data på for at bruge dem effektivt. Følgende udtryk er grundlaget for en datastruktur.

  • Interface − hver datastruktur har en grænseflade. Interface repræsenterer det sæt operationer, som en datastruktur understøtter. En grænseflade indeholder kun listen over understøttede operationer, typen af parametre, de kan acceptere og returnere typen af disse operationer.
  • implementering − implementering giver den interne repræsentation af en datastruktur. Implementering giver også definitionen af de algoritmer, der anvendes i datastrukturens operationer.

→ Karakteristik af en datastruktur :

  • korrekthed – implementering af datastruktur skal implementere dens grænseflade korrekt.
  • tidskompleksitet − køretid eller udførelsestiden for operationer af datastruktur skal være så lille som muligt.
  • Pladskompleksitet − hukommelsesforbrug af en datastrukturoperation skal være så lidt som muligt.

→ behov for datastruktur:

da applikationer bliver komplekse og datarige, er der tre almindelige problemer, som applikationer står over for nu om dage.

  1. datasøgning − overvej en opgørelse over 1 million(106) varer i en butik. Hvis applikationen skal søge efter et element, skal det søge efter et element i 1 million(106) elementer hver gang, der sænker søgningen. Efterhånden som data vokser, bliver søgningen langsommere.
  2. processorhastighed − processorhastighed selvom den er meget høj, falder den begrænset, hvis dataene vokser til milliarder poster.
  3. flere anmodninger − da tusindvis af brugere kan søge data samtidigt på en internetserver, fejler selv den hurtige server, mens de søger dataene.

for at løse de ovennævnte problemer kommer datastrukturer til undsætning. Data kan organiseres i en datastruktur på en sådan måde, at alle elementer muligvis ikke skal søges, og de krævede data kan søges næsten øjeblikkeligt.

lad os se en Stakindpakning i hurtig:

vi opretter en indpakning omkring hurtigens array, hvor vi bruger arrayet som en lagringsstruktur. Arrays giver konstant tid (O(1)) indsættelser og sletninger, når de udføres fra slutningen af arrayet.

det er FIFO først i først ud Data.

eksempler i iOS : UINavigation stak, Fortryd funktionaliteter, etc.

Skriv et svar

Din e-mailadresse vil ikke blive publiceret.