Structures de données et algorithmes - Présentation

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 fondamentaux 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.

  • Implementation- La mise en œuvre 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

  • Correctness - L'implémentation de la structure de données doit implémenter correctement son interface.

  • Time Complexity - Le temps de fonctionnement ou le temps d'exécution des opérations de structure de données doit être le plus petit possible.

  • Space Complexity - 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

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

  • Data Search- Considérez un inventaire de 1 million (10 6 ) articles d'un magasin. Si l'application cherche à rechercher un élément, elle doit rechercher un élément dans 1 million (10 6 ) éléments à chaque fois, ce qui ralentit la recherche. À mesure que les données augmentent, la recherche deviendra plus lente.

  • Processor speed - La vitesse du processeur, bien qu'étant très élevée, est limitée si les données atteignent des milliards d'enregistrements.

  • Multiple requests - 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, les structures de données viennent à la rescousse. Les données peuvent être organisées dans une structure de données de telle sorte qu'il ne soit pas nécessaire de rechercher tous les éléments, et les données requises peuvent être recherchées presque instantanément.

Cas de temps d'exécution

Il existe trois cas qui sont généralement utilisés pour comparer le temps d'exécution de diverses structures de données de manière relative.

  • Worst Case- Il s'agit du scénario dans lequel une opération de structure de données particulière prend le plus de temps possible. Si le pire des cas d'une opération est ƒ (n) alors cette opération ne prendra pas plus de ƒ (n) temps où ƒ (n) représente la fonction de n.

  • Average Case- Il s'agit du scénario représentant le temps d'exécution moyen d'une opération d'une structure de données. Si une opération prend ƒ (n) temps d'exécution, alors m opérations prendront mƒ (n) temps.

  • Best Case- C'est le scénario représentant le temps d'exécution le moins élevé possible d'une opération d'une structure de données. Si une opération prend ƒ (n) temps d'exécution, alors l'opération réelle peut prendre du temps en tant que nombre aléatoire qui serait maximum comme ƒ (n).

Terminologie de base

  • Data - Les données sont des valeurs ou un ensemble de valeurs.

  • Data Item - L'élément de données fait référence à une seule unité de valeurs.

  • Group Items - Les éléments de données divisés en sous-éléments sont appelés éléments de groupe.

  • Elementary Items - Les éléments de données qui ne peuvent pas être divisés sont appelés éléments élémentaires.

  • Attribute and Entity - Une entité est celle qui contient certains attributs ou propriétés auxquels des valeurs peuvent être attribuées.

  • Entity Set - Les entités d'attributs similaires forment un ensemble d'entités.

  • Field - Le champ est une seule unité élémentaire d'information représentant un attribut d'une entité.

  • Record - Record est une collection de valeurs de champ d'une entité donnée.

  • File - Le fichier est une collection d'enregistrements des entités dans un ensemble d'entités donné.