Timing informatique et notation Big O

1. Vidéo d'introduction: Bonjour à tous, et bienvenue dans ce cours sur la notation Big O. C'est un excellent sujet d' informatique qui vous aidera à devenir plus efficace dans votre travail. Et cela vous aidera également à mieux comprendre l' informatique. C'est idéal pour tous les types de professions, y compris les programmeurs, ainsi que pour tous les acteurs du monde des affaires. Cela vous aidera à augmenter votre productivité, car vous comprendrez un peu mieux sur quoi vous travaillez, ce qui vous permettra de mieux comprendre et d'agir les mesures à prendre pour rendre les choses plus efficaces. Et c'est ce que nous allons aborder dans ce cours. Nous allons aborder la notation qui sous-tend la façon dont nous analysons les différents algorithmes et l'évolutivité Nous voulons savoir si nous construisons un programme un morceau de code ou même simplement une unité organisationnelle. Peut-il évoluer ? Si nous créons des tâches et des procédures de nature exponentielle, elles ne pourront jamais être mises à l'échelle Et c'est ce que nous voulons pouvoir analyser : est-ce que cela fonctionne de la même manière si nous avons dix ou 100 000 personnes ? Demandez-vous si vous voulez vérifier chaque dossier d' un classeur. Il existe une méthode qui vous permet d' extraire chaque fichier et de l'examiner individuellement, ou de créer une procédure dans laquelle il est organisé et trié de manière à ce que vous sachiez où aller pour trouver des informations. Et c'est ce que vous pouvez également faire dans le domaine de la programmation, mais aussi avec ce qui nous entoure. Un autre exemple serait si nous devions ajouter quelqu'un à une organisation, mais pour ce faire, nous devions d'abord contacter tous les autres membres de l'organisation. Il s'agit d'une solution non évolutive. Il s'agit d'une procédure non évolutive. Et nous voulons être en mesure d'analyser cela, de le retravailler et d'en faire une procédure plus évolutive Nous allons donc tous deux nous concentrer sur le code à cet égard, tout en comprenant que ces principes s'appliquent également à la vie quotidienne. Ils s'appliquent à tout ce qui nous entoure. Passons donc à ce sujet d' informatique et examinons quelques mathématiques vraiment intéressantes. 2. Introduction à Big O: Parlons de notre premier sujet majeur en matière d'analyse des algorithmes, et ce sera cette idée de notation. Donc, nous allons en fait évoluer cela vers ce que l' on appelle la notation Big O, qui ressemblera à ceci où vous avez un O, puis la notation in entre à l'intérieur. Mais avant de pouvoir le faire, nous devons déterminer ce qu'il y a exactement dans la notation. Donc, dans la notation, il y a cette étrange sorte de relation, où est une fonction de in. Maintenant, reste avec moi. Cela prête à confusion au début. Nous allons donc devoir en quelque sorte le déballer un peu C'est ce genre de méthode où sortie est fonction de l'entrée, et il se trouve que c'est la même chose. Allons-y et créons une sorte de modèle visuel de cela. Chaque fois que nous créons un algorithme ou un programme, nous créons ce type de boîte noire. Donc, ce que nous avons, c'est que nous avons sur le côté gauche une entrée. Nous avons des objets qui entrent dans la boîte. Nous avons peut-être vos amis Facebook, peut-être votre Google Drive, toutes les données que vous y envoyez. C'est Internet. Lorsque vous téléchargez quelque chose, c'est l'entrée Il est envoyé à une sorte de logique, à une sorte de programme. C'est donc, vous savez, la logique ou le taux du contrôleur ici. Et puis il a une sorte de sortie. se passe quelque chose parce que c' est parti de cette logique ici même. Il s'est passé quelque chose ? Quelque chose a bougé, quelque chose a été sauvegardé. C'est vraiment ce que fait la logique. Supposons, par exemple, que nous téléchargeons des photos. Ce sont les photos qui entrent en ligne de compte. Nous l'envoyons au contrôleur. Il prend les photos, peut-être qu'il les réduit pour les rendre plus faciles à ranger. Ensuite, il prend ces photos et les enregistre dans une base de données. Il les place donc et les écrit dans la mémoire physique sur un disque dur. Et c'est donc le résultat. Ainsi, l'entrée, les images, la sortie correspondent à chacune de ces opérations de sauvegarde sur un disque dur. Donc, ce que nous essayons de comprendre est fourni en entrée. Il s'agit donc de l'entrée de in. Quel sera notre résultat ? Par rapport à cela. Et voici juste une variable. C'est simplement parce que nous ne savons pas combien de données nous parviennent. Si, par exemple, nous avions un programme qui avait des amis sur Facebook, j'aurais peut-être, vous savez, peut-être 182 amis sur Facebook. Eh bien, peut-être que vous en avez 1 373, et que votre cousin éloigné a 10 157 amis sur Facebook, vous savez, et ainsi Et disons qu' il n'y a pas de limite. Je pense qu'il y a une limite. Mais disons qu'il n'y a pas de limite aux amis sur Facebook. Cela signifie que vous pourriez avoir zéro jusqu'à l'infini. Nous ne savons donc pas quel numéro va entrer ici. Donc, au lieu d'essayer de simplement créer un nombre, nous disons simplement, qui sera simplement la valeur de l' espace réservé Nous allons donc mettre une entrée de ici. Il peut s'agir de n'importe lequel de ces nombres compris entre zéro et l'infini. Donc n'importe quel chiffre. Ensuite, cela va passer par notre logique. Et puis, à la fin, nous allons avoir un certain nombre d'opérations. Donc, entre ce taux de points, nous allons avoir la logique, puis les opérations, puis le résultat sera affiché. Et nous voulons savoir ce qui se passe à ce stade. Quel est le lien entre cela et cela ? Donc, ce sera la sortie ou notre fonction. Ce sera la notation. Et ce que nous écrivons généralement, c'est que nous l'écrivons également sous forme d'entrée. Mais nous l'écrivons en fonction de, ce qui signifie que ce n'est pas la seule chose que nous avons mise ici. Il y a en fait un tas de choses différentes que nous pourrions mettre ici. Donc, ce que nous aurions pu avoir est intégré, ce qui signifie simplement que chaque fois que nous introduisons, disons, 1 000 données, cela ne nécessite que 1 000 opérations. Par exemple, quelque chose comme ça se produit si vous trouvez un tas de fichiers sur votre disque dur et que vous souhaitez les déplacer vers un autre emplacement ? Eh bien, il n'y a rien d'autre qui doive vraiment se produire. On en prend un, on le déplace. On en prend un, on le déplace. Ça y est. Pour chaque donnée que vous incluez, il n'y a qu'une opération supplémentaire. Maintenant, il y a différentes choses, bien sûr. Donc, au lieu de cela, il pourrait y avoir un carré. Il y a ce qu'on appelle le log of. Il y a juste beaucoup de n. Il y a des cubes. Voici la racine carrée de. Et ainsi de suite. Donc, tout ce que nous faisons, c'est prendre tout cela, et nous en faisons une fonction de l'entrée. Cela restera toujours le même. Ce sera toujours là. C'est notre contribution. C'est la quantité de données qui arrive. À droite, il y a juste la relation, et nous l'utilisons simplement parce et nous l'utilisons simplement parce que cela nous montre que c'est ce dont nous faisons une fonction. Je veux dire, nous pourrions utiliser x et le x au carré , puis le log x de x et des trucs comme ça, et ainsi de suite et ainsi de suite Mais le problème, c'est que vous pourriez vous perdre en vous demandant ce qu'est exactement x. Ensuite, nous devons mettre quelque chose ici qui dit simplement : Eh bien, x est égal à n, x est égal à ou input. Et puis nous nous demandons simplement : pourquoi ne pas nous en tenir à N pour tout faire. Donc, c'est vraiment la partie la plus confuse de la notation, c'est que N semble être l'entrée et la sortie. Mais l'important, c'est que ce soit l'entrée, puis que la sortie ne soit qu'une fonction de N. C' une représentation de la durée ou nombre d'opérations que N doit effectuer pour passer au-dessus. Vers les sorties. Regardons maintenant un petit exemple concret. Revenons à celui des amis sur Facebook, car c'est quelque chose que nous pouvons tous visualiser très rapidement. Disons que j'ai un algorithme ici. J'ai un algorithme qui prend un certain nombre d'amis Facebook et les saisit dans une base de données au moment de la relation de. Et disons que j'ai un autre algorithme ici. Ce qui fait exactement la même chose. Sauf qu'au lieu de cela, il prend la même valeur que in, donc il absorbe, mais il sort au carré Il y a un peu moins d'efficacité ici. Alors maintenant, nous pouvons en quelque sorte regarder ces deux choses et les comparer un peu. Lequel de ces algorithmes est le plus rapide ? Donc, si nous allions de l'avant et que nous faisions juste quelques calculs rapides, disons que nous allons tester cela avec 100 % de Facebook France. Donc, pour ce premier, il y aura juste 100 entrées dans notre petite boîte noire, et il en ressortira avec 100 opérations différentes pour faire ce qu'il veut. Eh bien, sur celui du bas, nous avons 100 entrées dans notre petite boîte noire. N'oubliez pas que cela restera toujours la même, mais que notre fonction est n au carré, ce qui signifie que nous devons maintenant prendre 100 et la mettre au carré, ce qui s'avère être 100 fois 100, ce qui signifie que notre total sera Oups, nous devons obtenir les zéros Quatre zéros ou 10 000. Vous pouvez donc voir que le premier n'a nécessité que 100 opérations, tandis que le second n' a nécessité que 10 000 opérations. Nous y reviendrons un peu plus tard. Cependant, ce sont leurs modèles de croissance qui sont importants. Dans ce que nous avons, nous avons en fait ce qu' on appelle un linéaire, puis dans le carré, nous avons quelque chose qui s'appelle exponentiel, ce qui signifie que la croissance augmente de plus en plus au fil Mais comme je l'ai dit, nous y reviendrons plus tard. Ce que je voulais juste vous montrer , c'est comment nous envisageons les choses. Nous avons donc une valeur d'entrée et une valeur de sortie. Nous avons une autre valeur d'entrée et une autre valeur de sortie, et il existe deux algorithmes différents, algorithme A et l'algorithme B. Et nous pouvons rapidement dire : « Eh bien, A est certainement plus rapide que B. A, vous pourriez dire qu' il est supérieur à B, ou vous pourriez dire qu'il moins de temps que B ou comme vous voulez les comparer ». Mais celui-ci est rapide et celui-ci est lent à cause du nombre d'opérations nécessaires. Alors, à quoi ça sert ? Qu'est-ce que nous essayons d'atteindre ici ? Cela nous permet de voir comment un algorithme évolue en fonction de la taille d'entrée. Si nous concevons un algorithme, nous voulons savoir s'il est efficace avec plus de personnes et de contributions. Nous voulons que nos programmes soient couronnés de succès. Nous voulons donc créer des solutions évolutives. Et c'est quelque chose que vous allez beaucoup entendre. Nous voulons créer des solutions évolutives. Et une solution évolutive est une solution qui ne fonctionne pas uniquement pour le nombre exact de personnes qui l'utilisent actuellement. Donc, par exemple, comme je l'ai dit, nous allons continuer sur cet exemple de Facebook. Imaginez si Facebook utilisait celui-ci. Imaginez s'il utilisait l'algorithme au carré parce qu'il ne pensait pas qu'ils allaient évoluer Eh bien, le fait est que nous sommes des programmeurs. Nous essayons de faire de notre produit le meilleur produit possible. Cela signifie que nous voulons que le produit soit un succès. Et lorsqu'un produit réussit, de plus en plus de personnes l'utilisent, de plus en plus de données sont saisies, et l'algorithme devra utiliser ces nouveaux éléments Si nous ne créons pas un programme évolutif, nous serons confrontés à un problème exponentiel : oui, cela fonctionnera pour 100 personnes, peut-être pour 1 000 et peut-être pour 10 000 Mais si vous vous rendez compte que cela ne représente qu'une infime partie de la population. Disons qu'il s'agit peut-être d'un million de personnes. Vous souhaitez utiliser notre programme. Eh bien, maintenant, nous avons une solution qui ne fonctionne pas pour 1 million de personnes. Si nous le faisions 1 million fois 1 million. Eh bien, nous aurions un chiffre extrêmement élevé. Un chiffre qui n'est même pas compréhensible par notre cerveau. Et en fait, nous ferons une partie de ces calculs un peu plus tard. Un nombre aussi important finit par prendre des jours, voire des années, à exécuter. Donc, un ordinateur qui peut, vous savez, se connecter en ligne et faire tous ces calculs rapides prendra des jours, voire des années, pour accomplir une tâche simple, et c'est parce que le programme n'est pas évolutif. C'est donc la base de la notation. Il s'agit d'une forme de notation standardisée qui nous permet de comparer deux algorithmes dans un environnement totalement stérile, ce qui signifie que nous n' avons pas à les implémenter. Nous pouvons simplement les regarder. Cela nous permet de les comparer et déterminer lequel est le plus évolutif. Lequel sera le plus rapide chaque fois que nous y ajouterons plus de personnes, de données ou d'opérations. Et c'est le but de la notation. Et lors de la prochaine conférence, nous allons continuer à approfondir ce sujet et à déballer le cadre qu'est la notation afin d'obtenir cette base solide qui nous permettra de comparer différents algorithmes 3. Notation N: Examinons un peu plus en profondeur la notation finale et examinons certains des objectifs qui sous-tendent les raisons pour lesquelles nous, en tant qu' informaticiens, utilisons la notation finale et ce que nous essayons d'en tirer. Parce que la notation finale peut être utilisée de nombreuses manières différentes. Il existe un tas de combinaisons ou d' informations différentes que nous pouvons en tirer en utilisant cette notation. Mais ce que je veux aborder, c'est l'essentiel, quoi la plupart des informaticiens l'utilisent. Et quels en sont les objectifs ? Pourquoi l'utilisons-nous ? Ainsi, lorsque nous utilisons la notation, nous recherchons de grands modèles, et nous recherchons ces modèles dans une sorte d'espace théorique, ce qui signifie qu'aucun programme ne sera réellement implémenté ou quoi que ce soit d'autre. Nous cherchons juste ces grands motifs. Nous cherchons, par exemple, si un graphe va comme ça et l' autre comme ça. Peu importe si, à un moment donné nous avons ce graphique en bas, peut-être qu' il se présente comme ça, puis celui du haut va comme ça ou quelque chose comme ça ? Nous nous en fichons à ce stade, oui, il y a un point où I squared est en fait un peu plus efficace ? C'est une question de fond lorsque vous avez un algorithme devant vous et que vous essayez de l'optimiser  ? C'est ce que pourrait faire un optimiseur de serveur ou une gestion de base de données, des choses comme ça Nous nous intéressons simplement à cette théorie dans son ensemble. Nous cherchons quelle équation évolue le plus mal au fil du temps. Alors que nous nous dirigeons vers l'infini, alors que nous nous dirigeons vers le nombre inconnu de données qui pourraient provenir d'un algorithme intérieur, qu'arrivera-t-il à notre équation ? Allons-nous obtenir cette équation qui ne peut être terminée au cours de ce siècle à cause du nombre de calculs nécessaires, ou allons-nous obtenir quelque chose comme ça, où le nombre de calculs que nous lui donnons n'a pas d'importance. Ça va juste continuer à rouler . C'est donc ce que nous voulons voir. Nous voulons voir ce changement d'efficacité majeur entre les différents algorithmes. C'est le but de la notation et c'est pourquoi nous l'utilisons. Pour cette raison, il existe quelques règles que nous utilisons généralement avec la notation. Et ce ne sont que des raccourcis que nous utilisons pour ne pas nous embrouiller Et encore une fois, pour avoir une vue d'ensemble. Nous ne passons donc pas tout notre temps dans les détails. En fait, nous pouvons simplement regarder deux équations et nous dire, oui, celle-ci s'adapte un peu mieux. La première est que nous ne nous soucions pas des multiples. Et ce que cela signifie, par exemple, c'est si nous avons n au carré puis trois n au carré. Ils sont, à toutes fins utiles, égaux. Ils sont fondamentalement égaux les uns aux autres. On s'en fout. Je veux dire, trois, tu sais, peut-être que tu pourrais te justifier. Oui, trois c'est bien, mais ça pourrait être, tu sais, ça pourrait être 3 millions, 3 milliards, 30 milliards, 30 billions de dollars. Cela peut être n'importe quel chiffre que nous voulons, et cela n'a pas d'importance. Nous prenons ce multiple et nous l'effaçons. Les multiples ne nous intéressent pas. Et cela se résume, encore une fois, à l'essentiel : peu importe la taille de ce nombre à moment donné entre zéro et À un moment donné, n au carré rendra ce nombre même inefficace Imaginez si, à un moment donné, c'était égal à, je ne sais pas. 300 Google, et Google c'est 100 zéros au bout du compte. Vous avez donc 100 zéros à la toute fin. Pensez-vous que les 3 millions multipliés sont vraiment importants à ce moment-là ? Je veux dire, il va y avoir une très, très petite différence dans le résultat final. Nous parlons comme si vous savez, ce serait une différence entre un nombre qui ressemble à ceci ou entre un nombre qui contient ceci dessus. Tu sais, un petit plus. Cela n'a pas d'importance du tout. C'est pourquoi, en théorie, chaque fois que nous passons de zéro à l'infini, nous ne nous soucions pas des multiples. Donc, pour comparer deux algorithmes, cela pourrait être 3 millions au carré, et nous le comparons à un cube, peu importe le comparons à un cube, peu importe Nous sommes toujours en train de comparer n au carré à n cubes. Vous supprimez donc toujours les multiples au début. Maintenant, comment obtenons-nous ces multiples ? Eh bien, disons que nous avons une équation qui fait cela. Nous avons la boîte noire, donc nous avons les entrées qui arrivent ici. Nous avons une opération carrée. Ensuite, nous plaçons toutes ces entrées dans une autre boîte noire, une autre opération carrée OK. Et disons qu'à la toute fin, nous en avons une autre, mais celle-ci n'est qu'une opération de connexion. Donc, avec un algorithme comme celui-ci, nous créons en fait une petite équation ici. Nous faisons quelque chose comme ça. Nous allons au carré plus au carré et nous nous connectons. Ensuite, nous pouvons réellement les combiner en un multiple. Cela fait donc deux n au carré plus la connexion. C'est ainsi que nous arrivons à un multiple, et vous savez ce que nous disons ici, c'est que nous ne nous soucions pas vraiment du multiple. Je peux le faire autant de fois que nous le voulons. Nous examinons simplement ce grand facteur de changement. Cela devient donc carré et connectez-vous. Nous en arrivons donc à notre deuxième règle. Nous prenons l'équation la plus grande. Donc, chaque fois que nous avons une équation comme celle-ci, encore une fois, elle ne va pas évoluer aussi vite que celle-ci. Lorsque nous arrivons à ces chiffres géants avec 50 zéros, 1 milliard de zéros à la fin, je veux dire, c'est deux et c'est fini, donc il peut y avoir un milliard de zéros à un moment donné Il pourrait y avoir 1 milliard de zéros à la fin, pas un milliard Je parle d'un milliard de zéro réel. Ce serait un chiffre si long que, vous savez, vous ne pourriez pas l'adapter à la Terre entière. Il pourrait y avoir un chiffre comme celui-ci. Je veux dire, nous allons vers l'infini ici. Donc, à un moment donné, cela va devenir tellement plus élevé que ce chiffre que nous nous en fichons Ce n'est qu'un petit obstacle avant d'atteindre ce chiffre Cela va juste l' affecter de 0,00 000 1% à un moment donné. À un moment donné, il n'est affecté par presque rien. Ce sera un si petit chiffre. C'est presque zéro. Et à cause de cela, nous l'enlevons également, et nous laissons simplement une équation comme celle-ci pour dire : « Hé, tout cet algorithme ici, tout cet algorithme ici est en fait juste au tout cet algorithme ici est carré Il y a donc quelques règles de mise à l'échelle. Maintenant, si vous voulez passer à la technique, si nous faisons de l' optimisation des serveurs ou tout autre élément où nous avons réellement une équation devant nous, oui, c'est probablement quelque chose que équation devant nous, oui, nous voulons examiner parce que si nous examinons un serveur réel et que nous avons une équation qui peut l'exécuter à n carré plus connexion, au lieu de deux carrés plus n connexion nous voulons le faire parce que cela va être plus rapide dans la pratique. Mais encore une fois, ce n'est pas une pratique. C'est de la théorie. Nous essayons de comprendre uniquement les différences entre les applications à grande échelle. Dans ce sens, nous appliquons ces deux règles, nous les décomposons en fonction de leur durée d'exécution maximale. Et nous avons en fait de petits modificateurs tels que Big O, Little O et Beta Nous allons également en parler dans un petit moment, ce qui rendra les choses un peu plus faciles à comprendre. Jetons donc un coup d' œil à quelques graphiques ici. Jetons un coup d'œil, vous savez, à ce que j'ai détaillé ici avec tout ce qui concerne les chiffres, ils surpasseront leurs partenaires, ils surpasseront leurs partenaires, et nous ne nous intéressons donc vraiment qu'aux gros chiffres. Donc, ici, nous avons une sorte de représentation d'un graphique ici. Nous avons tout ce dont nous avons parlé. Il s' agit d'un temps constant. Cela signifie que nous pouvons en investir 000, 1 milliard, nous pouvons en investir autant que nous le voulons, et cela ne nécessitera qu' un nombre constant d'opérations. Donc ça n'en prendra peut-être que trois. Il s'agit peut-être de 62 opérations différentes. Quel que soit le chiffre que nous saisissons, 62 opérations sont nécessaires. C'est donc ce qu'est le temps constant. Ensuite, nous avons obtenu ce temps de connexion, et vous pouvez voir qu'il y a ce genre de graphique qui se présente comme suit. Ensuite, nous avons juste la racine carrée de N, qui est similaire à la connexion, mais elle augmente avec le temps. Nous avons un linéaire ou. Linar est juste une ligne droite inclinée. En se connectant, ça ressemble un peu à ça, mais ensuite ça forme une ligne linéaire, peut-être avec une légère tendance à la hausse. Ensuite, nous nous sommes retrouvés au carré, ce qui est exponentiel. Ensuite, nous avons obtenu deux facteurs n, qui sont encore plus exponentiels et vont presque droit dans les airs Ensuite, nous sommes entrés dans la factorielle, qui pourrait tout aussi bien ressembler à ceci Cela va presque droit dans les airs et cela crée des nombres si importants que si l'un de vos programmes s'exécute en mode factoriel, c'est une erreur Cela doit être fait d'une meilleure manière. Jetons un coup d'œil aux exemples de ce que tout cela pourrait être en quelque sorte si nous y ajoutions des chiffres, et de ce que pourraient être les durées d'exécution. Donc, dans cette situation, nous disons que nous pouvons voir ici le nombre d'intrants, et qu'en capital il y aura le nombre d'opérations. Donc, ici, ce sont les petits détails. C'est ce que nous saisissons. Nous saisissons les 100 000 , 10 000, 1110 ou un. Et voici le résultat le temps qu'il faudrait pour fonctionner. Et vous remarquez qu'au premier rang, c' est assez intéressant , c'est qu'avec une seule pièce, peu importe ce que vous avez, elle fonctionnera toujours en même temps. Bien sûr, il peut y avoir de petites différences, par exemple un temps constant. Peut-être que c'est une fois où, avec des temps constants 62, tout fonctionnerait un peu plus vite. Mais encore une fois, c'est une question de fond et cela ne nous intéresse pas vraiment Nous voulons examiner ces tendances au fil du temps. Donc, si nous passons à la factorielle, le E plus à la fin, cela signifie le nombre de zéros à la fin Cela signifie donc 9,3 ou neuf trois avec 157 ou 156 zéros si vous déplacez la décimale Quoi qu'il en soit, il y a beaucoup de zéros à la fin de celui-ci. Et celui-ci est, vous savez, quatre avec 2567350000, soit 456 000 zéros Et vous pouvez remarquer à quel point cela change au fil du temps. Et puis nous en avons deux ici. Il s'agit de deux, puis de deux factoriels. Donc, vous savez, dans cette situation, c'est deux dixièmes ou deux contre 100 et ainsi de suite et ainsi de suite. Mais de toute façon, vous pouvez remarquer que même ces deux-là. Ces deux-là sont essentiellement en l'air. Il y a une telle différence. C'est la différence entre 400 et 56 000 zéros et 300 ou 30 000 zéros et 300 ou 30 Et puis nous passons à autre chose de plus en plus. Et ce que nous avons, c'est que nous avons réduit à n au carré, ce dont nous avons parlé, et nous avons montré à quel point c'est inefficace Et cela semble en fait très infime par rapport à deux pour la factorielle n et n lorsqu'on le surpasse de plus en plus. Ensuite, nous avons N login. Nous arrivons en fait à des nombres lisibles ici, juste 1 660 000, puis juste n, ce qui, bien sûr, équivaudra au nombre que nous avons inscrit parce que N ira toujours à N. C'est ce que cela représente ici Et puis nous commençons à entrer dans ceux d'ici où vous remarquerez qu'ils sont plutôt cool. Ce sont des algorithmes efficaces ici. Nous en avons investi 100 000 et nous n'effectuons que 316 opérations. Il y a de plus en plus de changements au fil du temps. Et ceci, vous pouvez en quelque sorte remarquer comment nous pourrions obtenir une sorte d'algorithme pour devenir réellement assez efficaces. Je veux dire, regarde ça. Nous avons donc la différence entre 90 ici. Et dans cette différence, nous augmentons de trois opérations. Maintenant, nous avons la différence de 900 ici. Et combien allons-nous augmenter ? Eh bien, juste par environ trois opérations. Ensuite, nous avons la différence de 9 000 nouvelles données. De combien allons-nous augmenter ? Eh bien, environ trois opérations. Ensuite, nous augmentons de 90 000, c'est la prochaine étape. Et combien en avons-nous ? Eh bien, juste trois opérations. C'est exactement le contraire. nous y ajoutons, moins il augmente. Elle augmente de moins en moins avec le temps. Et il y a en fait des algorithmes dont nous allons parler tout au long de ce cours qui fonctionnent comme ceci. Il utilise quelque chose qui s'appelle diviser pour régner , là où nous nous séparons réellement. Les informations comme celles-ci, et de cette façon, nous pouvons y accéder très, très rapidement au lieu d' avoir à passer revue chaque élément pour obtenir ce que nous voulons. Quoi qu'il en soit, il s'agit simplement d' un autre aperçu de la notation, échelonnement, puis de certains des termes que nous utilisons avec la notation et la mise à l'échelle Dans la prochaine conférence, nous allons en quelque sorte passer en revue un exemple concret, peut-être ajouter un peu de côté théorique et examiner les différences entre les si nous appliquons réellement, vous savez, 0,01 seconde à chaque opération Nous pouvons voir à quel point ces chiffres augmentent et les différences entre eux. 4. Exemple de notation N: Mettons simplement quelques chiffres à ce dont nous avons parlé pour présenter un peu de respect que tout le monde puisse comprendre. Passons donc en revue ce problème ici et examinons les différences entre ce à quoi vous vous connectez et ce à quoi pourrait ressembler Squared Dans la dernière conférence, nous avons examiné ce type de taux graphique ici. Donc, ce que nous examinons, c'est ce taux ici, en connexion et au carré Et dans ce genre de petit graphique, je veux dire, ils semblent très proches l'un de l'autre, non ? On dirait qu'il n'y aurait pas tant de différence entre eux. Et c'est ce que je veux montrer, c'est qu'il existe des différences majeures, même entre les deux, et que le changement d'efficacité est très important. Alors, jetons un coup d' œil à cet exemple. Il va juste le passer en revue et, espérons-le , vous montrer les différences. Nous avons donc ou disons que chaque cycle d' un programme prend environ 0,001 seconde, ce qui correspond, je crois, à une milliseconde Donc, ce que nous voulons dire, c'est combien de temps la connexion sera plus rapide qu'au carré, si 1 000 données sont saisies, puis plus bas, si 25 000 données sont saisies Donc, avec ça, ce que nous allons faire c'est simplement le brancher. Nous allons calculer le nombre d'opérations nécessaires, le multiplier par une milliseconde, puis nous allons connaître le temps que prendrait multiplier par une milliseconde, un programme qui s'exécuterait de cette manière un programme qui s'exécuterait de cette Et donc, dans notre premier exemple, nous l'avons dans Login. Nous multiplions 1 000 par un log de 1 000, et nous utilisons un log basé sur deux, n'oubliez pas. Ce sont donc tous deux basés sur des journaux. Nous obtenons donc 9 960 fois les millisecondes, et tout cela revient à 9,96 secondes . Donc, si nous optons pour le carré, nous allons en faire 1 000 au carré Ce sera 1 000 fois 1 000, ce qui nous vaudra le numéro 1 million ici. Et avec 1 million, multipliez les millisecondes, et nous obtenons 1 000 secondes ou La différence entre l' utilisation de ces deux algorithmes est donc que l'un d'eux prendra 9,96 secondes. Donc, tu sais, 10 secondes. Ce n'est pas si long du tout, et l'autre prendra 16 minutes à accomplir. Imaginez que si vous êtes en ligne et que vous soumettez un formulaire, et que l'un d'eux utilise le mot de connexion n alors qu' un autre utilise n squared, de nombreuses personnes peuvent attendre 10 secondes pour qu'un formulaire soit soumis Mais si nous devions attendre 16 minutes, cela n'arriverait pas. Personne ne va le faire. Passons donc à un exemple un peu plus élevé. Supposons que nous ayons 25 000 éléments de données. Nous fabriquons donc les 25 000 pièces. C'est 25 fois la valeur d'un log, deux sur 25 000. Nous obtenons 365 000 fois les millisecondes. Cela revient ensuite à 6 minutes et 5 secondes. Notez ici qu'il est important de noter que même avec 25 000$ ou 24 000 éléments de données supplémentaires Cela prend tout de même 10 minutes de moins que si nous avions utilisé n carré sur le précédent Quoi qu'il en soit, nous jetons maintenant un coup d'œil au carré n. Nous faisons donc 25 000 fois 25 000. Cela nous rapporte 625 millions multiplié par une milliseconde, et nous obtenons ici quelque chose Nous avons sept jours et cinq heures pour y parvenir. Il ne s'agit donc que de 25 000 données Nous sommes passés de 6 minutes à sept jours. Et par exemple, si nous faisions 250 000 données, ce taux se chiffrerait ici en années ou en milliers d'années. Ce serait quelque chose qui ne serait pas accompli de notre vivant, ou du vivant de nos petits-enfants, le soleil pourrait s'éteindre avant que nous arrivions à l'accomplissement, avant que le programme ne soit réellement exécuté J'espère donc que ce petit exemple, juste à partir de ces petits calculs et en ajoutant les millisecondes ici, vous permettra de voir la grande différence, même s'ils se ressemblent un peu ici et peut-être même un peu Lorsque nous passons à de plus en plus de chiffres, nous commençons à obtenir de gigantesques incohérences Et ces incohérences géantes sont à l'origine du théorème de l'informatique C'est le but du programme d'informatique. Nous essayons simplement de trouver quel type de structure de données ou de techniques devons-nous utiliser dans chaque situation donnée afin de créer les algorithmes les plus efficaces possibles et de finir par accomplir les choses rapidement au lieu de dépenser du temps supplémentaire ou de ne même pas être en mesure d'accomplir ds parce que cela prendrait trop de temps Ce n'est donc qu'un petit exemple de cela. OK. 5. Big O: Maintenant que nous avons une bonne compréhension de N et de son fonctionnement exact, et que cela est lié à notre analyse des algorithmes, nous pouvons commencer à ajouter quelque chose à cela. Nous savons donc que c'est une façon de classer la rapidité d'exécution d'un algorithme, étant donné un certain nombre combien cela va-t-il prendre par rapport à ce nombre ? Alors, est-ce que cela va prendre juste le temps ? Donc, si c'était 1 000, est-ce que ça va être égal à 1 000 ou est-ce que ça va prendre environ n fois au carré, quand c'est 1 000, ça va être égal à 1 million Et c'est un type de classification vraiment important. Cependant, les programmes ne sont pas si simples. Ils ne se contentent pas de courir à une heure précise tout le temps. La plupart du temps, ils ont un lien. Ainsi, par exemple, peut-être que lors du chargement, il exécutera un n au carré, mais il exécute un in, puis il exporte un in dans le login Nous devons donc être en mesure d'examiner cela, d'examiner le programme et de classer le programme dans son ensemble. Ainsi, par exemple, dans ce programme, nous étudions toujours le pire des cas allons toujours au pire des cas, au carré Cependant, à certaines étapes, il fonctionnera plus vite. Et à cause de cela, nous avons en fait ce type de taux système ici, qui va classer les limites de notre notation en notation Alors allons-y en quelque sorte et jetons un coup d'œil à cela. Ils s' appellent Omicron là-haut. Vous avez Theta au milieu, puis Omega, et voici Omega en minuscules ici. Vous pouvez donc voir que ce sont des alphabets grecs, mais en mathématiques, nous utilisons souvent le grec parce que l' alphabet devient confus Nous utilisons donc le grec pour représenter les choses de manière symbolique. Et dans ce cas, chacun de ces symboles grecs représente symboliquement une limite Donc, ce que vous avez ici, c'est dessinons , par exemple, une borne juste au milieu. Et là-haut, c'est plus rapide. Je dirais donc que là-haut sera plus rapide, et qu'en bas, ce sera plus lent. Donc, notre première notation est le petit O, et vous pouvez voir que nous n'aimons tout simplement pas dire Omicron, comme une grosse notation Omicron qui Nous disons donc un petit grand O. Et si peu ici. Cela signifie simplement qu'il va être plus rapide, ce qui signifie que le programme sera toujours plus rapide que cette limite. Ainsi, par exemple, si notre borne était au carré, ici même, si nous avions le petit O de n au carré. Ici, nous verrons que cela signifie qu'il ne touchera jamais N au carré En fait, ce sera toujours plus rapide que n au carré. Il sera donc toujours juste au-dessus de cette ligne, mais plus vite que n au carré Donc, ce que nous pouvons faire, c'est que nous pouvons en quelque sorte utiliser pour déterminer la limite. Donc, le suivant, c'est que nous avons un grand O et un grand O signifie que ce sera plus rapide ou égal à. Cela signifie donc qu'il va toucher cette ligne ou être plus rapide. Ce sera donc au pire, et c'est quelque chose de très important ici. Cela signifie au pire. Ça va être au carré. Le suivant est Theta, ce qui signifie qu'il ne touchera aucune des deux Il ne va pas baisser, ni monter haut. Ce que ça va se passer, c'est exactement sur cette ligne. Donc, peu importe ce que cela va être au carré, ce sera juste le long de cette ligne quelque part Et puis la suivante est plus lente ou égale à. Nous avons donc celui-ci est Omega, et celui-ci est plus lent ou égal à. Il touche donc cette ligne, et c'est toujours plus lent. Donc, vous savez, nous sommes arrivés du troisième au quatrième ici, ici, nous l'aurions peut-être fait. C'est donc toujours plus lent que cela, ou égal à n au carré Donc, au mieux. Donc celui-ci est au mieux. Ça va fonctionner si tu le dis. Ainsi, par exemple, si nous écrivons n au carré de cette façon. Arrêtons-nous un peu, mais si n est au carré comme ça, alors nous comprenons que ce programme fonctionnera toujours au mieux, il s'exécutera au carré. Ce qui signifie que ça peut être pire que ça. Et puis en dessous, nous avons une valeur plus lente que, ce qui signifie que le résultat sera toujours inférieur à n au carré Il ne touchera jamais le carré, mais il fonctionnera moins bien que nSquared Alors pourquoi est-ce important ? Pourquoi voulons-nous nous concentrer sur celui-ci parmi toutes ces questions ? Et c'est parce que Big O dicte le pire des scénarios Et nous sommes préoccupés par le pire des scénarios car compte tenu de la probabilité et des statistiques, notre programme peut aborder le pire des scénarios à un moment donné, et nous voulons savoir sans aucun doute quel est ce pire scénario. C'est pourquoi nous utilisons le grand O. C'est au pire, qu' est-ce que ça va être. Et vous pouvez voir, je vais à nouveau faire apparaître le graphique ici. Lorsque nous avons cette idée, lorsque nous avons la capacité de dire quel sera notre programme, nous pouvons réellement commencer à la remplir. Donc, si nous avons, par exemple, peut-être un gros O de N. Nous comprenons qu'au pire, il y en aura. Cela peut donc être dedans, mais cela peut aussi être quelque chose de plus grand que dedans. Nous pouvons donc préparer tous nos diagrammes temporels, nos croquis et tout ce qui s'y rattache, partant du principe que cela ne se produira jamais ce côté de la ligne. Ça ira toujours de ce côté. Et c'est vraiment puissant parce que nous pouvons maintenant commencer comparer les pires scénarios des programmes, et nous pouvons commencer à constater que lorsqu' un programme évolue, par exemple, si nous avions un programme de connexion par rapport à un programme intégré, nous pourrions constater que lorsque celui-ci évolue, ce sera pire que celui-ci. Donc, décomposons les choses un peu, et nous verrons pourquoi certaines d'entre elles n'ont aucun sens Nous avons donc un programme qui s'exécute à Little O n squared, ce qui signifie qu'il est plus rapide que n squared Cela signifie donc que cela peut aller de n au carré à, en gros, il doit être juste plus rapide que cela Ce ne sera donc pas au carré, mais cela pourrait être plus rapide qu'au carré Et celui-ci est un peu comme un grand O. Mais le truc, c'est ce qu'on nous donne, donc c'est un petit O de N. Nous ne pouvons pas vraiment y toucher. Cela rend donc les choses un peu confuses. Cela nous donne une limite, mais cela ne nous permet pas de le voir facilement. Nous ne pouvons pas regarder cela immédiatement et nous dire  : « Oh, ça va prendre du temps ». Nous devons regarder ça et nous dire : « Oh, ça va aller plus vite que, mais nous ne savons pas vraiment où ». Et cela ne nous laisse pas vraiment beaucoup de marge de manœuvre. Et puis nous avons notre grande notation O. Et c'est ce que nous venons de passer en revue, c'est que nous pouvons regarder ça et nous dire : « Oh, au pire, il fonctionnera lors de la connexion ». Theta serait génial si nous pouvions toujours utiliser Theta. C'est égal ou parfois utilisé comme moyenne, mais la plupart du temps, cela signifie égal à. Ce serait donc génial. Mais le problème est que les programmes ne s'exécutent pas toujours exactement le long d'une ligne. Parfois, ils peuvent s'exécuter, peut-être à un moment donné, exécutent un, mais à un moment donné, s'exécutent et se connectent, et ils vont n'importe où entre les deux. Theta est donc trop spécifique pour que nous puissions vraiment l'aimer. Et puis elles n'ont pratiquement aucun sens car elles ne nous fournissent pas beaucoup d'informations Pensez-y. Celui-ci, ici, c'est Omega. Donc, Omega a quadrillé. Cela signifie qu'il sera plus lent ou égal à Omega Squared, ce qui est, comme vous le dites, soit que notre programme fonctionnera au carré, soit qu'il sera plus lent Comment sommes-nous censés planifier en gardant cela à l'esprit ? Parce que le plus lent peut aller à l'infini. Cela pourrait être aussi lent que possible, et nous ne serions jamais en mesure de nous y préparer car nous n' aurions jamais de limite. Nous dirions : « OK, donc ça va juste courir à quelle vitesse ça pourrait prendre n au carré, ça pourrait prendre une valeur factorielle, ça pourrait prendre l'infini Cela ne nous aide pas à analyser le programme parce qu'il a ce côté infini. Et exactement la même idée avec le petit Oméga ici aussi, c' est qu'il part à l' infini par le mauvais côté, ce qui ne nous aide pas. Ils nous aident donc parce que le mauvais côté, c'est je vais m'y attarder un peu et faire un peu plus de place. Ils nous aident donc parce que c'est le mauvais côté. Donc, disons qu' ici c'est à l'infini. Cela nous donne une limite. Quoi qu'il en soit, ça va être au pire ici, mais ça pourrait être mieux. Et on s'en fout. Par exemple, s'il revient et qu'il exécute cette constante, c'est bon. C'est parfaitement bien. Cela signifie que nos programmes fonctionnent parfaitement. Bien sûr. Mais nous pouvons nous y préparer. Cela signifie simplement que notre programme va s'exécuter plus rapidement que prévu. Ce que nous pouvons faire alors, c'est simplement prévoir le pire des scénarios. Cependant, si vous passez de l' autre côté de cette ligne, vous ne pouvez pas prévoir l'infini. C'est pourquoi Big O est si important, c'est la plus utile de toutes ces notations Cela nous donne le pire des scénarios. Prenons donc un exemple de la façon dont nous pourrions appliquer cela à un problème particulier. Donc, en général, vous utilisez toujours le pire des scénarios, c'est-à-dire à quel moment du programme, ce sera le plus inefficace Donc ici, par exemple, disons que nous avions un grand O de n au carré Nous avions un gros numéro de connexion. Un grand O de N puis un grand O de temps constant. Ils sont donc excellents ici. Mais le fait est que quoi qu'il arrive, nous serons toujours bloqués par ce type Et c'est parce que notre temps de chargement ici est exprimé au carré, ce qui signifie que ce programme va se connecter au carré, plus la première, ce qui me permet de le garder constant ici . Nous allons opter pour plus un. Et vous vous demandez peut-être pourquoi je fais ça ? Et c'est parce que vous pouvez réellement additionner chaque partie des étapes. Donc, parce que vous faites cette partie, alors, vous faites cette partie, puis vous faites cette partie, puis vous faites cette partie. Vous pouvez donc les additionner tous ensemble. Et je me souviens de ce que nous faisions auparavant lorsque nous parlions façon dont nous essayons de voir un programme tel qu'il va vers l'infini. Donc, si nous examinons ce chiffre, lequel d'entre eux dépassera les autres lorsque nous atteindrons l'infini ? Eh bien, par exemple, mettons-le à 1 million. Quelle est la signification de 1 million, ce qui sera le verset 1 million, le verset, peut-être quelque part autour de 3 millions, verset 1 quadrillion ou peut-être 1 billion, six, un et 12 zéros Celui-ci va être nettement plus grand. Il s'agira d'une portion de plus en plus petite du nombre à mesure qu'il atteindra l'infini. Jusqu'au point où leur importance sera proche de zéro. Vous allez donc commencer à avoir, vous savez, un numéro Google, qui est 100 zéro plus peut-être 8 millions ici ou quelque chose comme ça. Et cela signifie que cette partie est totalement insignifiante pour le moment. Nous éliminons donc les plus faibles et le temps d'exécution de ce programme est au carré Ensuite, nous allons simplement cimenter cela avec un autre exemple ici. Supposons que nous ayons eu notre mot à dire, nous avions un grand O de n au carré. Grand O de n au carré. Big O doit dessiner le s ici. grand O de n est à nouveau au carré, et disons maintenant que nous avons un grand O de n en troisième. Et maintenant, ce que nous avons ici, c'est que nous avons n au carré plus n au carré plus Nous pouvons donc les combiner jusqu'à trois n carré plus n le troisième Et maintenant, souvenez-vous de ce dont nous avons parlé dans la dernière conférence sur la notation finale. Ça n'a pas d'importance. Le taux constant ici n'a pas importance, car à mesure que nous avançons dans l'infini, il devient de moins en moins significatif jusqu'à ce qu'une fois que nous atteignons un nombre suffisamment élevé, il devienne pratiquement nul. Nous pouvons donc rayer celui-ci. Nous avons donc maintenant n carré plus n tiers. Et puis, bien sûr, celui-ci va décoller bien plus haut que l'autre. Notre programme finit donc juste en troisième position. Et comme ce sont toutes de grosses notations O, nous savons que dans le pire des cas, notre programme s'exécutera à la troisième place, qui signifie que nous avons maintenant cette limite de troisième et que l'infini du temps d'exécution se déroulera de cette façon Et maintenant, nous pouvons le planifier dans le pire des cas, nous allons avoir la troisième place, et nous pouvons tout planifier pour revenir à temps constant parce que maintenant tout ce que nous avons, c'est juste cette limite ici. Nous comprenons que, vous savez, si nous saisissons 1 million de données, cela risque de ne pas fonctionner. Peut-être que nous pouvons envisager de le faire, mais cela nous donne un point de départ. Cela nous donne un moyen de le comparer aux autres. C'est donc une grosse notation O. est très important et avec le temps, vous allez commencer en gros, C'est très important et avec le temps, vous allez commencer en gros, le simple fait de pouvoir regarder cela deviendra une seconde nature . Vous ne verrez jamais ces autres trop souvent. Vous verrez parfois celui-ci s'il indique qu' un certain point d'un programme est égal à cette durée d'exécution, alors vous verrez celui-ci. Mais à part ça, ces deux-là ne le verront probablement jamais et vous ne verrez probablement jamais Little Mercon Two Donc, ces notations ici , mémorisez-les en quelque sorte, comprenez ce qu'elles signifient, et vous devriez être prêt à partir Vous allez commencer à comprendre beaucoup plus de types de documents informatiques. 6. Monde réel: Maintenant, nous avons appris beaucoup de théorie. Allons-y, prenons du recul et passons en revue quelques analyses de code du monde réel. Maintenant, je ne vais pas utiliser de code complexe ou quelconque que vous devez connaître ici. Tout est un pseudocode, et je vais vous l'expliquer à chaque étape comme si vous n'aviez jamais touché au code auparavant car c'est ainsi que je veux expliquer tout ce type de cours : nous examinons la théorie qui sous-tend tout, pas le Cependant, l'appliquer à quelque chose du monde réel peut vous aider à connaître, en quelque sorte à comprendre certains des concepts, et c'est pourquoi nous le faisons. Regardons donc simplement notre premier morceau de code. Je vais aller de l'avant et passer en revue tout ça ici. Donc, ce que nous avons, c'est écrit, je l'ai écrit en pseudo qui se lit en quelque sorte directement sur la langue, quelque chose que vous pouvez regarder et comprendre ce qui se passe. Donc, il est dit, pour chaque donnée de la liste de données. Nous allons donc créer une liste de données ici dans une seconde, imprimer les données à l'écran. OK, c'est assez simple. Supposons que nous saisissions ici une donnée, une liste de trois, deux, dix. Ensuite, nous irons à Buffalo. Il s'agit donc de trois nombres entiers et d'une chaîne. C'est ainsi que cela serait classifié techniquement, mais nous n' allons même pas y réfléchir. Il s'agit de quatre éléments de données. Ce que nous disons, c'est que pour chaque donnée, donc pour chaque donnée de notre liste, nous allons imprimer ces données à l'écran. Donc, dans notre situation ici, qu'est-ce qu'il y a là-dedans ? Eh bien, dans cette situation, en termes égaux, un, deux, trois, quatre, parce que nous avons quatre éléments de données. Donc, dans cette situation, n est égal à quatre. Voyons maintenant quelle en serait la durée d' exécution. Nous avons donc pour chaque donnée, puis nous l'avons imprimée à l'écran. Alors, d'accord, parcourons la liste ici. Allons-y avec notre première donnée. Notre première donnée est donc de trois. Nous en déduisons trois de notre taux de documentation ici. Donc, c'est zéro dans un tableau ou si vous voulez bien y réfléchir , c'est un, deux, trois, quatre. Les ordinateurs utilisent généralement zéro, un, deux, trois, c'est juste leur façon de fonctionner. Nous allons donc récupérer notre première donnée ici, puis nous allons l' imprimer à l'écran. Nous avons donc pris nos trois, nous les avons imprimés à l'écran. C'est donc une seule exécution. Notre temps de fonctionnement actuel est donc de un. Et maintenant, nous allons prendre les deux parce que nous descendons dans la liste. Donc, pour chaque donnée, nous avons abordé celle-ci. Alors maintenant, nous passons à celui-ci. Alors maintenant, nous en prenons deux et nous les imprimons à l'écran. Alors maintenant, notre écran ressemble à ceci. Et c'est donc une durée d' exécution supplémentaire. Il s'agit d'un seul environnement d'exécution. Et maintenant, nous imprimons notre prochaine donnée , qui est dix. Maintenant, nous en avons trois, deux, dix. C'est là une durée de fonctionnement supplémentaire. Et maintenant, nous imprimons des buffles, ce qui serait trois, deux ou dix buffles. Comme ça. Et cela représente une durée de fonctionnement supplémentaire. Parce que nous ne faisons que saisir les données et les imprimer Il n'y a aucun processus de réflexion particulier ici. Nous ne faisons que saisir, imprimer, saisir, imprimer, saisir, imprimer Et maintenant, si nous additionnons tout cela, nous verrons que cela donne un plus un plus un plus un, ce qui équivaut à quatre. Dans cette situation, notre durée d'exécution est donc de quatre, et vous verrez que notre durée d'exécution est égale au montant du débit ici. Et si nous pouvions y réfléchir une seconde en théorie , si nous avions 1 million de données ici, il n'y aurait à aucun moment du programme où nous aurions à toucher plus d'un million de données Donc, quoi que nous fassions ici, le runtime sera celui de notre n, ce qui signifie que nous avons ici un temps d'exécution de N. Dans ce cas précis, nous pourrions utiliser Theta comme n car il est en fait égal à n. Il n'y a aucune sorte de marge de manœuvre ici, mais nous allons simplement dire que c'est au pire qu'il sera dedans parce que c'est la notation que nous aimons utiliser Voici donc un exemple d'entrée, on appelle une boucle à quatre. Quatre boucles sont donc généralement un exemple d' entrée dans une situation. Passons à un problème un peu plus complexe ici. Alors permettez-moi de décomposer celui-ci également. Ce que nous avons ici, c'est écrit, pour chaque donnée d'une liste de données. Cela signifie donc qu'au lieu de l'appeler data maintenant, chaque élément de donnée d'une liste y figurera. Vérifiez si les données figurent dans la liste. Nous allons donc utiliser chaque donnée de la liste de données, si n est égal à W, affiche vrai. Allons-y et décomposons un peu celui-ci également. Reprenons le même exemple que précédemment, à savoir trois, deux, dix Buffalo. Comme ça. Et dans cette situation, notre gain est toujours égal à quatre. Maintenant, ce que nous allons faire, c'est examiner le premier problème. Jetons donc un coup d'œil à droite. Maintenant, disons que nous allons récupérer chacune de ces données, donc nous allons récupérer les trois, et c'est fait. Et maintenant, pour chaque donnée de cette liste de données, vous pouvez voir que ces noms sont exactement les mêmes. Cela signifie donc qu'il s' agit de la liste de données. Nous sommes en train de vérifier la présence de ces deux éléments. Nous avons donc nos trois. Nous nous sommes fait saisir les trois. Et maintenant nous essayons de vérifier si ces trois points d' ici sont équivalents à quelque chose d'ici. Et le seul moyen d' y parvenir est la force brute. Nous allons donc prendre ces trois points. Nous allons le vérifier avec le premier. Nous allons le vérifier avec le second. Nous allons vérifier cela avec le troisième. Nous allons vérifier cela avec le quatrième. Il va donc y avoir une, deux, trois ou quatre opérations. Alors disons-le, genre, très loin d'ici. Nous avons les trois. Nous avons pris nos trois points, et maintenant nous sommes en train de vérifier , est-ce que c'est égal. Permettez-moi de le réduire un peu, car le graphique sera un peu plus grand. Nous disons donc que trois égal au premier élément de nos données, est égal au premier élément de nos données, qui sera à nouveau le trois parce que nous ne leur avons pas dit de commencer par un chiffre qui ne l'est pas ou par des choses fantaisistes de ce genre. Nous sommes juste en train de vérifier cette liste une deuxième fois. Nous avons donc nos trois points, et nous vérifions s'ils sont égaux au premier. Alors, est-ce que ça fait trois ? Oui, c'est le cas. Cela imprimera donc un vrai message. Et cela n'a nécessité qu'une seule opération. Maintenant, est-ce que nos trois sont égaux à deux, non. Nous n'imprimons donc rien. C'est une opération. Est-ce que nos trois sont égaux à dix. Ce n'est pas le cas. C'est donc une opération. Est-ce que nos trois sont égaux à Buffalo ? Ce n'est pas le cas. C'est donc une opération. Et maintenant on en a fini avec les trois. Nous sommes donc passés à autre chose. Nous nous sommes occupés des trois. Créons-en donc un deuxième ici. Voyons voir que T one sera celui auprès duquel nous allons vérifier. Ce sont exactement les mêmes, mais je veux juste que cela soit un peu plus visuel pour vous tous. Nous en avons donc fini avec les trois. Passons donc aux deux maintenant. Alors, deux font trois ? Ce n'est pas le cas. C'est une opération. Est-ce que deux font deux ? C'est le cas. C'est une opération. Est-ce que deux font dix ? Ce n'est pas le cas. C'est une opération. Est-ce que deux équivalent à Buffalo ? Ce n'est pas le cas. C'est une opération. Et puis redescendons encore une fois la liste. Est-ce que dix est égal à trois ? Ne le fait pas ? C'est une opération. Est-ce que dix est égal à deux, non. C'est une opération. Est-ce que dix est égal à dix. C'est le cas. C'est une opération. Est-ce que dix est égal à Buffalo. Ce n'est pas le cas. C'est une opération. Est-ce que Buffalo ? Je vais juste l'abréger en B ici, donc je ne veux pas continuer à écrire Buffalo. Est-ce que Buffalo est égal à trois ? Ce n'est pas le cas. C'est donc une opération. Est-ce que Buffalo est égal à deux ? Ce n'est pas le cas. C'est donc une opération. Est-ce que Buffalo est égal à dix ? Ce n'est pas le cas. C'est donc une opération. Est-ce que Buffalo est égal à Buffalo ? C'est le cas. C'est donc une opération. Et maintenant, si nous additionnons tous ces taux d'augmentation ici, nous allons voir que ce sera un, deux, trois, quatre, cinq, six, sept, huit, neuf, dix, 11, 12, 13, 14, 15, 16. Donc, dans cette situation, notre entrée était de quatre, mais notre temps d'exécution était d'environ 16. Et qu'est-ce que cela en ressort ? Eh bien, il s'avère que c'est au carré. Supposons donc que si nous en prenions quatre et que nous les mettions au carré, cela équivaudrait à 16 Et en théorie, nous pouvons également y réfléchir. Si nous portions ce chiffre à cinq, nous en aurions non seulement cinq supplémentaires ici, mais nous devrions également le multiplier, car maintenant nous devrions également en cocher un autre. Donc, pour chaque instance, nous en aurons cinq et nous en aurons cinq autres, qui les quadrillent. Donc, dans cette situation, notre temps d'exécution est au carré Et la raison en est que même si nous avons deux ou quatre boucles, il existe ce que l' on appelle la nidification. Nous avons imbriqué une boucle à quatre dans une autre boucle à quatre. Donc, cette partie ici. Dessinons ça en rouge. Cette partie est là. Bien que cette partie intérieure soit également dedans. Donc, ce que nous faisons, c'est prendre en compte l'extérieur. On le multiplie par le in à l'intérieur, et on obtient le carré Ce sera donc notre dernier délai pour faire face à cette situation. Donc, comme je l'ai dit, ce cours n'est pas principalement consacré écriture de code ou à l'outworithme, mais il définit tout de même la théorie, mais j'ai pensé que cela pourrait vous aider à vous montrer de quoi nous parlons depuis tout ce temps, comment le code peut être réellement analysé afin que nous puissions comprendre ces Et vous pouvez voir que quoi qu'il arrive, nous venons d'apprendre quelque chose de très important. Il y aura toujours quatre boucles, mais quatre boucles imbriquées le seront toujours, quel que soit le nombre de boucles imbriquées Donc, si celle-ci en imbriquait une troisième, ce serait une formule à n carrés, et vous commencez à obtenir très gros nombres pour commencer à vérifier toutes ces informations J'espère donc que cet exemple pratique vous a permis de mieux comprendre ce concept. 7. Exemple de structure de données: Passons maintenant à un exemple un peu plus concret. Et nous allons discuter de la différence entre un tableau et une liste et de la façon dont cela va être un tableau et une liste et de la façon dont lié à ce que nous avons appris ? Et ce que nous avons appris, c'est l'évolutivité, stockage des informations et la façon dont elles réagissent avec le temps d'exécution à mesure que nous obtenons de plus en plus d'informations Donc, avec ces deux exemples, nous allons examiner un tableau, et nous allons examiner une liste, et nous allons examiner leur accès et ajouter des informations sur les temps d'origine de ces tableaux Dans ce contexte, nous allons examiner comment cela évolue-t-il au fil du temps avec ces deux méthodes différentes de stockage des données ? Comment pouvons-nous utiliser cette analyse pour déterminer solution que nous aimerions utiliser à l'avenir ? Jetons un coup d'œil. Nous allons faire un aperçu de ce que sont ces structures de données. Il n'est pas nécessaire de connaître beaucoup d'informatique pour suivre cette leçon, mais il sera très important d'ajouter un élément concret à ce que nous avons appris. La première structure de données que nous allons examiner ici est donc le tableau. Donc, avec un tableau, ce que nous faisons essentiellement, c'est récupérer une donnée continue de notre mémoire Maintenant, le processeur va essentiellement nous indiquer où nous allons le récupérer Cela peut être le RAM ou le cache. C'est peut-être le disque dur. Ça n'a pas d'importance. Dans ce cas, il s'agit de mémoire, et c'est tout ce que nous devons savoir. Donc, avec la mémoire, en gros, nous séparons toute notre mémoire en petits blocs de données. Lorsque nous demandons une matrice au processeur, il trouve un petit morceau de mémoire pour nous. C'est continu et cela peut correspondre à ce que nous demandons. Dans ce cas, nous demandons ici quatre éléments de données. Il s'agit donc d'une taille de tableau de quatre. Maintenant, lorsque nous faisons cela, nous le créons, c'est continu, mais d'un autre côté, nous n'y avons pas accès, ce qui signifie que si nous devons augmenter la taille de ce tableau, nous devons créer un tout nouveau tableau et y copier des éléments. Et ce sera l'inconvénient. Passons donc en revue nos deux points ici, notre accès et notre publicité. Ainsi, chaque fois que nous accédons à des données sous forme de tableau, ce qui est génial, c'est que ce soit en temps constant, car chaque fois que nous les demandons, c'est continu. Par conséquent, nous pouvons demander des données très spécifiques ici. Donc, si nous devons déterminer, si nous devons saisir quelque chose à la deuxième ou dans cette position, la troisième place du tableau, qui est indexée par deux Cela signifie simplement que tout en informatique est un indice zéro, donc la première colonne est zéro, pas un. Nous pouvons utiliser ce petit taux de formule, qui fonctionne dans pratiquement tous les langages de programmation. Cela signifie simplement saisir cet élément juste là. Il va nous le rendre en temps constant. Il va simplement recracher ce qui est là en temps constant. Nous pourrions avoir des tonnes et des tonnes d'informations. Cela pourrait être long de 2000. Cela peut être long de 3 000. Cela pourrait être 20 000, 30 000$ et ainsi de suite. Et si nous le mettons ici, nous le retrouverons à temps constant à chaque fois. C'est ce qui permet à notre réseau d'avoir accès au pire des scénarios, à temps constant. Ce sera toujours constant. Maintenant, voici le problème. Souvenez-vous quand j'ai dit que lorsque nous ajoutons à la fin de tout cela, si nous avons atteint la limite de notre tableau, nous avons rempli le tableau, nous devons demander un tout nouveau tableau, ce qui signifie que le module de mémoire est basique et qu'il va tuer notre ancien tableau pour en trouver un plus grand dans lequel nous pouvons mettre des informations. Eh bien, pour nous assurer de ne pas perdre nos anciennes données, nous devons copier chaque élément. Plus d'un à la fois. Donc, si nous avons 300 000, 3 millions, 3 milliards d'entrées, elles doivent toutes être copiées, et chaque donnée contenue ici doit être modifiée. Et c'est très, très important car cela signifie qu' à mesure que la taille de notre tableau augmente, le nombre d'opérations que nous devons utiliser augmente également. Et il augmente de façon linéaire, ce qui signifie que nous avons le pire scénario de O jusqu'à la lors de l' ajout à un tableau. Alors maintenant, nous avons assez bien couvert le tableau. Jetez un coup d'œil à notre autre structure de données. La liste. La liste est intéressante parce que ce que nous faisons avec une liste, c' est essentiellement accéder à notre donnée ici. C'est ce que nous demandons. Et au lieu de nous fournir une donnée continue, cela nous donne essentiellement un élément à la fois. Nous pouvons donc en demander un, il sera là. Nous en demandons une autre. Il crée un pointeur, puis se dirige vers cette pièce. Nous en voulons un autre. Eh bien, ça va aller ici, et ainsi de suite. Et vous pouvez voir qu'il n'y a pas de méthode vraiment définie pour le faire. Je suis sûr que, vous savez, les modules de mémoire avancés et tout le reste sont efficaces, mais ils ne seront pas continus. Ils seront présents partout de la manière la plus efficace qui lui semblera appropriée. Cela signifie que si nous essayons d'accéder à nos informations et que nous voulons récupérer cette information ici, eh bien, regardez ce gâchis ici. Nous devons suivre le point. Nous devons donc commencer ici et aller ici. Alors ici, puis ici, puis ici. Et, oh, voici notre donnée. Cela signifie que lorsque nous accédons à nos données, si nous essayons de trouver quelque chose dans la liste, quelque chose de plus éloigné, et, vous savez, cela peut être quelque chose comme un chiffre, une lettre, une phrase, une image, n'importe quoi. Mettons simplement PE ici. Pour accéder à P, nous devons parcourir la liste complète des liens pour le trouver. Quel est donc notre temps d'accès ? Eh bien, cela ne semble pas constant. semblerait qu'à mesure que le nombre d'éléments augmente, notre temps d'accès augmente également, Il semblerait qu'à mesure que le nombre d'éléments augmente, notre temps d'accès augmente également, ce qui semble être un accès dans le pire des cas, si le temps d'entrée sera linéaire. Maintenant, la liste a l'avantage d'ajouter, tant que nous conservons ce que l' on appelle un pointeur de retour, qui est essentiellement une donnée que nous mettons à jour pour obtenir une flèche directe vers le bas. Donc, si nous ajoutons une nouvelle pièce, nous prenons simplement cette flèche et nous la déplaçons simplement vers la nouvelle pièce. Si nous maintenons cela à jour, ce qui n'est qu'une seule opération constante, eh bien, ajouter des données à cette opération revient à un temps constant. Ce sera toujours exactement la même opération. Nous pointons vers le verso et nous ajoutons à la suivante. En fait, dans ce cas, nous ne le savons pas, oui, nous le faisons. Nous avons donc le pointeur arrière ici. Donc, si nous devons effectuer un ajout au dos, nous suivons le pointeur de retour jusqu'à la fin de la liste de liens, puis nous ajoutons simplement un nouvel élément, puis mettons à jour le pointeur vers le nouvel élément. C'est une opération constante. Même s'il y a quelques étapes, ce sera toujours pareil. S'il y a 1 milliard de pièces ou une seule pièce, exactement les mêmes choses doivent se produire. Nous suivons le pointeur de retour, nous en ajoutons un nouveau, puis nous y insérons nos données. Cela signifie donc que notre temps d'ajout sera en fait constant. Nous pouvons donc maintenant voir qu'avec ces deux structures de données, nous avons deux possibilités différentes de solution ici. Si nous avons besoin d'un temps d'accès rapide, pensez à la liste dans votre téléphone, votre liste de contacts sur votre téléphone. Nous avons besoin d'un temps d'accès rapide pour cela. Vous ne voulez pas trouver quelqu'un dans votre liste de contacts et devez attendre qu'il recherche toutes les autres données. Cela ne semble pas du tout très efficace. Ce serait stupide. Et nous n'en ajoutons pas très souvent. Vous savez, nous ajoutons un contact ici et là, mais ce n'est pas quelque chose que nous ajoutons continuellement. La matrice pourrait donc être la meilleure solution à ce problème particulier. Maintenant, avec une liste, nous avons peut-être une opération qui doit stocker de nombreux éléments au fil du temps, mais elle n'a presque jamais besoin d'y accéder. Nous avons donc besoin d'un temps supplémentaire constant, vous savez , mais nous n'avons pas vraiment besoin de beaucoup de temps d'accès. Eh bien, alors nous examinerions une liste pour cette solution. Les choses que nous apprenons dans ce domaine peuvent donc être utilisées pour trouver de meilleures solutions à nos problèmes. Et dans ce cas particulier, il y a des problèmes de stockage dans la programmation informatique. Mais cela peut également s'appliquer à d' autres domaines du monde informatique et à la vie réelle. La solution dont vous disposez est évolutive. Et avec cela, nous pouvons voir lesquels le sont et lesquels ne le sont pas. 8. Vidéo de projet: Maintenant que nous avons passé en revue la notation, le bigot et toute la mise à l'échelle qui se produit entre les deux Le projet ici sera de prendre tout ce que vous avez appris et analyser quelque chose dans votre vie et de nous dire quelle en est la procédure, puis quelle en est la signature temporelle. Cela peut donc être lié à l' informatique. Vous pouvez créer un algorithme, un algorithme de recherche ou réfléchir, vous savez, façon dont une demande d'ami sur Facebook pourrait fonctionner ou quelque chose comme ça, mais cela peut aussi être simplement une question d' observation autour de vous Cela peut être je l'ai dit au début du cours, comme un classeur ou la façon dont quelqu'un pourrait rejoindre un membre de votre organisation ou comment vous pourriez effectuer une recherche et trouver quelque chose dans un grand ensemble de données ou un groupe de personnes ou quoi que ce soit de cette nature. Je veux que vous soyez créatifs , que vous analysiez simplement le monde qui vous entoure avec les connaissances que vous avez apprises et que vous les partagiez. C'est un exercice assez amusant, et c'est intéressant de voir que nous ne faisons essentiellement que des mathématiques appliquées chaque fois que nous programmons ou que nous travaillons avec ce type de théorie des mathématiques elle-même. Si nous l'appliquons, nous apprenons comment le monde fonctionne et fonctionne, puis nous nous y intéressons. C'est donc le but de ce projet. Pour créer une pensée critique, puis pour l' analyser et renforcer en quelque sorte ce que nous avons appris. Je suis vraiment impatiente de voir ce que tout le monde va proposer, et je serai dans la section des projets pour y répondre. Donc, Sea there, merci à tous d'avoir participé à ce cours.