[Powered by Google Translate] [Semaine 3, suite]
>> [David J. Malan - Université de Harvard]
>> [C'est CS50. - CS50.TV]
>> Très bien. Bienvenue à nouveau. C'est CS50 et c'est la fin de la semaine 3.
>> Donc, pour ceux qui ne connaissent, l'année dernière Harvard a lancé ce qu'on appelle l'Innovation Lab,
ou i-lab, qui est un magnifique bâtiment de l'autre côté de la rivière sur le campus HBS
qui est ouvert aux étudiants des collèges, des étudiants, des étudiants GSAS de tous les campus à travers,
y compris les professeurs, et c'est un endroit pour se réunir pour travailler sur des choses innovantes,
choses particulièrement entrepreneuriales
si vous et 0 ou plusieurs amis envisagez de faire quelque chose de l'esprit d'entreprise
soit au cours de cette classe, après cette classe, ou au-delà.
>> Ainsi, l'une des choses qu'ils font sur la durée J est de ces voyages,
dont l'un est à New York, dont l'un est à la Silicon Valley.
L'espace est très limité, mais c'est une occasion de côtoyer des MBA
et les étudiants diplômés sur le campus et en fait passer du temps dans ces domaines respectifs
bavarder startups, bavarder entrepreneurs, etc.
Donc, si vous êtes intéressé, consultez cette URL ici.
Il est également disponible sur les diapositives en ligne.
>> Pourrait-on atténuer l'audio maison juste un peu?
Si vous souhaitez vous joindre à nous pour le déjeuner ce vendredi, 1:15 pm in Fire & Ice, s'il vous plaît tête là.
Toutes mes excuses si le formulaire est déjà rempli au moment où vous vous y rendre.
Mais nous allons continuer cette tradition en avant.
>> Aujourd'hui, nous continuons la discussion de niveau supérieur de divers problèmes que nous pouvons résoudre,
en se concentrant beaucoup moins, aujourd'hui du moins, sur le code et bien plus encore sur les idées.
Alors, pensez à revenir à la semaine 0, lorsque nous arracha un annuaire téléphonique dans la moitié,
dont l'objectif était de faire quelque chose, il est vrai, un peu dramatique
mais pour envoyer le point de recherche qui n'a pas besoin d'être nécessairement
aussi évident à première vue que vous pourriez penser.
Et la résolution de problèmes en général ne sont pas nécessairement toujours le meilleur -
La solution la plus évidente serait pas nécessairement le meilleur.
Nous avons donc eu cet annuaire et, franchement, chacun d'entre nous dans cette salle avait les instincts,
très probablement, à commencer par le milieu lors de la recherche pour Mike Smith, puis aller à gauche ou à droite
sur la base de ce que la lettre de l'alphabet nous est arrivé de se retrouver sur.
>> Mais cette idée simple que nous, les humains ont pris pour acquis depuis si longtemps
devriez vraiment commencer à venir à la pointe de votre esprit
parce que les problèmes deviennent beaucoup plus complexes que d'un annuaire téléphonique,
ces mêmes simples, des idées brillantes sont ce que l'on va nous permettre
pour résoudre des problèmes beaucoup plus compliqués et plus intéressant,
parmi eux certaines des choses que nous tenons pour acquis déjà ces jours-ci.
Des milliards de pages Web dehors là, et pourtant, Google et Bing et autres
sont en mesure de trouver des choses pour nous comme ça.
Cela n'est pas le cas à l'aide d'une recherche linéaire, recherche dans toutes les pages Web possibles.
Facebook est en mesure de vous dire qui tous vos amis sont ou amis d'amis,
et cela aussi peut être fait en apparence en un instant ces jours-ci
même si elles ont des millions d'utilisateurs.
>> Et alors comment on fait résoudre des problèmes d'une telle ampleur finira par réduire
les idées, nous avons examiné la semaine 0 et un peu plus aujourd'hui.
Nous n'allons pas ré-exécuter cet algorithme, mais rappelons nous avons aussi fait la semaine 0 cet exercice
où nous avions tout le monde se lever, prendre le numéro 1,
et puis nous avons eu tout le monde l'auto-comptage par appariement éteint, ajouter vos numéros ensemble,
puis la moitié de la bande s'assit sur chaque itération.
Donc, nous sommes passés de 500 élèves de 250 à 125 et ainsi de suite.
Mais, comme nous l'avons dit, le lundi, l'idée puissant, il
était que si nous avons doublé la taille de ce problème
et tous les enfants de la Justice ou CE 10 revint dans la chambre et nous a rejoint,
ainsi, on pourrait probablement compter de ce groupe surplus total
avec juste 1 itération grand plus de la boucle, car ils ne peut-être le double de la taille
ou en cas de CE 10 un peu plus du double de la taille.
Et donc on aurait pu passer un peu plus de temps,
mais nous n'aurions pas à dépenser 400 ou 700 pas de plus.
>> Juste pour peindre cette image d'une manière qui est un peu moins abstrait, il ne faut pas avoir tout le monde debout.
Mais si ceux d'entre vous qui ont choisi de rester dans l'orchestre d'aujourd'hui ne me dérangerait pas debout,
nous allons voir si nous pouvons trouver parmi vous qui est la personne la plus
en faisant le même genre d'algorithme de comparaison.
Donc, si vous êtes assis à l'orchestre, toutes mes excuses, mais l'étape 1, levez-vous;
l'étape 2, paires au loin avec quelqu'un à proximité vous,
comprendre qui est plus grand, et asseyez-vous si vous êtes plus courte.
Ensuite, répétez.
[Étudiants en murmurant]
>> D'accord.
D'accord. On reste debout. Quel est ton nom? >> Andrew.
>> Andrew, vous êtes la personne la plus à l'orchestre, aujourd'hui.
>> Félicitations. [Applaudissements et des acclamations] D'accord. Asseyez-vous. Donc, nous avons trouvé Andrew.
Mais combien de temps cela a dû me prendre, par exemple, de trouver Andrew
dans cette section orchestre de 50 + ou tant de gens?
J'aurais pu prendre une approche assez simple et commencer ici.
Et j'ai 2 personnes debout et je viens de les comparer,
et puis je dis à celui qui est légèrement plus court: «Bon, vous vous asseyez,"
et je vais vous rappeler qui était le plus grand personne.
Puis-je répéter, répéter, répéter, et je m'accroche à la personne la plus grande
jusqu'à ce que je trouve quelqu'un un peu plus grand qu'eux, à quel point
la personne un peu plus court doit alors s'asseoir.
Mais dans cet algorithme dans cette section orchestre, s'il ya n d'entre vous,
le nombre de pas est que l'algorithme va prendre? >> [L'élève] N.
>> Il va falloir n, à droite, parce que dans le pire des cas, pour ainsi dire,
la personne la plus grande est la dernière personne que je reçois simplement par la malchance aléatoire.
Donc, dans le pire des cas, le temps d'exécution de cet algorithme est linéaire, il est n,
où n est le nombre total de personnes dans l'espace, l'ampleur du problème.
Qu'en est-il de cet algorithme?
Le fait que vous tous debout, puis encore la moitié d'entre vous assis,
moitié d'entre vous assis, la moitié d'entre vous assis.
Combien d'étapes faut qui ont pris si il ya des n-tu ici?
[L'élève] N log n. >> Ce serait pire. Log n.
>> Donc log n, même si vous ne me souviens pas bien ce qu'est un logarithme est,
pour l'instant, juste apprécier ce qu'il rapporte en quelque sorte à cette réduction de moitié et réduire de moitié et réduire de moitié.
Il ne doit pas être un facteur de 2. Ce pourrait être un facteur de 3.
Mais c'est cette répétition du même genre de facteur tels que la taille du problème commence ici
mais va immédiatement ici, puis là, puis là, puis ici.
Vous ne prenez de petites bouchées de régler le problème, vous êtes vraiment loin à lui couper
avec un grand coup à chaque fois.
Donc, nous avons eu 50 personnes, puis 25, puis 12 ½ ou 13 personnes debout,
puis 6 ans et demi et ainsi de suite jusqu'à ce que finalement juste debout Andrew a été laissé.
Donc, nous allons appeler ce journal de n, et vous pouvez visualiser ce qui suit.
Rappelons cette image là où un algorithme linéaire est comme la ligne rouge là-bas,
la ligne jaune est le comptage par l'algorithme de 2s que nous avons utilisé pour les élèves de comptage
dans le passé, mais aujourd'hui, le Saint-Graal va rester cette ligne verte
où si nous avons doublé le nombre de personnes dans l'orchestre, ou tout simplement dit:
l'enfer, nous allons avoir tout le monde dans toute la salle debout, pas une grosse affaire
parce que nous grosso modo doubler le nombre de personnes ici-bas,
1 plus itération, pas un problème.
>> Nous avons constaté Andrew ou celui qui arrive à être plus grand que Andrew
dans la mezzanine ou sur le balcon.
Donc, cette idée simple que nous avons pris tellement de soi dans un annuaire téléphonique,
rendre compte qu'il ya tellement d'endroits différents où nous pouvons l'appliquer.
Juste pour gifler un peu de jargon - en fait, plutôt que le jargon d'abord,
me laisser aller à cette image ici.
À l'heure actuelle, nous avons parlé n et n / 2 et puis connectez-vous de n,
mais nous pouvons certainement trouver, comme nous le verrons au cours du semestre,
autre type de formules mathématiques pour décrire cette notion générale du temps de marche.
Ceux-ci sont sortis de leur contexte pour l'instant car nous verrons d'ici peu
algorithmes que ceux-ci représentent en fait.
>> Mais remarquez ici la ligne linéaire n, la ligne droite, est en réalité très faible pointant vers la droite maintenant.
C'est en quelque sorte une illusion d'optique que nous venons de changer ce que l'axe des x représente
et l'axe des y, et nous pouvons faire un point en ligne droite dans n'importe quelle direction nous voulons.
Mais la raison pour laquelle il est si apparemment déchargées maintenant
C'est parce que nous avions besoin de faire de la place sur ce graphique pour beaucoup plus lents fois de suite.
Pour l'instant, sachez qu'il ya quelques algorithmes assez mauvais dans la vie,
dont certains n'ont pas pris les mesures n ou, mieux encore, vous n étapes, mais bien plus encore.
Donc, au-dessus de la ligne n ici à l'avis en bas il ya n fois journal de n,
et nous verrons ce que cela signifie avant longtemps.
Ci-dessus qui est n au carré, et nous n'avons pas vu tous les algorithmes n carrés encore, mais nous sommes sur le point d'.
Et cela a l'air vraiment mauvais.
Il ya 2 au n, quelque chose exponentielle, qui se sent encore pire.
Et pourtant, curieusement, alors il n en cubes, qui, si vous êtes en quelque sorte penser à l'avenir,
si vous sorte de faire le calcul, 2 au n devient effectivement beaucoup plus droite,
beaucoup plus haut que n cubes si vous regardez les axes assez loin.
Donc remarquerez tout de suite ces axes sont arbitrairement de 2 à 10 sur l'axe x.
>> Et qu'est-ce que ça veut dire?
Cela signifie que 2 personnes à 10 personnes dans la salle.
C'est tout moyen x: taille du problème, quel que soit le contexte.
Et un axe vertical en ce moment est le nombre de secondes ou le nombre d'étapes -
une certaine unité de temps.
Mais remarquez que c'est 0 à 60 et 0 à 10.
Mais si l'on sorte de zoom arrière, comme vous le feriez dans Excel ou un logiciel de cartographie,
et nous remontons à 200.000, remarquez que quelque chose comme 2 à n
va complètement submerger les temps d'exécution de carré n,
n cubes, n log n - tout ce dont nous avons parlé jusqu'à présent.
Et pourtant, le hic, c'est quand vous commencez à parler de choses comme Facebook
où vous avez beaucoup, beaucoup, beaucoup de gens tous interconnectés,
vous avez n personnes, dont chacun peut en avoir autant que des amis n
si tout le monde est une sorte de copain-copain dans le monde,
eh bien, c'est n fois n déjà, donc c'est n carrés amitiés possibles,
au moins dans 1 sens, n carrés amitiés possibles.
Alors que suggère déjà que la recherche graphe social de Facebook, pour ainsi dire,
peut commencer à être exprimé dans ces sortes de formules.
>> Nous allons revenir et faire ce beaucoup plus concret,
mais pour l'instant, l'objectif pour les prochaines semaines de nombreux
va pour être sûr de ne pas aller sur les algorithmes de mise en œuvre ou code
qui finissent par prendre autant de temps que quelque chose comme ça.
Mais la chose de fascinant de l'informatique si vous continuez dans ce domaine
prendre des cours comme CS121, CS124, qui sont tous deux des cours théoriques,
c'est qu'il ya effectivement quelques problèmes qui existent dans ce monde
que, fondamentalement, aussi loin que nous le savons, ne peuvent être résolus plus vite
que le pire de ces graphiques suggère en fait.
Donc, il ya beaucoup de problèmes ouverts dans ce monde pour faire beaucoup mieux que les humains ont à ce jour.
>> Donc, nous allons commencer puis avec cet exemple.
Nous avons vu Sean lutte avec cet appareil photo, trop maladroitement sur vidéo.
Mais la réalité était quand Sean a été chargé de trouver sur un tableau comme celui-ci au nombre 7,
rappelle que j'ai dit, "Il ya quelque part derrière ces morceaux de papier ou des portes blanches
"Le chiffre 7. Sean, le trouver pour nous."
Et il était extrêmement difficile à regarder
parce qu'il a été vraiment du mal avec ce problème.
Mais la réalité était Sean a fait comme tout le monde dans la salle pourrait avoir fait.
Il a fallu un peu plus d'une personne typique peut avoir,
mais il a supposé qu'il y avait un truc à ce problème,
il a supposé qu'il manquait quelque chose.
Et il n'a pas aidé des centaines d'yeux portaient sur lui.
>> Mais la réalité était si l'entrée au problème est une série de nombres aléatoires
et on vous demande de trouver 1 tel numéro,
le meilleur que vous pouvez faire est de recherche linéaire.
Commencez par la gauche, vers la droite, ou de commencer à droite, vers la gauche.
Rétroactivement, on pourrait penser, «Sean, pourquoi ne pas vous venez de commencer à partir de l'autre extrémité?"
Eh bien, 7 aurait tout aussi bien pu ici au hasard,
mais j'ai délibérément mis là parce que je pensais qu'il ne va pas commencer à la fin.
Donc j'ai un peu manipulé la situation, mais par hasard 7 aurait pu être n'importe où.
Ainsi, à partir de l'extrémité droite aurait pu être mieux alors,
mais que faire si l'an prochain je déménage 7 ailleurs?
Ce n'est pas une solution radicalement nouvelle du problème -
à partir de 1 extrémité ou l'autre - quand vous êtes pas donné d'autres hypothèses.
Donc, Sean a commencé à chercher à travers les chiffres et il dit: «5. Ce n'est pas ici."
Puis il est allé là et j'ai vu 19, puis il s'arrêta pendant environ 20 secondes,
puis il a ouvert ce pour le 13, puis il est devenu évident
qu'il ne semble pas y avoir de modèle ici.
Il n'était pas 1, 2, 3, 4 ou analogue. Il y avait des lacunes dans les chiffres, ce qui n'a pas aidé.
Et aussi, le fait que j'ai utilisé ces pièces bon marché de papier pour couvrir les numéros
est en fait délibérée, parce que si j'ai enlevé tous ces morceaux de papier,
plupart d'entre nous, Sean inclus, aurait probablement regarda sorte de macroscopiquement
au tableau et dit: «Oh, 7 est évidemment juste là." Nous l'avons fait instantanément.
>> Et c'est peut-être la façon dont le cerveau humain fonctionne dans une certaine mesure,
mais en réalité, ses yeux ou de l'esprit est probablement l'écrémage des numéros de droite à gauche,
de gauche à droite, au milieu de sur - quelque chose se passait physiologiquement
de telle sorte que c'était comme cela se passait instantanément,
mais les chances sont encore à l'intérieur il y avait une sorte de méthodologie pour trouver 7.
Et en effet, maintenant que nous parlons de tableaux et structures de données
et à l'intérieur mémoire d'un ordinateur, la seule chose que nous, les humains peuvent faire
est de regarder emplacements de mémoire individuels 1 à la fois.
>> Ainsi, chaque autre endroit pourrait tout aussi bien être couvert avec une feuille de papier
parce que nous ne pouvons pas le voir de toute façon. Nous pouvons seulement faire 1 chose à la fois.
Donc dans ce cas, en cas de Sean, nous y sommes allés et nous avons ici
et puis nous sommes allés ici, ici, ici, ici, a obtenu intelligent d'ici la fin
et juste un peu sauté celui-ci de façon arbitraire et il a trouvé 7.
Celui-ci n'était pas particulièrement spécial. Elle aussi était en panne.
Mais il a finalement trouvé 7.
Mais maintenant, les plats à emporter est vraiment le meilleur que vous pouvez faire quand donné aucune information
autres que les numéros au hasard triés consiste à partir de la gauche ou de la droite commence.
Ou diable, vous pouvez ouvrir des portes au hasard, mais même alors, qu'est-ce que cela signifie d'être aléatoire?
Eh bien, nous aurions en quelque sorte à formaliser ce que cela signifie de commencer ici,
puis aller ici, puis allez ici. Sean a bien fait, et il était juste amusant à regarder.
Et si au lieu nous changeons le problème un peu et faire apparaître Sean cette année, si vous voulez?
Souhaitez-on être à l'aise de monter sur scène et la résolution d'un problème un peu différent
et apparaissant sur l'appareil photo?
>> Allons au-delà de l'orchestre parce que vous les gars ont été très impliqué aujourd'hui déjà.
Que diriez-vous en rose, dans le chapeau? Allez vers le bas. Quel est votre nom? >> Alex. >> Alex. D'accord.
Donc Alex sera Sean cette année et apparaîtra dans les prochaines années
CS50 valeur de conférences.
Alex, ravi de vous rencontrer. >> Ravi de vous rencontrer aussi.
Le défi à portée de main pour vous est que vous avez un peu plus facile
en ce que je vous dis les mêmes numéros sont ici, mais ils sont maintenant triés.
Alors maintenant, votre objectif est de trouver le numéro 7.
Et en fait, nous devrions vraiment faire ceci - Tu es genre de tricherie, comme un ordinateur ne serait pas,
en regardant ce que les chiffres étaient il ya un instant.
Avec de la craie est en fait ce ne va pas aider tant que ça,
mais supposons que vous ne savez pas ce que le tableau original est.
Tout ce que vous savez maintenant, c'est que vous avez un tableau de nombres triés
qui pourrait avoir des écarts entre eux, et votre but est de trouver le numéro 7.
Comment voulez-vous, un être humain raisonnable étant, prendre pour trouver le numéro 7?
>> Aller de bas en haut? Ok >>. Allez faible à élevé.
Et ne pas les déchirer. Disons simplement les relever afin de pouvoir les réutiliser.
Ok, donc 1. Attendez. Avant de continuer, qui était de 1, manifestement erronée.
Donc ce qui se passe dans votre esprit maintenant? Quelle est votre prochaine étape?
Le prochain. Ok >>. Le prochain. Bon. 3, de manière incorrecte. Quelle est votre prochaine étape?
Continuer à avancer. Tous droits >>. Continuer à avancer. 5.
Donc, continuez à aller, et laissez-moi vous remettre ce pour la postérité.
7. >> Excellent. Très bon. Trouvé le numéro 7. [Applaudissements]
Donc, ce qui était bon, mais trop Sean trouvé le numéro 7.
Et je soutiens que vous n'avez pas vraiment exploité cette information supplémentaire,
qui est que ces nombres sont triés.
Ainsi pouvons-nous faire mieux? Toutes les suggestions ici? Oui, à l'arrière.
[L'élève] Recherche binaire. >> Je n'ai aucune idée de ce que recherche binaire est.
>> [L'élève] Commencer au milieu. >> Commencer au milieu. D'accord. Donc, nous allons voir si nous pouvons y arriver.
Donc, si on vous dit au lieu de départ à partir du milieu, aller de l'avant et d'ouvrir la porte du milieu.
Il ya 8 d'entre eux, de sorte que vous allez avoir à choisir arbitrairement le
légèrement vers la gauche ou vers la droite. D'accord. 7! [Applaudissements] Très bien.
D'accord, mais où allions-nous avec ça?
Supposons que pour briser l'égalité que vous aviez commencé ici
parce qu'il est tout aussi pu se passer ainsi.
Nous là juste pour savoir que 7 était là. Donc, c'est 13.
Donc, si ils sont triés et nous avons commencé dans le milieu,
quel serait le prochain mouvement optimal ont été?
Aller à gauche. Et donc voici l'exemple du livre de téléphone de nouveau.
Si 13 est ici et nous savons que la liste est triée,
alors tous ces morceaux de papier sont sans intérêt pour nous maintenant
parce que nous savons déjà que 7 doit être à gauche
si ces nombres sont triés et nous avons trouvé 13.
>> Alors, quel est votre prochain déménagement ici? >> Allez à gauche. >> Très bien.
Alors, allez à gauche, et - attendez, hey, hey, hey. C'est de la triche.
Alors vous avez trouvé 7, mais ce qui est l'algorithme que nous venons d'appliquer?
Commencer au milieu. Bon >>. Alors, quel est le prolongement logique de cette même idée?
Oh, juste pour eux. >> Exactement. >> Je commence donc ici. Bon >>.
Alors maintenant, nous sommes allés un peu à gauche à nouveau. Il est 3.
Mais les plats à emporter est intéressant, c'est maintenant que l'on ne vous pas à vous en soucier?
Ces 2. Ces 2 >>. Alors maintenant, celui-ci peut aller loin, celui-ci peut aller loin.
Maintenant, le problème qui était de 8, puis a été de 4 taille est la taille 2.
Nous recevons assez proche. Encore une fois, allez au milieu de ces 2 éléments.
>> D'accord. Donc, c'est une sorte de malheureux que maintenant nous allons toujours à gauche parce que nous sommes arrondi vers le bas.
Mais c'est bien parce que maintenant nous le jetez et tout le reste, nous laissant avec seulement 7.
Donnons une salve d'applaudissements. Nous avons trouvé 7 fois. [Applaudissements] D'accord. Bien sûr.
Accrochez-vous pour seulement 1 seconde de plus.
Même si ce genre de processus suivant a pris un peu plus longtemps que nous avons pensé qu'il serait,
franchement, vos premiers instincts étaient les meilleurs, pas vrai? Nous avons trouvé 7 instantanément.
Mais nous avons trouvé 7 plus rapide, peu importe ce que, dans cet exemple par rapport à celui-ci
parce que si les numéros sont tous triés, un peu comme les pages d'un annuaire téléphonique,
vous pouvez en effet couper la moitié du problème encore et encore et encore.
Et ce n'est pas tout à fait aussi facile de voir cela avec seulement 8 chiffres
par opposition à un annuaire de 1000 pages où vous avez vraiment le voir visuellement,
mais dans ce cas là quand Sean cherchait 7,
le nombre d'étapes dans le pire des cas, cela aurait-il emporté? >> [L'élève] 7.
7 dans le pire des cas. Eh bien, dans le pire des cas non pas 7 s'il ya 8 portes ici.
Il lui aurait fallu 8 étapes.
>> Donc, si il ya des portes n, il aurait pu prendre Sean il ya quelques années n étapes.
Maintenant, dans votre cas, Alex, étant donné que ces nombres sont triés -
et nous pouvons en déduire ce genre de d'où nous avons été à ce jour dans cette histoire -
quel est le temps d'exécution de l'algorithme plus intelligent Alex
de partir du milieu, puis répéter?
[L'élève] 3. >> Donc, il va y avoir 3, à peu près, si vous allez 8 à 4 à 2 à 1.
Donc 3 étapes ou, plus généralement, c'est à nouveau log n.
Chaque fois que vous réduire de moitié et réduire de moitié et réduire de moitié et réduire de moitié,
c'est une expression de cette idée de log n.
Et pour que vous aurait pris seulement 3 étapes, et elle l'a fait
une fois que nous avons ouvert les portes de réduire de moitié et réduire de moitié,
alors que cela aurait pris quelques Sean 7 ou 8 étapes.
Je vous remercie d'être avec nous cette année. >> Merci. Nice Vous réunion.
Merci à Alex. De même >>. [Applaudissements]
>> Quel est alors l'implication réelle de cette situation?
Maintenant, imaginez que ce n'est pas 8 portes, ce qui, franchement, nous pouvions tous trouver quelque chose
8 portes derrière assez rapidement simplement en déchirant les morceaux de papier et d'aller avec nos instincts.
Mais que faire si il ya un million de portes? Et si c'est 4 milliards portes?
Dans le cas de 4 milliards de portes, vous allez vraiment vouloir aller avec l'algorithme d'Alex,
binaire de recherche que nous allons commencer à l'appeler ou de diviser pour régner, plus généralement,
où vous gardez réduire de moitié et réduire de moitié le problème,
parce que si vous avez 4 milliards portes, combien de fois pouvez-vous couper 4 milliards de moitié?
[L'élève] 32. >> Il s'agit en fait 32. Vous pouvez nous en sortir sur un morceau de papier ou dans votre tête.
Vous allez 4 milliards à 2 milliards to 1 milliard à un demi-milliard, à 250 millions d'euros, point, point, point.
Et si vous faites le calcul, vous allez en effet obtenir 32,
et qui se rapporte effectivement à l'informatique car nous avons l'habitude de compter des puissances de 2.
2 à la 32 arrive à être de 4 milliards d'euros.
Donc, il ya beaucoup d'intérêt pour ce genre de puissances de 2 en informatique.
>> Mais qu'est-ce environ 8 milliards? Combien de pas est ce que cela va prendre s'il ya 8 milliards portes?
[L'élève] 33. Alors >> 33. Et s'il y avait 16 milliards portes? Combien de pas est ce que cela va prendre?
[L'élève] 34. >> 34. Nous pourrions poursuivre ce genre d'ad nauseam. Mais c'est une chose puissante.
Vous pouvez introduire des milliards de plus d'entrées à votre problème, mais pas une grosse affaire,
vous venez de prendre 1 morceau supplémentaire hors de lui et nous donne ainsi quelque chose comme binaire de recherche
ou diviser pour régner, plus généralement.
Mais je suis un peu tricher ici, non?
Dans le cas de l'algorithme d'Alex, elle avait un avantage sur Sean.
Elle savait que ces chiffres ont été triés, mais Alex ne pas avoir à les trier elle-même.
J'ai l'avance est venu vers le tableau noir et la nature des assurés
que j'ai dessiné les tous dans un ordre trié, puis je les ai recouvertes de papier.
Mais combien de travail cela s'est-il me prendre?
Si nous avions commencé avec ces numéros dans un ordre apparemment aléatoire -
dans ce cas, ces chiffres simples, 1 à 8 ici -
comment pouvons-nous aller sur le tri de ces valeurs?
Si vous étiez un homme chargé de cette tâche, ce type d'approche intuitive prendriez-vous
pour trier un tas de chiffres?
Ces choses ont été présentés comme des pièces de puzzle. Ouais.
>> [Étudiants] je prendrais chaque numéro et de le comparer à chacun
et continuez vers la gauche. >> Très bien.
Alors, prenez chaque numéro, de le comparer à celui à côté de lui,
et puis juste continuer à avancer le long de la liste, le type de rejiggering choses que vous allez.
Nous avons donc ici une chance pour peut-être un peu plus les gens à s'impliquer.
Avons-nous plus de 8 volontaires qui aimeraient venir?
Un peu moins de pression puisque vous n'êtes pas le seul. 1, 2, 3, 4, 5, 6, 7, 8.
Allez vers le bas. Les gars, vous allez être les numéros 1 à 8.
Voyons voir si nous ne pouvons pas faire ce tri pour Alex beaucoup de la même manière que je l'ai fait à l'avance.
1, 2, 3, 4.
Allez-y et si vous voulez, s'alignent sur scène entre le pupitre et moi ici
dans le même ordre que la diapositive à l'écran.
Uh-oh.
Nous allons vous travaillez dans l'exemple suivant. Oh, attendez, attendez. Nous y voilà. Attendez.
L'exemple suivant est maintenant. Ici vous allez. Numéro 8. Venez sur place.
Très bien. Trier selon vous-mêmes à ce sujet.
Faites glisser un peu sur le côté de la musique se trouvent ici.
Nous avons donc 4, 2, 6 - entrer là, par ici, juste là - 3.
Ouais. D'accord. Vous aller là-bas. Non, vous restez là.
Ouais, juste là. Non, je me trompe. Juste là. Bon, très bien. D'accord.
Alors maintenant, nous allons les trier dans un ordre croissant.
>> Comment puis-je m'y prendre?
L'algorithme qui a été proposé il ya un instant pourquoi ne pas simplement comparer
les gens qui sont un peu à côté de l'autre, puis corriger les erreurs,
se déplaçant de gauche à droite.
Nous avons donc ici 4 et 2, manifestement hors de l'ordre. Laissez vous échanger. D'accord.
Alors maintenant, je vais passer à la ligne. 4 et 6, nope. [Rires]
6 et 8, très bon. 8 et 1, permettez-moi de vous échanger les gars. Très bien.
Donc, 8 et 3, échangez-vous les gars.
8 et 7, permettez-moi de vous échanger les gars. 5 et 8, excellente.
Je vous donne une liste triée.
Très bien. Donc, pas tout à fait.
Mais il vaut mieux parce que le nombre de cas plus importants - au point 8 -
ont sorte de bouillonnait de la gauche vers la droite.
Alors, j'ai fait 1 d'entre eux le droit, mais il se sent comme cela ne résout pas complètement le problème.
>> Alors, que proposez-vous nous faire maintenant? >> [L'élève] Continuer à le faire. >> Nous vous continuez à le faire.
Et se rendre compte, encore une fois, nous avons mis les choses juste en ayant tous les êtres humains
sorte d'intelligence s'organisent en fonction de cette image,
mais maintenant nous devons être beaucoup plus méthodique.
Nous devons être algorithmique à ce sujet, comme si nous écrivons le code -
dans ce cas, pseudo-verbale.
Permettez-moi donc essayer de nouveau. Cela a plutôt bien fonctionné. Il n'a pas le résoudre.
Mais quand il doute, essayez et essayez à nouveau. Donc, 2 et 4, ne plus l'aider.
4 et 6. Ah! 6 et 1, soit un peu mieux maintenant.
6 et 3, c'est bien. 6 et 7, 7 et 5, 7 et 8, bien.
Et vous savez, je peux probablement ignorer 8 maintenant parce qu'il est à la fin de la liste.
Peut-être que nous n'avons pas à vous inquiéter au sujet de quelqu'un en passant devant lui.
Mais attendons de voir si c'est une hypothèse fort.
Maintenant, la liste est - putain - pas triée. Essayons encore une fois.
SO 2 et 4, 4 et 1, 4 et 3.
4 et 6, bon. 6 et 5, très bien.
6, 7, et 8, bien. Mais remarquez, je peux juste m'arrêter là maintenant et arrêter ici maintenant?
[L'élève] Oui. Ouais >>?
Que faire si l'un de vous avait été le numéro 9 tout le chemin là-bas?
Il aurait été triés. Bon >>. Il aurait été triés pour la première fois autour.
Bon. Donc, revenons à nouveau. Nous y sommes presque.
1 et 2, 2 et 3, 3 et 4, 4 et 5, 5 et 6, 6 et 7, 7 et 8.
>> Je fait maintenant, mais, encore une fois, je suis un ordinateur qui ne peut faire ce qu'on me dit de faire,
et je me souviens que c'est maintenant que je fait juste fait un peu de travail.
Quelque chose a changé ici.
Je n'ai donc pas techniquement confirmé visuellement ou algorithmiquement que cette liste est bien triée.
Donc, pour faire bonne mesure, juste pour être anale à ce sujet, nous allons faire cette fois-1 plus.
Si 1 et 2, 2 et 3, 3 et 4. Et vous savez quoi?
Pour faire bonne mesure, je vais garder la trace de ma main cette fois
combien de swaps je fais tout pour que je sache combien de travail que j'ai fait en réalité.
3 et 4, 4 et 5, 5 et 6, 6 et 7, 7 et 8. Pas de swaps.
Alors maintenant, je légitimement être idiot pour faire cela à nouveau
parce que si je le faisais pas de travail à travers ce passage des êtres humains,
il est clair que cela va se reproduire si aucun d'entre eux est une sorte de hasard
contradictoirement se déplacer. Alors maintenant, je peux m'arrêter.
Maintenant, nous allons poser la question, combien de travail cela at-il réellement me prendre?
Combien d'étapes ne prendrait-il? N >> carré.
Ouais, donc n carré. Où trouvez-vous n carré de?
Vous devez vérifier chaque numéro -
Il ya un nombre n, et vous devez vérifier chaque numéro avec les nombres n d'autres.
Bon. >> Donc ça n carré. Bon >>.
>> Ainsi, il se sent comme il pourrait très bien être n carré, non?
Il est n de ces gars-là, 8 précisément dans ce cas,
mais chaque fois que je suis passé par cette liste, je comparais la première personne contre le second,
le deuxième contre le troisième, encore et encore et encore,
et quand je suis arrivé à la fin, qu'est-ce que je dois faire? Je l'ai refait.
Donc, si nous généralisons cette explication, nous avons n personnes
et je fais, évidemment, 8 étapes, n étapes, chaque fois que je passe par cet algorithme.
Mais combien de fois dans le pire des cas, puis-je avoir à passer par cette liste de personnes?
[L'élève] N fois. Probablement >> n, à droite, parce que dans le pire des cas,
ce qui est probablement le pire des cas arrangement de ces gars de l'obtenir-aller?
Si elles sont complètement inversé l'ordre
parce que juste suppose que mentalement, let's - Quel est ton nom? >> Bowen.
Bowen. D'accord. Donc Bowen, viens par ici pendant un moment.
>> Supposons que Bowen était là au début de l'algorithme,
et nous ne savons pas ce que tout le monde l'est, mais Bowen ici, selon cet algorithme -
et si vous voulez simplement vous promener avec moi - va bouillonner, comme il l'a fait la première fois,
tout le chemin vers la fin.
Mais supposons que la personne à côté de Bowen était le numéro 7.
Je dois revenir en arrière et obtenir le numéro 7, ce qui signifie que je dois y aller tout le chemin de retour ici.
Maintenant, je dois avoir cette balade même avec la personne qui est le numéro 7.
Mais que faire si ensuite le numéro 6 était à côté de lui aussi?
Ensuite, je dois revenir en arrière et obtenir 6.
Encore une fois, à chaque itération de cette boucle je parle à chacun des n personnes,
et je pourrais avoir à faire n de ces promenades pour m'assurer que je suis en tirant
tous les grands éléments de dos et d'avant en arrière jusqu'à la fin de la liste.
Tant de choses n n fois est à n fois n ou n carrés.
>> Donc ici nous avons déjà un algorithme qui n'est plus n, ce n'est plus log n,
c'est en fait pire que tout ce que nous avons fait auparavant.
Donc genre de Alex eu de la chance dans ce que j'ai fait tout le travail apparemment à l'avant pour elle,
l'ensemble des travaux coûteux, de sorte qu'elle puisse profiter de cet algorithme de recherche binaire,
qui est log n.
Mais ce qui est cohérent avec le thème de lundi.
Nous avons donné un peu plus d'espace, nous avons utilisé plus de bits, afin d'accélérer notre temps de course.
Donc, un peu comme il ya ce compromis entre le temps et l'espace,
il pourrait aussi bien être compromis entre le temps passé en sorte avant de faire les choses prêt à aller
et fait exécuter un algorithme comme la recherche. Essayons une autre.
Si vous les gars ne me dérangerait pas juste rapidement réorganiser pour correspondre à ce que vous encore,
nous allons essayer quelque chose de légèrement différent, où ce n'est pas tout à fait aussi simple
comme on vient de corriger toutes les erreurs par paires, ce qui est super intuitive.
Disons plutôt être un peu plus délibéré et le faire.
Celui-ci aussi je vous propose est sans doute assez intuitive.
>> Choisissons la plus petite personne de la liste encore et encore. Alors on y va.
4, vous êtes la plus petite personne, j'ai donc vu jusqu'à présent,
donc je vais mentalement rappeler que simplement en pointant sur vous pour l'instant.
2. Ooh! Oubliez le numéro 4. Je viens de trouver le plus petit élément nouveau dans cette liste.
Je vais genre de souvenir. 6, 8.
Ooh! 1. Au revoir. Alors maintenant, je vais rappeler le numéro 1.
Nous savons que 1 est le plus petit, mais je suis l'ordinateur. Que faire si il ya un 0?
Que faire si il ya un -1? Je dois continuer.
Donc, 3, 7, 5, nope. D'accord. Donc, le numéro 1 est la plus faible.
Laissez-moi vous sélectionnez dans la liste - nous allons aller de cette façon -
et vous mettre arbitrairement au début de la liste.
Maintenant, attendez une minute. J'ai un peu triché.
Si ces gars-là ne représentent pas une liste de 8 personnes, mais un tableau,
8 gros morceaux de mémoire contiguë - ça vous dérange pas en arrière pour un instant?
Il ya en fait pas de place pour vous ici.
Alors, comment pouvons-nous faire de la place pour - quel est votre nom? >> Sammy. >> Sammy.
Comment pouvons-nous faire de la place pour Sammy?
>> Nous nous déplaçons les n qui sont devant moi. Ok >>.
Donc, nous pourrions déplacer les n personnes qui sont devant lui,
donc si vous voulez les gars de prendre 1 délibéré, étape spectaculaire vers la gauche.
Ils ont tous fait cela à l'unisson, mais la dernière fois que j'ai écrit un peu de code,
vous ne pouvez pas trier de passer beaucoup de choses à la fois.
On pourrait le faire dans une boucle, une fois en mouvement tout le monde à la fois.
Donc, si vous les gars ne me dérangerait pas en reculant vers la droite,
et Sammy, si vous pouviez revenir en arrière, car il n'y a toujours pas de place pour vous,
Maintenant, nous allons le faire. Où était Sammy il ya un instant? Juste là.
Il ya donc une lacune. Ainsi, vous pouvez déplacer dans l'angle de Sammy.
Maintenant personne suivante et maintenant personne suivante, maintenant personne suivante. Maintenant, nous avons la place pour Sammy.
Maintenant, quelqu'un dans le public - ce qui était bon, que c'était exact,
cela faisait un peu de temps - ce qui est plus rapide? Ouais.
[L'élève] Un nouveau tableau? >> Qu'est-ce que c'est? >> [L'élève] Un nouveau tableau? >> Très bien.
>> Donc compatible avec cette idée de juste compromis, pourquoi ne pas simplement faire un nouveau tableau
puis Sammy nagera dans l'espace en face de ces personnes, par exemple,
et nous pouvons commencer à remplir un nouveau tableau tout à fait. Cela aussi pourrait fonctionner.
Mais je ne suis pas intéressé à passer plus de place aujourd'hui. Ce qui est une autre approche?
[L'élève] Swap. Ok >>. Nous pourrions simplement échanger ces 2 gars. Quel est ton nom?
Mario. Mario >>. Alors Mario, vous étiez en train ici.
Sammy, tu peux revenir en arrière un instant? Mario était là.
Nous n'avons pas de place pour toi plus, donc si vous ne me dérangerait pas aller là où Sammy est,
nous allons mettre Sammy ici, et maintenant, je dirais que le fonctionnement échange de Sammy était beaucoup plus rapide.
Nous avons fait 1 opération d'échanger ces gars-là, ou peut-être 2 à échanger ces gars-là,
mais nous n'avons pas fait 1, 2, 3, 4, de sorte que se sent mieux. Maintenant, attendez une minute.
J'ai en quelque sorte fait qu'aggraver le problème, car le numéro 4 était un peu proche du début.
Maintenant, numéro 4 est un peu plus près à cette fin, mais je ne sais pas vraiment ou égal.
Donc, c'est juste la malchance que le numéro 4 est un peu plus loin de son lieu de destination.
Donc, nous allons maintenant répéter cet algorithme.
>> Pour résumer, aussi longtemps que cette histoire était tout ce que nous n'avons été marcher dans la liste
à la recherche de la plus petite personne numérotées.
Alors maintenant, nous allons le faire à nouveau. Nous n'avons pas à vous soucier de Sammy plus.
On peut juste aller ici. Ooh! Numéro 2. C'est un chiffre assez faible.
6, 8, 4, 3, 7, 5. Bon, très bien.
Et heureusement, par hasard, je n'ai pas à déplacer - >> Willie.
Willie parce qu'il est à sa place en ce moment.
Faisons-le encore une fois et ignorer ces 2 gars.
6. C'est un chiffre assez faible. Ooh! 8 est certainement plus grand.
4. Concentrons-nous sur 4. Ooh! 3 est encore mieux.
7 et 5. Alors, que faisons-nous maintenant avec - >> Roger. >> Roger?
Nous allons lui échanger avec le numéro 6.
Donc, si 6 et 3 aimerait échanger,
nous avons maintenant obtenu sorte de la chance que 6 est plus proche de l'endroit où elle devrait être,
mais c'est juste une coïncidence ici. Donc, nous allons maintenant passer ici.
8 est un nombre assez petit. Ooh! 4 est plus petite.
6, 7, 5. Que devons-nous faire maintenant? Swap >>. >> Exactement.
Alors maintenant, nous allons faire ce genre de rapide.
8, 6, 7, 5. D'où vient 5 aller? Bon. D'accord.
6, 7, 8. 6 obtient de rester là où elle est. Quel est ton nom? >> Rosalie.
Rosalie arrive à rester où elle est. 7 doit à - Voyons voir. 7, 8. D'accord.
Donc 7 arrive à rester où elle est. Quel est ton nom? Amna >>. Amna >>.
>> Donc, Amna arrive à rester où elle est, et le numéro 8 est déjà là où il devrait maintenant être.
Bon, très bien. Se sent comme nous ne faisons que créer du travail pour nous-mêmes ici, cependant.
Quel est finalement le temps d'exécution de cet algorithme?
Si l'on pense à ces gens pas comme 8, mais en tant que n? >> C'est n.
Il est n étapes, mais nous vérifions à chaque fois.
D'accord. N, mais que vous vérifiez à chaque fois?
D'accord, mais si elle est n étapes, je ne devrais pas avoir pu vous triez simplement en allant 1, 2, 3, 4?
Oh! D'accord, c'est une grosse différence.
Donc n carré pourquoi? Qu'est-ce qui se passe réellement?
Il ya n personnes dans cette liste, mais pour trouver la plus petite personne dans la liste
dans le pire des cas, combien de démarches dois-je prendre? N. >>
>> N, à droite, parce que dans le pire des cas, le numéro 1 est tout le chemin là-bas,
donc je dois aller le chercher ou elle.
Et puis, quand je me suis finalement rendu compte 1 était le plus petit, puis il est assez rapide pour les échanger.
Mais maintenant, je dois commencer par le début et chercher qui?
La personne la plus petite suivante, qui est de 2. Lorsque, dans le pire des cas est de 2?
Oh, mon Dieu. C'est tout le chemin là-bas à la fin.
Alors maintenant, je viens de faire un autre n étapes, un autre des étapes n.
Et si nous avons des gens n et dans le pire des cas, la personne est plus petit n quelques pas,
c'est encore n fois n, et nous avons à nouveau n carré.
Ce ne se sent pas bien.
Et en fait, même dans le meilleur des cas - supposer qu'ils commencent triés -
combien d'étapes faut-il pour moi en utilisant cet algorithme pour trier ces personnes n?
N au carré. >> J'ai entendu n carré. Pourquoi n au carré?
Parce que vous avez encore à vérifier à chaque fois. Ouais >>.
Et vous devez les échanger. >> Même si nous, les humains sont des sortes de omniscient
dans le sens visuel que nous pouvons juste une sorte de voir que ce sont triés,
un ordinateur n'est pas si malin.
Il va regarder ici et ici et ici,
mais si ce qu'il cherche le plus petit élément,
vous ne savez que vous avez trouvé le plus petit élément de ce moment-là? Une fois que vous êtes à la fin.
Mais à ce stade, vous avez trouvé que le plus petit élément pour le moment.
Vous ne savez pas nécessairement quoi que ce soit d'autre au sujet de l'état du monde.
Donc, il faut aller encore et encore et encore.
>> Alors cette fois je ne regarde muet parce que je vérifie, d'accord, 2, tu es le plus petit,
mais je ne sais pas qui, au total encore.
3, 4, 5, 6, 7, 8. Bon, très bien. 2 était bien plus petit.
Maintenant, nous allons trouver le plus petit côté. D'accord.
3, vous êtes actuellement le plus petit. Voyons voir. 4, 5, 6, 7, 8. Bon, encore une fois eu de la chance.
3 était bien au bon endroit. Mais je vais continuer à le faire encore et encore et encore.
Comment pouvons-nous faire un tant soit peu mieux?
Au lieu d'avoir les gens paires de bulles du plus petit au plus grand à
et au lieu d'aller d'avant en arrière dans la liste des choix de la personne la plus petite, puis,
pourquoi ne pas insérer à la place de ces personnes dans une étape nouvelle liste par étape?
Essayons ceci. Maintenant laissez-moi appeler cette chose tri par insertion.
Nous voici donc ici. Numéro 1. Je ne se soucie pas de n'importe qui d'autre dans cette liste.
Mon objectif maintenant est de mettre le numéro 1 au début d'une liste triée.
Et je vais proposer puisque je n'ai que 8 gros morceaux de la mémoire,
arbitrairement en ce moment je suis le mur entre ma liste de soi-disant non triés,
et toute personne qui est derrière moi, je vais la revendication est triée.
Nous avons donc maintenant le numéro 1.
Je veux l'insérer dans ma liste triée, donc je vais juste passer mon mur ici,
et maintenant je prétends que cette liste est triée, cette liste n'est pas triée - du moins pour autant que je sache.
Je ne peux pas voir tous les numéros à la fois.
>> Maintenant, il m'arrive de rencontrer le numéro 2. Que dois-je faire de lui?
Je vous insérez maintenant dans la liste triée. Mais remarquez avec quelle facilité ce que c'était.
Je viens de regarder. Le numéro 1 est là. Oh, bien sûr 2 passe à côté du numéro 1.
Maintenant que dois-je faire avec 3? Je vous insérer dans la liste triée. Mais c'était super facile.
C'est super facile, c'est super facile, c'est super facile, super facile, super facile.
Et maintenant, tout est trié derrière moi, et combien d'étapes ne prendrait-il?
[Étudiants] N. >> Donc, c'est seulement n. Nous avons été chanceux.
Ce n'est que n pourquoi? >> [L'élève] Parce que la liste a été triée.
La liste est déjà triée. Nous avons donc eu de la chance.
Mais nous avons conçu un algorithme qui exploite cette fois ce genre de chance,
que le meilleur des cas, de ne pas perdre de temps inutilement.
Donc, nous avons maintenant ce que nous appellerons sortes de bulles
où les gens sorte de bulle jusqu'à deux à deux.
Nous avons maintenant tri par sélection où nous arracher la plus petite personne encore et encore.
Et maintenant nous avons le tri par insertion où l'on sorte de façon proactive mettre les gens là où ils appartiennent
dans une liste triée de plus en plus.
Si nous pouvions, une salve d'applaudissements pour ces gars ici. [Applaudissements]
Prenons notre 5 minutes de pause ici.
Et quand nous reviendrons, nous ferons sauter ensemble de ces algorithmes hors de l'eau
quelque chose de mieux. Très bien. Merci beaucoup. Vous pouvez garder ces souvenirs.
Très bien. Nous sommes de retour.
>> Et pour résumer très vite, nous avons eu ces approches 3 différents pour le tri,
tout l'intérêt de ce qui était pour arriver au point où quelqu'un comme Alex
pourrait rechercher une liste de numéros rapides que quelqu'un comme Sean pouvait.
Et même si nous avons des exemples simples avec 8 numéros,
vous pourriez facilement extrapoler à 8 pages, 8 milliards de pages Web,
ou 800 millions d'amis sur Facebook.
Ainsi, ces algorithmes peuvent certainement évoluer pour ces types de valeurs,
et les idées sont finalement les mêmes.
Alors tri à bulles est le premier où l'on sorte de barboter jusqu'à la plus grande personne
tout le chemin à droite en échangeant les gens par paires.
Puis nous avons eu ce que nous appellerons tri par sélection où j'ai un peu plus délibérément
continué à regarder dans la liste, sélectionner le plus petit nombre encore et encore et encore,
la suite logique de ce qui est que la liste est finalement triés.
Puis, dans la troisième, j'ai inséré les gens à leur juste place,
et nous avons un exemple très artificiel en ce que la liste a été déjà triés,
mais c'était pour envoyer le message que dans le cas du tri par insertion,
vous pouvez avoir de la chance.
Si les numéros sont déjà triés, ça ne va vous prendre des mesures pour s'assurer n autant,
alors que vous êtes tri par sélection vision en tunnel un peu plus
et vous n'avez pas toujours se rendre compte que la liste est déjà triée.
Voyons donc ce tri à bulles en action ici.
Dans l'exemple suivant, nous sommes sur le point de voir des barres verticales
dont les hauteurs représenter des nombres afin que nous puissions régler le tri des visualize arriver.
Plus la barre est haute, plus le nombre; plus la barre est grande, plus le nombre.
>> Et nous allons le jouer à cette vitesse par défaut.
Ça va aller un peu vite pour le moment, mais le rouge est à l'affiche de 2 bars
on compare côte à côte.
Et si vous regardez attentivement, ce qui se passe, c'est que si les barres sont hors d'usage,
le plus petit est déplacé vers la gauche, plus l'un à droite,
et puis vous continuez à avancer.
Donc, si nous le faisons encore et encore, vous remarquerez que les plus petites barres
vont continuer à inching leur chemin vers la gauche
et les plus grandes barres vont continuer à inching leur chemin vers la droite.
Et en effet, nous commençons à voir un modèle tout le chemin sur la droite
comme nous l'avons vu 8 et puis 7 éventuellement bouillonne à l'autre bout de notre liste humaine.
Donc, cela va très vite devenir un peu fastidieux, alors laissez-moi arrêter ce pour un moment.
Permettez-moi de changer la vitesse beaucoup plus rapide.
Je ne change pas l'algorithme, je fais juste l'animation se produire plus rapidement.
Tri à bulles Pourtant, même algorithme,
mais maintenant vous pouvez voir beaucoup plus vite que notre démonstration verbale
que les plus grands éléments sont en effet bouillonne vers le haut.
>> Soit dit en passant, ces petits carrés en bas à gauche et en bas à droite
ne sont que des petits rappels concernant le nombre de comparaisons que vous faites.
Mais pour l'instant, nous pouvons nous concentrer sur la pyramide qui est train de prendre forme, et voilà.
Le plus petit élément est sur la gauche, le plus grand sur la droite, et tout le reste entre les deux.
Maintenant, nous allons plutôt jeter un oeil à tri par sélection.
Je vais aller de l'avant et appuyez sur Stop. Nous allons obtenir un nouvel ensemble aléatoire de barres.
Tri par sélection, rappel, parcourt la liste encore et encore et encore,
arracher le plus petit élément. Donc, voici tri par sélection.
On dirait qu'il ya moins de travail passe en ce moment parce que nous ne sommes pas comparer deux à deux
mais nous sommes juste une sorte de cherry picking les plus petits éléments de droite à gauche.
Cela a pris très peu de temps, il ya donc une dichotomie déjà.
Juste parce qu'un algorithme est dit de prendre le temps au carré n, comme tri à bulles
et comme tri par sélection, ceux qui sont vraiment pires moments de cas en cours d'exécution.
Par exemple, dans le cas de, disons, tri par sélection,
En fait, je suis sélectionnant la plus petite personne et de mettre lui ici,
alors je vais le faire à nouveau, alors je vais le faire encore une fois,
mais il y avait une légère optimisation que je pourrais faire.
>> Dès que je me suis déplacé numéro 1 ici - Sammy dans ce cas -
qu'est-ce que je dois faire avec lui par la suite? >> [L'élève] Laisse-le.
Laissez-le, non? Rien.
Je n'ai pas besoin de toujours parler à nouveau Sammy parce que si j'avais choisi le plus petit élément
et le mettre ici, pourquoi perdre du temps aller jusqu'au bout de ma liste?
Sur la prochaine itération permettez-moi de réellement se déplacer que le numéro 2, pour le numéro 3.
Donc, en réalité, je ne faisais pas les choses n n fois.
Je faisais des choses n, alors n - 1 choses, alors n - 2 choses, alors n - 3 choses,
alors n - 4, point, point, point.
Nous avons un peu d'une série géométrique, ce qui signifie simplement
vous ajoutez des numéros de plus en plus petites.
Non n + n + n + n mais n + 7 + 6 + 5 + 4 + 3 + 2 + 1.
Et qu'est-ce qui fonctionne généralement avéré être -
Je vais gâcher ma planche ici pour un instant -
qui va travailler à être quelque chose comme n (n - 1) / 2
si nous juste une sorte de coup d'oeil à l'arrière d'un livre de maths où vous avez tous les cheat feuilles
pour les formules.
Si vous êtes juste ajouter quelque chose de n + n - 1 + n - 2, cela revient à quelque chose comme ceci.
Et si nous multiplions ce genre de sortir, qui est n au carré moins n / 2.
Je répétais n carré, mais, et c'est parce que j'étais un peu en prenant un raccourci mental
car, en réalité, moins carré n n divisé par 2 est en effet le véritable nombre d'étapes
qu'un algorithme comme tri par sélection prendrait si on a vraiment compté jusqu'à
l'ensemble de ces comparaisons et tout le travail peu occupé que nous faisions.
Mais franchement, une fois n arrive à être comme un million ou un milliard, qui diable se soucie
si vous faites un milliard de moins carré d'un milliard divisé par 2?
Un milliard carré est un chiffre énorme.
Vous pouvez prendre un autre milliard hors de lui avec - n. Ce n'est pas une grosse affaire.
Donc, plus les nombres deviennent les moins importantes de ces conditions inférieures sont ordonnées.
Qui se soucie si vous divisez par 2 si vous parlez quadrillions de nombre d'étapes?
>> Donc, en général, les informaticiens ont tendance à jeter tout mais le plus grand terme,
et nous venons sorte de simplifier le monde et dire que cet algorithme
a pris des mesures à peu près n carré. C'est le temps d'exécution d'un algorithme.
Donc, nous allons revenir sur ce point dans un instant avec quelques exemples concrets,
mais pour l'instant, c'est un peu de la motivation derrière tout intuitive simplifiant notre monde
et parler des termes les plus importants plutôt que d'entrer dans toutes ces formules de fantaisie.
Donc, c'était tri par sélection, et nous avons eu un peu de chance là-bas.
Regardons le tri par insertion. Permettez-moi aller de l'avant et de commencer celui-ci aussi.
Maintenant, remarquez le modèle de ce qui se passe est un peu différent,
et nous avons commencé avec des nombres aléatoires,
mais si l'on fait de compter le nombre d'étapes dans le pire des cas,
si la liste a commencé tout à fait dans le bon ordre,
nous ne ferions que de prendre des mesures n de réaliser autant.
>> Mais si la liste devait effectivement vers l'arrière - par exemple, dans ce cas ici -
remarque alors nous avons à faire beaucoup plus de travail dans ce cas.
Et il devrait me sens un peu de vous comme celui-ci est une sorte de travailler plus fort
pour obtenir ces éléments plus petits à gauche, et c'est parce que nous avons eu de chance.
La liste a été triée par accident dans le sens inverse.
En revanche, avec le tri par insertion si nous imiter ce que nous avons fait avec nos hommes ici
en commençant par tout le monde, puis triés commencer, il est un algorithme assez bon, non?
C'est déjà, en fait, triées.
Donc, nous allons essayer de résumer exactement combien de temps ces choses nous prennent
en introduisant un peu de jargon ou de la notation qui est en fait beaucoup plus simple
que le genre de fanciness suggère.
Cette chose ici, ce grand A sur l'écran, ce qui est un informaticien utilise généralement
pour décrire le pire temps d'exécution d'un algorithme.
>> Encore une fois, par le pire des cas, il est totalement dépendant du contexte.
Ce que nous entendons par le pire des cas varie totalement basé sur le problème dont nous parlons.
Mais dans le cas du tri, ce qui est le pire possible?
Tout est à l'envers, car il se sent juste comme ça représente beaucoup de travail pour nous.
J'ai griffonné quelques-uns des algorithmes que nous avons vu jusqu'à présent:
recherche linéaire, binaire de recherche comme avec l'annuaire ou les morceaux de papier,
puis trier tri à bulles, tri par sélection, d'insertion et comme nous l'avons vu de nos hommes,
puis 1 autre qui est finalement va être appelé tri par fusion.
Donc, à la recherche linéaire dans le pire des cas, combien d'étapes faut-il pour trouver le numéro 7
si il ya des portes n comme Sean face? >> [L'élève] N.
N. Donc, nous allons écrire grand O de n.
Je vais remplir quelques blancs. Ceci est juste une grille d'ébauches.
Mais dans le meilleur des cas avec recherche linéaire, 7 aurait pu être au tout début de la liste,
et Sean aurait commencé à regarder le début de la liste.
Donc, si vous utilisez la recherche linéaire et vérifier simplement de gauche à droite ou de droite à gauche peut-être -
ils sont équivalent - dans le meilleur des cas, le nombre d'étapes pourraient recherche linéaire,
comme algorithme de Sean, prendre? Seulement 1 étape.
>> Alors, je vais dire que c'est la notation oméga.
C'est juste oméga majuscule.
Omega est juste la façon sexy de dire le meilleur des cas en temps continu.
Ainsi, dans le meilleur des cas, le temps d'exécution est une étape unique ou un nombre constant d'étapes -
1 dans ce cas -, mais dans le pire des cas, grand O, il est effectivement n étapes.
Et celui-là, thêta, nous sommes en fait ne va pas chercher à l'heure actuelle.
Ce n'est pas pertinent à cet exemple particulier.
Mais maintenant, nous allons essayer de recherche binaire.
Dans le pire des cas avec une recherche binaire, le nombre de pas est ce que ça va prendre pour trouver le numéro 7
ou ce que nous recherchons? >> [L'élève] Log n.
Encore faudra n log parce que tout comme Alex eu de chance
quand nous avons vraiment travaillé sur le problème méthodiquement
et elle n'a pas trouvé le numéro 7 jusqu'à la toute dernière porte, elle regarda,
même si, en toute justice, elle a obtenu de jeter certaines portes le long du chemin,
recherche binaire dans le pire des cas, a une durée de log n.
Et encore une fois, qui parle de cette division et de conquête.
Mais qu'en est-il dans le meilleur des cas?
Et Alex fait l'expérience que le meilleur des cas à droite quand elle est venue sur scène.
Combien de pas est-ce que prendre en binaire de recherche? >> [L'élève] 1.
1, juste parce qu'elle a été chanceux.
Mais c'est bien parce oméga se réfère à meilleur des cas,
Entrées meilleur des cas, même si c'est juste aléatoire simple chance.
>> Maintenant, cela aussi nous allons juste une sorte de vide congé pour le moment.
Tri à bulles Que diriez-vous maintenant?
Dans le pire des cas, avec une sorte de bulle, tout le monde est dans l'ordre inverse,
nous devons donc faire beaucoup de bulles.
Mais combien de pas est ce que cela va prendre dans le pire des cas? >> [L'élève] carré N.
Ce fut le n au carré, parce que si vous pensez cela,
si la liste est complètement à l'envers - 8 est ici, 1 est ici -
comme chose commence à faire des bulles, le numéro 8 va se déplacer de cette façon, de cette façon,
Ainsi, de cette façon, mais où est le numéro 7 dans le pire des cas?
Ici, elle est encore là-bas. Donc, nous devons le faire encore et encore.
Et c'est là que nous obtenons étapes n, alors n - 1 étapes, alors n - 2 étapes.
Et si vous prenez ma parole - que si vous multipliez sorte de sortir,
il est à peu près carré n à la fin avec quelques autres termes qui nous allons ignorer pour le moment -
puis dans le pire des cas, tri à bulles est n au carré, donner ou prendre.
Mais qu'en est-il le meilleur des cas avec tri à bulles?
Quel est le meilleur scénario? Tous les nombres sont triés déjà.
Et quel était l'heuristique que j'ai utilisé, le truc que j'ai utilisé,
se rendre compte que je n'avais pas fait de travaux et pourrait donc s'arrêter tôt?
[L'élève] Check it la fois. Check it >> une fois. Mais ce que je faisais en cours de route?
J'ai été faire le suivi du nombre de swaps que j'ai fait.
Et j'ai réalisé que si je n'ai pas compté les swaps sur mes doigts, puis je l'ai fait pas de travail.
Je certainement ne devrait pas essayer de ne pas travailler à nouveau, afin que je puisse s'arrêter.
>> Ainsi, dans le meilleur des cas, de tri à bulles lorsque la liste est déjà trié,
que diriez-vous de la notation oméga-dire, le meilleur des cas, temps de marche?
C'est juste n. Nous devons faire un peu de travail, mais nous ne disposons que de faire une valeur de 1 promenade de travail.
Et là aussi, je vais laisser ce champ vide partiel.
Et maintenant, tri par sélection.
Tri par sélection m'avait arracher la plus petite personne encore et encore.
Et qu'est-ce que nous disons que le temps d'exécution de ce test?
C'était n au carré dans le pire des cas.
Et malheureusement, dans le meilleur des cas, il est également n carré
parce que je n'ai pas le genre de vue omniscient du monde entier;
Je sais seulement sur une itération complète que j'ai effectivement trouvé la plus petite personne.
Alors sorte de suce tri par sélection, en ce sens,
mais l'avantage est que c'est un peu intuitive.
Il est assez facile à coder, car tout ce que vous avez à faire est d'écrire quelques imbriqué des boucles,
typiquement, qui passe par la recherche de la plus petite élément
et met ensuite le plus petit élément à sa place à la fin de la liste.
Donc, là aussi, il va y avoir un compromis.
La quantité de temps cela vous prend à penser et à réellement développer quelque chose en écrivant du code
pourrait très bien prendre plus de temps si vous voulez une meilleure performance algorithme et plus rapide.
>> Mais si vous avez vraiment juste une sorte de code quelque chose en place rapide et sale
et juste un peu prendre l'idée stupide possible que vous pouvez penser,
cela pourrait prendre quelques minutes pour le code, mais avec grands ensembles de données
votre algorithme pourrait prendre des heures à courir.
Et moi-même je l'école d'études supérieures serait parfois faire ces compromis.
Il serait 3h du matin, j'ai essayé d'analyser certaines très grand ensemble de données
liée à la recherche sur la sécurité que je faisais, et il a été soit passer 5 minutes
peaufiner mon programme pour analyser les données et d'aller dormir
ou de passer 8 heures, il se juste à droite de sorte qu'il fonctionne instantanément et ne pas aller dormir.
Et donc, là aussi c'est un peu une décision consciente.
Moins de temps de développement, plus de sommeil.
Avec le recul, je n'aurais probablement pas encourager cette
lorsque l'objectif ici est d'optimiser la qualité du code,
mais aussi dans le monde réel est un très bon compromis.
Moins de temps, moins de performance ou vice versa.
Nous voilà donc enfin avoir une chance de parler de thêta.
Theta notation est quelque chose informaticiens peuvent apporter dans la conversation
quand grand O et oméga arrive d'être la même chose.
Vous dites thêta pour vraiment envoyer le message que c'est un peu un serré lié.
Peu importe si le scénario est bon ou mauvais, il est n au carré.
Donc, il n'est tout simplement pas pertinente dans ces histoires ici.
Le tri par insertion est le dernier que nous avons regardé,
où je viens d'insérer tout le monde dans le bon endroit.
Dans le meilleur des cas, ce fut le temps d'exécution du tri par insertion que nous avons vu ici?
[L'élève] Le meilleur des cas? >> Le meilleur des cas.
>> Il a été n parce que, dans le meilleur des cas tous triés,
et Sammy et personne d'autre vraiment eu à se déplacer du tout.
Ils étaient déjà à leur juste place.
Ainsi, le tri par insertion dans le meilleur des cas, dans ce cas, n.
Mais dans le pire des cas, c'est une sorte de n carrés. Pourquoi?
Si ma liste de sujets humains est dans l'ordre inverse,
J'ai d'abord commencer par le numéro 8 et je lui insérer ou elle dans la bonne position, qui se trouve ici.
J'ai un peu de mouvement sur le côté. Ces gars-là ne sont pas triés, il ou elle est triée.
Mais maintenant, il m'arrive de trouver qui ensuite? >> [L'élève] 7.
7 dans le pire des cas, parce que c'est dans l'ordre inverse.
>> Voici donc 7. D'où vient 7 appartiennent? Définitivement derrière moi.
Mais maintenant 7 appartient effectivement pas immédiatement derrière moi, mais derrière le numéro 8,
Je dois donc dire: «Excusez-moi, le numéro 8, pouvez-vous s'il vous plaît déplacer de cette façon
"Faire de la place pour 7?" Maintenant, je rencontre 6.
"Oh, excusez-moi, le numéro 8 et le numéro 7, pouvez-vous aller pour faire place à 6?"
Donc, en d'autres termes, avec le tri par insertion, même si je ne fais pas beaucoup de mouvement,
les gens derrière moi faisons beaucoup plus de travail, et que ça doit coûter du temps à quelqu'un.
Il va coûter l'heure de l'ordinateur.
Ainsi, dans le cas du tri par insertion nous souffrons encore.
Si vous commencez à ajouter le nombre total d'étapes, on finit par frapper à peu près carré n
parce que ces gars ont besoin pour faire place à l'être humain à réinséré dans cette liste.
Et dans ce cas theta n'est tout simplement pas applicable à l'histoire particulière à portée de main.
C'est bien joli. Nous avons ces moyens 3 différentes de parler de la durée de fonctionnement.
Mais qu'est-ce que cela signifie réellement en termes réels si nous essayons réellement coder un algorithme?
>> Permettez-moi de proposer qu'il y ait un algorithme encore meilleur là-bas
que lui-même a certains compromis.
Nous allons appeler le tri par fusion, et c'est un peu de cet algorithme magique
qui fonctionne plus rapidement en quelque sorte, et c'est tellement facile à exprimer, au moins en pseudo-code.
La mise en œuvre de ce type de fusion algorithme va être comme suit.
Lorsque vous avez donné n éléments - nombres n, n personnes, quelle que soit - d'abord il ya un test de cohérence.
Si n est inférieur à 2, le tri par fusion s'arrête. Elle renvoie, pour ainsi dire.
Pourquoi vous arrêter si n est inférieur à 2? >> [Réponse de l'élève inaudible]
Droite. Et de plus, n est pas le numéro de la liste, n est la taille de la liste.
Si n est inférieur à 2, cela signifie que votre liste est soit 1,
où vous êtes évidemment triés si c'est numéro 1,
ou 0, auquel cas il n'y a rien à trier,
donc nous avons besoin de ce genre de scénario de base.
Si la liste est si courte qu'il n'y a tout simplement rien à faire, littéralement, ne rien faire. Retour.
Sinon trier la moitié gauche des éléments, puis trier la moitié droite des éléments,
puis fusionner les 2 moitiés triés.
>> Ce genre de ressemble à un petit tricheur laquelle je vous demande comment trier les éléments
et vous me dites, "Tri de la moitié gauche, trier la moitié droite."
Je suis comme: «Très bien. Comment pouvez-vous trier la moitié gauche?"
"Trier la moitié gauche de la moitié gauche, trier la moitié droite de la partie gauche, puis fait."
Vous êtes un peu cyclique définir ce que signifie pour trier,
mais il s'avère que c'est en fait brillante dans ce cas.
Ce n'est pas vraiment ce cercle vicieux qui n'en finit pas
parce qu'il ne finissent quand? >> [L'élève] Lorsque vous arrivez à 1 chose.
Lorsque vous arrivez à 1 chose.
Ainsi, même si vous pourriez commencer avec 8 personnes et je dis: «Trier la moitié gauche de ces personnes,
ces 4 personnes, "alors je dis:« Comment pouvez-vous trier la moitié gauche? "
"Eh bien, trier les 2 gens d'ici." Et puis vous êtes comme, "Très bien, très bien."
"Comment pouvez-vous trier la moitié gauche de ces gens?"
"Juste trier cette personne 1 ici." Quelle est la révélation éclatante maintenant?
Je dois trier 1 personne. Terminé. Je n'ai pas à faire n'importe quel travail.
Mais maintenant, je dois trier cette personne, mais ils sont une seule personne, rien à faire.
>> Ainsi, la magie est apparemment dans cette troisième étape: la fusion des moitiés triés.
Alors sorte de fusion prend cette idée brillante que si vous cassez un gros problème vers le bas
en 2 petites, de taille identique problèmes
et puis juste un peu de colle les plus petites solutions ensemble à la fin,
Je propose que nous pouvons faire beaucoup, [son de frappe] beaucoup mieux
que n'importe lequel de tri par sélection ou le tri par insertion.
En fait, j'ai été en ignorant que pendant une demi-heure, mais je ne sais vraiment pas ce qui se passe
dehors aujourd'hui. [Vrombissement] [rires]
Donc, nous allons voir si nous pouvons le voir avec un peu d'aide de notre ami Rob Bowden.
Il ya 2 grandes étapes dans le processus de tri par fusion.
Tout d'abord, en permanence diviser la liste en deux moitiés de tasses
jusqu'à ce que nous avons un tas de listes avec juste 1 tasse en eux.
Ne vous inquiétez pas si une liste contient un nombre impair
et vous ne pouvez pas faire une coupe parfaitement propre entre eux.
Juste choisir arbitrairement qui liste pour y inclure la tasse supplémentaire po
Donc, nous allons diviser ces listes.
Maintenant, nous avons 2 listes.
Maintenant, nous avons 4 listes.
Maintenant, nous avons 8 listes avec une tasse unique dans chaque liste.
Donc, c'est tout pour l'étape 1.
Pour l'étape 2, nous avons à plusieurs reprises réunis des paires de listes en utilisant l'algorithme de fusion, nous avons appris avant.
La fusion de 108 et 15, nous retrouver avec la liste des 15, 108.
La fusion de 50 et 4 on se retrouve avec 4, 50.
La fusion de 8 et 42 nous nous retrouvons avec 8, 42.
Et la fusion de 23 et 16 nous nous retrouvons avec 16, 23.
Maintenant, tous nos listes sont de taille 2.
Notez que chacun des 4 listes sont triées,
afin que nous puissions commencer la fusion des paires de listes.
La fusion de 15 et 108 et 4 et 50 nous avons d'abord prendre le 4, puis le 15,
puis le 50, puis le 108.
La fusion de 8, 42 et 16, 23 nous avons d'abord prendre le 8, puis le 16,
puis le 23, puis le 42.
Donc maintenant nous avons seulement 2 listes de taille 4, dont chacune est triée.
Alors maintenant, nous fusionnons ces 2 listes.
Nous prenons d'abord le 4, puis nous prenons le 8, puis nous prenons la 15
et 16 et 23 et 42 et 50 et 108.
Et c'est fait. Nous avons maintenant une liste triée.
>> Rob a eu la gentillesse de profiter de quelque chose que nous n'avons pas encore fait.
Il a été suggéré, mais nous n'avons pas vraiment le faire.
Il faisait quelque chose de physiquement avec les verres qui suggère
il passait une ressource en plus de temps. >> [L'élève] Space. >> C'est l'espace.
Le fait qu'il ait eu ce genre de bi-niveau de la table où il avait de place ici
et de l'espace a été fait ici-bas ce qui implique qu'il utilise deux fois plus d'espace
comme l'un de nos algorithmes à ce jour - tri tri par insertion, tri à bulles, ou la sélection -
mais il a été tirant parti de cet espace supplémentaire pour genre de choses se déplacent d'avant en arrière
tout en gardant les choses en ordre.
Et même si elle se sent comme nous sommes arrivés à une liste triée, on se sent comme il a fallu un certain temps.
En réalité, ce que Rob faisait était exactement cet algorithme.
Il a pris le premier problème de taille n, divisé en une moitié gauche et une moitié droite.
C'est quand il a déménagé les tasses. Puis, il répéta ce processus.
Il a divisé 4 en 2 groupes de 2 ici et ici.
Puis, il répéta ce processus et divisé 2 en 2 séries de 1 pour chacune de ces coupes différentes.
Et c'est là que l'occasion se présente brillante.
A ce moment de l'histoire, Rob avait 8 listes de taille 1,
qui ont tous été triés déjà.
>> Alors qu'est-ce qu'il procède à faire?
Deux à deux, il a pris cette liste triée et cette liste triée et les fusionner.
Puis il prit celui-ci et de les fusionner, puis celle-ci et de les fusionner,
alors celui-ci et de les fusionner.
Et puis, qu'at-il fait ensuite?
Il a ensuite re-fusionner les listes grandes et puis re-fusionné les listes plus grandes.
Et si vous pensez à ce que intuitivement pour l'instant, que faisait-il vraiment?
Il divisait le problème en deux, moitié, moitié, en deux
afin d'obtenir ces listes super-petits.
Puis il a eu la gentillesse de combiner double, double, double, double.
Alors qu'il faisait deux fois autant de travail que nous avons vu jusqu'à présent
avec tout ce qui touche à diviser pour régner, mais pas une grosse affaire.
Travail deux fois plus n'est pas une grosse affaire. C'est juste un facteur constant.
Et tout comme notre expression arithmétique avant, je vais juste à traverser les facteurs constants
comme le temps 2. Qui s'en soucie? Si c'est 2 fois 2 milliards, c'est encore beaucoup d'étapes.
Ainsi, cette étape de fusion semble être l'intuition clé.
Passons en revue ce que numériquement avant - Oh, ce n'est pas d'être poursuivi pour le moment.
Parcourons cette numériquement juste pour réellement voir comment cela se joue.
Il s'agit la plupart du temps juste un petit pauvre d'animation.
Nous allons proposer cela.
Le temps d'exécution du tri par fusion - nous avons juste besoin d'un moyen de parler à ce sujet.
Ce n'est pas les mathématiques, c'est juste une sorte de manière succincte de nous exprimer.
Donc T représente le temps et n représente quoi? >> [L'élève] La taille de la -
>> [Malan] L'ampleur du problème, le nombre de personnes.
Je suis donc prétendre que le temps d'exécution de trier les gens n va de 0 quantité de temps
si n est inférieur à 2, parce que si vous avez 1 tasse ou pas de tasses, vous n'avez rien à trier.
Mais plus généralement, je vais proposer que le temps d'exécution pour trier n éléments
sera le temps nécessaire pour trier la moitié gauche, plus la moitié droite
plus - de quoi s'agit supplémentaire + n? >> [L'élève] Tri par fusion.
[Malan] Il est en train de fusionner, parce que si vous avez n / 2 éléments ici
et vous avez n / 2 éléments ici, combien de temps faut-il pour les fusionner?
Tout comme Rob, vous avez pour arracher celui-ci ici, peut-être arracher par ici,
plumer par ici, par ici arracher, plumer ici.
Vous devez toucher chacune des coupelles fois.
Et s'il ya en plus 4 tasses 4 tasses, c'est 8 tasses
ou, plus généralement, 8 tasses n.
Ainsi, l'étape de fusion, nous pouvons exprimer que n,
et qui consiste littéralement le nombre de fois où Rob physiquement touché
l'un de ceux tasses en styromousse.
Donc, nous allons maintenant faire un exemple arbitraire.
S'il ya 16 tasses, quel est le temps d'exécution du tri, en utilisant l'algorithme de Rob, 16 tasses?
C'est 2 fois la quantité de temps qu'il faut pour trier 8 tasses
parce que nous avons ici, 8 tasses 8 tasses ici.
Je ne sais pas combien de temps cela prend, nous sommes donc en la généralisant comme T pour le moment.
Qui sait ce que c'est?
Mais maintenant, je peux trier de manière récursive ou à plusieurs reprises poser la même question.
Combien de temps faut-il pour trier 8 tasses?
8 tasses que je vais dire prend le temps qu'il faut pour trier 4 tasses 4 tasses ainsi que,
puis de les fusionner ensemble.
Très bien. Nous entrons dans un cycle déjà. Combien de temps faut-il pour trier 4 tasses?
Le temps qu'il faut pour trier 4 tasses 2 tasses est plus 2 tasses de tri ainsi que le processus de fusion.
Très bien. Combien de temps faut-il pour trier 2 tasses?
2 tasses est la quantité de temps qu'il faut pour trier 1 tasse plus le temps qu'il faut pour régler une autre tasse
plus la quantité de temps qu'il faut pour fusionner, ce qui est à seulement 2.
>> Très bien. Dernière question. Combien de temps faut-il pour trier 1 tasse?
Voici le scénario de base que nous avions prédit que nous avions frappé plus tôt.
Le fait qu'il ne prend pas de travail que ce soit pour trier le plus petit des problèmes
signifie que désormais, sorte de style école primaire,
on peut juste aller commencer à brancher ces chiffres en arrière po
Nous savons maintenant ce que T 1 est, si je peux brancher sur 0 pour T 1.
Cela me donnera la réponse à T 2, que j'ai ensuite peut brancher plus haut.
Cela me donnera de T 4, qui je peux brancher plus haut.
Cela me donnera T de 8, ce que je peux brancher plus haut.
Et si je fais réellement que les mathématiques en branchant ces réponses,
Je puis obtenir de T 16 est 64.
Et qu'est-ce que 64 représentent-ils?
Si T est de 16, oui, c'est 16 fois 4.
Donc je réclame maintenant que le temps d'exécution de cette chose appelée le tri par fusion -
et cela va être le plus chic de ceux que nous avons vus jusqu'à présent -
va être appelé n log n
car combien de fois peut diviser Rob tout un tas de coupes en deux? Log n.
C'est la même chose que l'exemple du livre de téléphone, c'est le même que l'exemple d'auto-comptage.
>> Combien de fois pouvez-vous partager quelque chose en deux?
Cependant, il ya cette étape de fusion.
Vous pourriez avoir à diviser les tasses dans la moitié encore et encore et encore,
mais chaque fois que vous allez avoir à fusionner.
Et nous l'avons dit plus tôt que la fusion tasses n prend les mesures n
parce que vous devez arracher une tasse, une tasse arracher, et vous avez de toucher chaque tasse une fois,
tout comme Rob a fait.
Donc, si nous faisons quelque chose de log n fois et nous faisons les choses n sur chacun de ces itérations,
chacun de ces halvings, nous avons n log n fois.
Donc, si nous branchons sur 16 dans cet exemple, 16 fois le logarithme de 16 -
ne vous inquiétez pas pourquoi c'est le cas pour l'instant parce que je n'ai pas tiré de la base -
mais logarithme de base 2 de 16 est 4, 16 fois 4 est 64.
Mais en revanche, si nous avions utilisé tri à bulles ou la sélection ou l'insertion de tri tri avec 16 numéros,
quelle serait la durée de fonctionnement ont été si n est de 16?
Il serait de 16 au carré, qui est de 256, ce qui, même si vous n'avez pas tout à fait suivi toutes les mathématiques,
256 est plus grand que 64. C'est vraiment l'emporter magique ici.
Et se rendre compte que le travail à travers ce dans les petits exemples que l'on veut sur un pset
Il est d'autant plus intuitif.
Mais qu'est-ce que cela signifie vraiment en termes de sensation de cet algorithme est la suivante:
Si l'on fait regarder tri par fusion ici - permettez-moi de tirer vers le haut dans cette fenêtre ici -
ceci est un exemple légèrement différent dans lequel nous avons tous les 3 de ces algorithmes -
bulle, la sélection, et de fusionner - juste à côté.
>> Ils ont tous commencé avec des barres aléatoires, et c'est une bonne chose.
Personne n'a un avantage fondamental sur l'autre.
Je vais dans un instant cliquez sur chacune de ces animations - Cliquez sur Démarrer, sur Démarrer, Démarrer -
aussi vite que je peux pour que, grosso modo, ils commencent tous en même temps,
et considérons que le pire des cas tri à bulles de temps de fonctionnement, c'est quoi? >> [L'élève] carré N.
N au carré. Pire des cas, tri par sélection du temps de fonctionnement est? N au carré.
Et tri par fusion est apparemment - même si vous n'avez pas bien suivi toutes les mathématiques aujourd'hui,
ça va devenir beaucoup plus intuitive avec le temps - est, nous prétendons, n log n fois.
Et parce que log n est strictement inférieur à n fois, nous avons de grands nombres,
n log n fois est plus petit que n fois n ou n au carré.
Alors qu'est-ce que ça fait d'être effectivement un meilleur algorithme en termes de temps d'exécution,
n log n fois par rapport au carré de n? Nous y voilà. Clic, clic, clic.
>> C'est ce que cela signifie d'utiliser quelque chose comme le tri par fusion.
Nous avons un moment. Voyons voir ce qui se passe ici.
[Rires] C'est l'argent de sur tri à bulles?
Il dépend plutôt de l'entrée parfois.
Voyons voir.
Allez. Il se sent comme il rattrape son retard. >> [L'élève] Aller, tri à bulles!
[Étudiants en murmurant]
[Malan] Ouais, ouais.
[Étudiants murmure] Allez, allez, allez!
[Tout acclamations] [applaudissements]
Alors maintenant, avec 1 dernière démo finale, si c'est un peu difficile à envelopper votre esprit autour de la mathématique
ou sorte de la visualisation de là, vous pouvez réellement entendre les vitesses
de différents algorithmes différemment.
Il s'agit d'une personne d'animation réalisé que réellement associés sons
le procédé de permutation et la hauteur des barres.
Comme nous allons le voir ici, il ya quelques algorithmes de tri plus là-bas que les gens ont pensé.
Cette première va être le tri par insertion, et ce sera voler à travers
et vous donner un sentiment sonore du fonctionnement de ces algorithmes différents.
Voici le tri par insertion.
[Bip électronique]
[Malan] Tri bulle.
[Bip rapide électronique]
[Malan] sort de sélection.
[Bip rapide électronique]
[Malan] tri par fusion.
[Bip électronique]
[Bip ralentit] [rires]
[Malan] Gnome sorte.
[Bip électronique]
>> C'est CS50. Nous vous verrons la semaine prochaine. [Applaudissements et des acclamations]
>> [CS50.TV]