>> [Jouer de la musique]
>> DAVID J. Malan: Ceci est CS50.
Et ceci est le début de trois semaines.
Donc, nous avons beaucoup d'exciter choses à couvrent aujourd'hui.
Un grand nombre de possibilités pour bénévoles sur scène.
Et en fin de compte, est aujourd'hui pas sur le code du tout.
Mais il est des idées, et il est sur les algorithmes,
et effectivement ramener quelques-uns des les leçons tirées de la semaine zéro,
dans lequel le rappel, nous introduit cette monstruosité.
Et emprunts d'inspiration à partir de cela, pour démarrer
pour résoudre de plus en plus sophistiquée problèmes algorithmique.
Mais d'abord, quelques annonces.
Donc un, si vous souhaitez rejoindre Le personnel et les camarades de classe de CS50 au déjeuner
ce vendredi, à la fois ici et dans Cambridge, et à New Haven,
s'il vous plaît visitez le cours de site Web, où une URL peut être trouvée.
Lecture de ce mercredi sera ne pas être ici à Sanders.
Il sera en ligne seulement, de sorte syntoniser sur le site de CS50,
que ce soit ici à Cambridge ou New Haven ainsi.
>> Et puis, problème réglé deux est déjà dans vos mains.
Si vous ne l'avez pas encore plongé, permettez-moi à offrir la suggestion très ferme
que, surtout maintenant, en tant que le problème définit l'avance,
vous ne voulez vraiment commencer maintenant, si pas tremper un peu sur le week-end ou avant
quand ils vont d'abord sur Vendredi, parce que vous allez
constatent qu'ils ne sont pas nécessairement obtenir plus longues ou plus difficile par
se.
Je pense que vous verrez que, dans général, ils ont tendance à prendre plus ou moins
autour même laps de temps.
Mais cela dépend certainement sur l'élève, et il
dépend de l'état d'esprit avec lequel vous vous en approchez.
Mais invariablement, vous allez de se heurter à un mur,
et vous allez frapper un bug, et vous êtes juste
ne va pas être en mesure de obtenir sur elle à un moment donné.
Et il est extrêmement précieux de pouvoir de prendre du recul, de revenir le lendemain,
aller à des heures de bureau, post sur CS50 Discutez ou similaire, pour obtenir réellement débloqué.
Alors garde cela en tête.
Début au plus tôt que possible est la meilleure chose que vous pouvez faire.
Alors, voici où nous avons commencé la classe, au cours de la semaine zéro.
Et pouvons-nous obtenir un bénévole ici pour me aider à trouver micros?
D'ACCORD.
Debout déjà.
Allez vers le haut.
Devinez qui est comment il va travailler.
Comment t'appelles tu?
ALAN ESTRADA: Alan Estrada.
DAVID J. Malan: Alan Estrada.
Allez vers le haut.
Enchanté de faire votre connaissance.
ALAN ESTRADA: Ravi de vous rencontrer.
DAVID J. Malan: Et vous étiez ici avec nous dans la semaine zéro, bien sûr.
ALAN ESTRADA: je me trouvais.
J'étais.
>> DAVID J. Malan: Pourriez-vous aller de l'avant et trouver pour nous Mike Smith,
aussi vite que tu peux?
Aussi vite que tu peux.
Littéralement déchirer le problème dans la moitié que vous avez besoin.
>> ALAN ESTRADA: Um.
DAVID J. Malan: Littéralement déchirer le problème en deux.
>> ALAN ESTRADA: Oh.
Mm.
Très bien.
>> DAVID J. Malan: OK.
Bien.
Merci.
ALAN ESTRADA: Très bon.
D'ACCORD.
>> DAVID J. Malan: Et maintenant, vous avez taillé vers le bas
à la moitié de la taille du problème.
Maintenant, nous en sommes à un quart.
Êtes-vous attentif à de quel côté nous gardons?
>> [Rire]
>> ALAN ESTRADA: Oui, je think--
>> DAVID J. Malan: Quelle section sommes-nous?
ALAN ESTRADA: Silencieux, donc.
>> DAVID J. Malan: OK.
Mais Mike Smith va être après Silencieux.
Ainsi--
>> [Rire]
>> Bien.
ALAN ESTRADA: Où cherchons-nous?
DAVID J. Malan: Mike Smith.
ALAN ESTRADA: Mike Smith.
DAVID J. Malan: Maintenant, nous sommes dans chirurgicale.
Maintenant, les médecins.
Maintenant--
>> ALAN ESTRADA: Let's- Passons avec du vrai.
Real.
>> DAVID J. Malan: Real.
D'ACCORD.
Si vous avez besoin réel.
Maintenant, où est Mike Smith?
>> ALAN ESTRADA: cette façon.
>> DAVID J. Malan: Quel chemin?
ALAN ESTRADA: Attendez.
M de la droite?
Nous avons commencé avec--
>> DAVID J. Malan: Ouais.
Ils sont partis.
Tu as raison.
>> ALAN ESTRADA: Ouais.
>> DAVID J. Malan: Donc Mike ici.
ALAN ESTRADA: Quoi?
>> [Rire]
>> Mauvais exemple, les gars.
Pardon.
DAVID J. Malan: Cela vous apprendra vous de sauter de votre chaise.
>> ALAN ESTRADA: Oh.
Oh.
Je vous ai compris.
Oh.
Cette est-- OK, je vous suis.
Smith ici?
>> DAVID J. Malan: Smith, je vous remercie.
Je vais donc continuer à chercher jusqu'à Smith?
>> ALAN ESTRADA: Oh, oui.
Non non Non.
Oh non.
Ceci est à moi.
>> DAVID J. Malan: Oh, vous avez Smith.
D'ACCORD.
>> ALAN ESTRADA: Ouais, je Smith a obtenu ici.
Désolé les gars.
Je pensais que nous Michael-- étaient à la recherche pour Michael.
Pardon.
>> DAVID J. Malan: Il est OK.
Très bien, maintenant nous sommes dans Paccini and Sons.
>> ALAN ESTRADA: Paccini et fils.
DAVID J. Malan: Seulement vous et moi sommes sur cette.
D'ACCORD.
Retrouvez-nous Mike Smith.
Smith.
>> ALAN ESTRADA: Smith.
>> DAVID J. Malan: Smith.
Nous sommes dans la R pour les déchets.
ALAN ESTRADA: Déchets.
Oh.
Cela va prendre un certain temps.
>> [Rire]
DAVID J. Malan: Chaussures.
Nous sommes dans les chaussures.
>> ALAN ESTRADA: Maintenant, nous sommes gonna--
>> DAVID J. Malan: Nice.
ALAN ESTRADA: qui--
[Rire]
Oh, ce qui est excellent.
[Rire]
>> DAVID J. Malan: Il est OK.
>> ALAN ESTRADA: Oh, ce qui est bon.
Je ne pense pas que je vais avoir des copains SPAT après cela.
DAVID J. Malan: Bon.
Sporting.
ALAN ESTRADA: Sporting.
Um, L, M, N, O, P.
DAVID J. Malan: OK.
Donc, nous allons déchirer cette moitié.
C'est bon.
Cela finit mal de toute façon, parce que Mike Smith ne sera pas dans les pages jaunes.
>> ALAN ESTRADA: Aw.
>> DAVID J. Malan: Non, il est OK.
Mais supposons que il est sur cette page.
Alors maintenant, vous avez taillé le problème vers le bas à une page, et nous avons trouvé Mike Smith.
>> [CHEERING]
D'accord, merci.
D'ACCORD.
Ce fut extraordinaire.
Mais il était encore plus rapide de la recherche linéaire,
dans laquelle nous commençons à la début du livre,
et nous passons notre chemin de gauche à droite, éventuellement à la recherche de Mike Smith.
Et donc, si le livre de téléphone avait peut-être de 1000 pages,
peut-être qu'il aurait fallu nous 10 ou si la page des larmes.
>> Mais vous avez peut-être mobilisé touché une hypothèse
Pendant tout ce qui est à dire que le livre de téléphone à l'avance était quoi?
AUDIENCE: Trier.
DAVID J. Malan: Il est triée.
Droit?
Il est triée par ordre alphabétique, de sorte que tous ces noms et numéros
sont triées de la Une de la Z de, et par ordre alphabétique entre les deux.
Mais aujourd'hui, nous demandons maintenant la question, eh bien,
comment avez Verizon ou le téléphone société l'obtenir dans cet état?
>> Parce qu'il est une chose à tirer parti cette hypothèse et, par conséquent,
résoudre un problème avec un algorithme plus efficace.
Mais on n'a jamais vraiment demandé à la semaine zéro, ainsi,
combien ça coûte Verizon ou quelqu'un d'autre
pour obtenir ce livre de téléphone dans l'ordre de tri?
>> Droit?
Il n'a pas d'importance si regardant Mike Smith
est super rapide, si cela vous prend un année pour trier les pages initialement.
Droit?
Vous pourriez tout aussi bien passer au crible à travers un livre de téléphone randomisé,
si ça va être super cher de faire le tri.
Donc, si nous pouvons avoir un autre bénévole.
Prenons un oeil ici à comment nous arrivons sur up-- might-- comment
nous pourrions aller sur le tri-ci.
>> Et si la Jordanie pouvait effectivement rejoignez-nous ici sur scène.
Allez pour un instant.
Comment t'appelles tu?
CAROLINE: Caroline.
DAVID J. Malan: Caroline, venu sur place.
Et vous serez rejoint par moi et la Jordanie ici.
Caroline, je vous remercie.
Bien.
Donc, ce que nous avons ici pour Caroline est de 26 livres bleus
que le SAF utilise pour administrer certains examens finaux.
Ceux-ci deviennent difficiles à trouver, mais ce que nous avons fait à l'avance
est que nous avons mis le nom de quelqu'un sur la face avant de chacun d'eux,
mais nous avons gardé les choses simples en puis éteindre les noms complets.
Nous voudrions donc mettre la personne avec le nom L, D, J, B, tout le chemin de A à Z,
mais ils sont dans un ordre aléatoire.
Et donc si vous voulez, parler votre chemin à travers le problème comme vous
do it, pouvez-vous aller de l'avant et trier ces pour nous, de A à Z.
>> AUDIENCE: OK, alors L est comme, au milieu.
C commence.
B. J avant L. B, Q.
>> DAVID J. Malan: Maintenez cette pensé pendant une seconde.
En raison par ailleurs, ceci est seulement intéressant pour vous, moi, et la Jordanie.
Nous y voilà.
AUDIENCE: [inaudible].
R.
DAVID J. Malan: OK.
Que faites-vous?
>> CAROLINE: M vient après O.
>> DAVID J. Malan: OK.
>> CAROLINE: O.
DAVID J. Malan: O, Bon.
>> CAROLINE: E.
>> DAVID J. Malan: E, F. Ouais.
>> CAROLINE: T, U, V
>> DAVID J. Malan: V, T, U, V. Donc, il dirait que vous êtes making-- continuer.
Il semble que vous faites un gros tas ici,
et une sorte de grand tas là-bas.
Donc, la première moitié de l'alphabet, deuxième moitié de l'alphabet.
D'ACCORD.
Bien.
Type de scinder le problème en deux.
M, N, X. Ouais.
CAROLINE: K.
DAVID J. Malan: OK.
K. Donc, vous sorte de la sélection les uns après les autres,
mettre à gauche ou à droite, ou Z qui se passe sur le plancher.
D'ACCORD.
>> CAROLINE: Z va sur le sol.
>> DAVID J. Malan: OK.
Y va sur le sol.
Maintenant, nous pouvons mettre X.
>> CAROLINE: G.
DAVID J. Malan: G va à gauche.
S va droit.
Tout à droite, un va tout le chemin à gauche.
>> CAROLINE: A, B, C, D.
>> DAVID J. Malan: Maintenant, bon.
Nous avons A, B, C. W va là-bas.
Tout droit, T.
>> CAROLINE: H, I, J.
DAVID J. Malan: H, I, J. Good.
CAROLINE: Dans le centre, je gonna--
DAVID J. Malan: OK.
Alors maintenant, nous allons genre de fusionner ces différentes piles.
Donc A à C, alors je ne vois D, et E, et F, et G, et H, et I. Nice.
J, K. Et puis, cette pile est à l'envers, mais ce est OK.
Bien sûr.
Nous pouvons couper certains coins.
D'ACCORD.
Et puis, nous avons besoin de W, X, Y, Z.
>> CAROLINE: Ouais.
>> DAVID J. Malan: Excellent.
Donc un grand merci à Caroline pour le tri-ci.
>> [CHEERING]
>> Merci.
Merci beaucoup.
Alors maintenant, nous allons examiner un instant comment Caroline a passé en faisant cela,
et exactement ce que nous avons ont pu to-- comment nous
ont réussi à résoudre que problème lorsque nous étions juste
étant donné tout un tas de données aléatoires.
>> Eh bien, il semble qu'il y était un peu d'un système là-bas?
Droit.
Ainsi, les premières lettres dans l'alphabet, elle
est mise à la gauche, et la dernières lettres de l'alphabet,
elle mettait dans le droit.
Et dès qu'elle a trouvé quelques lettres proximales, ceux
qui vont juste à côté de l'autre, elle mettrait ceux dans l'ordre.
Et donc nous avons eu ces genre de petite tas d'entrées triées survenus.
>> Et voilà tout à fait comme ce que la plupart d'entre nous les humains feraient.
Nous sorte de passer au crible, et nous aimerions sorte de avons un mécanisme.
Mais il pourrait être difficile d'écrire vers le bas dans une formule en soi.
Il se sentait un peu plus organique que cela.
Donc, nous allons voir si nous pouvons désormais liés le problème avec moins d'intrants.
>> Au lieu de 26, nous allons faire quelque chose de beaucoup moins
avec juste dire sept, derrière ces portes, pour ainsi dire.
Y at-il seulement sept chiffres?
Et si l'objectif maintenant à la main est de trouver une valeur,
nous allons voir comment efficacement nous pouvons le faire de manière.
Et nous allons voir si nous pouvons maintenant commencer à appliquer certains numéros,
ou certaines formules qui pour décrire l'efficacité de notre livre de téléphone
algorithme, notre algorithme de livre de l'examen, et plus généralement, la recherche d'informations.
>> Donc, pour cela, laissez-moi aller de l'avant, et sur l'écran tactile ici,
mettre en place un navigateur web qui a exactement ces sept portes.
Et si nous pouvions obtenir un autre volontaire de venir par ici,
Je l'ai mis ces mêmes portes ici.
Bénévole rapide.
>> Cette démos vont plus appréciées --choisissez-- à un moment plus en plus vite.
Venez faire un tour.
Comment t'appelles tu?
TREVOR: Trevor.
>> DAVID J. Malan: Trevor?
Tout droit, Trevor, allez vers le bas.
Donc, Trevor a fait du bénévolat ici pour faire un problème similaire, mais celui qui est
une portée plus restreinte, et que ça va pour nous permettre d'essayer de formaliser maintenant
le processus pour le tri de ces chiffres.
>> Donc, Trevor, agréable de vous rencontrer.
Donc, voici un tableau, pour ainsi parler, une liste de sept portes.
Allez-y et nous trouver le numéro 50.
Et puis après le fait, nous dire comment vous l'avez trouvé.
Devrait être: tout droit.
Oui, ceci est une ici?
Uh-oh.
D'ACCORD.
Vous avez cliqué sur celui-là.
Bien.
>> Et bien.
Maintenant vous avez cliqué sur celui-là.
Et permettez-moi de vous donner le micro, de sorte que vous avez dans un instant.
Allez-y et cliquez sur le côté que vous avez l'intention.
Oui bien.
TREVOR: Puis-je décocher une porte?
DAVID J. Malan: Non, vous ne pouvez pas décocher.
TREVOR: OK.
Celui-ci.
DAVID J. Malan: Où voulez-vous aller?
Lequel?
>> TREVOR: Celui-là.
>> DAVID J. Malan: Non
>> TREVOR: OK.
Celui-ci.
>> DAVID J. Malan: Oui.
C'était bien.
Bien.
Alors quel était votre algorithme ou procédure pour ce faire, Trevor?
>> TREVOR: Je vient de traverser portes jusqu'à ce que je trouve un 50.
DAVID J. Malan: OK.
Excellente algorithme.
Donc ça va.
Car en fait, si je révèle ce qui est derrière ces deux autres portes, ce qui
nous trouverons ici est que nous avons seulement entrée aléatoire.
Donc, qui était en réalité aussi bien que vous pourriez obtenir.
Et en fait, vous avez mieux que recherche exhaustive la totalité du tableau,
parce qu'il aurait été vraiment malchanceux si vous aviez frappé le nombre
50 à la dernière porte.
Mais que faire si nous avons la place vous a donné une hypothèse.
Supposons que je sorte tout ces portes autour,
de sorte que vous avez la numéros triées cette fois,
mais cette fois il est fait un different-- cette fois,
il est effectivement triés pour vous.
Et maintenant, l'objectif à portée de main est de frapper le numéro 50.
>> TREVOR: OK.
>> DAVID J. Malan: Quelle est votre algorithme va être?
>> TREVOR: Eh bien, si elle est trié, il est soit aller
à être-- si grand au plus grand, décroissant, ça va être le premier,
ou si elle est le contraire, ce sera la dernière.
Alors je vais vous suffit de toucher cette porte, et puis appuyez simplement sur la dernière porte.
DAVID J. Malan: Excellent.
Bien.
Donc, nous avons trouvé le numéro 50.
Donc dès que vous saviez ils ont été triés, nous
ont été en mesure de tirer parti de cette hypothèse.
Donc, ils sont trop comme l'exemple du livre de téléphone.
Dès que vous avez, même avec un petit problème de ce genre,
vos entrées pré-triés, nous pouvons effectivement trouver la valeur sans doute
plus efficacement.
>> Et je ne vous ai pas si elle était dis triés petite à grande, ou grand au plus petit,
et il était donc très raisonnable à commencer à une extrémité ou l'autre
pour trouver effectivement cette valeur cible.
Donc merci à Trevor ainsi.
Et je vais propose-- bien fait.
Nous avons un petit clip, en fait, que est parmi nos moments préférés dans CS50,
lequel, parfois, ces démos ne vont pas tout à fait comme prévu.
Et en effet, en ce moment, je tiré vers le haut de la mauvaise interface
avec laquelle d'utiliser l'écran tactile.
Donc, qui était de ma faute il.
>> Donc, ce sera pour faire le clip de l'année prochaine,
pourquoi je suis en cliquant sur mon propre écran.
Mais jetons un rapide coup d'oeil à ce qui est arrivé l'année dernière
avec Jay, qui est venu, beaucoup Trevor comme ici, volontaire,
et dans ce court clip, vous verrez comment cette même démo n'a pas tout
révéler les mêmes leçons apprises.
[LECTURE VIDÉO]
-Tous Je veux que vous faites maintenant est à trouver pour moi, et pour nous,
vraiment, le nombre 50 un pas à la fois.
>> -Le Nombre 50?
>> -Le Nombre de 50.
Et vous pouvez révéler ce qui est derrière chacune de ces portes
tout simplement en le touchant avec un doigt.
Bon sang.
>> [Rire]
>> [FIN LECTURE]
DAVID J. Malan: Alors qui va très bien.
Ce sont les portes non triés.
Et Jay, bien sûr, trouvé trop vite.
Trevor a fait un bien meilleur travail en termes d'un moment enseignable,
pour ainsi dire, cette année prendre plus de temps pour le trouver.
Bien sûr, nous avons Jay une deuxième chance,
lequel nous avons trié les portes, tout comme nous l'avons fait pour Trevor,
et Trevor a fait super bien passé cette fois.
Mais Jay l'a fait deux fois moins vite.
[LECTURE VIDÉO]
-Le Objectif est maintenant d'aussi nous trouver le numéro 50,
mais le faire de façon algorithmique, et nous dire comment vous allez à ce sujet.
>> -D'ACCORD.
>> -Et Si vous le trouvez, vous gardez le film.
Si vous ne le trouvez pas, vous lui donnez de retour.
>> -Man.
>> Oh!
>> - [Inaudible] OK.
Donc, je vais vérifier les extrémités d'abord déterminer si there's-- Oh.
>> [Applaudissements]
>> [FIN LECTURE]
DAVID J. Malan: OK.
Donc, le tri des portes clairement conduit à une plus grande efficacité.
Et oui, deux fois plus rapide est ce que je voulais dire il.
Et Jay eu de la chance les deux fois.
Et il a aussi eu de la chance dans ce dernier année, je commandé des disques Blu-ray
pour donner en fait sortir.
Je suis désolé de cette année, nous n'a pas eu le même, Trevor.
Mais mieux encore était il ya quelques années.
Et certains d'entre vous le savent garçon, Sean, qui quand il était dans CS50,
a été contestée avec l'exacte même problème, mais en SD,
comme vous le verrez bientôt, retour dans la journée.
Et vous verrez que non seulement fait il prend un peu plus longtemps que Jay,
un peu plus de Trevor, il était effectivement cette merveilleuse occasion
pour engager presque tout le monde dans le foule à la Price is Right, encourageant
lui de trouver le nombre que nous cherchions.
Voyons. jeter un regard rapide.
>> [LECTURE VIDÉO]
>> -D'ACCORD.
Donc votre tâche ici, Sean, est le suivant.
Je l'ai caché derrière ces portes le nombre de sept.
Mais caché dans certaines de ces portes ainsi sont les autres nombres négatifs.
Et votre but est de penser de cette ligne haut de numéros
comme juste un tableau, ou tout simplement séquence de morceaux de papier
avec des chiffres derrière eux.
Et votre but est, en utilisant uniquement le haut tableau ici, me trouver le nombre de sept.
Et nous allons ensuite critiquer comment vous allez le faire.
-Bien.
Nous -Trouver le nombre de sept, s'il vous plaît.
Non.
Cinq, 19, 13.
>> [Rire]
>> Il est pas une question piège.
One.
>> [Rire]
À ce stade, votre score est pas très bon, alors vous pourriez aussi bien continuer.
Trois.
>> [Rire]
>> Continue.
Franchement, je ne peux pas aider mais se demander ce que vous même y penser, so--
>> [Rire]
Seule la rangée du haut, de sorte vous avez trois.
Donc me trouver sept.
>> [Rire]
17.
Sept.
>> [Applaudissements]
>> Bien.
>> [FIN LECTURE]
>> DAVID J. Malan: afin que nous puissions regarder ces tout au long de la journée.
Et bien sûr, quelques-uns des Les démos de cette année peut-être
va maintenant se retrouver dans le prochain la vidéo de l'année ainsi.
Alors maintenant, de laisser effectivement mettre l'accent sur les algorithmes
ici, et voir si nous ne pouvons pas maintenant commencer à officialiser
comment nous pouvons prendre pour obtenir nos données dans cet état qu'il est triée,
de sorte que, finalement, nous pouvons réellement rechercher plus efficacement.
Et même si nous allons à utiliser assez petits ensembles de données,
comme le huit chiffres que nous avoir ici sur la carte,
finalement, ces mêmes idées pourraient appliquer 1000 entrées, un million d'entrées,
4 milliards d'entrées, car les algorithmes vont être fondamentalement la même.
>> Et donc cela est notre dernier occasion pour les bénévoles d'aujourd'hui,
mais peut-être le plus impliqué, pour lesquels nous avons besoin de huit volontaires
à venir et de nous guider à travers le processus de tri ce qui sera bientôt
être sur ces Pupitres ici.
Permettez-moi de commencer ici.
>> Donc, une dans le vert turquoise-- est-il?
Vous engagez-vous?
Deux.
Venez faire un tour.
D'ACCORD.
Trois.
Quatre.
Laissez moi-- OK, cinq.
Vous êtes étant désignés par votre ami.
Six, sept, huit.
Allez vers le haut.
Bien.
Merci beaucoup.
Allez vers le haut.
>> Bien.
Donc, ce que nous avons et ce ici-- est parmi les plus difficiles,
car cela nécessite que vous l'humour moi juste un peu de temps.
Tu seras numéro un.
Comment t'appelles tu?
>> Annan: Annan.
>> DAVID J. Malan: Annan.
David.
Comment t'appelles tu?
>> JOSEPH: Joseph.
>> DAVID J. Malan: Joseph, vous êtes numéro deux.
>> SERENA: Serena, numéro trois.
Stefan, numéro quatre.
CYNTHIA: Cynthia.
DAVID J. Malan: Cynthia, numéro cinq.
[Inaudible]
DAVID J. Malan: [inaudible].
David, le numéro six.
MATT: Matt.
DAVID J. Malan: le numéro de Matt sept.
Et?
>> WAVERLY: Waverly.
>> DAVID J. Malan: Waverly, numéro huit.
Bien.
Si vous could-- whoops.
Si vous tous, que votre premier défi, il
sont huit pupitres ici face à l'auditoire.
Si vous pouviez mettre vos numéros sur ces pupitres de telle sorte
qu'ils alignent avec le mêmes numéros sur la carte.
Donc, assurez-vous ressembler à ça par mettre vos numéros sur ces musiques
se tient ici.
Excellente jusqu'ici.
>> Excellente.
D'ACCORD.
Alors maintenant, nous allons demander à la question de plusieurs façons différentes.
Comment pouvons-nous aller sur le tri ces gens ici?
Parce que nous avons eu quelques approches plus tôt, de sorte que nous avons été
sorte de faire deux seaux différents.
Et puis nous étions généralement assemblant des choses ensemble.
Dès que nous avons vu deux numéros qui appartenaient ensemble,
nous les mettons ensemble.
Deux lettres qui vont ensemble.
>> Mais nous allons voir si nous ne peut pas formaliser ce,
de sorte que nous avons en fin de compte certains pseudo-code vous voulez,
avec lequel vous pouvez résoudre ces problèmes.
Alors maintenant, je suis à la recherche sur ces chiffres ici.
Et je vois tout un tas d'erreurs.
En fin de compte, je veux un sur le gauche et huit sur la droite.
>> Et donc je suis à la recherche ces deux, quatre et deux.
Et quel est le problème, évidemment?
Ouais.
Ainsi.
Deux vient évidemment avant quatre, de sorte que vous savez quoi?
Permettez-moi d'abord prendre une approche gloutonne, si vous voulez, comme beaucoup de problème
mettre One-- si vous vous souvenez de la Standard Edition du problème Set One,
où je viens de résoudre localement le problème qui est ici en face de moi
et voir où cela me mène.
>> D'ACCORD.
Donc, deux et quatre, laissez-moi aller avant et juste vous échanger deux.
Si vous pouvez déplacer physiquement vous et votre papier,
Il me semble avoir obtenu le énumérer dans un meilleur état.
>> Maintenant, ils sont bons.
Je vais passer à autre chose, quatre et six, semble bon.
Pas de problème.
Six et huit ans, OK.
Huit et un, un autre problème.
Parce que ce qui est vrai à propos de huit et un?
On vient avant huit, et ainsi que devrions-nous faire?
Disons permuter ces deux.
Un et huit.
Et maintenant, je vais continuer.
Je vais continuer à regarder de l'avant.
Et nous allons voir ce qui se passe.
Huit et trois, Bien sûr, sur commande.
Laissez de swap.
Huit et sept ans, bien sûr.
Hors service.
Laissez de swap.
Swap de huit et cinq ans, bien sûr, laisser.
Bien.
Liste est triée.
Oui?
>> OK, évidemment pas.
Mais il est un peu mieux, non?
Parce que ce qui est arrivé préavis.
Chaque fois que nous avons joué un swap, un plus petit Numéro sorte de percolation de cette façon,
et un plus grand nombre percolé cette façon, ou nous allons
commencer à dire barboter à la gauche ou barboter vers la droite.
>> Maintenant, il ne suffit pas, parce au mieux, un certain nombre pourrait
ont déplacé un seul endroit avant, ou au pire,
un certain nombre pourrait avoir déplacé un endroit plus loin.
Donc, vous savez quoi, ce genre d'assez bien fonctionné jusqu'ici.
Permettez-moi d'essayer à nouveau.
Deux et quatre, ils sont OK.
Quatre et six, ils sont OK.
Six et, sur commande.
Donc, nous allons vous deux swap.
Et maintenant, le problème de remarquer commence à faire un peu mieux encore.
Six et trois, sur commande.
Disons que vous deux swap.
Six et sept, vous êtes bon.
Sept et cinq, bien sûr, hors de l'ordre.
Sept et huit, dans l'ordre.
Et maintenant, je pourrais avoir besoin de faire un peu plus de temps.
Et en fait, pensez par vous-mêmes peut-être le nombre de fois maximum
pourrais-je avoir à marcher en arrière?
>> Nous reviendrons à cela.
Donc, deux et quatre sont toujours OK.
Quatre et un, Nope.
Donc, nous allons swap.
Et encore une fois, remarquez visuellement l'un est une sorte de bouillonnement
vers la gauche, où il devrait être.
Quatre et trois swap.
Quatre et six.
Six et cinq swap.
Six et sept.
Sept et huit sont bonnes.
>> Bien.
Nous recevons encore mieux.
Voyons donc.
, Nous avons maintenant deux et un.
Bien sûr, échanger.
Deux et trois, trois et quatre, quatre et cinq, six et sept, sept et huit.
Bien.
Et vous savez quoi?
Parce que je faisais un changement là, laissez-moi faire un test de cohérence.
Laissez-moi aller tout le chemin Retour au début.
D'ACCORD.
Un, two-- yup, vous voyez?
Quelque chose clochait.
Trois, quatre, cinq, six, sept, huit.
Et dans ce dernier passage, sont vous à l'aise avec mon maintenant
affirmant qu'il est triée?
D'ACCORD.
Visuellement, qui est absolument vrai.
Mais fonctionnellement, ce qui n'a également le fruit du hasard
dans cette dernière passe qui vous permet pour confirmer que cette liste est en effet
triés?
>> Qu'est-ce que je fais ou ne pas faire cette dernière passe?
PUBLIC: Il a eu aucun changement.
DAVID J. Malan: Désolé?
PUBLIC: Aucun changement.
DAVID J. Malan: Aucun changement.
Donc, il serait stupide de ma part refaire ce même algorithme
si je ne faisais pas modifie la première fois.
Et l'Etat n'a pas changé.
Certes, je ne vais pas faire change toute la deuxième fois.
Et donc, il est sûr maintenant à-dire, la liste est triée.
>> Et en effet, cela est maintenant quelque chose que nous allons généralement
appel tri à bulles, de sorte que deux à deux, vous corrigez les erreurs à nouveau,
et encore, et encore, et vous continuer à aller d'avant en arrière,
et d'avant en arrière, jusqu'à ce que vous faire aucune de ces swaps, à quel point
vous pouvez être sûr, oui, je terminé de résoudre tous des erreurs.
Disons réinitialisation et essayer une autre approche.
Si vous les gars pourrait retourner dans l'ordre que vous étiez il ya un moment,
qui ressemblait à ceci.
Maintenant, nous allons prendre une approche un peu plus comme le livre de l'examen,
par lequel nous étions constamment la sélection de la lettre de l'alphabet
que nous voulions type de pour faire face à la prochaine.
Peut-être qu'il était un haut lettre, comme A, ou une lettre de faible Z.
>> Donc tout le monde est de retour dans cet ordre.
Et maintenant, permettez-moi de le faire.
Voyons, je sais que je dois huit chiffres ici.
Je vais aller de l'avant et il suffit de sélectionner délibérément
les plus petits éléments.
Droit?
Cela semble trop intuitive.
Pourquoi je ne trouve pas le moindre élément, mis là où il appartient,
puis obtenir le prochain plus petit élément, mettez où il appartient, et il suffit de répéter.
>> Parce intuitivement, qui devrait fonctionner aussi.
Donc, quatre, qu'il ya un joli petit nombre.
Je vais me rappeler où cela est.
Attendez une minute.
Deux est plus petit.
Permettez-moi de me souviens maintenant où deux est, et oublier quatre.
Nous nous en occuperons plus tard.
Six, je ne suis pas intéressé.
Huit, je ne suis pas intéressé.
L'un est mon nouveau petit nombre.
Donc, je vais vous rappeler où l'on est.
Trois, pas intéressé.
Sept, pas intéressé.
Cinq, pas intéressé.
>> Donc sans tomber la scène cette année,
Je vais saisir le numéro One-- et ce qui est votre nom?
>> Annan: Annan.
>> DAVID J. Malan: Annan.
Et si vous pouviez me joindre au le début de la liste,
nous allons vous mettre où vous appartenez.
Unfortunately-- quel est votre nom?
>> STEFAN: Stefan.
>> DAVID J. Malan: Stefan est dans la manière.
Donc, avant de Stefan résout ce problème, que devrions-nous faire?
Que faisons-nous avec Stefan?
>> AUDIENCE: [inaudible].
DAVID J. Malan: OK.
Donc, nous pourrions le faire.
Nous pourrions sorte de prendre Stefan et son quatre, et il suffit de mettre dans une variable
et les garder avec lui pour une certaine quantité de temps,
rendant ainsi la place pour le numéro un.
Et qui est déjà pas mal.
Je pourrais suggérer, pourquoi ne pas nous venons de mettre Stefan ici?
Pourquoi ce pourrait violer l'une des idées que nous avons commencé
parler de la dernière fois, la semaine dernière?
Ouais?
>> AUDIENCE: [inaudible].
>> DAVID J. Malan: Il n'y a pas l'indice pour elle.
Si vous pensez cela, en effet, comme un diodes, elle est comme un négatif,
il n'y a donc pas de mémoire réellement ici si cela est en effet un tableau,
comme nous avons déclaré la semaine dernière dans la leçon.
Donc, nous ne devrions pas le faire.
Nous pourrions stocker dans une variable.
>> Ou vous savez quoi?
Je entendu quelqu'un d'autre, il suggère.
Que pourrions-nous faire avec Stefan?
Pourquoi avons-nous expulser non seulement lui et le mettre sur le lieu où était numéro un.
Donc, si vous voulez aller là-bas.
Et en effet, ceci est un assez bonne solution.
Maintenant, d'une part, je l'ai genre du fait qu'aggraver le problème.
Quatre est maintenant plus loin d'où il devrait être.
Il doit être orienté vers cette demi.
>> Mais vous savez quoi?
Cela aurait pu être la malchance.
Numéro huit Peut-être était ici.
Et ainsi, nous aurions peut- ont eu la chance,
et huit poussé plus près de la fin.
Donc à la fin de la journée, Il sorte de toutes les moyennes sur.
On n'a pas besoin de se soucier de quatre.
Tout ce que je me soucie de ce moment est la sélection du plus petit élément.
>> Et maintenant, ce que je vais faire oublier est numéro un
en permanence, parce que je sais que le Liste derrière moi est maintenant triée.
Donc ma liste était auparavant la taille de huit.
Maintenant, il est de la taille de sept.
Donc, mon problème est d'obtenir plus petit, quoique de façon linéaire.
Alors maintenant, je vais sélectionner le plus petit élément de courant, deux.
Six, huit, quatre, trois, sept, cinq.
Ce fut le plus petit élément.
Alors, que vais-je faire avec-- ce qui est votre nom?
>> JOSEPH: Joseph.
>> DAVID J. Malan: Joseph?
Nous allons laisser Joseph en place.
Maintenant, je vais faire semblant que ces gars soient: ainsi,
Je sais que ces deux sont déjà triés.
Concentrons-nous maintenant sur le reste de la liste.
Six est le plus petit courant.
Huit est plus grand.
Quatre est maintenant le plus petit courant.
Trois est maintenant le plus petit courant.
Et maintenant, je vais choisir trois, général qui: quel est votre nom?
SERENA: Serena.
DAVID J. Malan: Serena, si vous pouviez saisir votre numéro et d'échange avec--
Kalsang: Kalsang.
DAVID J. Malan: Kalsang.
Venez sur le dos, et nous sommes aller à échanger les deux.
Et maintenant, nous allons mettre cela sur le pilote automatique.
Je vais aller et le laisser à vous les gars pour sélectionner les prochains petits éléments.
Dun, Dun, Dun, Dun.
Numéro quatre, que devez-vous faire?
Excellente.
Maintenant, je vais faire un autre passage.
Dun, Dun, Dun, Dun.
Je vois cinq est le prochain plus petit.
Maintenant, je vais prendre une autre passe.
Dun, Dun, Dun, Dun.
Six est le plus petit.
Bien.
Sept est le plus petit.
Pas de changement.
Huit est le plus petit.
Terminé.
>> Donc, ce que nous venons de faire par itérative la sélection d'un élément après l'autre
est de mettre en œuvre quelque chose que nous sommes aller à formaliser que la sélection sorte.
Et il est peut-être même simple à expliquer,
en ce que littéralement tout ce que vous voulez faire est de simplement continuer
des allers-retours dans la liste la sélection, la prochaine plus petit élément,
jusqu'à ce que vous avez terminé.
>> Donc, il est encore plus simple, peut-être intuitivement, que la dernière.
Essayons un dernier.
Si vous les gars pourrait vous réinitialiser dans les positions suivantes
une dernière fois, nous allons voir si nous ne pouvons pas maintenant officialiser un autre approche.
En fait, quelqu'un aurait là vous proposer
sinon comment nous pourrions le faire de manière?
Sans jetant des mots à la mode ou genre des réponses qui sont déjà connus,
juste intuitivement, que pourrions-nous faire?
>> AUDIENCE: [inaudible].
DAVID J. Malan: Ouais.
Donc, il ya une certaine grande intuition il.
Les bonnes choses semblent se produire à ce jour en informatique quand nous divisons
et conquérir le problème de la division en deux et moitié-moitié.
Et en effet, nous pourrait commencer à le faire.
Et en fait, que ça va être, nous allons voir, un de nos meilleurs solutions encore.
Mais revenons à cette avant longtemps.
En fait, nous allons faire un peu plus tard cette semaine.
Que pourrions-nous faire pour résoudre ce problème?
Donc, tout le monde ici est en Afin apparemment aléatoire.
Tu sais quoi?
Plutôt que d'aller et venir, d'avant en arrière, d'avant en arrière
à chaque fois, cela se sent comme Je fais beaucoup de marche.
Pourquoi dois-je pas simplement commencer à le début de la liste,
et vient de mettre quatre où il appartient?
Alors permettez-moi suppose pour le moment que ma liste est seulement ce premier élément.
Est de quatre triés en ce moment dans le temps, si tout ce que je me soucie est tout ici?
Cette est une sorte de trivialement vrai, non?
Comme la liste contenant un certain nombre, et ce nombre est quatre évidemment triée.
>> Alors laissez-moi juste stipule par que cette liste est triée.
Mais maintenant, je dois le reste de cette liste.
Alors maintenant, je rencontre deux.
Où fait deux évidemment appartenir à l'égard de quatre?
Avant de quatre.
Alors qu'est-ce que je peux faire ici?
Quel est votre nom?
>> JOSEPH: Joseph.
>> DAVID J. Malan: Joseph, si vous pouviez revenir en arrière
juste un moment avec votre numéro.
Et maintenant, que devrait Stefan faire ici?
Changeons Stefan ici.
Et maintenant, laissez-Joseph venir ici.
Et maintenant, permettez-moi de prétendre que tout ici est triée.
Donc, résultat similaire, mais un approche fondamentalement différente.
Je l'ai même pas regardé ce qui est là-bas.
Je garde juste prendre les éléments comme ils sont remis à moi,
et de traiter avec eux.
>> Alors maintenant, je vois le numéro six.
D'où vient le numéro six appartiennent?
Nous avons deux, quatre, six.
Exactement là où elle est maintenant.
Alors laissons cela seul, et maintenant prétendre que cette partie de la liste
est maintenant triée.
Et oui, cela se sent fondamentalement différent que je suis juste
se déplaçant à travers la liste ici linéairement, et je ne suis jamais doubler dos.
Oui.
Bien.
Donc, huit, où appartenez-vous?
Ici.
Parfait.
Alors maintenant, un.
Uh-oh.
Cela se sent comme il est va être cher.
Maintenant, dans l'algorithme précédent, Je viens troqué personnes.
Donc, je pourrais le mettre tout le chemin à au début, mais ensuite déplacé Joseph.
Mais si je déménage Joseph, maintenant ce qui va être le problème?
>> Maintenant, je l'ai sorte de undone-- je l'ai fait un pas en avant, puis
un pas en arrière, parce que maintenant Joseph serait irrecevable.
Donc, nous allons le faire.
Si vous pouviez prendre le numéro un et pas en arrière pour un instant.
Comment pouvons-nous ce que put-- est votre nom?
>> Annan: Annan.
>> DAVID J. Malan: Annan en place?
Que faut-il en ce qui concerne à deux, quatre, six et huit?
Ils ont tous besoin de passer.
Donc, si huit aimerait déplacer d'abord, puis six, puis quatre, puis deux.
Et puis Annan, si vous aviez envie de venir ici, bon.
Mais ici, nous venons sorte de payé un prix
à un point différent dans l'algorithme.
Considérant que la dernière fois avec la sélection Trier, et même tri à bulles,
Je marche arrière et arrière, d'avant en arrière,
qui est certainement l'addition Time-Wise, et littéralement pas à pas.
>> Le tri par insertion, au premier vue, ressemble il est
super-intelligente, en ce que je suis juste faisant lent, des progrès graduels,
mais je ne vais pas ce retour en arrière.
Mais si quelqu'un est en effet sur ordonnance, un avis
tout le travail que je viens d'avoir à faire.
Je devais passer la moitié de la liste juste pour faire de la place pour le numéro un.
Il est donc la même quantité des travaux à ce jour, il
sent, juste un type de travail différent.
>> Nous allons continuer.
Alors maintenant, nous savons que tout le monde entre un et huit sont triés.
Ici, je dois numéro trois.
Si vous aimez à ramasser Numéro trois, un recul.
Et qu'est-ce que vous les gars ont besoin de faire?
Yep.
Voilà donc un autre, deux, trois étapes.
Trois unités de temps qui coûtent tout simplement moi, alors que trois peux maintenant adapter.
Enfin, sept.
>> Allons de l'avant et avoir vous prenez un pas en arrière.
Ceci est seulement va nous coûter une unité de temps, mais cela est OK.
Et maintenant, cinq va être un peu plus cher.
Si vous souhaitez prendre du recul.
Nous devons aller de huit, et sept, et six.
Et puis tout le monde est maintenant triée.
Donc une grosse main à nos bénévoles ici.
Merci beaucoup.
>> [Applaudissements]
>> Merci à tous.
Merci à tous.
Voyons donc maintenant à quel point coûteuse tout cela était.
Prenons peut-être le simple de ceux-ci, sorte de bulle.
Et je dis simple, seulement parce que vous pouvez résoudre avec avidité par tout
résoudre le problème par paires ici.
Correction du problème par paires ici, encore et encore
et encore, en répétant autant fois que vous avez réellement besoin pour.
>> Donc, il se trouve que avec une sorte de bulle, et bien,
combien d'étapes dois-je prendre le premier passage de cet algorithme?
Je pourrais take-- nous allons see-- un, deux, trois, quatre, cinq, six, sept.
Et il ya huit éléments ici.
Donc, il est comme n moins 1 à étapes obtenir dès le début de la liste
à la fin de la liste.
>> Mais avec la sélection sorte, rappelle que je suis sélectionnant encore et encore les éléments
et encore que le plus petit, Je mets en place,
mais je ne suis pas regarder derrière moi.
Donc, je pense qu'il est un peu plus clair alors que la première fois, je pourrais
prendre toutes les mesures n moins 1 pour trouver le plus petit élément.
Puis je les ai mis en place, et je évincer celui qui était là auparavant.
>> Mais je ne dois pas continuer à chercher à cet élément,
parce que je sais qu'il est déjà la plus petite.
Alors maintenant, je peux regarder seulement sept éléments, puis six éléments,
puis cinq éléments, puis quatre éléments.
Et si mathématiquement, si n est le nombre d'éléments ou de nombres
que nous avons commencé avec, vous pouvez l'imaginer ce qui est le même que n moins 1,
plus n moins 2 étapes, plus n moins 3 étapes,
ainsi n moins 4 étapes, tous les chemin vers le bas à une seule étape.
Et je suis sur ma dernière personne.
>> Et si vous vous souvenez que beaucoup des stats des livres ou des livres de mathématiques
avoir les formules sur le Relié dos ou face d'eux,
il se trouve que cette série peut être exprimé plus simplement
que n fois n moins 1 sur 2.
Et il est très bien si cela ne à la pointe de votre esprit.
Mais cela est vrai.
Voilà juste un moyen plus simple de l'écrire.
Et puis si vous pensez Retour à l'école primaire,
lorsque vous venez de commencer à multiplier les choses, cela bien sûr,
est tout simplement n carré moins n divisé par 2.
Tout ce que je l'ai fait est élargir les expressions là.
Et nous allons donc réécrire ce un peu différemment.
Cela n carré divisé par 2 moins n / 2.
>> Encore une fois, je suis juste un peu de l'application un peu d'arithmétique y règne.
Mais remarquez maintenant que le plus grand terme dans cette expression, pour ainsi dire,
n est que carré.
Alors oui, il est n carré divisée par deux, moins n / 2.
>> Mais en règle générale, si n est égal à va être une grande valeur,
Je vais prétendre que n carré va être le facteur dominant.
Il va juste être un plus grand contributeur
pour le nombre de pas que les n / 2.
Alors qu'est-ce que je veux dire par là?
Essayons un exemple simple, même si le calcul est un peu grosse.
>> Supposons donc que nous avons eu 1 million de personnes sur scène, ou 1 million de choses
que nous voulons trier.
Branchons un million dans exactement cette formule
pour voir combien d'étapes il faut totale pour trier un million d'éléments à l'aide par exemple,
tri par sélection.
>> Il faudrait donc la même formule que précédemment.
Je branche un millions, de sorte que je reçois un million carré divisé par 2,
moins d'un million divisé par 2.
Si je ne fais que les mathématiques à l'avance ici, nous avons 500 milliards
moins 500 000, qui nous donne 499 999 500 000,
qui est sacrément grand.
>> En fait, si vous comparez maintenant 499 000 000 000 999 millions d'euros,
500.000 contre notre valeur d'origine, 500 milliards, il est sacrément proche.
Droit? n au carré divisée par deux donne us-- ou plutôt, n au carré divisée par 2
nous a donné 500 milliards.
Voilà sacrément proche à 499 999 500 000,
qui est-à-dire hors soustrayant 500 000, ou, plus généralement, de soustraction
n carré, pas vraiment un gros problème.
Le n carré rend ces nombre augmente très vite.
>> Maintenant, ce qui est important dans la mesure où seulement comme nous, que les scientifiques informatiques,
ne sont généralement pas aller à tant de soin sur les nuances de ces formules
et exactement ce que le des réponses précises sont.
Nous nous soucions seulement que, vous savez quoi?
A la fin de la journée, cette formule est de l'ordre de n au carré.
>> Oui, nous sommes en divisant par 2 là.
Oui, nous soustrayant hors n moins 2.
Mais à la fin de la journée, le terme qui nous fait mal et nous coûte vraiment
beaucoup d'étapes est que ce terme carré.
Et alors un informaticien va généralement faire
est ignorer tous ceux petits termes d'ordre,
et il suffit de regarder celui qui contribue le plus au coût.
>> Et c'est bien, parce que nous pouvons parler maintenant de façon beaucoup plus générale
sur les algorithmes, et peut les comparer.
Et le fait que je suis en utilisant cette O est délibérée.
Quand je dis de l'ordre de, je suis particulièrement
faisant référence à quelque chose appelé Big O. et Big O
est une notation qui un ordinateur chercheur utilise pour décrire
une borne supérieure sur quelque chose.
>> Donc, si vous dites que un algorithme est dans le grand O n carré,
comme je l'ai proposé juste un il ya un moment, que des moyens
qu'en termes de son fonctionnement temps ou son efficacité,
il faut de l'ordre n étapes de carré.
Peut-être plus, peut-être moins.
Mais il est de l'ordre de n carré.
Et qui est la limite supérieure.
Ça ne va pas être plus douloureux que cela.
Ça ne va pas être n cubes, ou 2 au n, ou quelque chose de beaucoup plus grand.
Ceci est une borne supérieure sur tout ce que le coût est.
Donc, étant donné que, disons considérer que quelques exemples.
Et cela est juste une liste finie temps de course de très communes
pour les algorithmes qui est censé être illustrative de certaines choses que nous avons
déjà vu.
>> Ainsi, par exemple, dans le cas de tri par sélection, ce que je réclame ici
est la course de sorte que la sélection le temps est de l'ordre de n carré.
Dans le pire des cas, je vais devoir tout un tas de nombres aléatoires ici.
Et comme nous l'avons vu mathématiquement, si je continue à marcher
dans la liste, à travers la liste, sélectionner la prochaine plus petite
élément, encore et encore, si je fait écrire toutes les étapes
Je prends comme je l'ai proposé formulaically avant, il est de l'ordre de n carré
étapes que je vais prendre.
>> Et il se trouve que la bulle tri et le tri par insertion
sont tout aussi lente dans le pire des cas.
Considérons, par exemple, le tri par insertion, le dernier algorithme nous avons traité,
qui nous avait regardons l'élément, puis insérez où il appartient.
Et puis nous avons regardé l'élément suivant, et il inséré où il appartient.
>> Considérons donc le meilleur scénario possible.
Supposons que je l'avais ma ligne jusqu'à bénévoles littéralement comme cela, de un à huit,
déjà triés.
Combien d'étapes est le tri par insertion va prendre pour trier huit personnes,
si elles arrivent sur scène regarder comme ça?
>> Huit personnes déjà triées.
Et je l'utilise le tri par insertion.
Ce dernier des algorithmes.
Eh bien, nous allons rejouer très vite.
Donc, si je commence ici, je vois un.
Où peut-on appartiennent?
Il appartient ici.
Je vois deux.
Où est-ce deux appartiennent?
Ici.
Je vois trois.
Où est-ce trois appartiennent?
Ici.
>> Je vois quatre.
Ici.
Cinq, six, sept, huit.
Il n'y a pas de raison de me répéter.
Et oui, comment de nombreuses étapes est que, en termes de n?
Il est de l'ordre de n étapes, non? n moins 1.
Mais je pris un certain nombre linéaire d'étapes, et maintenant je suis fait.
Voilà donc le meilleur des cas, cependant.
Qu'en est-il le pire des cas?
Qu'est-ce que huit étaient là-bas, et sept étaient là-bas,
et un et deux étaient ici, donc que la liste était vraiment inversé?
>> Eh bien, ce qui se passe en effet si tel est le nombre?
Et nous le ferons seulement quelques exemples.
Que faire si, en effet, le nombre de huit est ici, et les whoops number--.
Alors que faire si, en effet, le nombre huit est tout le chemin ici,
et je suis en utilisant le tri par insertion?
>> D'ACCORD.
Je prétends au moment où il est en place.
Mais maintenant, où est-sept seven-- aller?
Bien sûr, il va ici.
Donc, je dois passer huit plus un seul endroit.
Maintenant, six, où faut-il aller?
Eh bien, tout droit.
Maintenant, je dois passer huit plus un lieu, et sept sur une place,
et puis je plop six.
>> Donc, la première fois, il coûts moi une étape pour arranger les choses,
alors il m'a coûté deux étapes pour arranger les choses.
Combien d'étapes est-il va prendre pour corriger
choses à mettre cinq au bon endroit?
Trois.
Parce que maintenant je dois déplacer un, deux, trois.
Combien d'étapes est qu'il va prendre de mettre quatre à la bonne place?
4 plus 5, plus 6, plus 7.
>> Et il est donc mathématiquement identique à ce que nous avons décrit pour la sélection sorte.
Nous avons cette série qui est juste de plus en plus.
1 + 2 + 3 plus 4, ou à l'inverse, plus 6 7
plus 5 plus 4 ajoute pour aujourd'hui à des fins de l'ordre de n carré.
>> Permettez-moi donc ce que stipule par trop tri à bulles est également n carré.
Parce que, avec tri à bulles, chaque fois que je vais dans la liste,
Je prends à peu près combien de pas?
Chaque fois que je me suis littéralement marcher de là à là?
Environ n étapes.
Mais combien de fois que je pourrais besoin de passer par la liste?
>> Eh bien, à peu près n temps.
Peut-être n moins 1, mais à peu près n fois.
Eh bien, pourquoi est-ce?
Eh bien, avec tri à bulles, si nous commençons avec tri à bulles,
avec la liste dans le pire possible situation qui est complètement nouveau
vers l'arrière, ce qui va se passer?
Je passe par la liste, et le nombre on appartient tout le chemin là-bas.
>> Mais avec tri à bulles, ne jusqu'où on déplacer sur mon premier passage dans la liste?
Combien de points peut-il obtenir plus proche de l'endroit correct?
Juste un.
Donc, si vous sorte de la raison à travers cela, à chaque fois grâce à cet algorithme,
Prenant environ n les étapes de David.
Mais combien de passes la liste est-il
va prendre pour l'un de bulle vers la gauche où il appartient?
>> Il a de se déplacer comme, n espaces de cette façon.
Il suffit donc de faire le tri de la liste, Je dois marcher en arrière n fois.
Et chaque fois, je suis regardant n éléments.
Donc, faire des choses n n fois sur l'ordre de n carré.
>> Maintenant, nous allons voir dans certains des shorts qui
sont intégrés dans le prochain problème de CS50 fixer, une autre approche à ceux-ci,
mais pour l'instant, nous allons examiner tout d'autres fois de suite,
surtout si ceux tri prennent un peu de temps pour sombrer dans.
Qu'est-ce qu'un algorithme que nous avons déjà vu qui prend de l'ordre de n étapes?
>> Ce qui devrait prendre un certain nombre linéaire des mesures que nous avons vu jusqu'à présent?
Qu'est ce que c'est?
La recherche dans l'annuaire de téléphone.
Le premier algorithme.
Droit?
Où nous sommes linéairement la recherche de Mike Smith?
En effet.
De la semaine zéro, quand je commencé tourner une page à la fois,
et même je l'ai dit qu'il était gentil d'un algorithme de sensation linéaire,
et nous avons eu cette image sur le bord avec la ligne rouge droite
et le jaune droite ligne, ceux qui étaient effectivement
algorithmes qui sont en grand O de n.
>> Parce que pour trouver Mike Smith dans un téléphone livre de n pages, dans le pire des cas,
n pourrait me prendre des mesures.
Qu'en est-il prendre les présences?
Un deux trois quatre cinq six.
Quelle est la durée de cette algorithme pour prendre les présences?
Big O n, car en théorie je faire pointer tout le monde dans la salle.
>> Maintenant, en aparté, que dire de la autre optimisation de la semaine zéro?
Deux, quatre, six, huit, 10, 12.
Un chercheur en informatique serait réaliser, attendez une minute,
qui est de l'ordre de n divisé par deux étapes.
Droit?
Parce que je fais deux personnes à la fois.
Mais nous allons ignorer ces termes d'ordre inférieur,
et nous allons juste jeter le diviser par 2,
et dire simplement, grand O n pour que l'algorithme ainsi.
>> Qu'en est-il celui-là?
Nous passerons sur certains d'entre eux, mais ce était un algorithme qui était journal de n?
Cela a pris environ log n étapes?
Le diviser pour régner.
Exactement.
Comme l'exemple du livre de téléphone dans semaine zéro et plus tôt aujourd'hui,
où nous avons divisé le problème Encore et encore et encore.
Nous avons tiré sur le conseil de la semaine zéro comme une ligne verte incurvée,
et nous avons dit ce jour-là, il était un algorithme logarithmique.
>> Et en effet, le nombre d'étapes qu'il prend pour effectuer diviser et conquérir,
ou recherche binaire que nous allons commencer l'appelant, comme dans le livre de téléphone,
est de l'ordre de journal et les étapes.
Et cela est un peu un étrange.
>> Qu'est-ce que fait un pas, ou plus précisément
un nombre constant d'étapes?
Peut-être qu'il est deux, peut-être il est trois, mais un informaticien juste
simplifie aussi grand O de 1, un certain nombre constant d'étapes.
Qu'est-ce quelque chose que vous pourriez le faire prend un nombre constant d'étapes?
>> Quelle est la durée de fonctionnement de frappant?
Constante de temps.
Droit?
Comme, quelle est la durée de fonctionnement de faire quelque chose qui prend un seul
fonctionnement, comme imprimer F Bonjour tout le monde.
Cela pourrait être considéré comme la constante de temps, moins moins le cas de coin avec impression F,
Quel pourrait être le temps d'exécution de l'impression F effectivement être?
Et pourquoi?
Quel est n mesure dans ce cas?
>> AUDIENCE: [inaudible].
DAVID J. Malan: Exactement.
Le nombre de caractères nous voulons imprimer.
Il est donc très sensible au contexte.
Aujourd'hui, nous nous concentrons beaucoup sur les lettres et chiffres ici sur la carte.
Mais il pourrait également être caractères dans une chaîne réelle.
Donc, il se trouve qu'il ya un autre mesure qui va commencer à se soucier,
et voilà le contraire de Big O, pour ainsi dire.
>> Voilà notation oméga.
Alors que Big O signifie ce qui est, la borne supérieure sur votre temps de fonctionnement?
Au maximum, combien de temps pourrait prendre quelque chose?
Omega-- désolé de ce qui continue à venir up-- est à l'opposé de cela,
de sorte qu'il est une borne inférieure sur le quantité de fois que quelque chose pourrait prendre.
>> Ainsi. par exemple, ce qui est un algorithme qui prend des mesures toujours n carrés?
Eh bien, l'un des algorithmes nous avons vu aujourd'hui, en fait, peut-être aussi.
Sorte de sélection.
Sélection est en quelque sorte assez stupide.
Même si le regrette algorithm--, même si le tableau est déjà trié,
tri par sélection va continuer à marcher dans la liste
pour vous assurer qu'il a le plus petit élément nouveau et encore et encore.
Et même si vous les humains dans le auditoire que, attendez une minute,
vous avez déjà passé le plus petit élément, l'ordinateur
ne sait pas que jusqu'à ce qu'il ressemble tout le chemin à travers la liste.
De même, une limite inférieure que pourraient également être pris en compte
pourrait être le temps linéaire.
>> Combien de temps faut-il pour Trier n éléments dans le meilleur
cas en utilisant quelque chose comme tri à bulles?
Supposons que votre liste est déjà trié.
Nous avons dit bubble sort prend l'ordre de n carré étapes.
Mais que faire si il est déjà triée?
Que faire si vous vous rendez compte après un passage à travers la matrice
que vous avez fait aucun swap?
Avez-vous besoin de continuer à faire plus de passes?
>> Non.
Donc, une limite inférieure tri à bulles pourrait être considéré comme linéaire.
Omega de n.
Et nous pouvons regarder d'autres de ces ainsi.
Donc, nous allons jeter un coup d'œil à seulement une visualisation ici
de voir comment ceux-ci se distinguent.
Je vais descendre ici dans cette page qui est disponible sur le site Web de C50,
mais ce sera une douleur à faire fonctionner, car il utilise une technologie appelée
Applets Java, qui est un largement non pris en charge ces jours,
au moins par Chrome et de certains autres.
>> Et laissez-moi aller de l'avant et la vitesse de cette et d'expliquer ce qui se passe.
Ceci est une démonstration de la bulle Trier, le premier algorithme que nous avons regardé.
Et il est une visualisation en ce que chaque de ces barres représente un nombre.
Le plus gros de la barre, plus le nombre.
Le plus petit de la barre, plus le nombre.
Et ce que vous pouvez voir visuellement, même si cela se passe super rapide,
est que la barre rouge est comme moi, marche arrière et des problèmes de fixation de suite.
Vous pouvez voir que les plus gros éléments sont en effet bouillonnant vers la droite,
et les éléments plus petits sont barbotage jusqu'à la gauche.
Et ici, si nous effectivement regarder de plus près,
nous pouvons réellement compter le nombre de comparaisons et des swaps
qui ont été faites.
>> Mais à la place, regardons à la deuxième algorithme
nous avons vu précédemment avec notre bénévoles, la sélection de tri.
Visuellement, il a un effet très différent.
Mais il est, à nouveau, très intuitive, dans que nous gardons en sélectionnant la prochaine plus petite
élément, et nous avons eu un peu de chance.
Qui se sentait fondamentalement plus rapide.
Mais si nous avons couru encore et encore et encore avec beaucoup d'entrées,
nous verrions qu'il est bien toujours en grand O n carré.
>> Faisons un dernier ici, le tri par insertion,
qui était le troisième algorithme nous avons regardé, et le rappel
que celui-ci traite de la éléments comme il les rencontre,
Mais alors, il peut-être des changements la parole à faire de la place,
insertion d'éléments où ils appartiennent.
>> Et cela aussi finit par donner le résultat final. Maintenant, tous les trois de ceux
senti assez vite.
Et en effet, je les ai couru à un assez bon clip.
Mais, fondamentalement, ils sont tous assez horrible, pour être honnête.
Tous ces algorithmes jusqu'ici qui fonctionnent en grande O n carré
prendre un peu de temps à courir à la fin.
>> Et en effet, nous pouvons voir et sentir ce enfin
si je tire cette troisième et dernière démo.
Ceci est un autre visualisation qui va
pour montrer tri à bulles sur la gauche, tri par sélection dans le milieu,
et quelque chose, comme l'un de nos main soulève suggéré plus tôt,
tri par fusion sur la droite.
Un diviser pour mieux régner stratégie sur la droite.
Et qui est, en fait, ce que nous sommes va regarder le mercredi.
Mais laisser le temps de ces pour fonctionner en parallèle.
Il est à peu près le même nombre de éléments, le tout fonctionnant en même temps.
Bubble sorte vs sélection Trier vs tri par fusion.
>> Maintenant, ils sont tous en cours d'exécution en théorie en même temps.
Le CPU tourne à la même vitesse, mais vous
peut sentir combien ennuyeux cela est va très rapidement devenir,
et à quelle vitesse lorsque nous injectons un peu de la semaine
Les algorithmes de zéro peut nous accélérer les choses.
>> Et maintenant, nous allons comparer ceux-ci dans une dernière forme.
Je vais aller de l'avant sur le site de CS50, où
nous avons ce lien finale pour aujourd'hui, où quelqu'un sur internet
mettre ensemble gentiment une vidéo capture ce tri différente
algorithmes ressemblent.
Ceci est le tri par insertion.
>> [BIP]
>> Lequel vous postulez une fréquence basé sur la hauteur de la barre de bar.
Ceci est tri à bulles.
>> [BIP Warped]
>> Prochainement est-- venir jusqu'à la prochaine sélection sorte est--,
où, là encore, nous sommes sélection le prochain plus petit élément,
et nous pouvons le voir grandir de gauche à droite.
>> Fusionner sorte, notre gagnant jusqu'à aujourd'hui.
Remarquez comment il est divisant les choses dans [inaudible] la moitié et les quartiers.
Trier Gnome, dont nous avons pas parlé, et crée visuellement
et audally un peu forme et son différent.
Aller et retour, nettoyage choses.
Consultez également heapsort sur le site de ce type.
>> Et c'est tout.
Nous vous verrons la prochaine fois.
>> [Whooshing ET MUSIQUE]