Leela Krishna
Leela Krishna

urmează

Apr 1, 2019 * 4 min citit

în limbajul de programare swift…

parte -1:

de ce structuri de date?

când se creează aplicații moderne, o mare parte din teoria inerentă algoritmilor este adesea trecută cu vederea. Pentru soluțiile care consumă cantități relativ mici de date, deciziile cu privire la tehnici specifice sau modele de proiectare pot să nu fie importante, deoarece doar lucrurile funcționează. Cu toate acestea, pe măsură ce audiența crește, datele vor crește. O mare parte din ceea ce companiile mari de tehnologie au succes este capacitatea moștenitorului de a interpreta cantități mari de date. Înțelegerea datelor permite utilizatorilor să se conecteze, să partajeze, să finalizeze tranzacții și să ia decizii.

Structuri De Date De La Articolul :

  • structuri de date fundamentale(elementare)

stivă, Coadă, algoritmi de sortare

  • copaci

copaci& arbori binari, Căutare binară, grămadă, Sortare grămadă, Coadă prioritară

  • grafice

grafice, Lista de adiacență, algoritmul lui Dijkstra, algoritmul lui prim

notație o mare:

analiza asimptotică este procesul de descriere a eficienței algoritmilor și este exprimat în mod obișnuit într-un format comun cunoscut sub numele de notație o mare.

  • Complexitatea Timpului :

cantitatea de timp pentru a finaliza algoritmul(funcția) ca dimensiunea sa de intrare(n) crește.

  • complexitatea spațiului :

cantitatea de memorie(spațiu) necesare pentru un algoritm (funcție) pentru a rula.

ambele pot fi exprimate în notație o mare.

  • cele mai frecvente complexități de timp :

→ timp Constant (O(1)) :-

un algoritm de timp constant este care are același timp de funcționare, indiferent de intrarea sa. Notația o mare pentru aceasta este O (1).

timp liniar (o(n)) :-

un algoritm de timp liniar este viteza sa care depinde de dimensiunea sa de intrare. Cu alte cuvinte, devine mai puțin eficient pe măsură ce dimensiunea sa de intrare(n) crește.

timp pătratic (o(N2)) :-

se referă la un algoritm care necesită timp până la proporțional cu pătratul dimensiunii de intrare. Se execută rapid de sub control ca dimensiunea sa de intrare crește.

timp logaritmic (o(log n)) :-

un algoritm comun cu o(log n) complexitatea timpului este căutarea binară a cărei relație recursivă este T(N/2) + O(1) adică la fiecare nivel ulterior al arborelui împărțiți problema în jumătate și faceți o cantitate constantă de muncă suplimentară.

timp cvasiliniar (o (n log n)) :-

se spune că un algoritm rulează în timp cvasiliniar(denumit și timp log-liniar) dacă T(n) = o(n log^k n) pentru o constantă pozitivă k; timpul liniaritmic este cazul k = 1.

exemplu :

structura datelor este o modalitate sistematică de a organiza datele pentru a le utiliza eficient. Următorii termeni sunt termenii de bază ai unei structuri de date.

  • Interfață − fiecare structură de date are o interfață. Interfața reprezintă setul de operații pe care o structură de date acceptă. O interfață oferă doar lista operațiunilor acceptate, tipul de parametri pe care îi pot accepta și tipul de returnare a acestor operațiuni.
  • implementare − implementarea oferă reprezentarea internă a unei structuri de date. Implementarea oferă, de asemenea, definirea algoritmilor utilizați în operațiunile structurii de date.

→ caracteristicile unei structuri de date:

  • corectitudine − implementarea structurii datelor ar trebui să implementeze corect interfața sa.
  • complexitatea timpului − timpul de funcționare sau timpul de execuție a operațiilor structurii de date trebuie să fie cât mai mic posibil.
  • complexitatea spațiului − utilizarea memoriei unei operații de structură de date ar trebui să fie cât mai mică posibil.

→ necesitatea structurii datelor:

deoarece aplicațiile devin complexe și bogate în date, există trei probleme comune cu care se confruntă aplicațiile acum.

  1. căutare Date − luați în considerare un inventar de 1 milion(106) articole ale unui magazin. În cazul în care cererea este de a căuta un element, trebuie să caute un element în 1 milion(106) elemente de fiecare dată încetinind căutarea. Pe măsură ce datele cresc, căutarea va deveni mai lentă.
  2. viteza procesorului − viteza procesorului, deși este foarte mare, scade limitată dacă datele cresc la miliarde de înregistrări.
  3. cereri Multiple − deoarece mii de utilizatori pot căuta date simultan pe un server web, chiar și serverul rapid eșuează în timp ce caută datele.

pentru a rezolva problemele menționate mai sus, structurile de date vin să salveze. Datele pot fi organizate într-o structură de date în așa fel încât toate elementele să nu fie necesare pentru a fi căutate, iar datele necesare pot fi căutate aproape instantaneu.

XV să vedem un înveliș de stivă în swift:

creăm un înveliș în jurul matricei swift, unde folosim matricea ca structură de stocare. Matricele oferă timp constant (o(1)) inserții și ștergeri atunci când sunt efectuate de la sfârșitul matricei.

este FIFO pentru prima dată în prima dată.

exemple în iOS : Uinavigation stivă, Anulează funcționalități, etc.

Lasă un răspuns

Adresa ta de email nu va fi publicată.