Leela Krishna
Leela Krishna

Suivre

1 Avril 2019 * 4 min de lecture

dans le langage de programmation swiftPart

Partie -1:

Pourquoi les Structures de Données ?

Lors de la création d’applications modernes, une grande partie de la théorie inhérente aux algorithmes est souvent négligée. Pour les solutions qui consomment des quantités relativement faibles de données, les décisions concernant des techniques ou des modèles de conception spécifiques peuvent ne pas être importantes, car il suffit de faire fonctionner les choses. Cependant, à mesure que l’audience augmente, les données le seront également. Une grande partie du succès des grandes entreprises technologiques est leur capacité à interpréter de grandes quantités de données. Donner un sens aux données permet aux utilisateurs de se connecter, de partager, d’effectuer des transactions et de prendre des décisions.

→ Structures de données :

  • Structures de données fondamentales (Élémentaires)

Pile, File d’attente, Algorithmes de Tri

  • Arbres

Arbres & Arbres Binaires, Recherche Binaire, Tas, Tri de Tas, File d’Attente Prioritaire

  • Graphiques

Graphes, Liste d’adjacence, Algorithme de Dijkstra, Algorithme de Prim

→ Notation Big O:

L’analyse asymptotique est le processus de description de l’efficacité des algorithmes, et elle est couramment exprimée dans un format commun connu sous le nom de Notation Big O.

  • Complexité temporelle :

Le temps nécessaire pour terminer l’algorithme (fonction) au fur et à mesure que sa taille d’entrée (n) augmente.

  • Complexité de l’espace :

La quantité de mémoire (espace) nécessaire à l’exécution d’un algorithme (fonction).

Les deux peuvent être exprimés en notation Grand O.

  • Complexités Temporelles Les Plus Courantes :

→ Temps constant (O(1)) :-

Un algorithme à temps constant est celui qui a le même temps d’exécution quelle que soit son entrée. La notation Big O pour cela est O(1).

→ Temps linéaire (O(n)) :-

Un algorithme de temps linéaire est dont la vitesse dépend de sa taille d’entrée. En d’autres termes, il devient moins efficace à mesure que sa taille d’entrée (n) augmente.

→ Temps quadratique (O(n2)) :-

il fait référence à un algorithme qui prend du temps à la proportionnelle au carré de la taille d’entrée. Il est rapidement hors de contrôle à mesure que sa taille d’entrée augmente.

→ Temps logarithmique (O(log n)) :-

Un algorithme commun avec une complexité temporelle O (log n) est la recherche binaire dont la relation récursive est T (n / 2) + O(1), c’est-à-dire qu’à chaque niveau suivant de l’arbre, vous divisez le problème en deux et effectuez une quantité constante de travail supplémentaire.

→ Temps quasilinéaire (O(n log n)) :-

Un algorithme est dit exécuté en temps quasi-linéaire (également appelé temps log-linéaire) si T(n) = O(n log^k n) pour une constante positive k ; le temps linéarithmique est le cas k = 1.

Exemple :

La structure des données est un moyen systématique d’organiser les données afin de les utiliser efficacement. Les termes suivants sont les termes de base d’une structure de données.

  • Interface – Chaque structure de données a une interface. L’interface représente l’ensemble des opérations prises en charge par une structure de données. Une interface fournit uniquement la liste des opérations prises en charge, le type de paramètres qu’elles peuvent accepter et le type de retour de ces opérations.
  • Implémentation – L’implémentation fournit la représentation interne d’une structure de données. La mise en œuvre fournit également la définition des algorithmes utilisés dans les opérations de la structure de données.

→ Caractéristiques d’une Structure de Données :

  • Correction – L’implémentation de la structure de données doit implémenter correctement son interface.
  • Complexité temporelle – Le temps d’exécution ou le temps d’exécution des opérations de la structure de données doit être aussi petit que possible.
  • Complexité de l’espace − L’utilisation de la mémoire d’une opération de structure de données doit être aussi faible que possible.

→ Besoin de structure de données:

Les applications devenant complexes et riches en données, il existe trois problèmes courants auxquels les applications sont confrontées de nos jours.

  1. Recherche de données – Considérez un inventaire de 1 million (106) d’articles d’un magasin. Si l’application doit rechercher un élément, elle doit rechercher un élément dans 1 million (106) d’éléments à chaque fois en ralentissant la recherche. À mesure que les données augmentent, la recherche devient plus lente.
  2. Vitesse du processeur – La vitesse du processeur, bien que très élevée, tombe limitée si les données atteignent un milliard d’enregistrements.
  3. Requêtes multiples – Comme des milliers d’utilisateurs peuvent rechercher des données simultanément sur un serveur Web, même le serveur rapide échoue lors de la recherche des données.

Pour résoudre les problèmes mentionnés ci-dessus, des structures de données viennent à la rescousse. Les données peuvent être organisées dans une structure de données de telle sorte que tous les éléments ne doivent pas être recherchés et que les données requises peuvent être recherchées presque instantanément.

→ Voyons un wrapper de pile dans swift:

Nous créons un wrapper autour du tableau du swift, où nous utilisons le tableau comme structure de stockage. Les tableaux donnent des insertions et des suppressions à temps constant (O(1)) lorsqu’elles sont effectuées à partir de la fin du tableau.

Il s’agit de données FIFO → Premier entré, Premier Sorti.

Exemples dans iOS : Pile d’UINavigation, fonctionnalités d’annulation, etc.

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée.