Share
Je suppose que vous êtes un programmeur informatique. Peut-être que vous êtes un nouvel étudiant en informatique ou peut-être un ingénieur en logiciel expérimenté. Peu importe où vous vous trouvez sur ce spectre, les algorithmes et les structures de données sont importants. Pas simplement comme des concepts théoriques, mais comme des blocs de construction utilisés pour créer des solutions aux problèmes de l'entreprise.
Bien sûr, vous savez peut-être comment utiliser le C # liste ou Empiler classe, mais comprenez-vous ce qui se passe sous les couvertures? Sinon, prenez-vous réellement les meilleures décisions concernant les algorithmes et les structures de données que vous utilisez??
Une compréhension significative des algorithmes et des structures de données commence par la possibilité d'exprimer et de comparer leurs coûts relatifs.
Lorsque nous parlons de mesurer le coût ou la complexité d’un algorithme, nous parlons en réalité d’effectuer une analyse de l’algorithme lorsque les jeux d’entrée sont très grands. L'analyse de ce qui se passe lorsque le nombre d'entrées devient très important est appelée analyse asymptotique. Comment la complexité de l'algorithme change-t-elle lorsqu'elle est appliquée à dix, mille, ou dix millions d'éléments? Si un algorithme s'exécute en cinq millisecondes avec un millier d'éléments, que pouvons-nous dire de ce qu'il va se passer lorsqu'il fonctionnera avec un million? Est-ce que cela prendra cinq secondes ou cinq ans? Ne préféreriez-vous pas comprendre cela avant votre client??
Ce truc compte!
Le taux de croissance décrit l'évolution de la complexité d'un algorithme à mesure que la taille de l'entrée augmente. Ceci est généralement représenté en utilisant la notation Big-O. La notation Big-O utilise un O majuscule ("ordre") et une formule qui exprime la complexité de l'algorithme. La formule peut avoir une variable, n, qui représente la taille de l'entrée. Voici quelques fonctions de commande courantes que nous verrons dans ce livre, mais cette liste n’est en aucun cas exhaustive..
Un algorithme O (1) est un algorithme dont la complexité est constante quelle que soit la taille de la taille d'entrée. Le "1" ne signifie pas qu'il n'y a qu'une seule opération ou que l'opération prend peu de temps. Cela peut prendre une microseconde ou une heure. Le fait est que la taille de l'entrée n'influence pas la durée de l'opération.
public int GetCount (int [] éléments) return items.Length;
Un algorithme O (n) est un algorithme dont la complexité augmente de façon linéaire avec la taille de l'entrée. Il est raisonnable de s'attendre à ce que si une taille d'entrée de un prend cinq millisecondes, une entrée de mille éléments prendra cinq secondes..
Vous pouvez souvent reconnaître un algorithme O (n) en recherchant un mécanisme de bouclage qui accède à chaque membre..
public long GetSum (int [] items) somme longue = 0; foreach (int dans les éléments) sum + = i; retourne la somme;
Un algorithme O (log n) est un algorithme dont la complexité est logarithmique à sa taille. Beaucoup d'algorithmes divisent et conquièrent tombent dans ce seau. L'arbre de recherche binaire Contient méthode implémente un algorithme O (log n).
Un algorithme linéarithmique, ou loglinear, est un algorithme qui a une complexité de O (n log n). Certains algorithmes divisent et conquièrent tombent dans ce seau. Nous verrons deux exemples lorsque nous examinerons le tri par fusion et le tri rapide.
Un algorithme O (n ^ 2) est un algorithme dont la complexité est quadratique par rapport à sa taille. Bien qu’il ne soit pas toujours évitable, l’utilisation d’un algorithme quadratique est un signe potentiel que vous devez reconsidérer votre choix d’algorithme ou de structure de données. Les algorithmes quadratiques ne s'échelonnent pas bien à mesure que la taille de l'entrée augmente. Par exemple, un tableau avec 1 000 entiers nécessiterait 1 000 000 opérations. Un intrant contenant un million d'articles nécessiterait un billion d'opérations (1 000 000 000 000). Pour mettre cela en perspective, si chaque opération prend une milliseconde, un algorithme O (n ^ 2) qui reçoit une entrée d'un million d'éléments prendra près de 32 ans. Rendre cet algorithme 100 fois plus rapide prendrait encore 84 jours.
Nous verrons un exemple d'algorithme quadratique quand on regarde le type à bulle.
Quand on dit qu'un algorithme est O (n), que dit-on vraiment? Sommes-nous en train de dire que l'algorithme est O (n) en moyenne? Ou décrivons-nous le meilleur ou le pire scénario?
Nous entendons généralement le pire scénario sauf si le cas commun et le pire des cas sont très différents. Par exemple, nous allons voir dans ce livre des exemples où un algorithme est en moyenne O (1), mais devient périodiquement O (n) (voir ArrayList.Add). Dans ces cas, je décrirai l'algorithme comme étant O (1) en moyenne et expliquerai ensuite quand la complexité change.
Le point clé est que dire O (n) ne signifie pas que ce sont toujours n opérations. C’est peut-être moins, mais ça ne devrait pas être plus.
Lorsque nous mesurons des algorithmes et des structures de données, nous parlons généralement de l’une des deux choses suivantes: le temps nécessaire à l’opération (complexité opérationnelle) ou la quantité de ressources (mémoire) utilisée par un algorithme (complexité des ressources)..
Un algorithme qui fonctionne dix fois plus vite mais utilise dix fois plus de mémoire peut être parfaitement acceptable dans un environnement de serveur avec de grandes quantités de mémoire disponible, mais peut ne pas convenir dans un environnement embarqué où la mémoire disponible est sérieusement limitée..
Dans ce livre, je me concentrerai principalement sur la complexité opérationnelle, mais dans la section Algorithmes de tri, nous verrons quelques exemples de complexité des ressources..
Voici quelques exemples de mesures que nous pourrions mesurer:
Le contexte de l'opération en cours vous indiquera généralement quel type de mesure est effectué..
Par exemple, lorsque vous discutez de la complexité d'un algorithme qui recherche un élément dans une structure de données, nous parlons presque certainement d'opérations de comparaison. La recherche est généralement une opération en lecture seule, il n’est donc pas nécessaire d’effectuer des tâches ou d’allouer de la mémoire..
Cependant, lorsque nous parlons de tri des données, il peut être logique de supposer que nous pourrions parler de comparaisons, d’affectations ou d’allocations. Dans les cas où il peut y avoir une ambiguïté, je vais indiquer le type de mesure à laquelle la complexité fait réellement référence..
Ceci termine la première partie sur les algorithmes et les structures de données. Ensuite, nous allons passer à la liste liée.
Accentsconagua