ENCEINTE: Très bien, c'est CS50. C'est la fin de la troisième semaine, et si vous n'avez pas pris avantage déjà, savent qu'il y aura déjeuner ce vendredi comme d'habitude, où vous pouvez profiter de la bonne conversation et de la nourriture à feu et de glace avec une partie de sa CS50 le personnel et les camarades de classe. Rendez-vous à l'adresse ici. Maintenant vous pouvez rappeler, ou vous pourrait bientôt se familiariser avec, ces choses ici, qui sont donnés à la fin du semestre pour de nombreuses classes. Livres bleus soi-disant examen, dans lequel vous écrivez vos réponses aux examens. Maintenant, je dois ici 26 comme livres bleus, sur chacun d'entre eux est écrit un nom, de A à Z. Et en effet les noms sont aussi simple que cela, un à Z. Et l'un des les buts fixés aujourd'hui va être de continuer ce nous avons commencé le lundi, ce qui n'est pas tellement regardant le code, mais vraiment regardant idées et la résolution de problèmes. Un des buts et promesses de ce cours est de vous apprendre à penser plus attentivement, plus méthodique, et de résoudre les problèmes de manière plus efficace. Et en effet, nous pouvons le faire vraiment sans même toucher une ligne de code. Donc, j'ai un couple d'éléphants jusqu'à aujourd'hui, orange et bleu, si nous pouvions obtenir un bénévole, peut-être de plus loin que d'habitude. Que diriez-vous là, venez nous voir. Le but de ce qui va être à aider ainsi administrer cet examen ici. Quel est votre nom? PUBLIC: Mary Beth. ENCEINTE: Mary Beth, venez sur place. Laissez-moi le micro là pour vous. Ravi de vous rencontrer. PUBLIC: Ravi de vous rencontrer. ENCEINTE: Très bien, donc j'ai ici bleu livres de A à Z, et je vais faire semblant que J'ai l'un des étudiants, et ils viennent dans un peu au hasard à la fin d'un bloc d'examen de trois heures, donc ils se retrouvent dans une certaine ordre semi-aléatoire comme ça. Maintenant, votre travail dans un instant va à être-- c'est en fait la façon dont ils se tourné à la fin de la classe, le plus probable. Votre travail maintenant va être, tout à fait tout simplement, pour trier ces livres bleus pour nous de A à Z. PUBLIC: Oh, c'est va prendre une éternité. ENCEINTE: Et nous allons regarder comme vous le faites, pas de pression. PUBLIC: Non, pas de pression ou quoi que ce soit. ENCEINTE: Et pour le plaisir, Mettons en place une minuterie. PUBLIC: Tellement amusant, très amusant. Président: Je peux tenir le micro pour vous. Très bien, nous venons de doubler notre vitesse. Alors en attendant, laissez-moi de poser ce qui est va être la question pour Mary Beth est ce qu'elle fait, comment est- elle va de résoudre cela? Et en fait, vous pourriez ne pas avoir jamais pensé à quelque chose aussi simple que lorsque vous décrochez jusqu'à 26 livres de ce genre, qui ne avoir un naturel leur ordonnant. Quel est le processus que vous utilisez réellement? Est-il assez aléatoire juste choisir le premier que vous voyez et de le mettre à sa place? Ne vous déplacez d'abord vos mains autour de Vous cherchez un alors à la recherche de B? Avez-vous jetez un oeil à un paire de côte à côte et dire simplement, attendez une minute, ce n'est pas droite, puis échanger l'ordre? Nous avons déjà vu le lundi qu'il ya un certain nombre de façons dans lequel nous pouvons le faire, et En effet, comme nous nous approchons de la fin ici, Je voudrais peut-être prendre note de ce que Mary Beth fait. Nous avons quelques pieux, il semble, une plus gros, trois petits. PUBLIC: Je leur ordonnant quand je trouve deux lettres que je connais sont ensemble dans une séquence, Je les ai mis ensemble pour que je ne fais pas avoir à vous soucier de garder piste de toute une rangée de livres. C'est juste, oh, A est le premier, J'ai cette pile ici. ENCEINTE: Alors, presque comme une pièces de puzzle qui avoir le droit de forme correspondre les uns aux autres. PUBLIC: Presque, oui. ENCEINTE: OK, excellent. Et maintenant, chacun de ces piles est probablement triés? PUBLIC: Ouais. ENCEINTE: Très bien, de A à Z. Tous droite, félicitations, vous l'avez fait. Vous avez le choix. Blue? Très bien, je vous remercie pour cela. Alors Mary Beth ne propose ce que son approche était, mais ce qui est une autre approche comment vous pourrait aller sur le tri de ces choses? Qu'auriez-vous fait? Le record à battre aurait été une minute et 50 secondes ou plus, ainsi que ceux que j'ai oublié de compter. Qu'auriez-vous fait? Ouais? PUBLIC: Prenez la pile. Commencer par le début. Vérifiez vos papiers. Et si le haut est plus élevé que, peut-être, ils sont, celui du bas est supérieur, puis les passer. ENCEINTE: OK, donc à partir en haut et en bas, et de travailler ensuite votre chemin intérieur comme ça, les échanger? OK, donc un peu similaire dans l'esprit de tri à bulles, mais en choisissant les extrêmes pas les paires adjacentes. Mais le court, c'est qu'il n'y a sûrement un tas de différentes façons nous pourrions le faire, et franchement, je pense que vous sorte de adopté quelques approches, non? Vous avez fait sorte de quatre piles triées, et alors effectivement les fusionnés. Et c'est, disons-le, un autre technique tout à fait. Vous n'avez pas le traiter comme un gros tas, vous avez divisé le problème en quatre quads, si vous voulez, et puis en quelque sorte les fusionner à la fin. Donc, nous allons examiner, en fin de compte, sinon comment nous pourrions le faire. Nous avons formalisé la notion de tri à bulles dernière fois, et tri à bulles rappel était une algorithme que nous avons visualisé avec huit de vos camarades de classe ici, apparemment triés au hasard au début. Et puis nous avons décidé par paires, si deux éléments sont hors d'usage, il suffit de les échanger. Donc, quatre et deux sont évidemment hors de commande, Donc, ces deux camarades de classe de changer de place. Et puis nous avons répété avec quatre et six, puis six et huit ans, à chaque itération, déplaçant vers la droite. Donc, étant donné huit personnes, combien de paires comparaisons que j'ai fait en marchant de de gauche à droite dans une telle itération? Combien de comparaisons? Sept, non? Parce que s'il ya huit personnes, mais vous avez la paire eux et vous garder en mouvement un bond vers la droite, vous n'allez pas avoir huit comparaisons parce que vous ne pouvez pas comparer un élément contre lui-même, ou il serait juste inutile, si vous avez sept. Ou, plus généralement, si nous avons n personnes, nous faire n moins 1 comparaisons avec tri à bulles. Donc, nous allons examiner maintenant comment bonne ou mauvais tri à bulles était réellement, et essayer de nous donner vocabulaire qui à des algorithmes de la critique de ce genre, et bientôt la nôtre. Ainsi, le premier passage à travers tri à bulles, la première fois Je suis de gauche à droite sur la stade, moi n moins 1 comparaisons pris. Et que ça va être mon unité de mesure, non? J'étais un peu parler et se promener, un peu rapide, un peu lent, donc compter mon nombre de secondes n'est pas particulièrement révélateur, mais le comptage du nombre de opérations que j'ai fait le lundi, comparaison de deux personnes, qui se sent comme une belle unité de mesure. Donc n moins 1 étapes de la première fois, mais alors qu'est-ce qui s'est passé après? Quelle est la seule tête d'un laissez-passer à travers une liste non triée autrement? Que pouvez-vous me dire à propos de l'élément qui était tout le chemin là-bas? Ouais? C'était le plus grand élément, non? Numéro huit, même si elle commencé ici, chaque fois que je son rapport contre un voisin, elle a gardé bouillonner vers la droite côté de la liste. Et en effet, c'est là que l'algorithme tire son nom. Maintenant, par cette logique, le nombre de comparaisons besoin que je fais sur le deuxième temps Je fais cette passe de gauche à droite? n moins 2, non? Il serait juste de perdre mon temps si je garder comparant huit contre quelqu'un d'autre parce que nous savons déjà elle était à la bonne place. Donc, c'est un peu d'une optimisation, de sorte que le passage suivant va être plus n moins deux étapes, où n est le nombre de personnes. Maintenant, vous pouvez sorte de extrapoler, même si vous n'êtes pas un informaticien, comment cela se termine. A l'issue de cet algorithme, probablement vous avez juste une comparaison gauche. Vous devez fixer le type de au début de la liste en cas de deux et un sont irrecevables et devrait être l'un et deux, si ce touche le fond à plus 1 comparaison finale. Maintenant, le point, point, point genre de vagues c'est mains de quelques-uns des plus juteux de détails, mais disons simplement aller de l'avant et de simplifier. Si vous vous souvenez de haute école, franchement, beaucoup d'entre vous eu livres de mathématiques qui ont un peu de feuille de triche sur le capot avant ou la couverture qui vous a montré sommations ce de la série comme ce finalement ajoutée jusqu'à. Dans le cas général, si vous avez un variables comme n, et en effet celui-ci, si vous regardé votre livre de mathématiques de la vieille école, vous verriez que ce fait ajoute à cette somme ici, n fois n moins 1 le tout divisé par 2. Donc pour l'instant je vais juste en définit cela est vrai, alors sur un acte de foi, c'est ce que cela résume jusqu'à, et nous avons pu prouver que, dans un cas plus général. Mais maintenant, nous allons étendre cela. Donc, nous allons multiplier ce, de sorte que c'est n carré, moins n, le tout divisé par 2. C'est vraiment n carré, divisé par 2, moins n plus de 2, de sorte que c'est tout beau et intéressant. Mais qu'advient-il si nous maintenant le plug-in d'une valeur? Supposons que je n'avais pas huit personnes, mais disent un million. Et un million seulement parce c'est un assez grand nombre, nous allons brancher que dans et voir ce qui se passe. Donc, si je branche un million dans cette formule Je vais me faire un million carré, divisée par deux, moins un millions d'euros, divisé par 2. Maintenant, qu'est-ce que cela va correspondre? Donc 500 milliards, moins de 500.000. Et si je fais effectivement que les mathématiques sur, que des moyens que le tri d'un million personnes atteintes de la sorte de bulle pourrait me prendre 499999500000 étapes ou des comparaisons à la fin, nous ne faisons que l'extrapolation. Cela se sent assez lent, mais franchement mesurer une entrée particulière comme ça, n'est pas du tout révélateur. Mais en effet, il ne suggère que n devient plus grand et plus large, cet algorithme sorte de se sent pire et pire, ou vous avez vraiment commencer à sentir la douleur de cette exponentiation, qui n carré, qui ajoute assez vite. Et ce détail n'est pas perdu sur les gens, en fait, Il ya quelques années, un certain sénateur qui était campagne, assis pour une entrevue avec Eric de Google Schmidt, PDG de l'époque, et a été contestée par une question un peu comme nous explorons aujourd'hui. Jetons un coup d'oeil. [VIDEO LECTURE] -Senator, Vous êtes ici à Google, et j'aime de penser à la présidence comme un entretien d'embauche. Maintenant, il est difficile d'obtenir un travail en tant que président, et vous allez à travers les rigueurs maintenant. Il est également difficile d'obtenir un emploi chez Google. Nous avons des questions, et nous demander à nos questions aux candidats, et celui-ci est de Larry Schwimmer. What-- que vous en pensez, je suis blague, c'est ici. Quel est le moyen le plus efficace pour trier un million de nombres entiers de 32 bits? -Well-- -Je Suis désolé, maybe-- Non, non, non. Je pense que le tri à bulles serait la bonne façon de faire. -Allez, Qui lui a dit cela? Je ne vois pas l'ordinateur la science dans votre arrière-plan. -We've Obtenu nos espions là-dedans. -OK, Nous allons demander un autre question de l'entrevue. [FIN LECTURE VIDÉO] ENCEINTE: Donc parler chiffres précis cependant, ne va pas être d'une grande utilité. Ce n'est pas une leçon de vie que de bulle sorte, donné un million entrées, pourrait prendre jusqu'à 500 milliards étapes. Vous ne pouvez pas vraiment généraliser aussi efficacement que de et prendre de bonnes décisions de conception lors de l'écriture des programmes. Alors concentrons-nous bien sur la façon dont nous pourrions simplifier ce résultat. Donc j'ai surligné en jaune ici le résultat au carré de n divisé par deux, si un million carré divisé par deux, et ensuite J'ai souligné ce la réponse ultime était une fois nous avons soustrait de n divisé par 2. Et la demande que je vais faire maintenant est, qui est le diable se soucie si vous soustrayez off un peu vieux n sur 2 lorsque le premier partie de cette formule est tellement plus grand? Il domine l'autre terme, n au carré divisée par 2 est tellement plus vaste, clairement, comme n devient grand comme un million, qui est-il vraiment une grande différence à la fin de la journée entre 500 milliards et 499 999 500 000? Pas vraiment. Et donc ce que nous allons faire comme les informaticiens est ignorer ces termes d'ordre inférieur et prendre quelque chose comme ça et vraiment juste simplifier à l' terme qui se passe à la matière. Les plus grands de nos ensembles de données obtiennent, le plus grand nos bases de données obtiennent, les pages Web plus nous devons rechercher, le plus amis que vous avez sur Facebook. Comme n est grande, plus nous sommes vraiment va se soucier de la plus grande terme à une telle analyse de les performances de nos algorithmes. Et je vais vous dire, vous savez quoi, tri à bulles est de l'ordre de grand O, de l'ordre de n au carré. Ce n'est pas exactement n au carré comme nous l'avons vu, mais qui se soucie vraiment sur ces petites conditions, et franchement, qui a vraiment se soucie si nous divisons par 2? C'est juste un facteur constant. Et est de 500 milliards contre 250 milliards vraiment un gros problème? Je ne pouvais tout simplement attendre un an, laisser mon ordinateur portable littéralement obtenir deux fois plus vite dans le matériel, et ce genre de différence juste disparaît naturellement avec le temps. Qu'est-ce que nous nous soucions est l'expression, la partie de l'expression qui va varier comme notre entrée devient de plus en plus grande. Et en effet, dans le monde réel, c'est ce qui se passe de plus en plus est des entrées à nos problèmes et algorithmes sont de plus. Donc grand O va être la notation, la notation asymptotique, que nous venons de utiliser comme des informaticiens pour décrire la performance, ou le temps d'exécution, d'un algorithme. Afin que nous puissions comparer les algorithmes sur des ordinateurs différents écrits par des personnes différentes, en utilisant une certaine mesure fondamentalement similaire comme le nombre de comparaisons que vous êtes faire, ou peut-être le nombre de swaps vous faites. Ce que nous n'allons pas compte est la quantité de temps qui passe sur l'horloge sur le mur en général. Qu'est-ce que nous n'allons pas à s'inquiéter est de savoir comment la quantité de mémoire vous utilisez aujourd'hui à moins, si c'est autre ressource que nous pourrions mesurer. Nous allons essayer de fonder nos analyses uniquement sur les opérations de base, les uns, franchement, que vous pouvez voir plus visuellement. Donc, avec quelque chose comme grand O n carré, je prétends que O n carré est une limite supérieure sur la soi-disant temps de tri à bulles en cours d'exécution. En d'autres termes, si vous voulu prétendre qu'il n'y a cette limite supérieure du nombre de les étapes d'un algorithme peut prendre, ça va être dans le grand O n carré dans ce cas, une limite supérieure. Que faire si je change le lieu histoire soit pas tri à bulles, mais de cette limite supérieure. Pouvez-vous penser à un algorithme que nous avons examiné déjà dont la borne supérieure, le maximum mesure du temps ou des opérations, serait, dit-on borné n par une fonction linéaire, pas une quadratique qui est courbé? Qu'est-ce que c'est un algorithme qui prend toujours plus que comme n étapes, ou 2n, étapes ou des étapes de 3n? Ouais? PUBLIC: Trouver l' plus grand nombre dans une liste? ENCEINTE: Parfait, trouver le plus grand nombre dans une liste. Si on me donne une liste de les gens, par exemple, chacun qui tient un certain nombre, quel est le nombre maximum des mesures qu'il doit me prendre, une personne raisonnablement intelligente, de trouver le plus grand personne dans cette liste? n, non? Parce que dans le pire des cas, où pourrait être la plus grande valeur? A droite, tout le chemin à la fin. Ainsi, dans le pire des cas limite supérieure, je pourrais avoir à aller tout le chemin ici et être comme, oh, voici le numéro huit, ou quelle que soit la valeur est. Maintenant, il serait tout simplement stupide si je continuais à aller, non? Vous recherchez de plus en plus des éléments si le dernier d'entre eux est là-bas? Alors sûrement, n est une limite supérieure. Je n'ai pas besoin de prendre plus de pas que cela. Alors que faire si la place j'ai proposé que il existe des algorithmes dans ce monde qui avoir un temps d'exécution qui est délimitée par le grand O de log n, log n? Où avons-nous vu cela auparavant? Ouais? PUBLIC: Dans le problème de l'annuaire téléphonique? ENCEINTE: Comme le problème de l'annuaire téléphonique. Quelle a été la mesure de la beaucoup de temps ou combien de larmes il ça m'a fait de trouver quelqu'un comme Mike Smith dans l'annuaire? Nous avons affirmé qu'il était log n, et même si inconnu ou il c'est un peu brumeux ce qu'est un logarithme ou exposant était, n'oubliez pas que log n désigne généralement le processus, dans ce cas, de diviser quelque chose de nouveau en deux, et encore, et de nouveau, et de nouveau, de telle sorte qu'il obtient de plus en plus petit que vous faites cela. Alors connectez-de n se réfère, bien sûr, à l'exemple du livre de téléphone, à la recherche binaire en théorie, lorsque nous eu les portes virtuelles sur le plateau, ou quand Sean était la recherche de quelque chose. S'il avait utilisé la recherche binaire, log n serait la limite supérieure de la quantité d' temps que prend. Mais ces algorithmes qui couraient dans log n assumé ce détail clé? Que la liste a été triée, non? Votre algorithme est erroné si votre entrée n'est pas triée, et pourtant vous utilisez quelque chose comme une recherche binaire parce que vous pourriez sauter droit sur l'élément sans se rendre compte qu'il s'agit bien là. Maintenant, ce que cela peut signifier, grand O d'un seul? Cela ne signifie pas que votre algorithme prend une et une seule étape, cela signifie simplement qu'il faut une nombre constant d'étapes. C'est peut-être une, c'est peut-être 10, c'est peut-être 1000, mais il est indépendant de l'ampleur du problème. Peu importe la taille n est, un algorithme de constante de temps prend toujours le même nombre de mesures. Alors, que peut-être un algorithme nous avons parlé ou tout simplement intuitivement que vient de vous que va toujours dans ce qu'on appelle la constante de temps? Ouais? PUBLIC: Ajouter deux nombres. ENCEINTE: Ajouter deux nombres, 2 plus 2 égale 4, c'est fait. Donc, cela pourrait fonctionner, quoi d'autre? Que diriez-monde plus réel, ouais? PUBLIC: Trouver l' première chose que dans une liste. ENCEINTE: Trouver le premier élément dans une liste, bien sûr. Nous avons effectivement parlé sur les tableaux déjà, Comment obtenez-vous à la premier élément d'un tableau, peu importe combien de temps l' tableau est en code C? Vous utilisez simplement comme le support notation zéro, bam, vous y êtes. Et en effet les tableaux, comme un côté, support chose généralement connue que l'accès aléatoire, accès aléatoire la mémoire, parce que vous pouvez littéralement sauter à un endroit quelconque. Nous pouvons le faire encore plus simplement nous pouvons revenir en arrière à la semaine zéro quand nous avons fait Scratch. Combien de temps at-il fallu pour l' dit bloc dans Scratch à exécuter? Juste le temps constant, non? Dis quelque chose, dit quelque chose, il n'a pas d'importance comment grandes rayures monde, il est toujours va prendre la même quantité de temps simplement dire quelque chose. Donc, c'est la constante de temps, mais quel est le revers de la médaille? Si tel était supérieure limites, si nous voulons pour décrire les limites inférieures de nos algorithmes durée? Près d'un meilleur des cas potentiellement, si vous voulez, si ces termes peuvent s'appliquer à mieux cas, pires, étuis moyenne plus en général, mais concentrons-nous seulement sur des bornes inférieures plus généralement. Qu'est-ce que c'est un algorithme qui a une borne inférieure de n étapes, 2n, ou des étapes ou des étapes de 3n? Certains facteurs de n étapes, c'est sa borne inférieure. Ouais? PUBLIC: Bubble sorte? ENCEINTE: Bubble sorte prend vous minimalement n pas, pourquoi? Pourquoi donc? Pourquoi devrait-il commencer à venir à vous intuitivement, même si ce n'est pas simplement encore? Ouais? PUBLIC: [inaudible]. ENCEINTE: Exactement. Dans le meilleur scénario possible de tri à bulles, et beaucoup d'algorithmes, si je vous remets huit personnes qui sont déjà triés, il serait insensé pour vous, l'algorithme, à aller et venir plus d'une fois, non? Parce que dès que vous marcher dans la liste une fois, vous devez réaliser, oh, je n'ai fait aucune swaps, cette liste est triée, sortie. Mais cela va vous prendre des mesures n. Et inversement, ce qui est une autre façon de penser? Tri à bulles est un oméga, pour ainsi dire, de n, parce que si vous regardez moins de n éléments, ce qui est la question fondamentale là-bas? Vous ne savez pas si c'est réglé, à droite. Nous les humains pourraient coup d'œil à huit personnes et être comme, oh, c'est réglé, Cela ne m'a pas pris les mesures n, mais il l'a fait. Vos yeux, même si vous nature de faire un grand champ de vision, vous avez regardé huit éléments, vous avez regardé huit personnes, c'est huit étapes efficacement. Et que si je marche dans l'ensemble faire la liste, je me rends compte, oui, triés. Si je m'arrête à mi-chemin de penser, tout à droite, il est assez triée jusqu'à présent, quelles sont les chances que ce n'est pas triée? Que les algorithmes ne va pas être correct. Peut être plus rapide, mais incorrect. Alors maintenant, nous avons un moyen de décrivant une baisse des limites, et que dire de la constante de temps? Qu'est-ce que c'est un algorithme qui a une faible lié à son temps d'exécution de celui-ci? 1 étape, 2 étapes, 10 étapes, mais constant, indépendant de n, la taille de l'entrée? Oui, à l'arrière. PUBLIC: Printf? ENCEINTE: Qu'est-ce que c'est? PUBLIC: Printf? ENCEINTE: Printf. OK, bien sûr. Donc, il faut un nombre fixe d'étapes. Et je dois maintenant-- maintenant que nous parlons de code C et pas Scratch, quelque chose comme par exemple, la fonction printf, nous devrions commencer à obtenir prudent. Parce que printf ne prend entrée, c'est une chaîne, et les chaînes n'ont techniquement longueur. Donc, si nous voulons maintenant prendre sur vous, si cela ne vous dérange pas, techniquement, nous pourrions soutenir que printf ne prendre une entrée de longueur variable, et sûrement cela peut prendre plus temps pour imprimer une chaîne de cette longue, de cette longueur. Alors que faire si l'on considère que la tri et de recherche des exemples? Qu'est-ce à propos de Mike Smith dans le téléphone livre, ou recherche binaire plus généralement? Dans le meilleur des cas, ce qui pourrait arriver? J'ouvre le livre de téléphone et, bam, il ya le numéro de Mike Smith. Je peux l'appeler tout de suite. Pris un peu, peut-être deux étapes, mais un nombre constant d'étapes si je eu de la chance. Et franchement, nous avons vu sur Lundi un camarade de classe être assez chanceux deux fois de suite. Et c'était en effet constant fois en baisse limites sur l'algorithme en question pour trouver le nombre 50 derrière ceux fermée portes. Maintenant, en passant, si vous découvrez que les deux grand O, la limite supérieure, et l'oméga, la limite inférieure, sont l'un dans le même, que C'est la même formule à entre parenthèses, vous pouvez également dire, juste pour être de fantaisie, que quelque chose est en thêta de n ou thêta d'une autre valeur. Cela signifie juste quand grand O et oméga sont les mêmes. Maintenant, qu'en est-il de sélection sorte? Nous allons utiliser ce nouveau vocabulaire. En sélection sorte, ce sont nous faire encore, et encore, et encore? J'allais en arrière à travers la liste, à la recherche de qui? Le plus petit nombre. Alors, comment de nombreuses étapes, comment de nombreuses comparaisons ai-je avoir à faire afin de déterminer qui le plus petit élément de la liste est? n moins 1, non? Parce que si je viens de commencer par celle que je suis donné et je commence à lui comparer, alors lui ou elle, lui ou elle, lui ou elle, je ne peut lier les éléments ainsi que n moins une fois. Donc, la sélection se sorte de la même n moins 1 étapes de la première heure. Combien de pas faut-il pour trouver le deuxième élément le plus petit? n moins 2, parce que je suis étant muet si je regarde toujours les mêmes personnes encore si je l'ai déjà choisi ou elle et les mettre à leur place. Et la troisième étape, n moins 3, puis n moins 4. Nous avons vu ce modèle avant, et en fait sélection sorte similaire a une borne supérieure de n au carré si nous le faisons jusqu'à ce que la somme. Quelle est sa limite inférieure, la sélection sorte? Au minimum, combien sélection de must de temps sorte prendre, comme nous l'avons défini le lundi? Proposer des deux options. C'est peut-être n, comme avant. C'est peut-être n carré, comme il est maintenant que la limite supérieure. PUBLIC: n carré. ENCEINTE: n carré. Pourquoi? PUBLIC: Parce que vous avez à définir [inaudible]. ENCEINTE: Exactement. Au moins que je l'ai définie sélection sorte il était assez naïf, continuez, trouver le plus petit élément. Allez encore une fois, trouver le plus petit élément. Allez encore une fois, trouver le plus petit élément. Il n'y a pas de genre l'optimisation de là que pourraient me laisser avorter après seulement n de marches. Donc, en fait, la sélection sorte, l'oméga de n carré. Qu'en est-il du tri par insertion, où j'ai pris qui m'a donné, et puis je lui laissais ou son au bon endroit? Puis je me rendis à la deuxième personne, lui balancé au bon endroit. Ensuite, la personne suivante, flac lui au bon endroit. Notez que ceci est très linéaire, pour ainsi dire. Je suis une ligne droite, je suis ne va-et-vient, Je n'ai jamais regarder en arrière vraiment, mais ce qui se passe quand je l'ai insérer ou elle dans le début de la liste que nous avons fait le lundi? Ce qui se passe? Ouais? PUBLIC: [inaudible]. ENCEINTE: Ouais, était la capture, non? Vous vous souvenez sans doute de vos camarades de classe, si elles ont été faire aucun mouvement avec leurs pieds, c'était une opération. Donc, si il y avait trois personnes ici et la nouvelle personne appartenait loin là-bas, sur une longue étape comme celle-ci, bien sûr, il ou elle pouvait aller jusqu'à la fin. Mais si nous pensons à un ordinateur et un réseau de mémoire, ces gens vont d'avoir à mélanger sur pour faire place à cette personne. Et pour que n moins 1 tergiversations, n moins deux tergiversations, n moins 3 tergiversations est juste un peu passe derrière moi, pas en face de moi comme avant, dans un certain sens. Maintenant, en passant, et comme vous pourriez avoir vu en ligne si vous commencez à fouiller sur sortes, il ya tant de ceux différents là-bas, certains d'entre eux mieux que d'autres. En effet, c'est une bogosort c'est le genre de plaisir à regarder. Bogosort prend un ensemble de numéros ou dire un jeu de cartes, les mélange de façon aléatoire, et vérifie si ils sont triés. Et si non, le fait encore. Et si non, le fait encore. Si non, le fait encore. Incroyablement stupide. Et en effet, si vous lisez comme l'article de Wikipedia, son surnom est une sorte stupide. Il finira par travailler, je l'espère, suffisamment de temps, mais ce laps de temps pourrait prendre un certain temps. Donc, les choses de la vitesse de si je pouvais, laisser à partir de l'exemple de Mary Beth plus tôt, en ayant un peu plus d'éléments, mais deux autres processeurs. Deux personnes, si vous ne me dérangerait pas vous joindre à moi. Comment environ 1 ici, et nous allons go-- personne là-bas? Personne là-bas? Dáccord. Vous avec le noir chemise, oui, allez vers le bas. Très bien, quel est votre nom? PUBLIC: Peter. ENCEINTE: Qu'est-ce que c'est? PUBLIC: Peter. ENCEINTE: Peter, David, ravi de vous rencontrer. Très bien, nous avons Peter ici, si vous envie de venir sur la table ici. Et quel est votre nom? PUBLIC: Elena. ENCEINTE: Elena. OK, nice to meet you. Elena répond Peter. Peter, Elena. Et nous aurons besoin Andrew ici aussi, s'il vous plaît. Et votre défi va être pour trier un jeu de cartes. Et si familier, pont de cartes devrait en fin de compte trier un petit quelque chose comme ce que nous ferons les clubs, alors les piques, les coeurs et diamants, de l'as comme un, tout le chemin jusqu'à roi. Les cartes que je vais vous donner vont être 52 en quantité. Nous allons similaire fois que vous, dans un instant. Nous allons jeter Andrew sur l'écran ici, de façon à regarder comme vous le faites. Et de sorte que l'intégralité de cette est d'autant plus visible, ce sont les cartes que j'ai eu sur Amazon. Donc, ils sont déjà au hasard trié, et nous allons vous chronométrer. Et nous allons keep it real cette fois, donc nous allons essayer de faire pression sur vous parce que sinon ce sera être fastidieux rapidement. Si vous pouviez passer à trier 52 éléments ensemble via des moyens, maintenant. Et encore une fois, comme nous le montre ces les gars font ce, à la fin va produire une évidente Par conséquent, penser vraiment comment ils sont chaque faire, comment vous pourriez le décrire. Parce qu'encore une fois, ce sont tous les processus, algorithmes que nous prenons pour acquis comme un être humain. Mais vous avez eu probablement longtemps intuition, longtemps avant que vous même pensé à prendre une informatique vous classe aurait eu l'intuition de qui pour résoudre les problèmes de ce genre. Mais une fois que vous reconnaissez les modèles et commencer de formaliser les étapes avec qui vous résoudre ces problèmes, vous verrez que vous pouvez résoudre beaucoup plus intéressant et beaucoup plus complexe problèmes rapidement. Donc, quelqu'un dans le public, ce qui est au moins un élément de l'algorithme qu'ils utilisent ici? PUBLIC: [inaudible] ENCEINTE: Qu'est-ce que c'est? PUBLIC: En costume. ENCEINTE: En costume. Alors d'abord ils se regroupent tous les diamants ensemble Il semble que l'ensemble de l' coeurs ensemble, il semble, et ainsi de suite, sans égard pour les numéros sur les cartes. Et maintenant, ils apparaissent, par exemple, à les trier par numéro. Très bon. Très bien, alors ce qui se passe à être la dernière étape alors ici? Une fois que nous avons quatre couleurs triées, ce qui devons-nous faire pour les quatre piles afin d'obtenir une triés pont, tout simplement? Nous avons donc besoin de les fusionner à nouveau. Donc, il ya une idée intéressante qui encore une fois, disons-le, est très intuitive même si vous ne l'auriez jamais giflé ce genre de étiquette. Cette notion fondamentale de la division le problème n'est pas dans la moitié de ce temps, mais au moins en quatre morceaux. Résolution à peu près problèmes fondamentalement identiques indépendamment les uns des autres, et en fusionnant les résultats. Et, excellent, fait. Très bien, un grand rond d'applaudissements, si nous le pouvions. [Applaudissements] Président: Je n'ai aucune idée de ce que vous aurez faites avec ceux-ci, mais vous pouvez y aller. Merci beaucoup. Voyons donc, à deux minutes et huit secondes, si vous souhaitez défier vos amis. Qu'est-ce donc qui se passe à être tirer de cette que nous pouvons tirer parti de façon plus générale? Eh bien, pensez à ce tableau de nombres, et repense maintenant à une partie de la pseudo que nous avons écrit dans le passé, et ce fut le pseudo-code pour résoudre le problème de l'annuaire téléphonique. Lequel en pseudo je énumérées de façon plus méthodique de décrire comment j'ai fait un très intuitive algorithme humain de diviser le téléphone livre en deux, répéter, répéter, répéter, jusqu'à ce que je trouve quelqu'un comme Mike Smith, si il est en effet dans l'annuaire téléphonique. Mais j'ai un peu l'habitude ce que j'appellerai une approche très itérative ici, en particulier préavis ligne 8 et la ligne 11. Ce sont la preuve d'une itératif approche, une approche en boucle, parce que c'est exactement le comportement qu'ils induisent. Ces lignes deux disent aller à ligne de trois, et vous pouvez sorte de penser que, dans votre l'œil de l'esprit comme étant une boucle. Il vous dit de revenir à l'étape trois et répéter, encore et encore, et de nouveau. Mais que faire si nous misons sur une idée clé ici que nous n'avons pas la dernière fois, et de simplifier la ligne 8 et ligne 11 et leurs voisins comme tout cela, en jaune. Ce n'est pas fondamentalement raccourcir le pseudo beaucoup, mais il est fondamentalement changer la nature de mon algorithme. Ce que je suis en train de dire à l'étape 7, à l'étape 10, est à la recherche de Mike de la même manière exacte, mais juste à la gauche la moitié ou la moitié droite. En d'autres termes, si Je pars de la première étape, ramasser annuaire téléphonique, ouverte à milieu de livre de téléphone, regardez les noms, si Smith est parmi Nom, appeler Mike, d'autre si Smith est antérieure dans le livre, l'étape sept rechercher Mike dans la moitié gauche de livre. Mais ce genre de sent comme ça me laissant pendre, non? En jaune, est une instruction, mais comment puis-je rechercher Mike dans la gauche la moitié de l'annuaire téléphonique? Où dois-je une Je algorithme avec lequel peut chercher quelqu'un comme Mike Smith? Eh bien, c'est nous regarder en face. Je peux littéralement utiliser exactement la même programme va effectivement au sommet et remettez-course les mêmes lignes de code. Ainsi, même si cela doit se sentir comme un peu de définition cyclique où vous répondez à quelqu'un est question par tout type de demande la même question, comme pourquoi, pourquoi, pourquoi? La réalité est que nous avons codé en dur quelques lignes spéciales, l'étape 4, qui est un cas, et l'étape 12, qui est effectivement une autre branche, parce que nous avons ces mesures palliatives, cet algorithme prend fin si nous trouver Mike, ou si nous ne le faisons pas. Mais à l'étape 7 et 10 maintenant, nous avons ce que nous appellerons un algorithme récursif. Et la récursivité est en effet une idée puissante c'est un peu l'esprit de flexion dans un premier temps, que nous pouvons maintenant appliquer comme suit. Le tri par fusion sera la dernière sorte que nous regardons, au moins en classe formellement. Et c'est fondamentalement différent de ces trois dernière, et certainement quatre derniers si nous incluons bogosort. Voici le pseudo-code pour le tri par fusion. Quand à l'entrée de n éléments, ainsi donné une matrice de taille n, si n est inférieur à 2, retourner. Alors, pourquoi ai-je que santé mentale vérifier d'abord? Quelle est la conséquence si je vous remets un réseau dont la longueur est inférieure à n 2? Il est déjà trié, de toute évidence, non? Parce que la liste a soit un élément, qui est trivialement trié parce que c'est la seule chose qui existe. Ou, il est de la taille zéro, ce qui signifie il n'y a rien à trier, donc par nature elle est triée. Il ya juste rien de mal là-bas. Donc, c'est notre affaire dite de base. C'est dans le même esprit à ce que nous avons fait avec Mike. Si Mike dans l'annuaire téléphonique, appelez-le. Si il n'est pas là, abandonner. C'est une affaire dite de base, pour s'assurer cet algorithme à la fin de la journée s'arrête dans certaines circonstances. Mais voici le saut de la foi maintenant, sinon, trier la moitié gauche des éléments, ensuite trier le droit la moitié des éléments, puis fusionner les moitiés triées. Et c'est là qu'il se sent comme nous défilez. Je vous ai demandé de trier n éléments, et je suis dire, OK, faites-le par le tri la gauche et la droite de tri. Mais je dis un autre chose, et ce est le thème clé, il semble dans l'intuition à ce jour, il ya cette troisième étape de fusion. Qui, même si elle semble tellement stupide dans l'esprit, comme juste fusionner des choses ainsi, il semble être une étape clé vers l' réassemblage de deux problèmes que ont été divisés en fin de compte la moitié. Donc, le tri par fusion, faisons cela, si vous voulez humour moi, avec un plus démonstration, tellement que nous avons une numéros de travailler avec. Puis-je échanger huit le stress balles pour huit personnes? Très bien, que diriez-vous trois, vous quatre dans cette section, cinq, six, et nous allons ne 7, 8, viennent sur place. OK, ouais OK. Minus 8, il nous aller, plus 1. Excellente. Tous sont à droite sur la place, nous allons vous donner rapidement des numéros. Le numéro deux, numéro trois, numéro quatre, nombre de cinq, six, sept et huit. J'ai fait huit correctement cette fois. OK, alors allez-y si vous le pouviez, et nous allons trier dans l'ordre original que nous avons eu hier qui a examiné comme ça, si vous voulez bien. Et nous allons le faire en face de la table. Très bien, alors le tri par fusion. C'est là que ça se passe pour obtenir assez intéressant, parce que j'ai l'impression de me donner beaucoup moins d'informations aujourd'hui. Donc, le tri par fusion d'abord sur l'entrée de n éléments, et n'est évidemment pas inférieur à deux, c'est huit, donc j'ai un peu plus de travail à faire. Alors maintenant, mentalement nous comme une classe sont maintenant dans l'autre branche, ce qui signifie trois étapes. Tout d'abord, je dois trier la la moitié gauche des éléments. Alors, comment puis-je m'y prendre? Eh bien, je vais type de diviser mentalement la liste ici, vous n'avez pas à déplacer physiquement, et je suis va se concentrer uniquement sur la la moitié gauche des éléments ici. Alors, comment dois-je aller sur le tri maintenant une liste de taille quatre? Quel est mon algorithme? D'abord, je vérifie est n moins de deux, non, si je passe à l'autre bloc à nouveau. Trier gauche de la moitié des éléments. Alors maintenant, à nouveau, mentalement, et c'est là que vous avez à courir beaucoup d' l'histoire mentale, si vous voulez. Maintenant, je suis le tri de la gauche la moitié de la moitié gauche. Très bien, alors maintenant je appeler mon même fusion algorithme de tri, est n moins de deux? Non, il est deux, donc je dois trier la moitié gauche et la moitié droite. Alors on y va, trier la moitié gauche. Pourquoi ne pas vous venez de avancer d'un pas. Quel est votre nom? PUBLIC: Darren. ENCEINTE: Dan. Dan a pris les devants. PUBLIC: Darren. ENCEINTE: Darren, fait. Avez-vous dit Darren ou Dan? PUBLIC: Darren. ENCEINTE: Darren. OK, Darren a intensifié vers l'avant et il est maintenant triée. Et c'est presque un revendication inepte, non? Je ne crois pas vraiment à la réalisation quoi que ce soit, mais nous allons procéder. Maintenant, permettez-moi de trier le droit la moitié des éléments. Quel est votre nom? PUBLIC: Luke. ENCEINTE: Luke. Allez, un pas en avant. Fait, j'ai trié Luke. La moitié gauche est maintenant triée et la moitié droite est maintenant triée, mais encore une fois, il ya une étape clé ici. Que dois-je la prochaine dois faire? Fusionner les deux moitiés triées. Maintenant, nous allons avoir juste chacun dans les deux sens de cette façon, parce que je sorte de besoin un espace de travail. C'est presque comme si ceux-ci les gars sont sur une table, et j'ai besoin d'une certaine marge pour les déplacer sur. Donc, je vais fusionner vous les gars en regardant à la moitié gauche et la moitié droite. Et qui vient évidemment en premier lieu, moitié moitié gauche ou à droite? Donc, la moitié droite, donc passons Luke sur ici à la position initiale de Darren. Et maintenant de fusionner leur moitié gauche dans, Darren va passer là. Alors se sent comme presque un effet bulle de tri, mais mon algorithme fondamental, très différent cette fois. Mais c'est maintenant que les choses deviennent un peu ennuyeux parce que vous avoir à rembobiner mentalement où ai-je m'arrête. Je viens fusionné les moitiés triées, qui signifie que je suis là où dans mon algorithme? Je dois trier la moitié droite, non? Si vous rembobinez, littéralement sur la vidéo, vous aurez voyons que nous sommes arrivés à ce point de Luke et Darren en triant la gauche la moitié de la moitié gauche. Ensuite, nous avons fusionné les moitiés triées, qui signifie la prochaine étape est en quelque sorte le la moitié droite de la moitié gauche. Très bien, nous allons donc le faire plus rapidement. Très bien, six, je vais la revendication vous êtes maintenant triées, allez de l'avant. Quel est votre nom? PUBLIC: Adriano. ENCEINTE: Adriano. Adriano est maintenant triée. Et quel est votre nom? PUBLIC: Alex. ENCEINTE: Alex est maintenant triée. La moitié gauche, moitié droite, ce qui est la dernière étape? Fusionner. Assez trivial, donc je suis s'apprêtent à fusionner en six, prendre un peu de recul, huit, prendre un peu de recul. Et maintenant, remarquez ce n'est un plat à emporter utile, ce est maintenant vrai sur la moitié gauche de l' liste, indépendamment de la façon dont nous avons commencé? Il est triée. Maintenant, il n'est pas triée dans le grand schéma des choses, mais il est trié indépendamment de l'autre moitié. Maintenant, ce que je suis pas sur si je continue rembobinage comment l'histoire a commencé? Maintenant, je dois trier la moitié droite. Alors maintenant, nous sommes le chemin du retour à le début de l'histoire, et nous allons le faire plus rapidement. Donc, je vais trier la moitié droite de l'ensemble de la liste. Quelle est la prochaine étape? Trier la moitié gauche de la moitié droite. Trier la moitié gauche de la la moitié gauche de la moitié droite. Et quel est votre nom? PUBLIC: Omar. ENCEINTE: Omar, pas en avant, c'est fait. La moitié gauche est triée. Et quel est votre nom? PUBLIC: Chris. Conférencier: Chris, faire un pas avant, vous êtes maintenant triées. Quelle est l'étape clé maintenant? Fusionner. Donc, on va fusionner en place ici, si vous pouviez prendre un peu de recul, et trois va prendre du recul, de fusionner. Donc, la moitié gauche de l' la moitié droite, est maintenant triée. Franchement, cet algorithme se sent comme nous gaspillent beaucoup plus de temps qu'avant, mais si nous l'avons fait en temps réel, nous allons voir ce que les plats à emporter vont être. Maintenant je suis ici, à droite la moitié de la moitié droite, laissez-moi aller de l'avant et trier la moitié gauche. Avancez, quel est votre nom? PUBLIC: Ramsey. ENCEINTE: Ramsey est maintenant triée. Quel est votre nom? PUBLIC: Marina. ENCEINTE: Marina est maintenant triée comme bien, si vous prenez un pas en avant. Étape clé ici est maintenant fusionner, je suis va arracher de mes deux listes, gauche et à droite. Cinq va venir en premier, et sept va venir après. Et encore une fois, c'est délibéré. Le fait qu'ils prennent étapes avant et en arrière est censé représenter que nous ne pouvons pas faire cet algorithme en place aussi facilement comme tri à bulles, et la sélection sorte, et le tri par insertion où nous venons gardé échange personnes. J'ai littéralement besoin d'une sorte de papier brouillon dans lequel de mettre ces gens pendant que je fais la fusion, et alors je peux les remettre en place. Et c'est la clé parce que je suis en utilisant un nouvelle ressource, l'espace, pas juste le temps. OK, c'est incroyable. La moitié gauche est triée, la moitié droite est trié, maintenant que la fusion touche pas. Comment vais-je fusionner ce? Donc, si vous suivez mon main gauche et la main droite, Je vais montrer ma main gauche à la moitié gauche, ma main droite à la moitié droite, et maintenant je dois décider, étape par étape qui à fusionner dans. Qui vient évidemment en premier? Numéro un. Alors, venez par ici, voici notre bloc-notes. Alors maintenant numéro un, et un avis ce que je vais faire avec ma main droite, Je vais passer ma seule main droite enjamber au point numéro trois, et maintenant je dois faire la même décision. Et en fait se tenir droit dans avant de Luc ici si vous pouviez, parce que c'est notre bloc-notes. Alors, qui vient après? Nous avons Luke avec le numéro deux ou Chris avec le numéro trois. Évidemment Luke, nombre deux, si vous venez ici. Mais ma main gauche maintenant va être incrémenté pour pointer vers Darren, et voici la clé emporter avec la fusion, je vais continuer à faire ça, évidemment, si vous nature de suivre la logique. Mais mes mains ne sont jamais va revenir en arrière, ce qui signifie que je ne jamais passer à la gauche avec mon processus de fusion, et que ça va être la clé de notre analyse dans un instant. Alors maintenant, nous allons terminer ce rapidement. Donc trois vient ensuite, puis quatre vient ensuite, et maintenant cinq vient ensuite, puis six, et sept, et enfin huit. On se sent comme le plus lent algorithme encore, mais pas si l'on fait exécuter au même genre de la vitesse d'horloge, pour ainsi prendre la parole, avec le même cochant horloge comme avant. Pourquoi? Eh bien, Jetons un regarder le résultat final. Revenons ici, laissez-moi tirer vers le haut une démonstration visuelle de ce que nous venons de faire. Zoom avant ici, sur ce Cette page ici, en disant Firefox que nous voulons faire la queue dans cette boîte, nous allons dire tri à bulles, avec laquelle nous sommes maintenant bien connu, sélection sorte, qui est un autre assez simple un, et maintenant le tri par fusion d'aujourd'hui, qui sera notre fin à son apogée. La raison pour laquelle il a pris beaucoup plus de temps ici avec les humains et moi verbalement est, évidemment, je vous explique chaque étape. Mais si vous exécutez simplement ceci, beaucoup comme nous l'avons fait tri et de sélection bulle sorte non seulement visuellement, montre combien plus efficace ce levier de division et conquête peut être appliqué à un ensemble de données qui est même pas la taille de huit, mais même beaucoup, beaucoup plus grand. Je vous donne le tri par fusion, à côté de l' côté de ces autres algorithmes. Cela va obtenir douloureux rapidement, et la fin n'est pas particulièrement à son apogée, ils finissent juste en haut triés. Mais l'essentiel est que emporter Regardez comment beaucoup plus rapidement le tri par fusion était, à moins que vous pensez que je suis juste un peu de jouer avec vous. Si nous faisons cela, une dernière fois, laissez de recharger ce, revenons et choisissez tri à bulles, et juste pour le plaisir, choisissons insertion sorte, pour faire bonne mesure. Et cette fois encore, nous allons choisir le tri par fusion et nous allons fait fonctionner ces côte à côte. Et ce n'est pas, en fait, un coup de chance. Ce que j'ai effectivement fait est que je n'ai divisé mon entrée dans la moitié, encore une fois, et encore, et encore. Et il ya seulement tant de fois que vous pouvez divisez votre entrée en deux moitiés, gauche et à droite. Quelle est la formule que nous continuons à voir qui décrit la division en deux encore, et encore, et encore, et encore? PUBLIC: Ouverture n. ENCEINTE: Ouverture n. Mais il ya une autre étape clé, cet algorithme n'est pas log n étapes. Si l'on ne log n étapes, nous serions dans le même problème comme avant où nous ne pouvons pas être que tout est trié. Vous devez regarder peu à n éléments pour être sûr que n éléments sont triés, sinon c'est un acte de foi. C'est donc peu log n étapes, mais Qu'en est-il de cette étape de fusion touche où j'ai fusionné ma moitié gauche et à droite moitié et traversa la scène? Combien d'étapes, c'est que de fusionner? C'est n, mais je n'ai pas juste fusionner la dernière fois. Sur chacun de ces appels imbriqués, sur chaque de ces fusions imbriqués, je n'ai toujours trié. J'ai fusionné ces deux gars, alors ces deux les gars, alors ces deux gars et ainsi de suite. Donc, je n'ai fusion, encore et encore. Combien de fois? Donc, chaque fois que je divise le liste dans la moitié, j'ai fait une fusion. Divisez la liste en deux, faire une fusion. Donc, si divisant la liste qui peut être fait log n fois, et la fusion prend finalement n étapes, ce qui pourrait être maintenant la partie supérieure lié à la gestion moment de notre algorithme? n log n. Et en effet, c'est ce que nous avons accompli ici. Donc la sensation que vous voyez visuellement quand ces trois choses fonctionnent côte à côte n est au carré en fonction de n carré contre n log n. Qui fondamentalement nous le verrons, non seulement aujourd'hui, mais à l'avenir, est beaucoup, beaucoup plus rapide. Une salve d'applaudissements pour ces gars-là, Je vais les récompenser avec des boules de stress. Disons ajourner ici aujourd'hui, et nous vous voir lundi.