[Powered by Google Translate] Vous avez probablement entendu des gens parler d'un algorithme rapide ou efficace pour l'exécution de votre tâche particulière, mais qu'est-ce que cela signifie pour un algorithme pour être rapide ou efficace? Eh bien, il ne parle pas d'une mesure en temps réel, comme des secondes ou minutes. C'est parce que le matériel informatique et logiciel varient considérablement. Mon programme pourrait fonctionner plus lentement que le vôtre, parce que je suis en train de courir sur un vieil ordinateur, ou parce que je suis à jouer à un jeu vidéo en ligne en même temps, ce qui est monopolisant toute ma mémoire, ou je pourrais être exécuté mon programme à travers différents logiciels qui communique avec la machine de manière différente à un niveau bas. C'est comme comparer des pommes et des oranges. Tout simplement parce que mon ordinateur plus lent prend plus de temps que le vôtre pour redonner une réponse ne signifie pas que vous avez l'algorithme plus efficace. 

Donc, puisque nous ne pouvons pas comparer directement les temps d'exécution des programmes en quelques secondes ou minutes, comment pouvons-nous comparer les 2 algorithmes différents quel que soit leur matériel ou logiciel? Pour créer une façon plus uniforme de mesure de l'efficacité algorithmique, les informaticiens et les mathématiciens ont mis au point concepts de mesure de la complexité d'un programme asymptotique et une notation appelée «Big Ohnotation ' pour la description de ce produit. La définition formelle est que la fonction f (x) s'étend de l'ordre de g (x) s'il existe une certaine valeur (x), x ₀ et une constante, C, pour lequel f (x) est inférieur ou égal à que les temps constant g (x) pour tout x supérieur à x ₀. 

Mais ne soyez pas effrayés par la définition formelle. Qu'est-ce que cela signifie réellement en termes moins théoriques? Eh bien, il s'agit essentiellement d'une méthode d'analyse la rapidité d'exécution d'un programme croît asymptotiquement. C'est, comme la taille de vos entrées augmente vers l'infini, mot à dire, vous triez un tableau de taille 1000 par rapport à un tableau de taille 10. Comment l'exécution de votre programme de grandir? Par exemple, imaginez compter le nombre de caractères dans une chaîne de la façon la plus simple  en marchant à travers toute la chaîne lettre par lettre et en ajoutant 1 à un compteur pour chaque caractère. Cet algorithme est dit de courir en temps linéaire en ce qui concerne le nombre de caractères, "N" dans la chaîne. En bref, il s'exécute en O (n). Pourquoi est-ce? Eh bien, en utilisant cette approche, le temps nécessaire pour traverser la totalité de la chaîne est proportionnelle au nombre de caractères. Compter le nombre de caractères dans une chaîne de 20 caractères va prendre deux fois plus longtemps que nécessaire pour compter les caractères dans une chaîne de 10 caractères, parce que vous devez examiner tous les caractères et chaque personnage prend la même quantité de temps à regarder. Lorsque vous augmentez le nombre de caractères, le runtime augmente linéairement avec la longueur d'entrée. 

Maintenant, imaginez si vous décidez que le temps linéaire, O (n), n'était tout simplement pas assez rapide pour vous? Peut-être que vous stockez des chaînes énormes, et vous ne pouvez pas payer le temps supplémentaire qu'il faudrait de parcourir la totalité de leurs caractères de comptage une après l'autre. Alors, vous décidez d'essayer quelque chose de différent. Que faire si vous souhaitez arriver déjà stocker le nombre de caractères dans la chaîne, par exemple, dans une variable appelée "len", dès le début du programme, avant même enregistré le premier caractère dans votre chaîne? Ensuite, tout ce que vous auriez à faire dès maintenant pour savoir la longueur de chaîne, est de vérifier que la valeur de la variable. Vous n'auriez pas à regarder la chaîne elle-même à tous, et accéder à la valeur d'une variable est considérée comme len une opération asymptotiquement temps constant, ou O (1). Pourquoi est-ce? Eh bien, rappelez-vous ce que signifie la complexité asymptotique. Comment le changement d'exécution que la taille de vos entrées pousse? 

Dites que vous tentiez d'obtenir le nombre de caractères dans une grande chaîne. Eh bien, il ne serait pas question quelle taille vous que la chaîne, même un million de caractères, tout ce que vous auriez à faire pour trouver la longueur de la corde avec cette approche, est de lire la valeur de la len variable, que vous avez déjà fait. La longueur d'entrée, c'est la longueur de la chaîne que vous essayez de trouver, n'affecte pas du tout la rapidité de votre programme fonctionne. Cette partie de votre programme irait aussi vite sur une chaîne d'un seul caractère et une chaîne de mille caractères, et c'est pourquoi ce programme serait appelé fonctionne en temps constant par rapport à la taille de l'entrée. 

Bien sûr, il ya un inconvénient. Vous passez d'espace mémoire supplémentaire sur votre ordinateur stocker la variable et le temps supplémentaire qu'il vous faut à faire le stockage réelle de la variable, mais le point est toujours debout, savoir combien de temps votre chaîne était ne dépend pas de la longueur de la chaîne du tout. Ainsi, il s'exécute en O (1) ou constante de temps. Cela ne veut certainement pas signifier que votre code s'exécute dans l'étape 1, mais peu importe combien d'étapes il est, si elle ne change pas avec la taille des entrées, il est encore asymptotiquement constant que nous représentons en tant que O (1). 

Comme vous pouvez probablement le deviner, il ya beaucoup de différents grands runtimes O algorithmes permettant de mesurer avec. O (n) ² algorithmes sont asymptotiquement plus lent que O (n) des algorithmes. Qui est, selon le nombre d'éléments (n) croît, finalement O (n) ² algorithmes prendra plus de temps que O (n) pour exécuter des algorithmes. Cela ne veut pas dire O (n) des algorithmes toujours courir plus vite que O (n) ² algorithmes, même dans le même environnement, sur le même matériel. Peut-être que pour des tailles d'entrée des petits,  O (n) ² algorithme peut effectivement travailler plus vite, mais, par la suite, comme la taille d'entrée augmente vers l'infini, le O (n) ² algorithme de runtime finira par éclipser le temps d'exécution de O (n) algorithme. Tout comme n'importe quelle fonction mathématique quadratique  finira par dépasser n'importe quelle fonction linéaire, peu importe combien d'un chef de démarrer la fonction linéaire commence avec. Si vous travaillez avec de grandes quantités de données, algorithmes qui s'exécutent en O (n) ² peut vraiment finir par ralentir votre programme, mais pour des tailles d'entrée de petites, vous n'aurez probablement même pas remarqué. 

Une autre complexité asymptotique est, temps logarithmique, O (log n). Un exemple d'un algorithme qui fonctionne aussi rapidement est l'algorithme de recherche binaire classique, pour trouver un élément dans une liste triée de déjà-éléments. 

Si vous ne savez pas ce que recherche binaire fait, Je vais l'expliquer pour vous très rapidement. Disons que vous êtes à la recherche pour le numéro 3 dans ce tableau d'entiers. Il se penche sur l'élément central du tableau et demande: «Est-ce que je veux élément supérieur, égal ou inférieur à cela?" Si c'est égal, tant mieux. Vous avez trouvé l'élément, et vous avez terminé. Si elle est supérieure, alors vous savez que l'élément doit être dans le côté droit de la matrice, et vous ne pouvez regarder que dans l'avenir, et si elle est plus petite, alors vous savez qu'il doit être sur le côté gauche. Ce processus est ensuite répété avec la baie de petite taille jusqu'à ce que l'élément a été retrouvé. 

Cet algorithme puissant coupe la taille du tableau en deux avec chaque opération. Ainsi, pour trouver un élément dans un tableau trié de taille 8, tout au plus (log ₂ 8), ou 3 de ces opérations, vérification de l'élément du milieu, puis en coupant le tableau dans la moitié sera nécessaire, alors un tableau de taille 16 a (log ₂ 16), ou 4 opérations. C'est seulement 1 de plus pour une vaste opération de doubler de taille. Doublement de la taille de la matrice augmente le temps d'exécution de seulement 1 morceau de ce code. Encore une fois, en vérifiant l'élément central de la liste, puis fractionnement. Ainsi, il est dit de fonctionner en temps logarithmique, O (log n). Mais attendez, dites-vous, N'est-ce pas dépendre du lieu dans la liste l'élément que vous recherchez est? Que faire si le premier élément que vous regardez se trouve être la bonne? Ensuite, il ne prend que 1 opération, peu importe la taille de la liste est. 

Eh bien, c'est pourquoi les informaticiens ont termes plus la complexité asymptotique qui reflètent le meilleur des cas et le pire des cas les performances d'un algorithme. Plus exactement, les limites supérieure et inférieure sur le runtime. Dans le meilleur des cas pour la recherche binaire, notre élément est juste là au milieu, et vous l'obtiendrez en temps constant, peu importe la taille du reste du tableau est. Le symbole utilisé pour cela est Ω. Ainsi, cet algorithme est dit de courir dans Ω (1). Dans le meilleur des cas, il trouve rapidement l'élément, peu importe la taille du tableau est, mais dans le pire des cas, qu'il doit accomplir (log n) vérifie fendus du tableau pour trouver le bon élément. Le pire des cas limites supérieures sont appelées avec le grand "O" que vous connaissez déjà. Ainsi, il est O (log n), mais Ω (1). 

Une recherche linéaire, en revanche, dans lequel vous guidera à travers chaque élément du tableau pour trouver celui que vous voulez, Ω est au mieux (1). Encore une fois, le premier élément que vous voulez. Donc, ce n'est pas grave la taille du tableau est. Dans le pire des cas, c'est le dernier élément du tableau. Donc, vous avez à marcher à travers tous les éléments contenus dans le tableau n pour le trouver, comme si vous étiez à la recherche d'un 3. Ainsi, il s'exécute en O (n) car il est proportionnel au nombre d'éléments dans le tableau. 

Un autre symbole utilisé est Θ. Cela peut être utilisé pour décrire des algorithmes où les meilleurs et les pires des cas sont les mêmes. C'est le cas dans les algorithmes de chaîne de longueur dont nous avons parlé plus tôt. Autrement dit, si nous le stocker dans une variable avant nous stockons la chaîne et y accéder ultérieurement en temps constant. Peu importe ce numéro que nous stockons dans cette variable, nous aurons à le regarder. Le meilleur cas est, nous le regardons et calculer la longueur de la chaîne. Alors Ω (1) ou le meilleur des cas la constante de temps. Le pire des cas est, nous regarder et trouver la longueur de la chaîne. Donc, O (1) ou constante de temps dans le pire des cas. Donc, puisque le meilleur des cas et le pire des cas sont les mêmes, ce qui peut être dit de courir en Θ (1) fois. 

En résumé, nous avons de bonnes façons de raisonner sur l'efficacité des codes sans rien connaître le temps du monde réel qu'ils prennent à courir, qui est affectée par de nombreux facteurs extérieurs, y compris le matériel différent, logiciels, ou les spécificités de votre code. De plus, il nous permet de bien raisonner sur ce qui va se passer lorsque la taille de l'augmentation des entrées. 

Si vous utilisez en O (n) ² algorithme, ou pire, un O (2 ⁿ) algorithme, l'un des types les plus rapides en croissance, vous allez vraiment commencer à remarquer le ralentissement lorsque vous commencez à travailler avec de grandes quantités de données. 

C'est la complexité asymptotique. Merci.