Leela Krishna
Leela Krishna

Seguire

Apr 1, 2019 · 4 min leggere

in swift linguaggio di programmazione…

Parte -1:

Perché le Strutture di Dati?

Quando si creano app moderne, gran parte della teoria inerente agli algoritmi viene spesso trascurata. Per le soluzioni che consumano quantità relativamente piccole di dati, le decisioni su tecniche specifiche o modelli di progettazione potrebbero non essere importanti come solo far funzionare le cose. Tuttavia, come pubblico cresce così sarà i dati. Gran parte di ciò che le grandi aziende tecnologiche di successo è erede capacità di interpretare grandi quantità di dati. Dare un senso ai dati consente agli utenti di connettersi, condividere, completare le transazioni e prendere decisioni.

→ Strutture dati :

  • Fondamentali(Elementare) strutture di dati

Pila, Coda, Algoritmi di Ordinamento

  • Alberi

Alberi & Alberi Binari, Binari di Ricerca, Heap Heap Sort, Coda a Priorità

  • Grafici

Grafici, Adiacenza Elenco, l’Algoritmo di Dijkstra, L’Algoritmo di Prim

→ Notazione O Grande :

Asintotica analisi è il processo di descrivere l’efficienza degli algoritmi, e è comunemente espressa in un formato comune, noto come Notazione O Grande.

  • Complessità temporale :

La quantità di tempo per completare l’algoritmo (funzione) man mano che la sua dimensione di input(n) cresce.

  • Complessità dello spazio:

La quantità di memoria (spazio) necessaria per l’esecuzione di un algoritmo(funzione).

Entrambi possono essere espressi in notazione Big O.

  • Complessità temporali più comuni:

→ Tempo costante (O(1)) :-

Un algoritmo a tempo costante è che ha lo stesso tempo di esecuzione indipendentemente dal suo input. La grande notazione O per questo è O(1).

→ Tempo lineare (O (n)) :-

Un algoritmo di tempo lineare è che la sua velocità dipende dalla sua dimensione di input. In altre parole diventa meno efficiente man mano che la sua dimensione di input(n) cresce.

→ Tempo quadratico (O (n2)) :-

si riferisce a un algoritmo che richiede tempo al proporzionale al quadrato della dimensione di input. Si esaurisce rapidamente il controllo come la sua dimensione di ingresso aumenta.

→ Tempo logaritmico (O(log n)) :-

Un algoritmo comune con complessità temporale O(log n) è la ricerca binaria la cui relazione ricorsiva è T(n/2) + O(1) cioè ad ogni livello successivo dell’albero si divide il problema a metà e si esegue una quantità costante di lavoro aggiuntivo.

→ Tempo quasilineare (O (n log n)) :-

Si dice che un algoritmo funzioni in tempo quasilineare(noto anche come tempo log-lineare) se T(n) = O (n log^k n) per qualche costante positiva k; il tempo linearitmico è il caso k = 1.

Esempio :

La struttura dei dati è un modo sistematico per organizzare i dati al fine di utilizzarli in modo efficiente. I seguenti termini sono i termini di base di una struttura di dati.

  • Interfaccia-Ogni struttura dati ha un’interfaccia. L’interfaccia rappresenta l’insieme di operazioni supportate da una struttura dati. Un’interfaccia fornisce solo l’elenco delle operazioni supportate, il tipo di parametri che possono accettare e il tipo di ritorno di queste operazioni.
  • Implementazione-Implementazione fornisce la rappresentazione interna di una struttura dati. L’implementazione fornisce anche la definizione degli algoritmi utilizzati nelle operazioni della struttura dati.

→ Caratteristiche di una struttura dati:

  • Correttezza-L’implementazione della struttura dei dati dovrebbe implementare correttamente la sua interfaccia.
  • Complessità temporale: il tempo di esecuzione o il tempo di esecuzione delle operazioni della struttura dati deve essere il più piccolo possibile.
  • Complessità dello spazio: l’utilizzo della memoria di un’operazione di struttura dati dovrebbe essere il meno possibile.

→ Necessità di struttura dati:

Poiché le applicazioni diventano complesse e ricche di dati, ci sono tre problemi comuni che le applicazioni affrontano ora al giorno.

  1. Ricerca dati: considera un inventario di 1 milione(106) articoli di un negozio. Se l’applicazione deve cercare un elemento, deve cercare un elemento in 1 milione(106) elementi ogni volta che rallenta la ricerca. Man mano che i dati crescono, la ricerca diventerà più lenta.
  2. Velocità del processore – Velocità del processore pur essendo molto alta, cade limitata se i dati cresce a miliardi di record.
  3. Richieste multiple – Come migliaia di utenti possono cercare i dati contemporaneamente su un server web, anche il server veloce non riesce durante la ricerca dei dati.

Per risolvere i problemi sopra menzionati, le strutture dati vengono in soccorso. I dati possono essere organizzati in una struttura dati in modo tale che non sia necessario cercare tutti gli elementi e che i dati richiesti possano essere cercati quasi istantaneamente.

→ Vediamo un wrapper di stack in swift :

Creiamo un wrapper attorno all’array di swift, dove usiamo l’array come struttura di archiviazione. Gli array forniscono inserimenti e cancellazioni a tempo costante (O(1)) quando vengono eseguite dalla fine dell’array.

È FIFO → First In First Out Data.

Esempi in iOS : Stack di UINavigation, funzionalità di annullamento, ecc.

Lascia un commento

Il tuo indirizzo email non sarà pubblicato.