[Jouer de la musique] 

DAVID J. Malan: Très bien. Alors, bienvenue en arrière. C'est CS50, et l'est la fin de la troisième semaine. 

Donc, rappeler au cours des dernières semaines, nous avons consacré un peu de fois sur C, la programmation, la syntaxe. Et c'est tout à fait normal, si vous êtes encore aux prises avec des problèmes Set 2, pour être cogner la tête contre le mur. C'est messages d'erreur cryptique prospectifs et les bugs que vous ne peut pas tout à fait pourchasser. Parce que, rassurez-vous, qui en seulement une le temps de quelques semaines, vous allez regarder en arrière sur des choses comme César, et [? V-Genair,?] peut-être même se fissurer, et réalisez à quel point vous êtes dans une courte période de temps. Donc, si c'est une consolation, accrochez-vous pour l'instant. 

Aujourd'hui, cependant, nous commençons à transition à des choses plus haut niveau. Et nous commençons à prendre pour acquis que vous les gars savent comment programmer, ou à moins les débuts de que le niveau de confort. Et nous allons commencer à examiner comment nous pouvons aller sur la conception de programmes plus efficacement. Comment pouvons-nous aller sur l'optimisation de la efficacité de nos algorithmes, et généralement résoudre plus problèmes intéressants. Et à partir de tenir pour acquis que, si nous le voulions, nous pourrions coder tout des exemples que nous avons à l'esprit. Donc, aujourd'hui, nous ne touchons pas le clavier pour toute forme de code. Ça va être beaucoup plus élevé, et en fin de compte, sur la résolution de problèmes. 

Donc, pour arriver à ce point, permettez-moi de proposer que les sept suivants rectangles représentent sept portes, derrière qui sont tout un tas d' numéros, parmi lesquels se trouve le numéro 50. Permettez-moi de projeter cette sur cette écran ici. Et de proposer que nous avons besoin d'un volontaire pour m'aider à trouver un numéro devant Internet ici pour voir. Venez sur place, dans le rose. Très bien. Quel est votre nom? 

JENNIFER: [Inaudible] 

DAVID J. Malan: Pardon? 

JENNIFER: Jennifer. 

DAVID J. Malan: Jennifer. Tout droit, Jennifer. Enchanté de faire votre connaissance. Venez sur place. Il s'agit donc voici sept portes, et ce J'aimerais que vous fassiez pour nous ici, en face de l'ensemble de vos camarades de classe, est nous trouver le numéro 50. Pour trouver un numéro, vous pouvez coup d'oeil derrière l'une de ces portes en tapant simplement sur l'une des portes, et va révéler son numéro. Et nous allons voir à quelle vitesse vous peut nous trouver le numéro, 50. 

15. 16. 50. Bien fait. Très bien. Salve d'applaudissements pour Jennifer. 

[Applaudissements] 

Très bien. Alors quelle est votre stratégie pour trouver le nombre, 50? 

JENNIFER: Euh, je pensais que peut-être si - [Inaudible] 

DAVID J. Malan: Oh. Donnez-lui une seconde. Ainsi était votre stratégie pour trouver le nombre, 50? 

JENNIFER: Je viens de commencer à l' commence à voir le premier numéro j'étais, et puis j'ai pensé, peut-être si ils sont triés, je vais continuer tapant plus haut? 

DAVID J. Malan: OK. Et nous semblons avoir trouvé que ce soit le cas. Bien, nous allons peler les couches juste un peu, et vous voulez aller avant et révéler les autres portes vous auriez pu choisir? 

JENNIFER: Oh, ma chérie. 

DAVID J. Malan: Ah. 

JENNIFER: Je viens donc eu de la chance. 

DAVID J. Malan: Donc, vous avez de la chance. Très bien. Donc pas mal. Mais c'est une question intéressante aperçu, non? Si vous avez pris, et que vous avez reçu, En effet, un peu de chance là-bas. Mais si vous supposiez que les chiffres étaient triée, pouvez-vous être plus précis la manière dont cette influence votre comportement? 

JENNIFER: Donc, si ils ont été triés, je pensait peut-être plus petit au plus grand. 

DAVID J. Malan: OK. 

JENNIFER: Ou si cela a fini par être vraiment grand, alors le plus grand au plus petit. 

DAVID J. Malan: OK. Donc, du plus grand au plus petit, ou plus petit au plus grand. Mais permettez-moi de proposer, supposons que vous deviez eu de chance, et supposer qu'ils n'ont pas été, en fait, triées, combien d' ces portes pourraient vous ont dû peek derrière dans ce pire des cas? 

JENNIFER: Tous. 

DAVID J. Malan: Tous. Donc, nous allons généraliser que n. Il se trouve être 7, mais nous allons plus dire généralement qu'il ya n portes sur le écran ici. Ainsi, dans le pire des cas, vous auriez regarder derrière 7 portes ou n portes. Et donc c'est vraiment, c'est un peu de chance aujourd'hui, mais c'est vraiment un linéaire algorithme de toutes sortes, même si vous ont eu la gentillesse de sauter autour. Est-ce juste? 

JENNIFER: Ouais. 

DAVID J. Malan: Eh bien, laissez-moi voir si votre changements de stratégie si je nous déplacer notre deuxième exemple ici avec 7 portes différentes. Mêmes chiffres, mais cette moment où ils sont triés. Quelle est votre stratégie ici va être, essayer de mettre hors de votre esprit ce que les autres numéros ont été - 

JENNIFER: OK. 

DAVID J. Malan: - plus tôt? 

JENNIFER: Commençons avec la première. 

DAVID J. Malan: Très bien. Commencez avec la première. 4. Maintenant, où allez-vous aller, et pourquoi? 

JENNIFER: 4 est vraiment petit. Donc, si ils sont en quelque sorte peut-être plus petit au plus grand, il devrait être le double, et -. 

DAVID J. Malan: OK. Voyons, que vous en pensez? 

JENNIFER: Essayez la dernière. Nice. 

DAVID J. Malan: Très bien fait. Très bien. 

[Applaudissements] 

DAVID J. Malan: OK. Donc, vous êtes en train de faire cette horriblement, parce que vous êtes le faire très bien. Qui nous laisse incapable de faire certains points. Donc, nous allons essayer de revenir ici. 

JENNIFER: OK. 

DAVID J. Malan: Très bien fait, néanmoins. Vous avez donc commencé dès le début, vous avez vu que c'était 4, puis vous déplacé à la fin. Mais supposons que vous n'avez pas eu la chance là-bas, et supposons 50 était ailleurs. Que votre troisième étape aurait été? 

JENNIFER: Retour au début. 

DAVID J. Malan: Retour au début. OK, donc vous avez touché cette porte, qui était de 8. Très bien. Donc, ce n'est pas 50. Où aimeriez-vous avoir regardé prochaine? 

JENNIFER: Si je n'ai pas savent qu'ils triés. 

DAVID J. Malan: C'est exact. Eh bien, si vous ne saviez ils ont été triés - 

JENNIFER: Oh, je ne savais, oui. 

DAVID J. Malan: - Mais vous n'avez pas savoir où 50 était encore? 

JENNIFER: Juste continuer. 

DAVID J. Malan: Très bien. OK. Continuez. OK, je peux travailler avec. 

JENNIFER: OK. 

DAVID J. Malan: Maintenant, si vous êtes juste va continuer, quel est votre algorithme dévolues soutenu dans. 

JENNIFER: Le linéaire -. 

DAVID J. Malan: C'est un peu linéaire. Mais permettez-moi de proposer, laissez- me mis sur la sellette. Permettez-moi de vous rafraîchir la page. même nombre, même arrangement, mêmes portes. Mais repense à cette première journée classe quand nous avons déchiré un annuaire téléphonique dans la moitié, en quelque sorte, et ce qui était notre stratégie là-bas? 

JENNIFER: Commencez par le milieu. 

DAVID J. Malan: OK. Donc, commencer au milieu. Allons donc de l'avant et de simuler cela. Commencez par le milieu par révéler cette porte. Ainsi, le nombre 16. Alors, qu'est-ce que le gars fort dû le faire, qui a déchiré le livre de téléphone de moitié, pour se rendre à la prochaine idée? 

JENNIFER: Va avec cette moitié. 

DAVID J. Malan: Et pourquoi à droite? 

JENNIFER: S'ils étaient en quelque sorte de plus petit au plus grand, puis 50 devrait être à cette fin. 

DAVID J. Malan: Bon. Tout à fait raisonnable. Donc, comme un annuaire téléphonique, vous allez à l' droit, par opposition à la gauche, mais ici est la clé emporter. Vous pouvez maintenant jeter ou déchirer, la moitié de ce problème, vous laissant pas avec 7 portes, mais vraiment avec seulement 3. Qui est à peu près la moitié de la ampleur du problème. Très bien. Alors maintenant, ce que vous auriez fait après que vous allez bien? 

JENNIFER: Donc 16 est encore assez faible, par rapport à 50, alors peut-être que je vais essayer, comme, celui-ci. 

DAVID J. Malan: Très bien. 42. Très bien, alors maintenant quel est votre instinct vous dit? 

JENNIFER: Je peux jeter ce et puis juste - 

DAVID J. Malan: OK. Bon, vous pouvez jeter la moitié gauche là. 

JENNIFER: - choisir celui-ci. 

DAVID J. Malan: Et la droite. 

JENNIFER: Ouais. 

DAVID J. Malan: Donc, même si c'est dur à voir peut-être, quand il ya seulement 7 portes, pensent, maintenant, la cohérence de l' algorithme que vous venez d'appliquer. Dans le cas précédent, vous avez fait avoir de la chance, ce qui était super. Mais vous avez utilisé une heuristique, Je dirais. Vous avez utilisé sorte de vos instincts, et sachant qu'elle soit triée, si c'est assez petite au début, évidemment, nous avons obtenu d'aller plus vers la droite. Mais dans un certain sens, vous avez de la chance, parce que c'était peut-être le numéro 100, et peut-être 50 était plus dans le milieu. Peut-être 50 était encore ici. 

Mais qu'est-ce que vous avez fait un peu différemment cette époque, vous avez fait la même chose encore et encore. Et je dirais que ce que vous venez n'a, bien influencé par le téléphone exemple livre, est quelque chose de beaucoup plus algorithmique, et beaucoup moins spécial tubé. Beaucoup moins instinctive. Donc à la fin de la journée, comment vous décrivez l'efficacité de l' premier algorithme, où vous êtes allé de gauche à droite, par rapport à la second algorithme ici? 

JENNIFER: celui-ci devrait, comme, peut-être réduire de moitié le temps, voire plus, oui. 

DAVID J. Malan: OK, peut-être même plus. Poussons un peu plus à ce sujet. Ce qui, si nous continuons cette logique, nous avons certainement réduit de moitié le temps de fonctionnement de ce second algorithme en jetant la moitié de la chiffres, mais qu'avons-nous fait à la prochaine itération, lorsque Jennifer a révélé le deuxième nombre? 

Nous nouveau divisé par deux le nombre de portes. Et puis, qu'avons-nous fait après cela, si il y avait plus de portes pour jouer avec? Nous souhaitons réduire de moitié, et encore, et encore, et encore. Et ce n'était que comme vous les gars tout debout à la première semaine de classe, la moitié d'entre vous assis, à moitié de vous asseoir, la moitié d'entre vous assis, jusqu'à ce qu'un seul âme était debout. Et nous avons dit que le temps d'exécution de que le nombre d'étapes qu'il a fallu était de l'ordre de quoi? 

INTERLOCUTEUR 1: [inaudible] 

DAVID J. Malan: Donc log base 2 de n, ou tout simplement plus simple, connectez-vous sur n. Donc, quelque chose logarithmique. Et le graphique n'est pas une ligne droite qui vient juste de pire en pire, c'était Cette courbe intéressante qui n'a pas devenir si mauvais temps. Donc, nous allons tenir à cette idée. Remercions Jennifer. Merci beaucoup d'être venu sur place. Et une seconde. Pas de lampes de bureau aujourd'hui, mais nous n'avez CS50 balles anti-stress. 

JENNIFER: Yay. 

DAVID J. Malan: Très bien, ici. Merci pour encourir la contrainte ici. Très bien. Donc, nous allons voir si nous ne pouvons pas maintenant formaliser cela un peu plus. Encore une fois, ce que nous venons de faire est essentiellement la même chose que nous avons fait en ce que la première semaine. Mais plutôt que de fin avec juste un linéaire algorithme, qui nous dépeint précédemment que cette ligne droite, de sorte que, si nous mettons une plus porte sur l'écran, puis Jennifer serait ont dû chercher, potentiellement, derrière une porte plus. Si nous mettons deux portes, elle pourrait avoir regarder derrière deux portes. 

Et donc, il y avait cette linéaire la relation entre la taille de l' le problème, par exemple, l'axe des x, et la quantité de temps nécessaire pour résoudre le y. Mais l'image que je faisais allusion à était au début de cette ligne verte. Vert délibérément, parce que il me sentais mieux. En théorie, l'algorithme, lorsque nous l'avons fait avec l'annuaire téléphonique, lorsque nous l'avons fait avec vous les gars compter les uns les autres, et dans le second cas, lorsque Jennifer juste at-il ici, c'était en quelque sorte de fondamentalement mieux. Parce que ce n'était pas simplement deux fois plus vite. Ce n'était même pas quatre fois plus rapide. Il était tout dépend de ce que l' taille de l'entrée était, quant au nombre de mesures qu'il a finalement pris. 

Et si cette idée simple que nous avons tous pris pour acquis avec l'annuaire téléphonique, peut même être appliquée à quelque chose comme ça. Et cela pourrait être plus décontractée connu sous le nom, comme vous pouvez imaginer, diviser pour régner. Non contrairement à ce qu'on a fait, bien sûr, avec l'annuaire. 

Mais le pseudo, le rappel était présent. Donc, nous ne le ferons pas nouveau, mais rappelle cette première semaine, nous avons tous se levèrent puis la moitié d'entre vous assis, la moitié des vous vous êtes assis, la moitié d'entre vous assis. Cet algorithme a été mis en œuvre dans un peu d'une façon de tricher, en ce sens, il n'était pas seulement l'un des me compter, fondamentalement, de manière plus efficace. Dans ce cas, je me tirant parti une ressource secondaire. En quelque sorte, plusieurs processeurs, plusieurs cerveaux, plusieurs gens intelligents dans l' chambre aidaient-moi de quelque chose linéaire à quelque chose logarithmique, à partir de quelque chose rouge à quelque chose de vert. 

Mais dans ce cas, Jennifer seul peut améliorer fondamentalement sur l' les performances de son premier algorithme par, encore une fois, juste à y penser un peu plus difficile. Et maintenant, quand vient le temps de mettre en œuvre ces choses, calculer quelles lignes de code que vous pouvez écrire comme que vous pouvez répéter à nouveau, et encore, et encore, une sorte de dans un mode en boucle. Parce que vous n'allez pas avoir le luxe, comme Jennifer a fait au début, à tout simplement avoir tout un tas d'ifs et de dire, hmm, si ce premier numéro est 4, Permettez-moi de sauter tout le chemin jusqu'à la fin. Oh, si ce nombre est trop grand, Passons arbitrairement retour au second élément. Vous verrez que ça va être beaucoup difficile à formaliser ce que nous, les humains tenir pour acquis que très raisonnable heuristiques, mais un ordinateur est seulement vais faire ce que vous lui demandez de faire. 

Maintenant, cela a très intéressant implications. Ce graphique est une sorte de destinée à trier des submerger visuellement, mais demeure, où est la droite de ce graphique? Où est le graphe linéaire que nous appelons n? Eh bien, c'est un peu vers le bas de cette image, non? Donc, tout ce que nous avons fait c'est que nous avons sorte de zoom arrière à l'axe des x et l' axe des ordonnées pour tenter de se faire une idée de ce que d'autres types de courbes ressemblent. 

Et les spécificités de la mathématique expressions d'aujourd'hui ne sera pas question de manière beaucoup, mais remarquez qu'il ya beaucoup de algorithmes qui sont bien pires que quelque chose qui est linéaire. En effet, n cubes semble assez mauvais. 2 au n semble assez mauvais. n carré semble assez mauvais. Et nous verrons ce que certains d'entre eux pourrait être en réalité aujourd'hui. Et log n ne se sent pas aussi mauvais, mais mieux que n est log base 2 de n. Mais vous savez, il aurait été encore Plus étonnant si Jennifer, ou si nous, cette première semaine, était venu avec quelque chose qui n'est journal de journal de n. 

Donc, en d'autres termes, il ya toute cette éventail de solutions possibles à problèmes, mais même ici, un avis ce qui va se passer. Quand je effectuer un zoom arrière, laquelle de ces courbes qui va se révéler être l'absolu pire de celles sur l'écran maintenant? Alors n cubes semble assez mauvais pour le moment. Mais si l'on zoom arrière et voir plus de la x et l'axe des y, qui va dominer finalement? Ainsi, il s'avère en fait que 2 à l' n, et vous pouvez comprendre cela juste par branchant un plus grand chiffres, et vous verrez que 2 à l' n effet, s'agrandit beaucoup plus vite. Si nous voulons vraiment effectuer un zoom arrière, un 2 à la algorithme n aspire absolument. Je veux dire que cela va prendre un peu de temps pour la ordinateur à travers le taux de désabonnement. 

Mais vous verrez au fil du temps, en particulier avec les futures séries de problèmes et même derniers projets, vos données sont ensemble devient grand, d'accord? Même dans la première version de Facebook, comme le nombre d'amis, et l' nombre d'utilisateurs enregistrés a large, vous pouvez trier de téléphone à l'intérieur et mettre en œuvre quelque chose avec recherche linéaire, ou un simple tri algorithme, comme nous le verrons aujourd'hui. Vous devez commencer à penser plus difficile et plus difficile à propos de ces problèmes. Et les types de lieux de problèmes tels que Facebook et Google et Microsoft, et d'autres travaillent sur sont précisément ces sorte de Big Data genre de questions de plus en plus ces jours-ci. 

Très bien. Donc, le succès de Jennifer dans ce second algorithme, franchement, elle n'a étonnamment bien la première fois, mais nous allons écrire comme chance pour que nous peut faire ce point. Dans le second cas, elle a mobilisé une algorithme qui répète encore et encore une fois, mais elle a pris pour acquis une certaines hypothèses que nous permettions , mais elle exploite le détail deuxième fois qu'elle n'a pas eu l' première fois. Qui était quoi? 

Que la liste a été triée. Donc dès que la liste a été triée, nous affirment que Jennifer était capable de faire fondamentalement mieux. 7 portes, oui, n'est-ce pas intéressant, mais supposons que ce que nous sommes 7 millions de portes. Connexion de n va certainement d'effectuer beaucoup, beaucoup plus rapide dans le long terme. Mais elle a dû subir l' portes triés pour elle. Maintenant, j'ai pris la liberté de le faire à l'avance sur l'écran de l'ordinateur ici, mais supposons que Jennifer eu à le faire elle-même? Supposons que les portes en question données représentées dans une base de données, ou amis inscrits à Facebook, ou toutes les pages Web sur l'Internet qui divers sites Web pourraient avoir besoin à l'index ou la recherche terminée. 

Supposons que vous venez d'avoir un ensemble de données brutes défini et il a été laissé à vous, ou à Jennifer à faire que le tri? C'est, plutôt, exige que nous répondions la question, eh bien, combien de temps aurait pris Jennifer, ou même moi, pour trier ces chiffres à l'avance afin qu'elle pouvait tirer parti de cela? Droite? Parce que l'implication, bien sûr, est si ça me prend un certain temps pour trier les nombres, qui est le diable se soucie que vous peut trouver un nombre comme 50 si vite, comme dans le cas de Jennifer, si nous avons plus que accablé la quantité de temps totale il a fallu en triant les choses à l'avance? 

Donc, nous allons voir si nous ne pouvons pas l' peindre le tableau ici. J'ai tout un tas plus de stress boules, si cela aide briser la glace ici. Et si vous voulez bien, nous besoin de sept bénévoles - sur, OK. Wow. Donc, nous n'avons pas à dépenser sur les lampes de bureau, paraît-il. Très bien. Alors que diriez-vous deux à l'avant. Que diriez-vous deux gars dans le dos. C'est donc quatre. Que diriez-vous devant cinq, six et sept ans. Juste là. Votre ami vous a souligner, ainsi vous obtenez le prix. 

Très bien. Venez sur place. Et pourquoi ne pas vous avons les gars viennent par ici. Je vais vous donner à chacun un numéro. Et aller de l'avant et d'organiser vous-mêmes identique à ce qui est représentée sur l'écran. 

[Interposition VOIX] 

DAVID J. Malan: Oop, désolé. Bug. Très bien. Eh bien, nous y voilà. Le numéro cinq. Le numéro six. Un, deux, trois, quatre, cinq, six, sept ans. Oh, c'est bizarre. 

ENCEINTE 2: Je vais chercher un -. 

DAVID J. Malan: Bonne affaire. Très bien. Merci pour votre participation. 

[Applaudissements] 

OK. Très bien. Nous avons donc quatre, deux, six, un, trois, sept, cinq. Parfait, donc nous avons sept bénévoles ici, qui sont de largeur égale à l' tableau que nous jouons avec la précédente. Et j'ai choisi sept pour des raisons ce sera juste pratique dans un peu. Et je vais proposer d'abord que nous trions ces sept bénévoles. Si vous le souhaitez, d'abord, pour dire bonjour si. Depuis cela va être un maladroites plusieurs minutes. Présentez-vous. 

GRACE: Salut, je suis la Grâce. Je suis un étudiant en deuxième année dans Leverett House. 

BRANSON: Salut. Je suis Branson. Je suis un étudiant de première année en soudure. 

GABE: Salut. Je suis Gabe. Je suis un junior dans le Cabot. 

NEIL: Je suis Neil. Je suis un étudiant de première année à Matthews. 

JASON: Je suis Jason. Je suis un étudiant de première année en Greenough. 

MIKE: Je suis Mike. Je suis un étudiant de première année à Grays. 

JESS: Je suis Jess. Je suis un étudiant en deuxième année dans Leverett. 

DAVID J. Malan: Excellent. Très bien. Eh bien, merci à tous nos bénévoles ici jusqu'à présent. Et le défi à relever maintenant va être de trier de ces gars, mais nous allons devoir réfléchir un peu dur sur l'efficacité avec laquelle nous avons fait triés eux. Donc, nous allons d'abord essayer. Les gars, vous pouvez voir les numéros les uns des autres tout en plaçant autour des coins. Allez-y et prenez quelques secondes, et Trier-vous de plus petit sur le laissé à la plus grande sur la droite. Allez. 

OK. Bon. C'était vraiment sacrément rapide. Maintenant, quelqu'un ici, ce qui était l'algorithme que ces gars-elles appliquées? 

INTERLOCUTEUR 1: petit au plus grand. 

DAVID J. Malan: OK. Au plus grand est vraiment le genre de objectif, mais je ne suis pas sûr que c'est vraiment un algorithme. Au plus grand ne veut pas dire moi étape par étape quoi faire. Ouais? 

INTERLOCUTEUR 1: [inaudible] 

DAVID J. Malan: OK. Donc si vous voyez une personne plus petite que votre numéro, puis passer à le droit d'entre eux. Donc, c'est maintenant obtenir plus expressive, ressemble plus à un algorithme, parce que vous peut dire, si ce, alors que. Nous avons donc une sorte de construction conditionnelle. Et ces gars-là ont semblé faire quelques fois, parce que certains d'entre vous ont déplacé un bit d'une distance. Donc il y avait sans doute une sorte de boucle passe dans leur esprit. 

Mais nous allons essayer de formaliser cela. Si vous pouviez réinitialisé à cet arrangement. Voyons voir si nous ne pouvons pas formaliser ce une bit, puis poser la question, juste comment efficace est-ce? Bien sûr, lorsque nous faisons cela plus lentement, il va se sentir aussi bien d' un algorithme, mais nous allons voir si nous pouvons mettre nos doigts sur les mesures précises. 

Alors vous deux gars sont quatre et deux ans. Ou vous commandez correcte ou incorrecte? De toute évidence erronée. Donc nous avons échangé. Maintenant, je vais passer à côté ici et dire quatre à six. Êtes-vous correcte ou incorrecte? 

GABE: C'est exact. 

DAVID J. Malan: C'est exact. Six et un? Nan. Swap. C'est donc deux swaps. Six et trois? Nan. Swap. Six et sept? On dirait bien. Sept et cinq ans? 

JESS: [Inaudible] 

DAVID J. Malan: OK, échanger. Et triés. Très bien. Alors, évidemment pas, non? Donc il y avait plus de choses. Mais, en effet, ces gars-là, même juste instinctivement. maintenu en mouvement. Ils ne s'arrêtent pas, une fois qu'ils corrigé un problème. So. En effet, je vais devoir de faire la même chose. Je vais faire le tri de rembobinage retour au début de ce problème, ou le début de cette gamme de personnes, nous allons commencer à les appeler. 

Et maintenant, que si mon algorithme sur la seconde passe être? 

INTERLOCUTEUR 1: Même chose. 

DAVID J. Malan: Même chose. Et cela, je commence à aimer, non? Dès que vous pouvez vous retrouver à faire la même chose encore et encore, c'est de plus en plus comme un algorithme, et l'instinct moins humain. 

Alors maintenant, nous y revoilà. Deux et quatre? No. Quatre et un? Ah, il y avait effectivement un certain encore du travail à faire. Pour et trois? Bon. Quatre à six? Six et cinq? Six et sept? OK, maintenant, c'est fait. OK, no. Je dois y retourner. 

Alors maintenant, encore une fois, nous faisons ce un peu plus délibérément. Et maintenant, il ya juste un cerveau l'exécution de cet algorithme. Un CPU, si vous voulez. Et franchement, c'est la seule ressource nous allons avoir accès. Et une fois que nous ne retournons à un clavier et avoir quelque chose comme C à notre disposition, nous ne sommes qu'à l'écriture d'un programme que peut faire une chose à la fois. Considérant que, ces gars-là il ya un instant, nous leveraged leur intelligence collective comme vous avez fait dans la semaine zéro. Donc, nous allons continuer à faire ça. 

Deux et un. Deux et trois. Trois et quatre. Quatre et cinq. Cinq et six ans. Six et sept ans. Fait? Donc je suis, mais laissez-moi jouer l'avocat du diable. Dois-je, le type d'ordinateur qui vient fait une passe dans cette gamme de personnes, savent que je suis fait? 

INTERLOCUTEUR 1: No. 

DAVID J. Malan: Alors pourquoi? Qu'est-ce que je dois faire pour conclure de façon décisive que je suis fait? Probablement encore une passe. Droite? Parce que tout ce que je sais de ce précédent passe, c'est que j'ai corrigé une erreur. Et cela signifie, peut-être il ya encore une autre erreur que je dois corriger. Donc, je ne peux être sûr de rembobinage, et puis vérifier, un à deux, deux et trois, trois et quatre, quatre et cinq, cinq et six, six et sept ans. OK, maintenant je n'ai pas de travail. 

Je peux certainement me rappeler que je n'ai rien fait de travailler avec quelque chose comme une variable, comme un int. Appelez-swaps, et si swaps est 0 une fois que je obtenir ici, et il a commencé à 0, puis Je voudrais juste être stupide pour continuer dans les deux sens, en vérifiant à nouveau, et encore, et encore, pas vrai? Parce que vous êtes coincé dans une certaine sorte de boucle infinie. Donc dès que il ya 0 swaps, nous pouvons affirmer que cette algorithme est en effet complet. 

Maintenant, nous allons mettre un nom sur ce point. L'algorithme que je propose que nous venons de mise en œuvre est quelque chose appelé bulle trier, connue en tant que telle dans le sens d' les chiffres qui sont plus grands types de bulle leur chemin vers le haut, ou vers le haut à la fin de la série de nombres. Mais comment était efficace cet algorithme? Combien d'étapes je n'ai eu physiquement Prenez, par exemple, pour trier ces sept humains? 

Quatre à cinq? OK, trop nombreux, c'est en fin de compte va être la réponse. Mais même alors, le nombre précis n'est pas si intéressant. Nous allons généraliser comme n. Donc, si je n'avais N nombre de personnes ici, et ils étaient, en quelque sorte, dans un ordre aléatoire à l' commencer, en ce que l'ordre original. Eh bien, combien d'étapes je n'ai eu à prendre sur la première passe? C'était un, deux, trois, quatre, cinq, six, et ils sont sept personnes, donc c'est sept, six -, c'est donc n moins un étapes la première fois. 

Maintenant, combien d'étapes je n'ai eu à prendre quand j'ai rembobiné? Eh bien, nous pourrions doubler que si nous voulions vraiment, mais pour l'instant, je suis juste dire, tout droit, autre n moins 1. Ainsi, le n moins 1 va se faire ennuyeux à suivre, nous allons donc juste arrondir légèrement. Donc 2n étapes. Donc, 14 étapes, donner ou prendre. 

Combien de fois ai-je pris une étape la prochaine fois? Eh bien, c'est 3n. vraiment. Et maintenant, dans le pire des cas, pour Ainsi, combien de fois aurais-je passé d'avant en arrière, d'avant en arrière, l'exécution de cet algorithme, en échangeant personnes sur chaque passe, en gros? Il s'agit en fait sur n carré, non? 

Parce que dans le pire des cas, vous pouvez genre de penser intuitivement, même si cela peut prendre un peu peu de temps à couler po Dans le pire des cas, à quoi ces sept personnes ont ressemblé, dans termes de l'accord de leur nombre? Complètement à l'envers, non? Et juste pour simuler que, quel est votre nom? 

MIKE: Mike. 

DAVID J. Malan: Mike? OK, Mike, pouvez-vous joindre à moi juste sur ici juste pour une seconde? En fait, non. Désolé Mike, le rembobinage let. Quel est votre nom? 

NEIL: Neil. 

DAVID J. Malan: Neil. OK, Neil, tu viens avec moi, si vous ne me dérange pas. Donc je vais proposer, juste pour simplicité, que Neil est maintenant dans sa pire des cas. Mais souviens comment j'ai mis en place mon algorithme. Je compare, comparer, comparer, comparer, comparer, oh. Maintenant, ces gars-là sont hors de l'ordre, de sorte que je fixe. Alors vous les gars swap. Mais considérons maintenant, combien plus loin Neil ne doivent aller? C'est à peu près n. Vous savez, ce n'est pas vraiment n. C'est comme si, n moins 1, mais je suis en train de garder une trace agacé de la petite numéro, nous allons donc simplement l'appeler n. 

Donc, si Neil se déplace d'une étape au maximum chaque temps, et pour déplacer une étape Neil, Je dois faire ce passe vraiment fastidieux dans les deux sens, c'est à peu près Ce faisant, n étapes, un total de n fois, parce que ça va me prendre que de nombreuses mesures pour obtenir Neil tous la voie à l'endroit où il appartient. Sans parler de tout le monde si vous les gars ont tous mis-commandé ainsi. 

Alors appelons sorte de bulle n carré. Le temps d'exécution de cet algorithme, l' les performances de cet algorithme, l' l'efficacité de cet algorithme, nous allons seulement décrire plus généralement que le n au carré. Ce qui est bien, parce que je pouvais faire le même exemple avec huit personnes, dont neuf personnes, un million de personnes, et que réponse ne va pas changer. 

Donc, si vous les gars ne me dérangerait pas, nous allons vous remettre à l'endroit où vous avez commencé. Et nous allons essayer deux autres approches et voir si nous ne pouvons pas faire fondamentalement mieux que cela. Alors, cette fois, je vais proposer une sorte d'algorithme différent. C'était très intelligent de nous la dernière fois, et vous les gars avaient raison d'avoir l' instincts droit de tout genre d'échange par paires. Mais si je voulais vraiment aborder cette simplement, et mon but est de déplacer tous les petits nombres de cette façon, et pousser tous les grands chiffres que Ainsi, pourquoi ne pas simplement le faire dans le plus naïve façon possible et voir si je peut faire mieux que ce qui était un algorithme assez complexe? 

Voyons donc. Quatre est un joli petit nombre, donc je suis vais vous laisser là-bas moment. Ooh, numéro deux, c'est encore mieux. Ainsi, vous pouvez simplement aller de l'avant pour un moment? C'est actuellement mon petit numéroté candidat, et je vais vous rappeler que, avec, comme, une variable. Mais je vais garder le contrôle. Y at-il quelqu'un dont nombre est plus petit? Six, non. Oh, il ya encore Neil. 

Donc, je vais vous faire reculer sorte de point de vue conceptuel. Neil se présentera. Et maintenant, la variable que j'utilise pour garder trace de qui a la plus petite nombre est mis à jour pour contenir L'emplacement de Neil. Eh bien, voyons voir. Trois, sept, cinq. OK, je sais que Neil était le plus petit. Quelle est la chose la plus simple pour moi de faire maintenant? Je ne vais pas perdre mon temps par tout bouillonnement Neil un endroit à la gauche. Pourquoi ne pas simplement mettre Neil où il appartient, ce qui est bien sûr où? 

Tout le chemin au début. Donc, Neil, viens avec moi. Et quelle est votre nom? 

GRACE: Grace. 

DAVID J. Malan: Grace. OK. Donc, Grace, malheureusement, vous êtes type de la manière. Alors, comment pouvons-nous résoudre ce problème? Droite? Si c'est un tableau, il ya seulement sept emplacements. Rappelons que, avec Rob, nous avons parlé déclarant âges, et nous n'avions qu'une nombre fini d'âges? Même idée ici. Nous ne disposons que d'un nombre fini d'entiers. La grâce est en quelque sorte dans notre Ainsi, alors comment pouvons-nous résoudre ce problème? 

Le plus simple, c'est comme, Grace, désolé. Vous allez avoir à aller sur il afin que nous puissions faire de la place. Maintenant, si vous pensez à ce sujet, peut-être nous avons juste fait qu'aggraver le problème. Et peut-être que nous avons fait, parce que si Grâce étaient au bon endroit? Mais nous savons qu'elle n'est pas, parce que autrement, elle aurait été debout avant au lieu de Neil en ce moment, non? Nous avons déjà vérifié son numéro rupture. 

Très bien. Alors maintenant, Neil est au bon endroit, et Je peux faire une légère optimisation. Pour la prochaine minute, je vais ignorer Neil tous ensemble, afin de ne pas perdre son temps, ou accidentellement permuter lui au mauvais endroit. Alors maintenant, comment puis-je trouver le prochain élément qui est plus petit? Deux. C'est un assez bon nombre, si vous voulez aller de l'avant et Je me souviens de vous. Six, rien de bon. Quatre, trois, sept, cinq, rien de bon. Permettez-moi de vous déplacer à votre juste place. Et nous avons juste eu de la chance cette fois. 

Maintenant, je vais ignorer ces deux gars, et maintenant faire une plus passer à travers cela. Six, c'est un assez petit nombre. Allons de l'avant. Oh, désolé. Le nombre de Grace est meilleure, donc marcher sur l'avant. Four. Désolé, Grace. Y retourner. Numéro trois, c'est mieux. Seven. Cinq. Et maintenant, quel est votre nom? 

JASON: Jason. 

DAVID J. Malan: Jason. Alors, Jason est maintenant le plus petit élément j'ai choisi. Où est-ce qu'il va aller? Alors, où est six. Et votre nom est nouveau? 

GABE: Gabe. 

DAVID J. Malan: Gabe. Gabe est dans la manière. Quelle est la meilleure chose à faire? Échanger ces deux gars et continuez. Alors maintenant, nous allons voir. Qui est le plus petit? Four. Laissez-moi juste un peu de triche. Cinq va être le plus petit. Je trouve prochaine, si vous voulez à l'étape avant, qu'est-ce que je dois faire avec ces gars-là, avec Gabe? Swap nouveau. Alors maintenant, encore un peu dans le désordre. J'ai trouvé Gabe pour être la plus petite, de sorte Je pop sortir, vous vous déplacez gars plus. Et fait. 

Donc réponse est la même. Le résultat final est le même. Laquelle de ces deux algorithmes est le meilleur? Le second, j'ai entendu. Pourquoi? 

Intervenant 3: Il n pas [inaudible]. 

DAVID J. Malan: C'est n étapes au maximum. Intéressant. Alors, est-ce bien? Alors, comment ai-je trouvé l' plus petit élément? Combien d'étapes je n'ai eu à prendre le trouver le plus petit élément? J'ai jeté un oeil tout le chemin à la fin, non? Parce que dans ce cas le plus défavorable, ce qui si Neil était ici? Il suffit donc de trouver le plus petit élément me n étapes, ou n moins 1 prend. Mais, OK. Donc, fixer Neil. Rappelez-vous que, il ya une minute ou deux. 

Mais comment ai-je trouver le prochain plus petit élément? C'est n moins 1 ou moins 2 n vraiment, à partir du nombre d'étapes. Alors OK. Donc, je n'ai N moins 2. Très bien. Alors, qui se sent un peu mieux. Très bien. Combien d'étapes la prochaine fois pour trouver le numéro trois? Alors n moins 4. Donc ça baisse, soit un de moins l'étape à chaque itération. Donc, ce ne se sent mieux, non? Si la dernière fois, c'était à peu près n fois n, cette fois, c'est n moins 1, plus n moins 2, plus n moins 3, plus n moins 4, point, point, point. Mais si vous vous souvenez de votre lycée manuels scolaires, la petite triche feuille à l'arrière qui a des formules, si vous ajoutez cette série de chiffres, quel est le nombre total d'étapes va être que je prends ici? 

C'est l'un de ceux, comme, n moins 1, n fois, divisé par deux. Alors permettez-moi de voir si je peux tirer cette place pendant un moment. Et encore, je suis un peu arrondi certains chiffres juste pour garder notre vie simple, mais si je me souviens, c'est quelque chose comme si Je fais n moins 1 choses, alors n moins 2, alors n moins 3, il ya à peu près quelque chose comme ceci sur 2, et si je multiplier cette rupture, c'est fait place n. Cela ne veut pas se sentir trop bon. n moins n supérieur à 2. 

Mais voici la chose. En informatique, lorsque les problèmes commencer à devenir intéressant, c'est lorsque n devient vraiment grand. Et quand n devient vraiment grand, ce qui ces valeurs va dominer tous des autres? C'est un peu le n carré, non? Oui, en divisant par 2 est très bonne. Mais si vous parlez milliards d'éléments de données, ou des milliards d' morceaux de données, OK, donc vous êtes deux fois plus vite. Mais qui se soucie vraiment si grand nombre, si ce facteur est ce qui est plus en plus. Et sûrement, il fait plus de une différence que ce gars-là. Ainsi, même si vous les gars ont raison, le deuxième algorithme, nous l'appellerons tri par sélection, est, dans le monde réel, un peu plus rapide potentiellement, parce que je suis prenant de moins en moins étapes chaque fois. 

Ce n'est pas vraiment fondamentalement plus rapide. Parce que si nous jouons en fait cela pour les grandes valeurs de n, à la fin de le jour, pendant assez grand n, il est toujours va se sentir assez lent. Eh bien, permettez-moi de prendre un dernier passage à cela. C'est ce que j'appellerais sélection sorte. Vous les gars vous pouvez réinitialiser une dernière fois? Et dans ce dernier cas, je vais de proposer quelque chose appelé le tri par insertion. Le tri par insertion être, conceptuellement, un peu différent. 

Plutôt que d'aller d'avant en arrière et sélectionner le plus petit élément, je suis aller juste pour faire face à chacun de ces les gars que je rencontre, et insérer eux dans leur bon endroit. Donc je vais commencer avec Grace, et je vois qu'elle est numéro quatre. D'où vient le numéro quatre appartiennent? Je n'ai pas commencé le tri rien, ainsi la grâce arrive à rester là. Et maintenant, je vais demander, si vous pouviez faire un pas à droite, cette ma liste triée, c'est mon non triés liste restante. Alors maintenant, je vais passer à côté, et quel est votre nom? 

BRANSON: Branson. 

DAVID J. Malan: Branson. Alors Branson est le numéro deux. Donc, je vais vous prendre pour un moment. Et maintenant, où vous situez-vous dans ce tableau? Donc, pour le droit de grâce. Encore une fois, nous sommes en quelque sorte de faire Grâce faire beaucoup de travail ici. Où allons-nous vous mettons? Nous allons donc vous glisser à l' à gauche, et insérer Branson là. Mais maintenant, je prétends que vous les gars sont faites. Mais remarquez, je ne vais pas utiliser l'espace supplémentaire. C'est encore 2 éléments ici, 5 ici. Taille totale du tableau est 7, donc je suis ne triche pas, d'accord? 

Nous avons donc maintenant, avec Gabe ici, l' numéro six, où vous situez-vous? Vous avez encore de la chance. Donc, vous arrivez à rester là. Il suffit de prendre un léger cran vers la droite juste pour faire comprendre que vous êtes triés. Et maintenant nous avons Neil nouveau numéro un, où allez-vous? Et maintenant où nous commençons à voir que Cet algorithme, bien que le premier vue, se sent assez intelligent, regarder ce qui va se passer. Si vous pouviez aller de l'avant. 

Où voulons-nous mettre Neil? Alors, évidemment, ici, alors comment pouvons-nous obtenir Neil là? Faisons cette étape-par-étape. Gabe, où devez-vous aller? Yep, alors prenez un grand pas, ou deux demi-étapes pour faire une étape là-bas. Grace, où allez-vous? Bon. Donc, une autre étape. Et enfin, Branson? Une autre étape. Et maintenant, nous pouvons mettre en place Neil. 

Alors maintenant, poursuivre cette logique. Même si nous ne sommes pas en train de passer Neil plus, et plus, et plus, pour le mettre où il va, dans le pire des cas, le prochain numéro nous pourrions rencontrer pouvait soit le nombre, par exemple, il y avait un certain nombre zéro, alors nous allons passer tout de ces gars-là. Supposons qu'il ya un certain nombre, négatif un, alors nous devons changer tous ces gars-là. Nous sommes donc vraiment juste une sorte de retournement le problème autour, de sorte que nous sommes le transfert de la charge de la Procédé de sélection de manière à l'insertion processus, tels que vous les gars ont juste eu de se déplacer à peu près n moins quelque chose nombre d'étapes. Et que nombre de mesures ne va à augmenter à mesure que je sélectionne plus de numéros, si je dois continuer à pousser les gars dos, et le dos, et le dos. 

Donc, le plus triste, c'est maintenant l'ensemble de ces algorithmes sont n au carré. Allons de l'avant et grâce à ces les gars, et de visualiser ces un peu différemment. Très bien fait. 

[Applaudissements] 

Très bien. Là vous allez. Merci pour - 

BRANSON: [Inaudible] garder les chiffres. 

DAVID J. Malan: Non, vous pouvez garder les numéros ainsi. Très bien. Bien fait. Très bien. Donc, nous allons voir si nous ne pouvons maintenant résumer plus rapidement et plus visuellement, exactement ce qui vient de se passer ici comme suit. Je vais aller de l'avant et tirez Firefox. Nous allons lier cette manifestation sur le site Web du cours. Java est un peu gênant de faire fonctionner dans certains navigateurs de nos jours. Donc, si vous jouez avec ça à la maison, réalisez que vous pourriez avoir besoin d'utiliser Firefox pour que cela marche. Et ce que je vais faire avec cette démonstration est le suivant. 

Au fond, j'ai tout un tas d' les options du menu, y compris un début et une le bouton d'arrêt. Par ailleurs, en passant, il semble y avoir une bug dans ces programmes, par lequel vous ne peut pas réellement voir le démarrage ou d'arrêt bouton sauf si vous détenez commande ou Alt plus et zoom, qui curieusement vous montre plus de boutons. Il suffit donc de FYI si vous jouez avec ça à la maison. Maintenant, je vais cliquer sur Démarrer en un moment, après avoir spécifié un délai d', comme, à 200 millisecondes ici, afin que nous puissions voir ce qui se passe. 

Donc, je prétends que c'est une visualisation du premier algorithme ces gars ont fait, sorte de bulle, où nous avons échangé personnes par paires. L'idée maîtresse de cette visualisation est que la hauteur des barres représente la taille du nombre. Donc, le plus grand de la barre, le Plus le nombre. Shorter la barre, plus le nombre. Et si vous remarquez, nous allons à travers la première itération de l'algorithme, permutation nombre, petits et grands, de sorte que le petit nombre vient en premier et le grand nombre va vers la droite. 

Et dès que nous aurons le fin d'un tableau de beaucoup plus nombreux que les sept, nous sommes va revenir au début. Et d'anticiper cela. À l'extrême gauche, ce petit gars va à échanger sur le côté, et ce processus se répète. Maintenant, cette visualisation devient rapidement ennuyeux, alors laissez-moi aller de l'avant et arrêter , changer le retard quelque chose de beaucoup plus rapide juste pour obtenir maintenant, une idée de cet algorithme. 

Donc, même si je n'ai SPEd it up, c'est comme passer mon processeur, l'achat un nouvel ordinateur. Je n'ai pas fondamentalement changé ma algorithme, mais vous pouvez en effet voir plus clairement qu'avec des humains, que le grand numéros bouillonnent vers le haut, et le petit nombre bouillonnent vers le bas. Et maintenant cette chose ici triée. Et en passant, sur les places, il ya juste un peu de comptabilité là pour vous aider à compter le nombre de comparaisons, ou combien de swaps ont effectivement été fait. 

Eh bien, nous allons essayer l'un des les autres que nous avons vu. Permettez-moi clique sur sorte de bulle ici, et Permettez-moi à choisir, et cette page Web entière est un peu buggé. Nous allons accepter le risque et le relancer. Nous y voilà. Alors, faisons sélection sorte. Je ne sais pas pourquoi le menu apparaît là-bas. Prenons un zoom avant pour résoudre ce problème bug, changer cela en 50. Ah, nous allons faire en fait beaucoup plus rapidement. Cinq millisecondes ou plus, et le démarrer. 

Donc, c'est la sélection sorte. Encore une fois, pensez à ce que nous fait avec les humains ici. Nous sommes allés dans le tableau et sélectionné le plus petit élément nouveau, et encore, et encore. Je prétends maintenant que c'était encore assez mauvais. Il était encore sur n carré, donner ou prendre, mais il était, dans le monde réel, un peu plus rapide, parce que je prends en effet légèrement moins pas à chaque fois. Mais nous ne parlons quoi? Peut-être 40 ou si les bars ici? Nous ne parlons pas 40 millions. Donc, il n'est pas totalement clair pour moi que était en effet un gain significatif. 

Permettez-moi maintenant de revenir en arrière et changer à notre troisième algorithme, qui a été sélectionnez le tri par insertion. Et maintenant c'est vraiment buggé parce que le menu devrait vraiment pas être là-bas. Alors maintenant, nous allons revenir en arrière ici et commencer à cet algorithme. Whoop, démarrer et arrêter. Alors celui-ci sorte de a un joli motif pour cela, par lequel nous sommes à nouveau l'insertion, les humains, ou en ce cas, les barres en leur emplacement approprié. Et il l'a déjà fait avant Je me suis retourné. Mais celui-ci, aussi, en théorie, n est encore au carré. 

Donc, nous allons voir si nous ne pouvons pas résumer ceux-ci comme suit. Je vais aller de l'avant et juste pour donner nous une sorte de façon commune de parler à propos de ces choses, permettez-moi de vous présenter juste un peu de notation ici. Vous êtes sur le point de voir quelque chose appelé grand O, parce que c'est littéralement un grand O. Et c'est une façon qu'un ordinateur scientifique ou un mathématicien utilise même pour décrire le temps d'exécution d'un algorithme. Combien d'étapes faut-il réellement prendre? 

Maintenant, je vais me mettre dans l'embarras avec mon écriture ici dans un instant. Mais permettez-moi d'aller de l'avant et dire que ce sera grand O ici. Et permettez-moi de vous présenter un autre symbole, un oméga de capital. Omega va être le contraire, essentiellement, de la grande O. considérant grand O moyens, dans le pire des cas, combien de temps pourrait un algorithme prendre, fonction de n, oméga va être combien de temps pourrait-il prendre dans le meilleur des cas. Et nous verrons ce que nous entendons par meilleur des cas, dans un instant. 

Commençons donc quelque chose de simple. Permettez-moi de commencer par une recherche linéaire. Donc, pas de tri. Nous appelons cette recherche linéaire. Et maintenant, faire un peu d' tableau de là. Et maintenant, dans le cas de la recherche linéaire, dans le pire des cas, le nombre d'étapes est il va me prendre pour trouver un nombre de choix arbitraire? Et il ya n portes au total ou le nombre total de n. Le pire des cas. Combien d'étapes que je vais devoir prendre pour trouver le numéro 50 dans un tableau de n portes? Et pourquoi? Car il pourrait être tout le manière plus sur la fin. Alors, un peu comme Jennifer a rencontré, le numéro 50 était tout le chemin, donc dans le pire des cas, la recherche linéaire est grand O de n, on va dire. 

Qu'en est-il le meilleur des cas, si vous avez vraiment de la chance? Il va juste faire un pas, ou un nombre constant d'étapes. Nous allons donc décrire que comme 1. Donc, c'est très bon. Maintenant, si nous avons fait quelque chose comme la recherche binaire? Recherche donc binaire, dans le pire cas, a pris combien de temps? 

[Interposition VOIX] 

DAVID J. Malan: Donc en fait, je entendu à quelques endroits. Donc, c'est en fait log n, donner ou prendre, parce que nous divisons la liste de moitié encore, et encore, et encore, nous sommes en mesure à trouver, en fin de compte, la valeur, si elle est là, mais il ya un hic. Quel est le principe que nous devons tenir pour acquis pour la recherche binaire? Il doit être trié. Ce n'est pas triée, vous pouvez diviser la chose dans la moitié encore et encore, et vous peuvent aller à gauche, et vous pouvez aller à droite, et vous pouvez aller à gauche et à droite, mais vous êtes ne va pas à trouver l'élément si la liste n'est pas triée, parce que vous pourriez le manquer. Parce que votre heuristique, pour aller à gauche ou à droite va être faussée si c'est en effet non trié. Il ya donc une sorte de coût caché d'utiliser quelque chose comme ça. 

Maintenant, passons à notre tri algorithmes ne recherche - Oh, en fait, allons dans ce vide. recherche binaire dans le meilleur des cas? C'est également 1 si elle se trouve être au beau milieu de la baie, ou au milieu de l'annuaire téléphonique. Maintenant, nous allons faire sorte de bulle. Encore une fois, maintenant, nous entrons dans l' sortes, et pas les recherches. 

Dans le pire des cas, combien d'étapes avons-nous réclamation sorte de bulle va prendre? n au carré. Donc, je vais faire ça. Oh, mon écriture est encore pire quand il est prévu que les gros. Très bien. Donc, c'est yan carré. Et dans le meilleur des cas, de sorte de bulle, combien d'étapes que ça va prendre? 1, j'ai entendu. 

INTERLOCUTEUR 1: n. 

DAVID J. Malan: n, j'ai entendu. 

INTERLOCUTEUR 1: 2. 

DAVID J. Malan: 2, j'ai entendu. Dois-je entendre 3? Très bien. Alors j'ai entendu 1, n, 2, mais Reprenons en dehors d'au moins la première de celles suggestions, 1. Ce n'est pas un mauvais instinct, car il genre de suit un modèle ici. Mais si cela ne prend que 1 étape, comment dans le monde pourrais-je prétendre que la liste est trié, parce que si je suis seulement permis de prendre 1 étape, combien d'éléments pourrais-je fait vérifier pour être sûr? Eh bien, 1, ce qui signifie qu'il ya n moins 1 des éléments qui pourraient être hors de ordre, et je vais sur la foi après consultant d'une élément sur lequel l' chose est triée. Donc 1 n'est pas correct ici. Donc, minimalement, combien de dois-je regarder? 

[Interposition VOIX] 

DAVID J. Malan: n moins 1, ou vraiment, n, parce que je dois regarder chaque élément pour s'assurer que ce n'est pas en panne. Mais encore une fois, nous allons sorte de vague notre mains sur les petits chiffres et présumons que, en n devient grand, ils sont inintéressant de toute façon. C'est donc ce tri à bulles. Et maintenant, nous allons faire ces deux derniers. Sélection sorte, et puis nous allons faire le tri par insertion. Et puis nous allons faire sauter votre esprit avec quelque chose de beaucoup mieux que tout cela. Très bien. 

Quel est le pire des cas en cours d'exécution moment de la sélection sorte? 

Intervenant 4: n carré. 

DAVID J. Malan: n carré, j'entends. Mais pourquoi n carré, intuitivement? 

Intervenant 4: Parce que nous venons de le faire. 

DAVID J. Malan: Parce que nous venons de le faire. OK. Bonne réponse. Mais intuitivement, pourquoi est-sélection Trier carré n? Qu'avons nous avons à faire encore et encore? Nous devions garder la numérisation à travers, sont vous le plus petit, vous êtes le plus petite, êtes-vous la plus petite. Et a accordé, nous avons pu prendre n étapes, alors n moins 1, alors n moins 2. Mais si vous ajoutez genre de ceux tout en place, ou les prendre sur la foi que j'ai ajouté leur place à l'avance, on obtient à peu près n carré moins certains nombres plus petits. Donc, je vais appeler ce n carré. Mais avec la sélection sorte dans le meilleur cas, combien d'étapes il est va me prendre? 

ENCEINTE 5: [inaudible] 

DAVID J. Malan: C'est malheureusement toujours n carré, non? Parce que si je sélectionne les plus petits élément, et nous avons eu sept personnes ici, Je sais seulement que, une fois que j'arrive à la très fin, que j'ai trouvé le plus petit nombre, partout où il elle aurait pu. Mais comment puis-je trouver le prochain plus petit nombre? Je dois faire un autre passage. Donc, dans le meilleur des cas, ce qui est le entrée à la sélection sorte? Il s'agit d'une liste déjà de tri, numéro un, numéro deux, numéro trois, numéro quatre. Mais je suis un ordinateur. Je ne peux que regarder un chose à la fois. Je ne peux pas trier de franchir une étape arrière comme un humain et dire, ooh, cela semble correct. 

Je ne peux que juger la justesse dans tri par sélection en sélectionnant l' plus petit nombre. Mais même si je trouve un nombre premier, si je ne sais rien d'autre sur les autres numéros, que je n'ai pas, tout ce que je sais que j'ai remis un tableau ou un ensemble de portes qui sont derrière nombres, la seule façon que je sais que l'un était la plus petite? Si je reçois tout ce chemin et de réaliser, putain, on était en effet le plus petit. 

Mais comment puis-je alors déterminer que deux est le plus petit à côté? En faisant la même inefficacité encore et encore. Donc finalement, avec le tri par insertion, comment, dans le pire des cas, avons-nous dit qu'il exécute? Elle aussi est n carré. Et que diriez-vous avec le meilleur des cas? Nous allons laisser cela comme un cliffhanger. Nous allons combler cette vierge prochaine fois, mais d'abord, permettez-moi de proposer que nous fondamentalement faire mieux que tout cela, tout va bien? 

Alors, pensez par vous-même ce que l'insertion Trier ça va être. Eh bien, ce n'était pas très spectaculaire, parce que je suis le seul qui a vu le changement. Wow. OK. Nous avons donc ici un peu démonstration différente. Si je zoome ici, vous verrez que le la gauche, nous avons sorte de bulle, dans la milieu nous avons sélection sorte, et sur l'extrême droite, nous avons quelque chose que nous n'ont pas encore regardé appelé le tri par fusion. Mais considérons ce que nous avons fait ici jusqu'à aujourd'hui. Quand Jennifer premier venu sur la scène, nous sommes allés à travers le tableau de nombres encore, et encore, avec recherche linéaire, et nous avons eu temps de fonctionnement linéaire, grand O de n, pour ainsi dire. 

Lorsque l'on considère maintenant la première semaine de classe, quand nous avions diviser et conquérir, et nous avions l'annuaire déchirement, et Jennifer, et nous avons collectivement effet de levier qui perspicacité clé, qui était de vous répétez encore et encore par en quelque sorte jeter, jeter, jeter, la moitié du problème, ou généralement, la division d'un problème dans la moitié, puis le traitement du morceau de plus petit le problème que conceptuellement équivalente à l'autre, nous avons en quelque sorte fondamentalement mieux. Mais avec tri à bulles, avec sélection sorte, avec le tri par insertion, nous avons peut aucune de ces idées que Jennifer a fait. Nous avons assez bien y sommes allés en arrière et de suite tout un tas de fois, et nous choses un peu tordu, l'échange dans cet ordre, peut-être l'insertion ou la sélection. Mais à la fin de la journée, j'ai fait beaucoup de la marche maladroite en arrière. Nous n'avons pas vraiment tirer parti de quelque chose intelligent comme Jennifer aimé division et conquérante. 

Donc, le tri par fusion, en revanche, que nous ne verra pas avant la semaine prochaine, ça va tirer parti de cette idée clé en divisant l'entrée, puis réduire de moitié, puis réduire de moitié, puis réduire de moitié. Et à chaque itération de la boucle, le tri de la moitié gauche et la droite la moitié, puis la moitié gauche de la moitié gauche, et la moitié droite de la gauche, puis la moitié gauche de la moitié droite, et la moitié droite de la partie droite. Et répéter encore et encore. 

Vous verrez donc cela visuellement, mais cette est ce qui nous attend la semaine prochaine. Et en général, quand on pense un peu peu plus difficile sur un tel problème. Nous avons n carré sur la gauche, n carré au milieu, et n log n sur la droite. Il ya donc votre véritable cliffhanger. Nous vous verrons lundi. 

[Applaudissements]