[Jouer de la musique] DAVID MALAN: Très bien. Très bien, bienvenue. Donc, c'est la Semaine 4, le début de celui-ci, déjà. Et vous vous souviendrez que la semaine dernière, nous avons mis coder de côté pour un peu et nous avons commencé à parler un peu plus de haut niveau, sur des choses comme recherche et de tri, qui, bien que idées un peu simples, sont représentatif d'une catégorie de problèmes vous allez commencer à résoudre en particulier que vous commencez à penser finale projets et des solutions intéressantes que vous pourrait avoir des problèmes du monde réel. Maintenant sorte de bulle a été l'un des plus simples de tels algorithmes, et il travaillé en ayant ces petits nombres dans une liste ou d'une sorte de matrice de bulle leur chemin vers le sommet, et la grands nombres déplacent leur chemin vers la fin de cette liste. Et rappelons que nous pouvions visualiser sorte de bulle un peu quelque chose comme ça. Alors laissez-moi aller de l'avant et cliquez sur Démarrer. J'ai présélectionné sorte de bulle. Et si vous vous souvenez que le plus grand bleu lignes représentent grands nombres, petit Les lignes bleues représentent un petit nombre, comme nous passons par ce encore et encore et de plus, la comparaison de deux barres côte à côte autre en rouge, nous allons échanger les le plus grand et le plus petit si ils sont hors d'usage. Donc cela va durer et continuer et aller , et vous verrez que le plus grand éléments font leur chemin à l' à droite, et les plus petits éléments sont se frayer un chemin vers la gauche. Mais nous avons commencé à quantifier l'efficacité, la la qualité de cet algorithme. Et nous avons dit que, dans le pire cas, cet algorithme a à peu près combien d'étapes? Alors n carré. Et ce qui était n? AUDIENCE: Nombre d'éléments. DAVID MALAN: Donc n est le nombre d'éléments. Et donc nous allons le faisons pas souvent. Chaque fois que nous voulons parler de la taille d'un problème ou la taille d'une entrée, ou la quantité de temps nécessaire pour produire une sortie, nous allons simplement quelle que soit généralisée l'entrée est la n. Donc, retour à la Semaine 0, les pages numériques dans le livre de téléphone est n. Le nombre d'étudiants dans la salle a été n. Donc, là aussi, nous suivons ce modèle. Maintenant, n carré n'est pas particulièrement rapide, donc nous avons essayé de faire mieux. Et donc nous avons regardé un couple de d'autres algorithmes, parmi lesquels était tri par sélection. Donc, tri par sélection était un peu différent. C'était presque simple, j'ose le dire, par lequel j'ai commencé au début de l' Liste de nos bénévoles et je viens à nouveau et encore et encore passé par la liste, arracher le plus petit élément à la fois et lui mettre ou elle au début de la liste. Mais cela, aussi, une fois que nous avons commencé à penser par le calcul et plus image, pensé à combien de fois J'allais en arrière et retour et-vient, nous l'avons dit dans le pire des cas, sélection sorte, aussi, était quoi? n au carré. Or, dans le monde réel, il pourrait en fait être légèrement plus rapide. Parce qu'encore une fois, je n'ai pas eu à tenir retour en arrière une fois que j'avais le tri plus petits éléments. Mais si nous pensons très grand n, et Si vous sorte de faire le calcul comme Je l'ai fait sur le plateau, avec le n carré moins quelque chose, tout le reste Outre le n carré, une fois n devient vraiment grand, ne vraiment autant d'importance. Donc, comme les informaticiens, nous trions de tourner un oeil aveugle à la plus petite facteurs et se concentrer uniquement sur le facteur de une expression qui va faire la plus grande différence. Eh bien, finalement, nous avons examiné au tri par insertion. Et ce fut dans le même esprit, mais plutôt que de passer par itérative et sélectionner le plus petit élément de l'un à un temps, j'ai plutôt pris la main que je a été traitée, et j'ai décidé, tout à droite, vous appartenez ici. Puis je suis passé à l'élément suivant et a décidé qu'il elle appartenait ici. Et puis je suis passé ainsi de suite. Et je pourrais à, le long du chemin, déplacer ces gars-là pour faire de la place pour eux. C'était donc en quelque sorte le renversement mentale de sélection sorte que nous appelé le tri par insertion. Donc ces sujets à se produire dans le monde réel. Il ya quelques années, quand un certain Le sénateur a été candidat à la présidence, Eric Schmidt, au moment où le chef de la direction Google, en fait eu l'occasion pour l'interviewer. Et nous avons pensé partager cette YouTube Clip pour vous ici, si nous pouvions mettre en place le volume. [LECTURE VIDEO] -Maintenant, sénateur, vous êtes ici chez Google, et je me plais à penser de la présidence comme un entretien d'embauche. [Rires] -Maintenant, il est difficile d'obtenir un travail en tant que président. Et vous allez à travers les rigueurs maintenant. Il est également difficile d'obtenir un emploi chez Google. Nous avons des questions et nous demandons nos candidats des questions. Et celui-ci est de Larry Schwimmer. [Rires] -Les gars, vous pensez que je plaisante? C'est juste ici. Quel est le moyen le plus efficace pour trier un million deux entiers bits? [Rires] -Eh bien, euh - -Je suis désolé. Peut-être que nous devrions - -Non, non, non, non, non. -Ce n'est pas une - OK. -Je pense que le tri à bulles serait être le mauvais chemin à parcourir. [Rires] [Acclamations et applaudissements] -Viens, qui lui a dit cela? OK. [FIN LECTURE VIDÉO] DAVID MALAN: Donc là vous l'avez. Nous avons donc commencé à quantifier ces cours d'exécution fois, pour ainsi dire, avec quelque chose appelé notation asymptotique, qui est seulement allusion à notre sorte de tournant les yeux sur ces facteurs petites et seulement en regardant le temps d'exécution, les performances de ces algorithmes, que n devient vraiment grande au fil du temps. Et donc nous avons introduit grand O. et Big O représentait quelque chose que nous avons pensé de comme une limite supérieure. Et effectivement, Barry, peut-on réduire que le micro un peu? Nous avons pensé que c'est une limite supérieure. Donc grand O de n moyens carré que dans le pire des cas, quelque chose comme sélection sorte prendrait n pas carré. Ou quelque chose comme le tri par insertion n serait pas carré. Maintenant, quelque chose comme insertion genre, ce qui était le pire des cas? Étant donné un tableau, ce qui est le pire possible scénario que vous pourriez trouver vous face à? C'est complètement à l'envers, non? Parce que si ce n'est complètement à l'envers, vous avez à faire beaucoup de travail. Parce que si vous êtes complètement à l'envers, vous allez trouver l' le plus grand élément ici, même si il appartient bas. Alors vous allez me dire, tout droit, à ce moment-là, vous appartenez ici, si vous le laissez seul. Ensuite, vous vous rendez compte, oh, zut, je dois déplacer cet élément légèrement inférieure à à gauche de vous. Ensuite, je dois le faire à nouveau et encore et encore. Et si je retournais en arrière, vous trierait de sentir la performance de cet algorithme, parce que je suis constamment brouillant tout le monde dans la tableau pour faire de la place pour cela. Donc, c'est le pire des cas. En revanche - et ce fut un cliffhanger dernière fois - nous avons dit que le tri par insertion était un oméga de quoi? Quel est le meilleur des cas rodage moment du tri par insertion? Donc, c'est en fait n. C'était le vide que nous avons laissé sur le plateau la dernière fois. Et c'est l'oméga de n car pourquoi? Eh bien, dans le meilleur cas, ce qui est tri par insertion va être remis? Eh bien, une liste qui est complètement triée déjà, un minimum de travail à faire. Mais ce qui est ordonnée au sujet de tri par insertion est que parce qu'il commence ici et décide, oh, vous êtes le numéro un, vous place ici. Oh, quelle bonne fortune. Vous êtes le numéro deux. Vous appartenez aussi ici. Numéro trois, c'est encore mieux, vous appartenez ici. Dès qu'elle arrive à la fin de l' Le pseudo-code de liste, par le tri par insertion que nous avons traversé verbalement la dernière fois, c'est fait. Mais la sélection sorte, en revanche, continué à faire quoi? Gardé en passant par la liste encore et encore et encore. Parce que l'idée fondamentale qu'il y avait seulement Une fois que vous avez regardé tout le chemin à l' fin de la liste peut vous être certain que l'élément que vous avez sélectionné est en effet le moment plus petit élément. Donc, ces différents modèles fin mentale par céder quelques-uns dans le monde réel très différences pour nous, ainsi que ces différences théoriques asymptotiques. Donc, pour récapituler, puis, grand O n carré, nous avons vu un peu comme algorithmes jusqu'ici. Big O n? Qu'est-ce qu'un algorithme qui pourrait être dit grand O de n? Dans le pire des cas, il faut un certain nombre d'étapes linéaires. OK, recherche linéaire. Et dans le pire des cas, où est l' élément que vous cherchez lorsque l'application de la recherche linéaire? OK, dans le pire des cas, il n'est même pas là. Ou dans le second cas le pire, c'est tout le chemin à la fin, ce qui est de plus-ou-moins une différence d'une seule étape. Ainsi, à la fin de la journée, nous pouvons dire que c'est linéaire. Big O n serait recherche linéaire, parce que dans le pire des cas, le élément n'est même pas là ou il est tout le chemin à la fin. Eh bien, grand O de journal de n. Nous n'avons pas parlé en détail sur , mais nous avons vu cela avant. Ce qui passe dans ce qu'on appelle logarithmique temps, dans le pire des cas? Ouais, recherche de manière binaire. Et recherche binaire dans le pire des cas pourrait avoir l'élément quelque part dans au milieu, ou quelque part à l'intérieur de la matrice. Mais vous ne trouverez une fois que vous diviser la liste en deux, en la moitié, en deux, la moitié. Et puis voilà, il est là. Ou encore, le pire des cas, il n'est même pas là. Mais vous ne savez pas que ce n'est pas là jusqu'à ce que vous atteignez cette sorte de dernier bottom-la plupart des éléments en réduisant de moitié et réduire de moitié et réduire de moitié. Big O 1. Donc, nous pourrions grand O 2, O grand de 3. Chaque fois que vous voulez juste un nombre constant, nous juste une sorte de juste simplifier que aussi grand O de 1. Même si si réaliste, il faut 2 ou même 100 mesures, si c'est un nombre constant d'étapes, nous disons juste big O 1. Qu'est-ce qu'un algorithme qui est en gros O 1? AUDIENCE: Trouver la longueur d'une variable. DAVID MALAN: Trouver l' longueur d'une variable? PUBLIC: Non, la longueur si elle est déjà trié. DAVID MALAN: Bon. OK, afin de trouver la longueur de quelque chose si la longueur de cette chose, comme un tableau est stocké dans une variable. Parce que vous pouvez simplement lire la variable, ou imprimer la variable, ou juste généralement accéder à cette variable. Et voila, cela prend du temps constant. En revanche, pensez à gratter. Repensez à la première semaine de C, appelant juste printf et l'impression quelque chose sur l'écran est sans doute constante de temps, car il suffit d' certains nombre de cycles CPU pour montrer que le texte sur l'écran. Ou attendre - t-il? Sinon, comment pourrions-nous modéliser l' performance de printf? Quelqu'un voudrait-il pas d'accord, que c'est peut-être pas le temps de vraiment constant? En quel sens peut-printf est en marche temps, en fait l'impression d'une chaîne de l'écran, que ce soit quelque chose autre que constante. AUDIENCE: [inaudible]. DAVID MALAN: Ouais. Tout dépend donc de notre point de vue. Si nous pensons réellement de l'entrée de printf comme étant la chaîne de caractères, et donc nous mesurons la taille de ce entrée par sa longueur - de sorte que nous appellerons que la longueur n et - sans doute, est lui-même printf grand O n parce que ça va vous prendre les mesures n à imprimer chacun de ces n personnages, le plus probable. Au moins dans la mesure où nous supposons que c'est peut-être l'aide d'une boucle for sous la hotte. Mais nous aurions à examiner cette code pour mieux le comprendre. Et en effet, une fois que vous les gars commencer l'analyse de vos propres algorithmes, vous littéralement faire exactement cela. Sorte de globe oculaire de votre code et de penser sur - tout droit, j'ai cette boucle ici ou j'ai un boucles imbriquées ici, qui va faire les choses n n fois, et vous pouvez trier la raison à votre façon dans le code, même si c'est pseudo et pas de code réelle. Alors que sur l'oméga de n carré? Ce qui était un algorithme qui dans le meilleur cas, a encore pris les mesures n carrés? Ouais? AUDIENCE: [inaudible]. DAVID MALAN: sélection sorte So. Parce que dans ce problème vraiment réduit au fait que de plus, je ne sais pas J'ai trouvé le plus petit courant jusqu'à J'ai vérifié tous les éléments sacrément. Donc l'oméga de, disons, n, nous viens avec un. Le tri par insertion. Si la liste se trouve être triés déjà, dans le meilleur des cas que nous venons de faire une passe à travers elle, à quel point nous sommes sûrs. Et puis, qui pourrait être dit est linéaire, c'est sûr. Qu'en est-il l'oméga de 1? Que, dans le meilleur des cas, pourrait prendre un nombre constant d'étapes? Recherche donc linéaire, si vous avoir de la chance et l'élément que vous cherchez qui est juste au début de la liste, si c'est là que vous commencez votre linéaire traversée de cette liste. Et cela est vrai d'un certain nombre de choses. Par exemple, même binaire recherche est l'oméga de 1. Parce que si vous avez vraiment sacrément la chance et smack-dab au milieu de votre tableau est le nombre vous cherchez? Ainsi, vous pouvez avoir de la chance là-bas, aussi. Celui-ci, enfin, l'oméga de n log n. Alors n log n, nous n'avons pas vraiment parler encore, mais - AUDIENCE: le tri par fusion? DAVID MALAN: Tri par fusion. C'était le cliffhanger de la dernière fois, où nous avons proposé, et nous avons montré visuellement, qu'il ya des algorithmes. Et le tri par fusion d'un seul exemple algorithme qui est fondamentalement plus rapide que certains de ces autres gars. En fait, fusionner courte est non seulement dans l' meilleur des cas n log n, dans le pire des cas n log n. Et quand vous avez cette coïncidence de Omega et grand O étant la même chose? Nous pouvons en fait décrire ce que ce qui est appelé thêta, si c'est un peu moins commun. Mais cela signifie simplement que les deux bornes, dans ce cas, sont les mêmes. Donc, le tri par fusion, qu'est-ce que cette vraiment se résument à nous? Eh bien, rappeler la motivation. Laisse-moi ôter une autre animation nous n'avons pas examiné la dernière fois. Celui-ci, même idée, mais il est un peu plus grand. Et je vais aller de l'avant et de souligner première - nous avons le tri par insertion sur En haut à gauche, puis sélection sorte, sorte de bulle, un couple d'autres sortes - coquille et rapide - que nous n'avons pas parlé environ, et le tas et le tri par fusion. Ainsi, au moins essayer de se concentrer vos yeux sur les trois premiers sur la gauche et ensuite le tri par fusion lorsque je clique cette flèche verte. Mais je vais laisser tous les exploités, juste pour vous donner une idée de la diversité des algorithmes qui existent dans le monde. Je vais laisser cette course pour quelques secondes. Et si vous vous concentrez vos yeux - choisir un algorithme, se concentrer sur cela pour seulement un secondes - vous allez commencer à voir le motif qu'elle est mise en œuvre. Le tri par fusion, un avis, est fait. Heap sorte, rapide genre, coquille - il semble donc que nous a présenté les trois pires algorithmes de semaine dernière. Mais c'est bien que nous sommes ici aujourd'hui pour regardez tri par fusion, qui est l'un des les plus faciles consiste à examiner, même mais il sera probablement plier votre esprit juste un petit peu. Ici, nous pouvons voir à quel point sélection sorte suce. Mais le revers de la médaille, c'est vraiment facile à mettre en œuvre. Et peut-être pour P Set 3, c'est l'un des algorithmes que vous avez choisi de mettre en œuvre pour l'édition standard. Parfaitement bien, parfaitement correct. Mais encore une fois, en tant que n devient grand, si vous choisir d'implémenter un algorithme plus rapide comme le tri par fusion, les chances sont plus grandes et grandes entrées, votre code est juste va courir plus vite. Votre site va travailler mieux. Vos utilisateurs vont être heureux. Et il ya ces effets de donner effectivement nous certains pensaient plus profond. Donc, nous allons jeter un oeil à ce que fusionner tri est fait tout au sujet. Le truc cool, c'est que fusionner tri est exactement cela. C'est, encore une fois, ce que nous avons appelé pseudo, étant pseudo- La syntaxe anglaise-like. Et la simplicité est sorte de fascinant. Donc, à l'entrée de n éléments - de sorte que signifie simplement, voici un tableau. Il faut que les choses n en elle. C'est tout ce que nous disons là. Si n est inférieur à 2, le retour. Donc, ce n'est que le cas le plus trivial. Si n est inférieur à 2, alors évidemment c'est 1 ou 0, dans ce cas, la chose est déjà trié, voire inexistante, Il suffit donc de retour. Il n'y a rien à faire. C'est donc un cas simple à arrachez. Sinon, nous avons trois étapes. Trier la moitié gauche des éléments, trier la moitié droite des éléments, puis fusionner les deux moitiés triés. Ce qui est intéressant ici, c'est que Je suis une sorte de barques à fond plat, non? Il ya une sorte de définition circulaire à cet algorithme. Dans quel sens est-ce algorithme de circulaire définition? AUDIENCE: [inaudible]. DAVID MALAN: Ouais, mon algorithme de tri, deux de ses mesures sont «tri quelque chose. "Et pour que pose la question, eh bien, ce que je vais utiliser à trier la moitié gauche et la moitié droite? Et la beauté, c'est que même si encore une fois, c'est l'esprit de flexion partie potentiellement, vous pouvez utiliser le même algorithme pour trier la moitié gauche. Mais attendez une minute. Quand on vous dit de trier les la moitié gauche, ce sont les deux mesures vont être le prochain? Nous allons régler la moitié gauche de l' la moitié gauche et la droite la moitié de la moitié gauche. Merde, comment puis-je trier ces deux moitiés ou en quartiers, maintenant? Mais c'est OK. Nous disposons d'un algorithme de tri ici. Et même si vous vous inquiétez au d'abord il s'agit d'une sorte d'infini boucle, c'est un cycle qui n'est jamais va finir - il va finir une fois ce qui se passe? Une fois que n est inférieur à 2. Qui finalement va se passer, parce que si vous continuez à réduire de moitié et réduire de moitié à réduire de moitié ces moitiés, sûrement finalement, vous allez finir avec seulement 1 ou 0 éléments. À ce moment-là, cet algorithme dit que vous avez terminé. Donc, la vraie magie dans cette algorithme semble être en que dernière étape, la fusion. Cette simple idée juste de fusionner deux choses, c'est ce qui est finalement aller pour nous permettre de trier un tableau de, disons, huit éléments. Je n'ai donc plus de huit balles anti-stress up ici, huit morceaux de papier, et un Google Glass - ce que je peux garder. [Rires] DAVID MALAN: Si nous pouvions prendre huit bénévoles, et nous allons voir si nous pouvons jouer cette rupture, donc. Wow, OK. Informatique devient amusant. Très bien. Alors que diriez-vous trois, plus grosse main là-haut. Quatre dans le dos. Et que diriez-vous, nous vous faisons trois dans cette ligne? Et quatre à l'avant. Donc vous huit, allez vers le haut. [Rires] DAVID MALAN: Je suis effectivement pas sûr de ce qu'il est. Est-ce les balles anti-stress? Les lampes de bureau? Le matériel? L'Internet? OK. Alors, venez sur place. Qui voudrait - garder à venir. Voyons voir. Et cela vous met dans un endroit - vous êtes dans un endroit un. Uh-oh, attendez une minute. 1, 2, 3, 4, 5, 6, 7 - oh, bon. Très bien, nous sommes bons. Très bien, alors tout le monde a un siège, mais pas sur le verre Google. Permettez-moi de faire la queue ces haut. Quel est votre nom? MICHELLE: Michelle. DAVID MALAN: Michelle? Tout droit, vous arrivez à ressembler le geek, si c'est OK. Eh bien, moi aussi, je suppose, pour un instant. Tout droit, veille. Nous avons essayé de trouver une cas d'utilisation de Google verre, et nous pensé qu'il serait amusant de faire ce quand les gens sont sur scène. Nous enregistrerons le monde à partir de leur point de vue. Très bien. Probablement pas ce que Google vise. Très bien, si vous ne me dérange pas porter ce pour les prochaines minutes difficiles, ce serait merveilleux. Très bien, nous avons donc ici un tableau de des éléments, et cette matrice, comme pour l' morceaux de papier dans ces gens-là » mains, est actuellement non triés. MICHELLE: Oh, c'est tellement bizarre. DAVID MALAN: C'est à peu près aléatoire. Et dans quelques instants, nous allons essayer de mettre en œuvre le tri par fusion ensemble et de voir où cette compréhension est la clé. Et le truc, ici, avec le tri par fusion est quelque chose que nous n'avons pas encore pris. Nous avons réellement besoin d'une espace supplémentaire. Alors, que va être particulièrement intéressant, c'est que ces les gars vont se déplacer un peu peu, parce que je vais supposer que il ya un tableau supplémentaire de l'espace, dire, juste derrière eux. Donc, si ils sont derrière leur chaise, c'est le réseau secondaire. S'ils sont assis ici, c'est la matrice primaire. Mais c'est une ressource que nous avons pas mobilisé à ce jour avec la bulle genre, avec sélection sorte, avec le tri par insertion. Rappelons semaine dernière, tout le monde juste genre de traîna en place. Ils n'ont pas utilisé toute la mémoire supplémentaire. Nous avons fait de la place pour les personnes en le déplacement des personnes autour. Donc, c'est une idée fondamentale, aussi. Il ya ce compromis, en général informatique, des ressources. Si vous voulez accélérer quelque chose comme le temps, vous allez avoir à payer un prix. Et l'un de ces prix est très souvent l'espace, la quantité de mémoire ou disque l'espace disque que vous utilisez. Or, franchement, le montant du temps du programmeur. Combien de temps cela vous prend, les ressources humaines, mettre en œuvre effectivement un peu plus algorithme compliqué. Mais pour aujourd'hui, le trade-off est le temps et dans l'espace. Donc, si vous pouviez juste levez numéros afin que nous puissions voir que vous êtes en effet correspondant 4, 2, 6, 1, 3, 7, 8. Excellente. Donc, je vais essayer d'orchestrer choses, si vous les gars ne peux suivre mon exemple ici. Je vais donc mettre en œuvre, d'abord, l' première étape du pseudo-code, qui est sur l'entrée de n éléments, si n est égal à inférieur à 2, puis revenir. Évidemment, cela ne veut pas s'appliquent, si nous passons. Donc trier la moitié gauche des éléments. Donc, cela signifie que je vais concentrer mon attention pour un instant sur ces quatre gars ici. Bon, qu'est-ce que je fais à côté? AUDIENCE: tri de la moitié gauche. DAVID MALAN: Alors maintenant, je dois trier la moitié gauche de ces gars-là. Parce qu'encore une fois, assumer vous-même l' objectif est de trier la moitié gauche. Comment pouvez-vous faire cela? Il suffit de suivre les instructions, même si nous le faisons encore. Donc trier la moitié gauche. Maintenant, je vais trier ces deux gars. Qu'est-ce qui vient après? AUDIENCE: trier la moitié gauche. DAVID MALAN: tri de la moitié gauche. Alors maintenant, ces derniers, ce siège ici, est une liste de taille 1. Et quel est votre nom? PRINCESSE DAISY: Princesse Daisy. DAVID MALAN: Princesse Daisy est ici. Et si elle est déjà trié, parce que la liste est de taille 1. Que dois-je faire la prochaine? OK, revenir, parce que cette liste est d' taille 1, qui est inférieur à 2. Alors quelle est la prochaine étape? Et maintenant que vous avez à type de revenir en arrière dans votre esprit. Trier la moitié droite, ce qui est - Quel est votre nom? Linda: Linda. DAVID MALAN: Linda. Et que faisons-nous maintenant que nous avons une liste de taille 1? AUDIENCE: Return. DAVID MALAN: Attention. Nous revenons d'abord, et maintenant la troisième étape - et si je genre de dépeindre par embrassant les deux sièges maintenant, maintenant je disposer de fusionner ces deux éléments. Alors maintenant, malheureusement, les éléments sont hors d'usage. Mais c'est là que le processus de fusion commence à obtenir convaincante. Donc, si vous pouviez défendre seulement un moment, je vais avoir besoin de vous, dans un moment, à l'étape derrière votre chaise. Et si Linda, parce que 2 est inférieur à 4, pourquoi ne pas vous venez autour première? Restez là. Donc, Linda, vous venez d'abord. Or, dans la réalité si c'est juste un tableau nous pourrions simplement déplacer son en temps réel à partir de ce fauteuil à cet endroit. Alors, imaginez qui a eu une constante nombre d'étapes 1. Et maintenant - mais nous avons besoin de vous mettre en le premier emplacement ici. Et maintenant, si vous pouviez venir autour, ainsi, nous allons être en position deux. Et même si cela se sent comme c'est prendre un certain temps, ce qui est bien c'est maintenant que la moitié gauche de l' la moitié gauche est maintenant triée. Alors quelle est la prochaine étape, si nous maintenant rembobiner plus loin dans l'histoire? AUDIENCE: la moitié droite. DAVID MALAN: tri de la moitié droite. Alors vous les gars ont à faire, aussi bien. Donc, si vous pouvez résister pour un instant? Et quel est votre nom? JESS: Jess. DAVID MALAN: Jess. OK, donc Jess est maintenant à gauche la moitié de la moitié droite. Et si c'est une liste de taille 1. Elle est évidemment triée. Et votre nom? MICHELLE: Michelle. DAVID MALAN: Michelle est évidemment une liste de taille 1. Elle a déjà triée. Alors maintenant, la magie opère, le processus de fusion. Alors, qui va venir d'abord? Évidemment, Michelle. Donc, si vous pouviez venir autour du dos. L'espace dont nous disposons pour elle maintenant est juste derrière cette chaise ici. Et maintenant, si vous pouviez revenir ainsi, nous avons maintenant, pour être clair, deux moitiés, chacune de taille 2 - et juste pour l'amour de représentation, si vous pourrait faire un peu d'espace - une moitié gauche ici, on la moitié droite ici. Rembobinez plus loin dans l'histoire. Quelle étape est le prochain? AUDIENCE: Fusionner. DAVID MALAN: Nous avons donc maintenant à fusionner. Alors OK, maintenant, heureusement, nous juste libéré quatre chaises. Donc, nous avons utilisé deux fois plus de mémoire, mais nous pouvons donner volte-face entre les deux tableaux. Alors quel numéro est à venir d'abord? Donc, Michelle, évidemment. Alors venez autour et de prendre votre siège ici. Et puis le numéro 2 est évidemment prochaine, si vous venez ici. Numéro 4, numéro 6. Et encore, même si il ya une peu de marche à pied, vraiment, ceux-ci pourraient se produire instantanément, en déplaçant une - OK, bien joué. [Rires] DAVID MALAN: Et maintenant nous sommes en assez bonne forme. La moitié gauche de l'ensemble entrée a été trié. Très bien, alors ces gars-là avait l'avantage de ma - Comment at-il finir toutes les filles sur le à gauche et tous les garçons sur la droite? OK, donc les gars au tour maintenant. Donc, je ne vais pas vous guidera à travers ces étapes. Nous allons voir si nous pouvons présenter une nouvelle demande le même pseudo. Si vous voulez aller de l'avant et se tenir debout, et vous les gars, laissez-moi vous donner le micro. Voyez si vous ne pouvez pas reproduire ce nous venons de faire ici sur la autre fin de la liste. Qui a besoin de parler le premier, sur la base de l'algorithme? Alors, expliquez ce que vous faites avant vous faites des mouvements du pied. INTERLOCUTEUR 1: D'accord, donc depuis Je suis la moitié gauche de l' la moitié gauche, je reviens. Droite? DAVID MALAN: Bon. INTERLOCUTEUR 1: Et puis - DAVID MALAN: Qui fait le micro aller à la prochaine? INTERLOCUTEUR 1: numéro suivant. ENCEINTE 2: Je suis donc la moitié droite de la moitié gauche de l' la moitié gauche, et je reviens. DAVID MALAN: Bon. Vous revenez. Alors maintenant, quelle est la prochaine étape pour vous deux? ENCEINTE 2: Nous voulons voir qui est plus petit. DAVID MALAN: Exactement. Nous voulons fusionner. L'espace que nous allons utiliser pour fusionner vous en, même si elles sont évidemment déjà triés, nous allons de suivre le même algorithme. Alors, qui va dans le dos en premier? Donc 3, puis 7. Et maintenant le micro va à ces gars-là, OK? Intervenant 3: Je suis la moitié droite de l' la moitié gauche, et mon n est inférieur 1, donc je vais juste passer - DAVID MALAN: Bon. Intervenant 4: Je suis la moitié droite de l' la moitié droite de la moitié droite, et je suis aussi une personne, donc je suis va revenir. Alors maintenant, nous fusionnons. Intervenant 3: Donc nous retournons. DAVID MALAN: Donc vous allez dans le dos. Donc 5 passe en premier, puis 8. Et maintenant public, qui est la étape, nous devons maintenant revenir en arrière sauvegarder dans nos esprits? AUDIENCE: Fusionner. DAVID MALAN: Fusion moitié gauche et à droite la moitié de la moitié gauche d'origine. Alors maintenant - et juste pour que cela soit clair, faire un peu d'espace entre vous deux les gars. Alors maintenant, c'est les deux listes, à gauche et à droite. Alors, comment pouvons-nous vous fusionnez maintenant les gars en la première rangée de sièges à nouveau? 3 passe en premier. Puis 5, évidemment. Ensuite, 7, 8 et maintenant. OK, et maintenant nous sommes? Audience: non fait. DAVID MALAN: pas fait, parce que évidemment, il ya une étape restante. Mais encore une fois, la raison pour laquelle je suis en utilisant cette jargon comme "rewind dans votre esprit», c'est parce que c'est vraiment ce qui se passe. Nous allons à travers toutes ces étapes, mais nous sommes en quelque sorte une pause pour un moment, plongée profondément dans le algorithme, s'arrêtant un instant, plonger plus profondément dans l'algorithme, et Maintenant, nous devons trier du rembobinage dans notre esprit et annuler toutes ces couches que nous avons en quelque sorte mis en attente. Nous avons donc maintenant deux listes de taille 4. Si vous pouviez lever une dernière fois et de faire un peu de place ici pour clairement que c'est la gauche moitié de l'original, l' la moitié droite de l'original. Qui est le premier numéro que nous besoin de tirer dans le dos? Michelle, bien sûr. Nous avons donc mis Michelle ici. Et qui a le numéro 2? Numéro 2 vient sur le dos aussi. Numéro 3? Excellente. Numéro 4, numéro 5, numéro 6, numéro 7 et numéro 8. OK, donc il se sentait comme un grand d'étapes, pour sûr. Mais maintenant nous allons voir si nous ne pouvons pas confirmer sorte d'intuition que cette algorithme fondamentalement, d'autant plus que n devient vraiment grand, comme nous l'avons vu avec des animations, est fondamentalement plus rapide. Donc je revendique cet algorithme, dans le pire cas et même dans le meilleur des cas, est grand O n log n fois. Autrement dit, il ya certains aspects de cette algorithme qui prend n étapes, mais il ya un autre aspect quelque part dans cette itération, que boucle, qui prend log n étapes. Peut-on mettre le doigt sur ce que ceux deux numéros font référence à? Eh bien, où - Où as le micro aller? ENCEINTE 1: Est-ce le journal n être nous briser en deux - en divisant par deux, pour l'essentiel. DAVID MALAN: Exactement. Chaque fois que nous voyons dans n'importe quel algorithme ainsi Jusqu'ici, il ya eu ce modèle de diviser, la division, la division. Et il est généralement réduite à quelque chose qui est logarithmique, log base 2. Mais il pourrait être n'importe quoi, mais vous identifier base 2. Maintenant, qu'en est-il n? Je vois que nous avons sorte de vous divisés les gars - vous divisé, vous divisées, vous divise, vous divisée. D'où vient la fin de? Donc, c'est la fusion. Parce que penser. Lorsque vous fusionnez huit personnes ensemble, selon laquelle la moitié d'entre eux sont un ensemble de quatre et l'autre moitié est un autre ensemble de quatre, comment allez-vous de faire la fusion? Eh bien, les gars vous at-elle assez intuitive. Mais si je l'ai fait à la place un peu plus méthodiquement, je pourrais avoir pointé la personne la plus à gauche d'abord avec ma gauche main, pointé vers la personne la plus à gauche de la moitié de ma main droite, et juste par la suite traversé la liste, montrant le plus petit élément à chaque fois, se déplaçant le doigt dessus et plus que nécessaire tout au long de la liste. Mais quelle est la clé de cette fusion processus est je compare ces paires des éléments. De la moitié droite et de la gauche demi, je n'ai jamais faire marche arrière. Ainsi, la fusion elle-même prend pas plus de n étapes. Et combien de fois ai-je eu faire que la fusion? Eh bien, pas plus que n, et nous venons d' vu que la fusion finale. Et si vous faites quelque chose qui prend log n étapes n fois, ou vice versa, il va nous n log n fois donner. Et pourquoi est-ce mieux? Eh bien, si nous savons déjà que log n est mieux que n - à droite? Nous avons vu, à la recherche binaire, l'annuaire exemple, log n était certainement mieux que linéaire. Cela signifie donc que n log n fois est certainement mieux que n fois un autre n, n Alias ​​carré. Et c'est ce que nous ressentons en fin de compte. Alors salve d'applaudissements, si nous avons pu, pour ces gars-là. [Applaudissements] DAVID MALAN: Et vos cadeaux de départ - vous pouvez garder les numéros, si vous le souhaitez. Et votre cadeau d'adieu, comme d'habitude. Oh, et nous vous enverrons le film, Michelle. Je vous remercie. Très bien. Servez-vous d'une balle anti-stress. Et laissez-moi m'arrête, dans l'intervalle, notre ami Rob Bowden à offrir perspective un peu différente sur ce point, puisque vous pouvez penser à ces étapes se déroulent dans un peu manière différente. En fait, la mise en place de ce que Rob est sur le point pour nous montrer suppose que nous avons déjà fait la répartition de la grande liste en huit petites listes, chacun de taille 1. Nous allons donc changer le pseudo d'un peu juste sorte de faire au idée de base du fonctionnement de fusion. Mais le temps d'exécution de ce il s'agit de faire est encore va être la même. Et encore, la mise en place ici, c'est qu'il est commencé avec huit listes de taille 1. Alors vous avez raté la partie où il est effectivement fait le journal n log n, log n division de l'entrée. [LECTURE VIDEO] -C'est tout pour la première étape. Pour la deuxième étape, à plusieurs reprises fusionner des paires de listes. DAVID MALAN: Hm. Seulement audio est à venir sur mon ordinateur. Essayons encore une fois. -Il suffit de choisir arbitrairement qui - Nous avons maintenant quatre listes. En savoir avant. DAVID MALAN: Nous y voilà. -Fusion 108 et 15, nous finissons avec la liste 15, 108. La fusion de 50 et 4, nous retrouver avec 4, 50. Fusion 8 et 42, nous retrouver avec 8, 42. Et la fusion de 23 et 16, nous retrouver avec 16, 23. Maintenant, toutes nos listes sont de taille 2. Notez que chacun des quatre listes sont triées. Donc, nous pouvons commencer à fusionner des paires de listes nouveau. Fusion 15 et 108 et les 4 et 50, nous d'abord prendre le 4, puis le 15, puis le 50, puis le 108. Fusion 8, 42 et 16, 23, nous prenons d'abord le 8, puis le 16, puis le 23, puis le 42. Alors maintenant, nous avons seulement deux listes de taille 4, dont chacun est triée. Alors maintenant, nous fusionnons ces deux listes. Tout d'abord, nous prenons le 4, puis nous prenons le 8, puis nous prenons le 15, puis 16, puis 23, puis 42, puis 50, puis 108. [FIN LECTURE VIDÉO] DAVID MALAN: Encore une fois, un avis, il n'a jamais touché une tasse donné plus d'une fois après avoir progressé au-delà. Alors qu'il n'a jamais répéter. Donc, il est toujours en mouvement sur le côté, et c'est là que nous avons eu notre n. Pourquoi ne pas laisser me soulever une animation que nous avons vu précédemment, mais cette fois se concentrer uniquement sur le tri par fusion. Permettez-moi d'aller de l'avant et de zoom sur cette ici. D'abord, permettez-moi à choisir une entrée aléatoire, magnifier cela, et vous pouvez trier de voir ce que nous avons pris pour acquis, plus tôt, le tri par fusion est en train de faire. Donc remarquerez que vous obtenez ces moitiés ou ces quartiers ou ces huitièmes de la problème qui tout d'un coup commencer à prendre la bonne forme. Et puis enfin, vous voyez à la toute fin que bam, tout est fusionné ensemble. Donc, ce ne sont que trois différents prend la même idée. Mais l'idée fondamentale, tout comme fracture et la conquête de la première classe, c'est que nous avons décidé de diviser en quelque sorte le problème en quelque chose de grand, en quelque chose sorte d'identique dans l'esprit, mais plus petite et plus petite et plus petite et plus petits. Maintenant, une autre façon amusante de tri de penser sur ceux-ci, même si elle n'est pas vais vous donner la même intuitive compréhension, est l'animation suivante. Donc, c'est un quelqu'un vidéo mis en place celle associée différente sons avec les diverses opérations de tri par insertion, par le tri par fusion, et pour un couple des autres. Donc, en un instant, je vais frapper Play. C'est environ une minute. Et même si vous pouvez encore voir l' les modèles se passe, cette fois vous pouvez également entendre comment ces algorithmes sont effectuer différemment et avec motifs quelque peu différents. C'est le tri par insertion. [TONS Lecture en cours] DAVID MALAN: Il essaie à nouveau pour insérer chaque élément dans laquelle elle appartient. C'est sorte de bulle. [TONS Lecture en cours] DAVID MALAN: Et vous pouvez trier des sensations comment relativement peu de travail qu'il fait à chaque étape. C'est ce qui sonne comme ennui. [TONS Lecture en cours] DAVID MALAN: C'est sélection sorte, où nous sélectionnons l'élément que nous voulons par en passant par encore et encore et encore et de le mettre au début. [TONS Lecture en cours] DAVID MALAN: C'est le tri par fusion, qui vous pouvez vraiment commencer à sentir. [TONS Lecture en cours] [Rires] DAVID MALAN: Quelque chose appelé gnome sorte, que nous n'avons pas examiné. [TONS Lecture en cours] DAVID MALAN: Alors, laissez-moi voir, maintenant, distrait que vous êtes Espérons que le musique, si je peux glisser un peu peu de mathématiques ici. Donc, il ya une quatrième façon que nous pouvons réfléchir à ce que ces moyens fonctions pour être plus rapide que ceux que nous avons vu auparavant. Et si vous venez au cours de un fond de mathématiques, vous savoir en fait peut-être déjà que vous peut gifler un terme à cette technique - à savoir la récursivité, une fonction qui se dit en quelque sorte. Et encore une fois, rappelons que le tri par fusion pseudocode était récursive dans le sens que l'une des étapes de tri par fusion était d'appeler sorte - qui est, elle-même. Mais heureusement, parce que nous avons gardé appelant tri ou tri par fusion, plus précisément, sur un plus petit et plus petit et petite liste, nous avons finalement creux de la vague grâce à ce que nous appellerons un scénario de base, le cas codée en dur qui dit que si la liste est petit, moins de 2 dans ce cas, il suffit de retourner immédiatement. Si nous n'avions pas ce cas particulier, le algorithme n'aurait jamais toucher le fond, et vous auriez fait entrer dans un boucle infinie vraiment jamais. Mais supposons que nous voulions maintenant mettre quelques chiffres à ce sujet, à nouveau, en utilisant n comme la dimension de l'entrée. Et je voulais vous demander, qu'est-ce le temps total impliqués dans courir tri par fusion? Ou, plus généralement, quel est le coût de celui-ci dans le temps? Eh bien, c'est assez facile à mesurer. Si n est inférieur à 2, le temps impliqué dans le tri n éléments, où n est 2, est égal à 0. Parce que nous retournons juste. Il n'ya pas de travail à faire. Maintenant, sans doute, c'est peut-être une ou deux étapes des mesures pour déterminer le montant de travail, mais il est assez proche de 0 que Je vais juste dire qu'aucun travail n'est requis si la liste est si petit d'être inintéressant. Mais ce cas est intéressant. Le cas récursif était la branche de le pseudo-code qui dit autre, en quelque sorte la moitié gauche, trier le bon la moitié, de fusionner les deux moitiés. Maintenant, pourquoi cette expression représenter cette dépense? Eh bien, T de n signifie simplement que l' le temps de trier n éléments. Et puis sur le côté droit de l' signe égal là, le T de n divisé par 2 se réfère au coût de quoi? Tri de la moitié gauche. L'autre T de n divisé par 2 est fait probablement référence au coût de trier la moitié droite. Et puis le plus n? Est la fusion. Parce que si vous avez deux listes, l'une des taille n sur 2 et un autre de taille n plus de 2, vous devez toucher essentiellement chacun de ces éléments, tout comme Rob touché chacun des gobelets, et juste comme nous l'avons souligné à chacun des bénévoles sur scène. Donc n est le coût de la fusion. Maintenant, malheureusement, cette formule C'est également lui-même récursive. Donc, si posé la question, si n est, disons, 16, si il ya 16 personnes sur scène ou 16 tasses dans la vidéo, combien au total mesures faut-il faire le tri avec tri par fusion? Il s'agit en fait pas une réponse évidente, parce que maintenant vous avez en quelque sorte récursive répondre à cette formule. Mais c'est OK, parce que je vous propose ce que nous faisons ce qui suit. Le temps nécessaire pour trier 16 personnes ou 16 tasses va être représenté généralement en T de 16 ans. Mais cela équivaut, selon notre formule précédente, 2 fois le montant de temps qu'il faut pour trier 8 tasses plus 16. Et encore une fois, plus 16 c'est le moment de fusionner, Et les deux fois T de 8 est le le temps de trier la moitié gauche et la moitié droite. Mais encore une fois, ce n'est pas suffisant. Nous devons plonger plus profond. Cela signifie que nous devons répondre à la question, ce qui est T de 8? Eh bien T de 8 à seulement 2 fois T de 4 et de 8. Eh bien, ce qui est de T 4? T 4 est à seulement 2 fois 2 T de plus 4. Eh bien, ce qui est de T 2? T 2 est de seulement 2 fois T de 1, plus 2. Et encore une fois, nous sommes en quelque sorte d'obtenir coincé dans ce cycle. Mais c'est sur le point de frapper ce dite cas de base. Car ce qui est de T 1, ne nous revendiquons? 0. Alors maintenant, enfin, nous pouvons travailler à reculons. Si T 1 est égal à 0, je peux maintenant monter d'un Ligne à ce gars ici, et je ne peux branchez 0 pour T 1. Ce qui signifie qu'il est égal à 2 fois zéro, autrement connu comme 0, plus 2. Et afin que toute expression est 2. Maintenant, si je prends le T de 2, dont la réponse est 2, branchez-le sur la ligne médiane, T de 4, ça me donne 2 fois 2 + 4, donc 8. Si je branche ensuite dans 8 à la précédente ligne, qui me donne 2 fois 8, 16. Et si nous continuons alors que le 24, en ajoutant 16, nous obtenons finalement une valeur de 64. Maintenant que, en soi, sorte de parle rien à la notation n, l' Big O, l'oméga que nous avons parlé. Mais il s'avère que 64 est en effet 16, la taille de l'entrée, Connectez-base 2 de 16. Et si c'est un peu familier, juste repense, et il reviendra vous finalement. Si c'est la base log 2, c'est comme 2 élevé à la quelle vous donne 16? Oh, c'est 4, il ya 16 fois 4. Et encore, ce n'est pas un gros problème si cette est une sorte de vague souvenir maintenant. Mais pour l'instant, prendre sur la foi que 16 log 16 est 64. Et en effet, avec cette simple bon sens vérifier, nous avons confirmé - mais pas prouvé formellement - que le temps d'exécution de fusion genre est en effet n log n. Donc pas mal. C'est certainement mieux que l' algorithmes que nous avons vu jusqu'à présent, et c'est parce que nous avons misé, un, une technique appelée récursivité. Mais le plus intéressant que cela, qui notion de division et de conquête. Encore une fois, véritablement semaine 0 trucs qui même maintenant est récurrent dans un plus de manière convaincante. Maintenant, un peu d'exercice amusant, si vous avez jamais fait cela - et vous avez probablement n'aurait pas, parce que sorte de la normale les gens ne pensent pas à cela. Mais si je vais à google.com et si Je veux apprendre quelque chose sur récursivité, Entrée. [Rires] [Plus de rires] DAVID MALAN: mauvaise blague propager lentement. [Rires] DAVID MALAN: Juste au cas où, il est là. Je n'ai pas l'épelle mal, et il ya la plaisanterie. Très bien. Expliquer aux gens à côté de vous si il n'a pas assez cliqué tout de suite. Mais récursivité, plus généralement, se réfère le procédé d'une fonction d'appel lui-même ou, plus généralement, la division d'un problème en quelque chose qui peut être résolus au coup par coup en résolvant identique problèmes de représentation. Changer les vitesses du bien, permettez- pour un instant. Nous aimons mettre fin à certains rebondissements, Commençons donc à mettre l'étape, pendant quelques minutes, sur une idée très simple - que d'échanger deux éléments, non? Tous ces algorithmes que nous avons été parler des deux dernières conférences impliquent une certaine sorte de permutation. Aujourd'hui, il a été visualisée en obtenant d'eux lever de leurs chaises et se promener, mais dans le code, nous n'aurions il suffit de prendre un élément d'un tableau et plop dans un autre. Alors, comment allons-nous faire cela? Eh bien, permettez-moi d'aller de l'avant et à écrire un programme rapide ici. Je vais aller de l'avant et faire ce que ce qui suit. Appelons cela - Que voulons-nous pour appeler celui-ci? En fait, non. Permettez-moi de revenir en arrière. Je ne veux pas faire ça encore cliffhanger. Il va gâcher le plaisir. Faisons-le à la place. Supposons que je veux écrire un peu programme et qui englobe maintenant cette idée de la récursivité. J'ai en quelque sorte devancé de moi là-bas. Je vais faire ce qui suit. Tout d'abord, un rapide incluent la norme io.h, ainsi qu'un comprennent des cs50.h. Et puis je vais aller de l'avant et déclarer void main int de la manière habituelle. J'ai réalisé que je l'ai mal nommé le fichier, de sorte Permettez-moi d'ajouter une extension c. ici, donc que nous pouvons compiler correctement. Commencez cette fonction. Et la fonction que je veux écrire, tout à fait simplement, est celui qui demande le utilisateur pour un certain nombre, puis ajoute tous les nombres compris entre cette nombre et, disons, 0. Alors d'abord je vais aller de l'avant et déclarer int n. Puis-je copier un code qui nous avons utilisé pendant un certain temps. Alors que quelque chose est vrai. Je reviendrai dans un instant. Ce que je veux faire? Je veux dire printf positif entier s'il vous plaît. Et puis je vais dire n obtient obtenir int. Encore une fois, un peu de code passe-partout que nous avons utilisé auparavant. Et je vais le faire tandis que n est inférieur à 1. Donc, cela fera en sorte que l'utilisateur me donne un entier positif. Et maintenant, je vais faire ce qui suit. Je tiens à ajouter tous les numéros et entre 1 et n, ou 0 et n, équivalente, pour obtenir la somme totale. Ainsi, le grand symbole sigma que vous vous en souvenez. Donc, je vais le faire en première convocation une fonction appelée sigma, passer en n, et puis je vais printf dire, la réponse est là. Donc en bref, je reçois et Int de l'utilisateur. Je m'assure que c'est positif. Je déclare une variable appelée réponse type int et boutique en elle le retour valeur de sigma, en passant dans le n en entrée. Et puis je imprimer cette réponse. Malheureusement, même si sigma sonne comme quelque chose qui pourrait être en le fichier math.h, sa déclaration, c'est vraiment pas. Donc, c'est OK. Je peux mettre en place moi-même. Je vais mettre en place une fonction appelée sigma, et ça va prendre un paramètre - Appelons cela m, juste donc c'est différent. Et puis ici, je vais vous dire, De plus, si m est inférieur à 1 - ce qui est un programme très inintéressant. Donc, je vais aller de l'avant et retourner immédiatement 0. Il n'a tout simplement pas de sens d'additionner tous les nombres compris entre 1 et m si m est lui-même égal à 0 ou négative. Et puis je vais aller de l'avant et le faire très itérative. Je vais faire ce genre de vieille école, et je vais aller de l'avant et dire que je vais déclarer une somme égale à 0. Alors je vais devoir une boucle de int - et laissez-moi faire pour qu'il corresponde à notre Code de la distribution, de sorte que vous avez une copie à la maison. int i obtient 1 sur un maximum de i est inférieur ou égal à m. i plus plus. Et puis à l'intérieur de cette boucle for - nous y sommes presque - somme se montant plus 1. Et puis je vais retourner la somme. J'ai donc fait ce rapidement, tout à fait vrai. Mais encore une fois, la fonction principale est assez simple, basé sur le code que nous avons écrit jusqu'à présent. Utilise la double boucle pour obtenir un positif Int de l'utilisateur. Je puis passer cette int à une nouvelle fonction appelé sigma, l'appelant, encore une fois, n. Et je stocke la valeur de retour, la réponse à partir de la boîte noire actuellement connue sous le nom sigma, en une variable appelée réponse. Puis je l'imprime. Si maintenant nous continuons l'histoire, comment est-sigma mise en œuvre? Je propose de mettre en œuvre comme suit. Tout d'abord, un peu de vérification des erreurs pour s'assurer que l'utilisateur n'est pas déconner avec moi et en passant une valeur négative ou 0. Ensuite, je déclare une variable appelée résumer et mettre à 0. Et maintenant, je commence à passer de i égale 1 tout le chemin jusqu'à et y compris m, parce que je veux inclure tout le nombres de un à m, inclusivement. Et à l'intérieur de cette boucle for, je fais juste somme obtient ce qu'il est maintenant, plus l' valeur de i. Plus la valeur de i. En passant, si vous n'avez pas vu ce avant, il ya un peu de sucre syntaxique pour cette ligne. Je peux réécrire ce que, plus égal à i, juste pour me sauver quelques frappes et de regarder un peu plus frais. Mais c'est tout. C'est fonctionnellement la même chose. Malheureusement, ce code de ne va pas compiler encore. Si je cours faire sigma 0, comment vais- Je vais faire engueuler? Qu'est-ce que ça va pas aimer? AUDIENCE: [inaudible]. DAVID MALAN: Oui, je n'ai pas déclaré la fonction en haut, à droite? C est un peu stupide, en ce qu'elle ne Est-ce que vous lui demandez de faire, et vous avoir à le faire dans cet ordre. Et donc, si je frappe Entrez ici, je vais obtenir un avertissement sur sigma implicite déclaration. Oh, pas un problème. Je peux aller jusqu'au sommet, et je peux dire, d'accord, attendez une minute. Sigma est une fonction qui renvoie un int et il s'attend à une int en entrée, point-virgule. Ou je pourrais mettre toute la fonction dessus principal, mais en général, je serais recommander contre cela, parce que c'est agréable d'avoir toujours principal en haut de sorte vous pouvez plonger à droite et savoir ce qu'est un programme est de faire en lisant principal en premier. Alors maintenant, laissez-moi éclaircir l'écran. Remake sigma 0. Tout semble à vérifier. Permettez-moi de courir sigma 0. Inter positive. Je vais lui donner le nombre 3 Pour faire simple. Alors qu'il devrait me donner 3 plus 2 plus 1, donc 6. Entrer, et en effet je reçois 6. Je peux faire quelque chose de grand - 50, 12, 75. Tout comme une tangente, je vais faire quelque chose de ridicule comme un très gros nombre, Oh, qui a effectivement travaillé sur - hein, je ne pense pas que ce soit juste. Voyons voir. Disons vraiment plaisante pas avec elle. C'est un problème. Que se passe-t-il? Le code n'est pas si mal. C'est toujours linéaire. Sifflement est un bon effet, si. Que se passe-t-il? Ne sais pas si je l'ai entendu. Ainsi, il s'avère - et c'est une parenthèse. Ce n'est pas au coeur de l' idée de la récursivité. Il s'avère, parce que je suis en train de représenter un tel grand nombre, la plupart Elle est certainement une mauvaise interprétation C en tant que numéro de pas positif, mais nombre négatif. Nous n'avons pas parlé de cela, mais il s'avère qu'il ya des nombres négatifs dans le monde en plus de nombres positifs. Et les moyens par lesquels vous pouvez représenter un nombre négatif essentiellement, c'est, vous utilisez une peu spécial pour indiquer positif et négatives. C'est un peu plus complexe que cela, mais c'est l'idée de base. Donc, malheureusement, si C est une source de confusion de ces bits comme réellement un sens, oh, c'est un nombre négatif, ma boucle ici, par exemple, est en réalité jamais va se terminer. Donc, si je devais imprimer réellement quelque chose encore et encore, nous aurions voir grand-chose. Mais encore une fois, ce n'est pas la question. C'est vraiment juste une sorte de curiosité intellectuelle que nous viendrons sauvegarder à terme. Mais pour l'instant, c'est un bon mise en œuvre si nous supposons que l' utilisateur fournira ints , qui entrent dans ints. Mais je prétends que ce code, franchement, on pourrait faire tellement plus simple. Si l'objectif à portée de main est de prendre un certain nombre comme m et additionnez tous les nombres compris entre 1 et, ou, inversement, entre 1 et, je prétends que je peux emprunter cette idée que fusionner Trier avait, qui prenait un problème de cette taille et en le divisant en quelque chose de plus petit. Peut-être pas la moitié, mais plus petit, mais de la même manière représentative. Même idée, mais un petit problème. Donc, je suis en fait - permettez-moi de sauvegarder ce fichier avec un numéro de version différent. Nous appelons cette version 1 au lieu de 0. Et je prétends que je peux réellement réimplémenter ce dans ce genre de hallucinante façon. Je vais laisser une partie de lui seul. Je vais dire si m est inférieur supérieure ou même égale à 0 - Je vais juste être un peu plus anal cette fois avec ma vérification des erreurs - Je vais aller de l'avant et retourner 0. C'est arbitraire. Je suis tout simplement de décider si l'utilisateur me donne un nombre négatif, je suis retour 0, et qu'ils auraient dû lire la documentation de plus près. Autres - Remarquez ce que je vais faire. Sinon, je vais retourner m plus - ce qui est sigma de m? Eh bien, sigma de m plus m moins 1, plus m moins 2 m + moins 3. Je ne veux pas écrire tout cela. Pourquoi ne pas simplement botté de dégagement? Moi-même de manière récursive avec un peu petit problème, point-virgule, et appeler cela un jour? Droite? Maintenant, ici aussi, vous pourriez vous sentir ou de s'inquiéter qu'il s'agit d'une boucle infinie que je suis induisant, par lequel je suis la mise en œuvre sigma en appelant sigma. Mais c'est tout à fait correct, parce que je pensé avant une ajouté, dont les lignes? AUDIENCE: [inaudible]. DAVID MALAN: 23 à 26, qui c'est mon cas condition. Parce que ce qui est bien sur l' soustraction ici, parce que je continue distribuant les petits problèmes sigma, plus petit problèmes, plus petit - ce n'est pas la moitié de la taille. Ce n'est qu'une étape de plus petit bébé, mais c'est OK. Parce que finalement, nous travaillerons notre chemin vers le bas à 1 ou 0. Et une fois que nous avons atteint 0, sigma n'est pas va s'appeler plus. Il va retourner immédiatement 0. Ainsi, l'effet, si vous sorte de vent cette dans votre esprit, est d'ajouter m plus m moins 1 m + moins 2 m + moins 3, plus point, point, point, m moins m, éventuellement en vous donnant 0, et le effet est finalement d'ajouter tous ces choses ensemble. Donc, nous n'avons pas, avec la récursivité, résolu le problème que nous ne pouvait pas résoudre avant. En effet, la version 0 de cela, et chaque problème à ce jour, a été solvable avec juste l'aide de boucles ou de tout des boucles ou des constructions similaires. Mais la récursivité, si j'ose dire, nous donne une autre façon de penser problèmes, de sorte que si l'on peut prendre un problème, divisez-le à partir de quelque chose un peu large dans quelque chose un peu petit, je prétends que nous pouvons le résoudre peut-être un peu plus élégamment en termes de la conception, avec moins de code, et peut-être même résoudre des problèmes qui pourraient être plus difficile, comme nous allons finalement voir, la résolution purement itérative. Mais le cliffhanger que j'ai fait vouloir nous quitter sur ce n'était. Permettez-moi d'aller de l'avant et ouvrir un fichier à partir de - en fait, permettez-moi d'aller d' faire très vite. Permettez-moi d'aller de l'avant et propose ce qui suit. Parmi le code d'aujourd'hui est ce fichier ici. Celui-là, NOSWAP. Donc, c'est un peu stupide programme qui J'ai fouetté jusqu'à ce que prétend faire ce qui suit. En principal, il déclare d'abord une int appelé X et lui attribue la valeur de 1. Puis il déclare un int y et assigne la valeur 2. Puis il affiche ce x et y est. Puis il dit, en échangeant, dot dot dot. Ensuite, il prétend être l'appel d'une fonction appelé swap, passant en x et y, dont l'idée est que nous espérons x et y reviendront différent, c'est le contraire. Il prétendre ensuite échangé! avec un point d'exclamation. Puis il affiche x et y. Mais il s'avère que cette très démonstration simple vers le bas ici est en fait buggy. Même si je suis déclarant temporaire variable et mettre temporairement dans un , alors je suis réaffectation un la valeur de b - qui se sent raisonnable, parce que j'ai enregistré une copie d'un en température. Puis-je modifier b à l'égalité tout ce qui était en température. Cette sorte de jeu de coquille de déplacer une en b et b en en utilisant cette Moyen-homme appelé température se sent parfaitement raisonnable. Mais je prétends que quand je lance cette code, comme je le fais maintenant - laissez-moi aller de l'avant et le coller dans ici. Je vais appeler cette noswap.c. Et comme son nom l'indique, ce n'est pas va être un bon programme. Faire NOSWAP. / Non échangeable. x est 1, y est égal à 2, permutation, permuter. x est 1, y est égal à 2. Ceci est fondamentalement mauvais, même si cela semble parfaitement raisonnable pour moi. Et il ya une raison, mais nous ne sommes pas vais vous révéler la raison pour l'instant. Pour l'instant le deuxième cliffhanger je voulais vous laisser avec cette, une annonce de toutes sortes sur les codes promos. Notre innovation avec jours de retard cette année a provoqué un nombre non négligeable de questions, ce qui était pas notre intention. L'intention de ces codes promo, où si vous faites partie du problème mettre au début, obtenant ainsi une journée supplémentaire, C'était vraiment pour vous aider les gars aide vous commencez tôt, en quelque sorte par vous incentivizing. Nous permet de répartir la charge sur les heures de bureau mieux afin que c'est une sorte de gagnant-gagnant. Malheureusement, je pense que mes instructions n'ont pas été, à ce jour, très claire, de sorte Je suis retourné ce week-end et mis à jour le spec en plus, le texte audacieux de expliquer balles comme celles-ci. Et juste pour le dire plus publiquement, par par défaut, les ensembles de problèmes sont dus jeudi à midi, par le programme. Si vous commencez tôt, finir une partie de le problème posé par les mercredi à 12h00 PM, la partie qui se rapporte à un coupon code, l'idée est que vous pouvez prolonger votre date limite pour la P fixé jusqu'à vendredi. C'est, peu hors une infime partie de la P définir par rapport à ce qui est généralement le problème plus vaste, et que vous achetez vous un jour supplémentaire. Encore une fois, il vous arrive de penser à l'ensemble des problèmes, vous reçoit les heures de bureau plus tôt. Mais le problème de code promo est encore tenus, même si vous ne les envoyez pas. Mais il est plus convaincante cela. (Aparté) Et ces gens de quitter début vas le regretter. Comme le sont les gens sur le balcon. Je m'excuse à l'avance pour les gens sur le balcon, pour des raisons qui seront effacer en un instant. Donc, nous avons la chance d'avoir l'un des Anciens boursiers de l'enseignement de la tête de CS50 à une société appelée dropbox.com. Ils ont très généreusement fait don d'un code promo ici pour cet espace, qui est en place à partir de la habituelles 2 gigaoctets. Donc ce que je pensais que nous allions faire sur cette la note finale est de faire un peu un cadeau, lequel, dans un instant, nous allons révéler le gagnant et qui dispose d'un coupon code que vous pouvez ensuite aller à leur site web, tapez-le, et voila, obtenir un ensemble beaucoup plus d'espace pour votre Dropbox appareil et vos fichiers personnels. Et d'abord, qui souhaiterait participer dans ce dessin? OK, maintenant que rend encore plus amusant. La personne qui reçoit ce 25 giga-octets code promo - ce qui est loin plus convaincante que la fin jours maintenant, peut-être - est celui qui est assis sur le dessus d'un Coussin de siège sous lequel il ya que le code de coupon. Vous pouvez maintenant regarder sous le coussin de siège. [LECTURE VIDEO] -Un, deux, trois. [CRIE] Vous obtenez une voiture! Vous obtenez une voiture! DAVID MALAN: Nous allons voir vous mercredi. Vous obtenez une voiture! Vous obtenez une voiture! Vous obtenez une voiture! Vous obtenez une voiture! Vous obtenez une voiture! DAVID MALAN: les gens avec balcon, venez ici-bas à l'avant, où nous avons extras. -Tout le monde a une voiture! Tout le monde a une voiture! [FIN LECTURE VIDÉO] Narrateur: Lors de la prochaine CS50 - ENCEINTE 5: Oh mon dieu mon dieu mon dieu mon dieu mon dieu mon dieu mon dieu mon dieu mon dieu mon dieu - [JEUX] UKELELE