[Jouer de la musique] 

PROFESSEUR: Très bien. Ceci est ce qui est CS50 la fin de la troisième semaine. Donc, nous sommes ici aujourd'hui, pas dans Sanders Théâtre, place dans Weidner Bibliothèque. A l'intérieur de laquelle est un studio connu sous le nom Hauser en studio, ou dirons-nous en studio H, ou sont nous say-- si vous avez apprécié cette blague, il est fait à partir de camarade de classe, Mark, en ligne, qui a suggéré autant via Twitter. Maintenant, ce qui est cool à propos être ici dans un studio est que je suis entouré par ces verts murs, un écran vert ou incrustation, pour ainsi dire, ce qui signifie que ce CS50 équipe de production, à mon insu en ce moment, pourrait être mise m'a le plus partout dans le monde, pour le meilleur ou pour le pire. 

Maintenant ce qui nous attend, problème réglé deux est dans vos mains pour cette semaine, mais avec problème posé trois cette semaine à venir, vous serez mis au défi avec le jeu soi-disant de 15 ans, une faveur vieux parti qui vous pourriez rappeler réception comme un enfant qui a tout un tas des chiffres qui peuvent glisser vers le haut, le bas, gauche et droite, et il ya un fossé dans le puzzle, dans lequel vous peut effectivement glisser les pièces du puzzle. En fin de compte vous recevez ce Puzzle dans un ordre aléatoire demi, et l'objectif est de le tri, de haut en bas, de gauche à droite, d'un tout le chemin à travers 15. 

Malheureusement, la mise en œuvre vous aurez à portée de main va être un logiciel basé, non pas physiquement. Vous allez vraiment avoir à écrire code avec lequel un étudiant ou un utilisateur peut jouer le jeu de 15. Et en fait, dans le pirate édition de jeu de 15 ans, vous serez un défi de mettre en œuvre, pas seulement le jeu de cette ancienne école jeu, mais plutôt la résolution de celui-ci, la mise en oeuvre mode de dieu, pour ainsi dire, qui fait résout le casse-tête pour l'humain, en leur fournissant soupçon, après soupçon, après soupçon. Donc plus sur que la semaine prochaine. Mais voilà ce qui nous attend. 

Pour l'instant rappeler que plus tôt cette semaine nous avons eu ce cliffhanger, si vous voulez, de sorte que le mieux que nous faisions le tri sage était une limite supérieure de Big O n au carré. En d'autres termes, tri à bulles, tri par sélection, le tri par insertion, chacun d'entre eux, bien que différente dans leur mise en œuvre, dégénéré en un carré n courir temps dans le pire des cas très. Et nous supposons généralement que le pire cas pour le tri est celui qui vos entrées sont complètement à l'envers. Et en effet, il a fallu pas mal de marches pour mettre en œuvre chacune de ces algorithmes. 

Maintenant, à la fin de la classe rappel, nous avons comparé tri à bulles contre la sélection sorte contre un autre que nous avons appelé le tri par fusion à l'époque, et je propose que cela prend profiter d'une leçon de la semaine zéro, diviser pour régner. Et la réalisation de quelque sorte une sorte de logarithmique durée en fin de compte, lieu de quelque chose qui est purement quadratique. Et il est pas tout à fait logarithmique, il est un peu plus que cela. Mais si vous vous souvenez de la classe, il était beaucoup, beaucoup plus rapide. Jetons un oeil à où nous nous sommes quittés. 

Bubble sorte contre la sélection Trier par rapport tri par fusion. Maintenant, ils sont tous en cours d'exécution, en théorie, dans le même temps. Le CPU tourne à la même vitesse. Mais vous pouvez sentir comment cette ennuyeuse va très rapidement devenir, et à quelle vitesse, lorsque nous injectons un peu des algorithmes de la semaine zéro, pouvons-nous accélérer les choses. 

Donc sorte marque semble incroyable. Comment pouvons-nous en tirer parti, dans l'ordre Pour trier des numéros plus rapidement. Eh bien, nous allons réfléchir retour à un ingrédient qui nous avaient Retour à la semaine zéro, celle de la recherche de quelqu'un dans un livre de téléphone, et de rappeler que la pseudo que nous avons proposé, par lequel nous pouvons trouver quelqu'un comme Mike Smith, regardé un petit quelque chose de ce genre. 

Maintenant, jetez un coup d'oeil en particulier à la ligne 7 et 8, et 10 et 11, qui induisent cette boucle, par lequel nous gardions revenir à la ligne 3, encore et encore, et encore. Mais il se trouve que nous pouvons voir cet algorithme, ici en pseudo, un peu plus holistique. En fait, ce que je suis à la recherche à ici sur l'écran, est un algorithme de recherche pour Mike Smith chez certains ensemble de pages. Et en effet, nous pourrions simplifier cette algorithme dans ces lignes 7 et 8, et 10 et 11 à juste dire cela, que je vous ai présenté ici en jaune. En d'autres termes, si Mike Smith est tôt dans le livre, nous ne devons spécifier étape par étape, maintenant comment aller le trouver. Nous ne disposons pas de spécifier pour revenir à la ligne 3, Pourquoi ne pas tout simplement à la place, par exemple, plus généralement, rechercher Mike dans le la moitié gauche de l'ouvrage. 

Inversement, si Mike est effectivement plus tard dans le livre, pourquoi ne nous citons pas seulement la recherche unquote pour Mike dans la bonne moitié du livre. En d'autres termes, pourquoi le faisons-nous pas simplement sorte de botté de dégagement de nous dire, rechercher Mike dans ce sous-ensemble de l'ouvrage, et de laisser à nos clients existants algorithme pour nous dire comment chercher Mike dans que la moitié gauche de l'ouvrage. En d'autres termes, notre algorithme fonctionne si elle est un annuaire téléphonique de cette épaisseur, de ce épaisseur, ou de toute épaisseur que ce soit. Donc, nous pouvons de manière récursive définir cet algorithme. En d'autres termes, sur la écran ici, est un algorithme pour la recherche de Mike Smith parmi les pages d'un livre de téléphone. Donc, à la ligne 7 et 10, nous allons juste dire exactement cela. Et je utiliser ce terme un moment Il ya, en fait, la récursivité est le mot d'ordre pour l'instant, et il est de ce processus de faire quelque chose d'une certaine manière cyclique par en utilisant le code que vous avez déjà, et de l'appeler à nouveau, et de nouveau, et de nouveau. Maintenant, il va être importante de toute façon que l'on fond dehors, et ne faites pas cela infiniment long. Sinon, nous allons ont en effet une boucle infinie. Mais nous allons voir si nous pouvons emprunter cette idée d'une récursion, faire quelque chose de nouveau et encore et encore, pour résoudre le problème de tri par fusion Trier, d'autant plus efficacement. 

Donc, je vous donne le tri par fusion. Nous allons jeter un coup d'oeil. Voici donc pseudo, avec que nous pourrions mettre en œuvre le tri, en utilisant cet algorithme appelé tri par fusion. Et il est tout simplement cela. En entrée de n éléments, en d'autres termes, si vous êtes n donné des éléments et des chiffres et lettres ou ce que l'entrée est, si vous êtes donné n éléments, le cas n est inférieur à 2, il suffit de revenir. Droit? En effet, si n est inférieur à 2, qui signifie que ma liste d'éléments est soit de taille 0 ou 1, et dans ces deux cas triviaux, la liste est déjà trié. Si il n'y a pas de liste, elle est triée. Et si il ya une liste de longueur 1, il est évidemment triés. Donc, l'algorithme doit seulement vraiment faire quelque chose d'intéressant, si nous avons deux ou plus éléments donnés pour nous. Alors regardons la magie alors. Else trier la moitié gauche des éléments, ensuite trier la moitié droite d'éléments, puis fusionner les moitiés triés. Et ce qui est un peu l'esprit de flexion ici, est que je ne pas vraiment semblent vous avoir dit rien pour l'instant, pas vrai? Tout ce que je l'ai dit est, donné une liste de n éléments, trier la moitié gauche, puis la moitié droite, puis fusionner les moitiés triés, mais où est la sauce secrète réelle? Où est l'algorithme? Bien il se trouve que ces deux lignes d'abord, la moitié gauche de tri des éléments, et trier moitié droite d'éléments, sont des appels récursifs, pour ainsi dire. 

Après tout, à ce point dans le temps, je dois un algorithme avec lequel trier tout un tas d'éléments? Oui. Il est juste ici. Il est ici à l'écran, et si je peux utiliser ce même ensemble d'étapes pour trier la moitié gauche, que je peux la moitié droite. Et en effet, encore, et encore. Donc, d'une certaine manière ou d'une autre, et nous allons bientôt voir cela, la magie de tri par fusion est intégré dans ce très finale ligne, fusionnant les moitiés triés. Et cela semble assez intuitif. Vous prenez deux moitiés, et vous, en quelque sorte, les fusionner, et nous verrons ce concrètement dans un instant. 

Mais ceci est un algorithme complet. Et nous allons voir exactement pourquoi. Eh bien supposons que nous sommes donné ces mêmes huit éléments ici sur l'écran, un à huit, mais ils sont afin apparemment aléatoire. Et l'objectif est à portée de main pour trier ces éléments. Eh bien comment puis-je aller sur le faire en utilisant, à nouveau, tri par fusion, selon ce pseudo? Et encore, ce ancrer dans votre esprit, pour un instant. Le premier cas est assez triviale, si elle est inférieure à 2, juste retour, il n'y a pas de travail à faire. Alors, vraiment, il ya juste trois des mesures pour vraiment garder à l'esprit. Encore une fois, et encore, je suis allez vouloir d'avoir pour trier la moitié gauche, trier la moitié droite, puis une fois que leur deux moitiés sont triées, Je tiens à les fusionner en une liste triée. Alors garde cela en tête. 

Alors, voici la liste originale. Traitons cela comme une tableau, comme nous avons commencé à la deuxième semaine, ce qui est une bloc contigu de mémoire. Dans ce cas, contenant huit numéros, dos à dos à dos. Et maintenant, nous allons appliquer le tri par fusion. Donc, je tiens d'abord à trier la moitié gauche de cette liste, et nous allons, par conséquent, concentrer le 4, 8, 6, et 2. 

Maintenant, comment puis-je faire le tri d'une liste de taille 4? Eh bien, je dois tenir compte maintenant tri de la gauche de la moitié gauche. Encore une fois, nous allons rembobiner pour un instant. Si le pseudo-code est présent, et je me donne huit éléments, 8 est évidemment plus grande supérieur ou égal à 2. Donc, avec le premier cas ne concerne pas. Donc, pour trier huit éléments, je premier trier la moitié gauche d'éléments, puis-je trier la moitié droite, puis je fusionne les deux moitiés, chacune triées de taille quatre. D'ACCORD. 

Mais si vous venez de me dire, trier la la moitié gauche, qui est maintenant de la taille 4, comment puis-je trier la moitié gauche? Eh bien, si je dois un quatre éléments de saisie, Je trie d'abord la gauche deux, puis le droit à deux, et puis je les fusionner. Encore une fois, ça devient un peu d'un esprit de flexion jeu ici, parce que vous, en quelque sorte, doivent rappelez-vous où vous êtes dans l'histoire, mais à la fin de la journée, étant donné un certain nombre d'éléments, vous voulez d'abord pour trier la la moitié gauche, puis la moitié droite, puis de les fusionner. Commençons à faire exactement cela. Voici l'entrée de huit éléments. Maintenant, nous sommes à la recherche à la moitié gauche ici. Comment puis-je trier quatre éléments? Eh bien, je trie première la moitié gauche. Maintenant, comment puis-je trier la moitié gauche? Eh bien, je l'ai été donné deux éléments. Donc, nous allons trier ces deux éléments. La figure 2 est supérieur ou égal à 2, bien sûr. Alors que le premier cas ne concerne pas. 

Donc, je dois maintenant trier la gauche la moitié de ces deux éléments. La moitié gauche, bien sûr, est à seulement 4. Alors, comment puis-je trier une liste d'un élément? Eh bien maintenant, ce cas de base spéciale en haut, pour ainsi dire, applique. 1 est inférieur à 2, et ma la liste est en effet de taille 1. Je viens donc de retour. Je ne fais rien. Et en effet, regarder ce que je l'ai fait, 4 est déjà trié. Comme je suis déjà partiellement réussi ici. 

Maintenant que semble un peu stupide la revendication, mais il est vrai. 4 est une liste de taille 1. Il est déjà triée. Voilà la moitié gauche. Maintenant, je trier la moitié droite. Mon entrée est un élément, 8 de même, déjà triés. Stupide, trop, mais encore une fois, ce principe de base va nous permettre maintenant de construire en haut de cette succès. 4 triés, 8 sont triés, maintenant quelle était cette dernière étape? Donc, la troisième et dernière étape, toute fois que vous êtes le tri d'une liste, le rappel, était de fusionner les deux moitiés, la gauche et la droite. Donc, nous allons faire exactement cela. Ma moitié gauche est, bien sûr, 4. Ma moitié droite est 8. 

Donc, nous allons le faire. Je vais d'abord à allouer de la mémoire supplémentaire, que je vais représente ici, comme un tableau secondaire, qui est assez grand pour tenir cette. Mais vous pouvez imaginer d'étendre ce rectangle, la totalité de la longueur, si nous avons besoin plus tard. Comment dois-je prendre 4 et 8, et de fusionner ces deux listes de taille 1 ensemble? Ici aussi, assez simple. 4 vient en premier, puis vient 8. Parce que si je veux trier la la moitié gauche, puis la moitié droite, puis fusionner ces deux moitiés ensemble, dans l'ordre de tri, 4 vient en premier, puis vient 8. 

Donc, nous semblons faire des progrès, même si je ne l'ai pas fait tout le travail réel. Mais rappelez-vous où nous sommes dans l'histoire. Nous avons pris l'origine huit éléments. Nous avons réglé la moitié gauche, qui est de 4. Ensuite, nous avons trié la moitié gauche de la moitié gauche, ce qui est deux. Et c'est reparti. Nous en avons terminé avec cette étape. 

Donc, si nous avons trié les la moitié des 2 partis, maintenant nous avoir pour trier la moitié droite de 2. Donc, la moitié droite de 2 est ces deux valeurs, ici, six et deux. Alors prenons maintenant une entrée de la taille 2, et de trier la moitié gauche, puis la moitié droite, puis les fusionner. Eh bien, comment puis-je trier une liste de taille 1, contenant juste le numéro 6? Je suis déjà fait. Cette liste de taille 1 est triée. 

Comment puis-je trier une autre liste de taille 1, la demi prétendu droit. Eh bien, elle aussi, est déjà trié. Le numéro 2 est seul. Alors maintenant, je dois deux moitiés, gauche et Bon, je dois les fusionner. Permettez-moi de me donner un peu d'espace supplémentaire. Et de mettre 2 là, puis 6 là, ainsi trier cette liste, gauche et droite, et la fusion ensemble, en fin de compte. Donc, je suis légèrement meilleure forme. Je ne suis pas fait, parce que clairement 4, 8, 2, 6 est pas la dernière commande que je veux. Mais je dois maintenant deux listes de taille 2, que ont tous deux, respectivement, été triés. Alors maintenant, si vous rembobinez dans votre esprit de oeil, où n'a que de nous laisser? Je ai commencé avec huit éléments, alors je taillé vers le bas de la moitié gauche de quatre, puis la moitié gauche de deux, et puis la moitié droite de 2, Je finis donc, le tri de la gauche la moitié des 2 et la moitié droite de 2, alors quelle est la troisième et dernière étape ici? Je dois fusionner deux listes de taille 2. Donc, nous allons aller de l'avant. Et sur l'écran ici, donner moi un peu de mémoire supplémentaire, si, techniquement, remarque que je l'ai eu tout un tas d'espace en haut sommet vierge Là. Si je veux être particulièrement efficace de l'espace sage, Je ne pouvais tout simplement commencer à déplacer les éléments avant et en arrière, haut et bas. Mais juste pour la clarté visuelle, Je vais le mettre en bas, de garder les choses belle et propre. 

Donc, je dois deux listes de taille 2. La première liste a 4 et 8. La deuxième liste a 2 et 6. Disons fusionner ces ensemble dans l'ordre. 2, bien sûr, vient en premier, puis 4, puis 6, puis 8. Et maintenant, nous semblons un endroit intéressant. Maintenant, je suis la moitié de l'trié liste, et comme par hasard, il est tous les nombres pairs, mais que est, en effet, juste une coïncidence. Et maintenant je l'ai trié la gauche moitié, de sorte qu'il est 2, 4, 6 et 8. Rien est irrecevable. Qui se sent comme progrès. 

Maintenant, il se sent comme je l'ai été de parler toujours maintenant, donc ce qui reste à voir si cette algorithme est, en effet, plus efficace. Mais nous allons à travers it Super méthodiquement. Un ordinateur, bien sûr, serait faire comme ça. Alors, où en sommes-nous? Nous avons commencé avec huit éléments. Je trié la moitié gauche de 4. Je semble être fait avec cela. Alors maintenant, la prochaine étape est de trier la moitié droite de 4. Et cette partie nous pouvons aller grâce à un peu plus rapidement, même si vous êtes Bienvenue pour rembobiner ou faire une pause, juste penser par elle au votre propre rythme, mais ce nous avons maintenant l'occasion de faire la même algorithme exact sur quatre des nombres différents. 

Donc, nous allons aller de l'avant, et se concentrer sur la moitié droite, que nous sommes ici. La moitié gauche de cette la moitié droite, et maintenant le la moitié gauche de la gauche la moitié de cette moitié droite, et comment puis-je trier une liste de taille 1 contenant juste le numéro 1? C'est déjà fait. Comment dois-je faire la même chose pour une liste de taille 1 contenant seulement 7? C'est déjà fait. Étape trois pour cette demi puis est de fusionner ces deux éléments dans une nouvelle liste de taille 2, 1 et 7. Ne semble pas avoir fait tout que beaucoup de travail intéressant. Voyons ce qui arrive ensuite. Je viens trié la moitié gauche de la la moitié droite de mon entrée d'origine. Maintenant, nous allons trier le droit moitié, qui contient 5 et 3. Voyons à nouveau regarder à gauche la moitié, triés, la moitié droite, triés, et de fusionner les deux ensemble, dans un peu d'espace supplémentaire, 3 vient en premier, puis vient 5. Et maintenant, nous avons trié les la moitié gauche de la moitié droite du problème d'origine, et la moitié droite de la moitié droite du problème original. Quelle est la troisième et dernière étape? Eh bien, pour fusionner ces deux moitiés ensemble. Alors permettez-moi de me mettre un peu espace supplémentaire, mais, encore une fois, je pourrait être l'aide de cet espace en haut sommet de rechange. Mais nous allons continuer simple visuellement. Permettez-moi de fusion dans l'entreprise 1, et puis 3, puis 5, puis 7. Ainsi me laissant maintenant avec le moitié droite du problème original qui est parfaitement triés. 

Donc ce qui reste? Je me sens comme je ne cesse de dire le mêmes choses encore et encore, mais qui est le reflet de la fait que nous utilisons la récursion. Le processus de l'aide d'un algorithme encore, et encore, sur de plus petits sous-ensembles de le problème d'origine. Donc, je l'ai maintenant une gauche trié la moitié du problème d'origine. Je dois une demi triée droit du problème original. Quelle est la troisième et dernière étape? Oh, il est la fusion. Donc, nous allons le faire. Disons allouer une partie supplémentaire mémoire, mais mon dieu, nous pourrait mettre partout maintenant. Nous avons tellement d'espace disponible pour nous, mais nous allons garder les choses simples. Au lieu d'aller en arrière et -vient avec la mémoire originale, disons simplement faire visuellement ici-bas, pour finir la fusion de la la moitié gauche et la moitié droite. 

Donc, en fusionnant, que dois-je faire? Je veux prendre les éléments dans l'ordre. Donc, en regardant la moitié gauche, Je vois le premier numéro est de 2. Je regarde la moitié droite, Je vois le premier numéro est 1, donc évidemment, qui numéro dois-je tiens à arracher, et de mettre en premier dans ma liste finale? Bien sûr, 1. Maintenant, je veux poser la même question. Sur la moitié gauche, je l'ai encore obtenu le numéro 2. Sur la moitié droite, Je dois le numéro 3. Lequel veux-je choisir? Bien sûr, le numéro 2 et Remarquez maintenant les candidats 4 sont à gauche, 3 à droite. Allons, bien sûr, choisir 3. Les candidats sont désormais sur 4 la gauche, 5 à droite. Nous, bien sûr, choisir 4. 6 sur la gauche, 5 à droite. Nous, bien sûr, choisir 5. 6 sur la gauche, sur la droite 7. Nous choisissons 6, puis nous choisissez 7, puis nous choisissons 8. Voila. 

Donc, un grand nombre de mots plus tard, nous ont trié cette liste de huit éléments dans une liste de un à huit, que ça augmente avec chaque étape, mais combien de temps fait il nous a fallu pour le faire. Eh bien, je l'ai délibérément choses énoncées imagée ici, afin que nous puissions type de voir ou apprécier la division dans la conquête de ce qui a été le cas. 

En effet, si vous regardez en arrière à la veillée, Je l'ai laissé tous ces pointillés en place des titulaires, vous pouvez, sorte de, voir, dans l'ordre inverse, si vous regardez en arrière de type dans l'histoire maintenant, ma liste originale est, bien sûr, de la taille 8. Et puis, précédemment, je étais traiter avec deux listes de taille 4, puis quatre listes de taille 2, puis huit listes de taille 1. 

Alors qu'est-ce, en quelque sorte, de vous rappeler? Eh bien, en effet, l'une des les algorithmes que nous avons regardé jusqu'ici où nous fracture, et diviser, et diviser, garder d'avoir des choses à nouveau, et encore, les résultats de cette idée générale. Et donc il ya quelque chose logarithmique passe ici. Et il est pas tout à fait du journal n, mais il ya un élément logarithmique à ce que nous venons de faire. 

Voyons maintenant comment cela est fait. Alors connectez-de n, était à nouveau un grand temps de fonctionnement, quand nous avons fait quelque chose comme recherche binaire, comme nous l'appelons maintenant, la stratégie de diviser pour mieux régner par l'intermédiaire duquel nous avons trouvé Mike Smith. Maintenant, techniquement. Voilà journal de base 2 n, même si dans la plupart des classes de mathématiques, 10 est généralement la base que vous assumez. Mais les scientifiques informatiques presque toujours penser et à parler en termes de base 2, donc nous disons généralement juste de journal n, au lieu de log base 2 de n, mais ils sont exactement une seule et même dans le monde de l'informatique la science, et en passant, il ya un facteur constant différence entre les deux, il est donc moot de toute façon, pour des raisons plus formelles. 

Mais pour l'instant, ce que nous nous soucions à propos de cet exemple est. Donc, il ne faut pas prouver par exemple, mais à utiliser moins un exemple des numéros à portée de main comme un test de cohérence, si vous voulez. Donc, la formule était précédemment base de journal 2 n, mais ce qui est n dans ce cas. Je devais nombres n originales, ou 8 du nombre initial spécifiquement. Maintenant, cela fait un peu tout, mais je suis assez assurer que log base 2 la valeur de 8 est 3, et en effet, ce qui est agréable à ce sujet est 3 qui est exactement le nombre de fois que vous pouvez diviser une liste de longueur 8, encore et encore, et encore, jusqu'à ce que vous êtes de gauche avec des listes de juste taille 1. Droit? 8 va à 4, va à 2, passe à 1, et que ce reflète exactement ce que image que nous avions il ya un instant. Donc un peu de raison de vérifier l'endroit où le logarithme est en réalité impliqué. 

Alors maintenant, quoi d'autre est impliqué ici? n. Donc remarquerez que tous les fois que je partagerai la liste, mais dans l'ordre inverse dans l'histoire ici, je faisais toujours n choses. Cette étape de fusion exige que Je touche chacun des numéros, afin de glisser dans son emplacement approprié. Ainsi, même si la hauteur de cette schéma est de taille log n de n ou 3, en particulier, en d'autres termes, Je l'ai fait trois divisions ici. Combien de travail ai-je fait horizontalement le long de ce tableau à chaque fois? 

Eh bien, je l'ai fait n étapes de travailler, parce que si je l'ai obtenu quatre éléments et les quatre éléments, et je dois les fusionner. Je dois passer par ces quatre et ces quatre, en fin de compte pour les fusionner Retour en huit éléments. Si à l'inverse, je dois huit doigts ici, que je ne le fais pas, et huit fingers-- sorry-- Si je l'ai eu quatre doigts sur ici, ce que je fais, quatre doigts ici, ce que je fais, alors que ce même par exemple comme avant, si je fais ont huit doigts si, dans totale, ce que je peux, en quelque sorte, faire. Je peux faire exactement ici, alors je peux certainement fusionner toutes ces listes de taille 1 ensemble. Mais je dois certainement à regarder à chaque élément exactement une fois. Ainsi, la hauteur de ce processus est log n, la largeur de ce processus, pour ainsi dire, est N, donc ce que nous semblons d'avoir, en fin de compte, est un temps de course de taille n log n fois. 

En d'autres termes, nous avons divisé la liste, journal n fois, mais à chaque fois que nous avons fait, nous avons eu de toucher tous les éléments afin de les fusionner tous ensemble, qui a été n étape, nous avons donc n fois log N, ou comme un informaticien dirait, asymptotiquement, qui serait le grand mot pour décrire la partie supérieure lié sur un temps de fonctionnement, nous courons dans une grande o de log n fois, pour ainsi dire. 

Maintenant, cela est significatif, parce rappellent ce que les durées de fonctionnement étaient avec tri à bulles, et la sélection Trier, et le tri par insertion, et même quelques autres qui existent, n carré était où nous en étions. Et vous pouvez, en quelque sorte, le voir ici. Si n est évidemment carré n fois n, mais ici nous avons n log n fois, et nous savons déjà de la semaine zéro, ce log n, l'logarithmique, est quelque chose de mieux que linéaire. Après tout, rappeler l'image avec le rouge et le jaune et les lignes vertes que nous Drew, logarithmique ligne verte était beaucoup plus faible. Et donc, beaucoup mieux et plus vite que les lignes jaunes et rouges droites, n fois log n est, en effet, de mieux de n fois n, ou n au carré. 

Donc, nous semblons avoir identifié une fusion de l'algorithme genre qui fonctionne dans beaucoup le temps plus vite, et en effet, Voilà pourquoi, plus tôt cette semaine, lorsque nous avons vu ce concours entre les bulles Trier, tri par sélection, et de fusionner tri, le tri par fusion vraiment, vraiment gagné. Et en effet, nous ne l'avons même pas attendre pour tri à bulles et de sélection Trier finir. 

Prenons maintenant un autre passe à ce, à partir d'un peu plus point de vue formel, juste au cas, cela résonne mieux que la discussion de niveau supérieur. Alors, voici à nouveau l'algorithme. Demandons-nous, ce que le temps d'exécution est de cette algorithmes différentes étapes? Divisons dans la première boîtier et le deuxième cas. Le SI et de l'autre dans le cas si, Si n est inférieur à 2, il suffit de retourner. On se sent comme constante de temps. Il est, en quelque sorte, comme deux étapes, Si n est inférieur à 2, puis retour. Mais comme nous le disions, le lundi, constante de temps, ou grand o 1, peut être deux, trois étapes mesures, voire 1000 étapes. Ce qui importe est qu'il est un nombre constant d'étapes. Donc, la surbrillance jaune pseudo tourne ici dans, nous l'appellerons, constante de temps. Donc, plus formellement, et nous allons cette to-- sera la mesure dans laquelle on officialiser ce droit maintenant-- T de n, le temps d'exécution d'un problème qui prend n somethings comme entrée, Big O est égal à un, Si n est inférieur à 2. Donc, il est conditionnelle à ce sujet. Donc, pour être clair, si n est inférieur à 2, nous avons une très courte liste, puis le temps d'exécution, de T n, où n est égal à 1 ou 0, dans ce cas très précis, il va juste être constante de temps. Il va prendre un l'étape, à deux pas, peu importe. Il est un nombre fixe d'étapes. 

Ainsi, la partie juteuse doit sûrement être en l'autre cas dans le pseudo-code. Le cas ELSE. Trier moitié gauche d'éléments, en quelque sorte droit la moitié des éléments, fusionner moitiés triés. Combien de temps dure chacune de ces étapes prend-il? Eh bien, si le fonctionnement le temps de trier n éléments est, disons qu'il est très génériquement, T n, puis le tri de la gauche la moitié des éléments est, en quelque sorte, comme dire, T de n divisé par deux, et le tri de même la moitié droite d'éléments est, en quelque sorte, comme dire, T n de 2 divisée, et ensuite la fusion des moitiés triées. Eh bien, si je dois un peu nombre d'éléments ici, comme quatre, et un nombre d'éléments ici, comme quatre, et je dois fusionner chacun de ces quatre dans, et chacun de ces quatre, une après l'autre, de sorte que finalement, je dois huit éléments. Il se sent comme si ce Big O de n étapes? Si je dois n doigts et chacun des eux doit être fusionné en place, qui est comme un autre n étapes. 

Donc, en effet formulaically, nous pouvons exprimer cela, quoique un peu au premier abord effroyablement coup d'oeil, mais il ya quelque chose qui capte exactement cette logique. Le temps d'exécution, de T n, si n est supérieur ou égal à 2. Dans ce cas, le cas ELSE, est T de n divisé par 2, plus T de N divisé par 2, en plus grande de n o, certains Numéro linéaire d'étapes, peut-être exactement n, peut-être 2 fois n, mais il est à peu près, afin de n. Alors que, aussi, est de savoir comment nous pouvons exprimer cette formulaically. Maintenant, vous ne seriez pas le savoir à moins vous avez enregistré dans votre esprit, ou recherchez-le dans le Retour d'un manuel, qui pourraient avoir un peu antisèche à la fin, mais cela est, en effet, va nous donner une grande o n log n, parce que la récurrence vous voyez ici à l'écran, si vous avez réellement fait sortir, avec un nombre infini d'exemples, ou vous l'avez fait formulaically, vous le feriez voir que cela, parce que cette formule lui-même est récursive, avec des t n sur quelque chose sur la droite, et t du N de la gauche, cela peut être effectivement exprimé, en fin de compte, aussi grand feu de n log n. Si pas convaincu, que ce bien pour le moment, juste prendre sur la foi, qui est que, en effet, ce qui conduit à récurrence, mais ceci est juste un peu plus d'un approche mathématique de la recherche à la durée de fonctionnement de tri par fusion sur la base de son seul pseudocode. 

Prenons maintenant un peu pause de tout cela, et jeter un oeil à une certaine ancien sénateur, qui pourrait ressembler un peu familier, qui est assis avec Eric de Google Schmidt, il ya quelque temps, pour une entrevue sur scène, en face de tout un tas de personnes, parler en fin de compte à propos un sujet, qui est assez maintenant familière. Nous allons jeter un coup d'oeil. 

Eric Schmidt: Maintenant, sénateur, vous êtes ici chez Google, et je plais à penser de la présidence comme une entrevue d'emploi. Maintenant, il est difficile d'obtenir un emploi en tant que président. PRÉSIDENT OBAMA: Droit. Eric Schmidt: Et vous êtes va faire [inaudible] maintenant. Il est également difficile d'obtenir un emploi chez Google. PRÉSIDENT OBAMA: Droit. 

Eric Schmidt: Nous avons des questions, et nous demandons à nos questions aux candidats, et celui-ci est de Larry Schwimmer. 

PRÉSIDENT OBAMA: OK. 

Eric Schmidt: Qu'est-ce? Les gars, vous pensez que je plaisante? Il est juste ici. Quel est le moyen le plus efficace pour trier une entiers de 32 millions de bits? 

PRÉSIDENT OBAMA: Well-- Eric Schmidt: Parfois, peut-être je suis désolé, maybe-- PRÉSIDENT OBAMA: Non, non, non, non, non, je think-- Eric Schmidt: Ce ne est pas it-- PRÉSIDENT OBAMA: Je penser, je pense que la bulle Trier serait le mauvais chemin à parcourir. Eric Schmidt: Viens. Qui lui a dit cela? D'ACCORD. Je ne l'ai pas l'informatique on-- 

PRÉSIDENT OBAMA: nous avons obtenu nos espions là-dedans. PROFESSEUR: Très bien. Laissons derrière nous maintenant monde théorique d'algorithmes dans l'analyse asymptotique celui-ci, et de revenir à certains sujets de la semaine zéro et un, et le démarrage pour enlever des roues de formation, si vous voulez. Pour que vous compreniez vraiment en fin de compte à partir du sol, ce qui est passe sous le capot, lorsque vous écrire, compiler et exécuter des programmes. Rappelons en particulier, que cela était le premier programme de C, nous avons examiné, canonique, programme simple de toutes sortes, relativement parlant, dans laquelle, elle imprime, Bonjour tout le monde. Et rappeler que je l'ai dit, le processus que le code source passe par est exactement cela. Vous prenez votre code source, passez à travers un compilateur, comme Clang, et il en sort code objet, que pourrait ressembler à ceci, zéros et de uns que le processeur de l'ordinateur, centrale unité de traitement ou du cerveau, comprend finalement. 

Il se trouve que ce est une peu d'une simplification excessive, que nous sommes maintenant dans un mesure de démêler de comprendre ce qui a vraiment été passe sous le capot chaque fois que vous exécutez Bruit, ou plus généralement, chaque fois que vous faites un programme, utilisant Marque et CF 50 IDE. En particulier, des trucs comme ci est généré, lorsque vous compilez d'abord votre programme. En d'autres termes, lorsque vous prendre votre code source et le compiler, ce qui est premier étant délivré en sortie par Clang est quelque chose de connu comme le code assembleur. Et en fait, il ressemble exactement à cela. 

Je courais une commande à la ligne de commande plus tôt. La hello.c de Clang dash capitale, et cela a créé un fichier pour moi appelées hello.s, l'intérieur de laquelle étaient exactement ces contenus, et un peu plus ci-dessus et un peu plus bas, mais je l'ai mis le plus juteux ici des informations sur l'écran. Et si vous regardez attentivement, vous verrez au moins quelques mots-clés familier. Nous avons principale en haut. Nous avons printf dans le milieu. Et nous avons aussi Bonjour tout le monde n barre oblique inverse entre guillemets bas. 

Et tout le reste ici est instructions de niveau très bas que le processeur de l'ordinateur comprend. Instructions CPU qui se déplacent mémoire autour, que les chaînes de charge de la mémoire, et, finalement, d'impression choses sur l'écran. Maintenant, ce qui se passe si après ce code d'assemblage est généré? En fin de compte, que vous faites, en effet, générer encore de code objet. Mais les mesures qui ont vraiment été se passe sous le capot regarder un peu plus comme ça. Source code devient le code assembleur, qui devient alors le code objet, et les mots-clés ici sont que, lorsque vous compilez votre code source, out vient code assembleur, puis lorsque vous assemblez votre code d'assemblage, out vient code objet. 

Maintenant Clang est super sophistiqué, comme beaucoup de compilateurs, et il fait tout de ces étapes en même temps, et il ne fait pas nécessairement sortie tout intermédiaire fichiers que vous pouvez même voir. Il compile les choses, qui est le terme général qui décrit tout ce processus. Mais si vous voulez vraiment d'être particulier, il ya beaucoup plus de choses là-bas aussi. 

Mais nous allons examiner maintenant aussi que même ce programme super simple, hello.c, une fonction appelée. Il appelle printf. Mais je ne l'ai pas écris printf, en effet, qui vient avec c, pour ainsi dire. Il est un rappel de la fonction qui est déclaré dans io.h standard, qui est un fichier d'en-tête, qui est un sujet que nous allons effectivement plonger plus en profondeur avant longtemps. Mais un fichier d'en-tête est généralement accompagnée par un fichier de code, fichier de code source, de sorte tout comme il existe io.h. norme 

Il ya quelque temps, quelqu'un, ou quelqu'un, a également écrit un fichier appelé io.c standard, dans où les définitions réels, ou implémentations de printf, et grappes d'autres fonctions, sont en fait écrit. Donc, étant donné que, si nous considérons avoir ici sur la gauche, hello.c, que lorsque compilé, nous donne hello.s, même si Clang ne dérange pas l'épargne dans un endroit nous pouvons le voir, et que le code assembleur obtient assemblés en hello.o, qui est, en effet, le nom par défaut donnée chaque fois que vous compilez la source coder en code objet, mais ne sont pas tout à fait prêt à l'exécuter encore, car une autre étape qui doit arriver, et a est passé pour le passé quelques-uns semaines, peut-être à votre insu. 

Plus précisément, quelque part CS50 en IDE, et ce, aussi, sera un peu une simplification pour un moment, il est, ou était sur un temps, un fichier appelé io.c standard, que quelqu'un compilé dans io.s standard ou l'équivalent, que quelqu'un ensuite assemblé io.o en standard, ou il se trouve dans un fichier légèrement différente format qui peut avoir un différent extension de fichier tout à fait, mais en théorie et conceptuellement, exactement ces mesures devaient se produire dans une certaine forme. Ce qui veut dire, que maintenant quand je écrire un programme, hello.c, qui dit simplement, Bonjour tout le monde, et je suis en utilisant le code de quelqu'un d'autre comme printf, qui était autrefois sur un temps, dans un fichier appelé io.c standard, puis de toute façon je dois prendre mon code objet, mes zéros et de uns, et l'objet de cette personne code, ou zéros et de uns, et en quelque sorte lier ensemble dans un fichier final, appelé bonjour, que a tous les zéros et ceux de ma fonction principale, et tous les zéros et ceux pour printf. 

Et en effet, ce dernier processus est appelé, reliant votre code objet. La sortie de laquelle est un fichier exécutable. Donc, en toute équité, à la fin de la journée, rien a changé depuis la première semaine, quand nous première commencé à compiler des programmes. En effet, tout cela a été passe sous le capot, mais maintenant nous sommes dans une position où nous pouvons réellement démêler ces différentes étapes. Et en effet, à la fin de la journée, nous sommes toujours gauche avec des zéros et de uns, qui est en fait une excellente introduction maintenant à l'autre de capacité C, qui nous avons pas eu à tirer parti le plus probable à ce jour, connu sous le nom opérateurs binaires. En d'autres termes, à ce jour, chaque fois que nous avons traiter les données en C ou les variables C, nous avons eu des choses comme chars et des flotteurs et ins et longs et doubles et similaires, mais tous ceux qui sont au moins huit bits. Nous avons encore jamais été en mesure de manipuler des bits individuels, même si un bit individuel, nous savez, peut représenter un 0 et un 1. Or il se trouve que, dans C, vous peuvent avoir accès à des bits individuels, si vous connaissez la syntaxe, avec laquelle de les atteindre. 

Donc, nous allons jeter un coup d'oeil aux opérateurs au niveau du bit. Donc, ici photographiés sont quelques symboles nous avons, en quelque sorte, en quelque sorte, vu avant. Je vois une esperluette, un vertical bar, et quelques autres ainsi, et rappeler que esperluette esperluette est quelque chose que nous avons vu auparavant. L'opérateur logique ET, où vous avez deux d'entre eux en même temps, ou la logique OU l'opérateur, où vous avoir deux barres verticales. Opérateurs binaires, que nous allons voir fonctionner sur des morceaux individuellement, il suffit d'utiliser un seul esperluette, un seule barre verticale, le symbole caret vient ensuite, la petite tilde, puis à gauche support de crochet gauche, ou crochet droit crochet droit. Chacun de ceux-ci ont des significations différentes. 

En fait, nous allons jeter un coup d'oeil. Allons vieille école aujourd'hui, et l'utilisation un écran tactile d'antan, connu comme un tableau blanc. Et ce tableau blanc va nous permettre pour exprimer certains symboles assez simples, ou plutôt des formules assez simples, que nous puissions finalement l'effet de levier, afin à l'accès individuel bits dans un programme C. En d'autres termes, nous allons le faire. Parlons d'abord pour une instant sur esperluette, qui est le bit à bit ET opérateur. En d'autres termes, ceci est un opérateur qui permet moi d'avoir une variable de gauche généralement, et une variable de droite, ou une valeur individuelle, que si nous ET ensemble, me donne un résultat final. Alors qu'est-ce que je veux dire? Si dans un programme, vous avez une variable qui stocke une de ces valeurs, ou nous allons garder les choses simples, et juste écrire zéros et de uns individuellement, voici comment l'opérateur esperluette fonctionne. 0 0 esperluette va égaler 0. Maintenant, pourquoi est-ce? 

Il est très similaire à Expressions booléennes, que nous avons discuté jusqu'à présent. Si vous pensez que, après tout, le 0 est false, 0 est faux, faux et faux est, comme nous l'avons discuté logiquement, aussi fausse. Donc, nous obtenons 0 ici aussi. Si vous prenez 0 esperluette 1, ainsi que, aussi, va être 0, car pour cette expression du côté gauche pour être vrai ou 1, il aurait besoin d'être vrai et vrai. Mais ici nous avons fausse et vrai, ou 0 et 1. Maintenant, encore une fois, si nous avons une esperluette 0, qui, lui aussi, va être 0, et si nous avons une esperluette 1, Enfin ne nous avons un peu 1. Donc, en d'autres termes, nous ne faisons pas quelque chose d'intéressant avec cet opérateur pour l'instant, cet opérateur esperluette. Il est le bit à bit ET opérateur. Mais ce sont les ingrédients par lequel nous pouvons faire choses intéressantes, comme nous le verrons bientôt. 

Maintenant regardons juste la seule barre verticale ici sur la droite. Si je dois un bit 0 et je OU avec le bit à bit OU opérateur, un autre bit 0, que ça va me donner 0. Si je prends un peu et ou il avec 0 un bit 1, alors je vais obtenir 1. Et en fait, juste pour clarté, permettez-moi de revenir en arrière, de sorte que mes barres verticales ne sont pas pris pour des 1. Permettez-moi de réécrire tous ma 1 est un peu plus clairement, afin que nous voyons ensuite, si je ont un 1 ou 0, cela va être un 1, et si je dois un 1 ou 1 que, aussi, va être un 1. Donc vous pouvez voir que la logique OU opérateur se comporte très différemment. Cela me donne 0 ou 0 me donne 0, mais toute autre combinaison me donne 1. Tant que je suis un 1 dans le formule, le résultat va être une. 

Par contraste avec le ET l'opérateur, l'esperluette, que si je dois deux 1 dans le équation, puis-je obtenir en fait un sur 1. Maintenant, il ya quelques autres opérateurs ainsi. L'un d'eux est un peu plus compliquée. Alors laissez-moi aller de l'avant et d'effacer ce afin de libérer un peu d'espace. Et nous allons jeter un oeil à la caret, juste un instant. Ceci est typiquement un caractère que vous pouvez taper sur votre Maj de maintien de clavier et puis l'un des numéros au sommet de votre US clavier. 

Donc, cela est l'exclusif Opérateur OU, OU exclusif. Donc, nous venons de voir l'opérateur OR. Ceci est l'opérateur OU exclusif. Ce qui est réellement la différence? Eh bien disons juste regarder la formule, et l'utiliser comme ingrédients finalement. 0 0 XOR. Je vais dire est toujours 0. Voilà la définition de XOR. XOR 0 1 va être une. Une XOR 0 va être 1, et 1 XOR 1 va être? Faux? Ou à droite? Je ne sais pas. 0. Maintenant, ce qui se passe ici? Eh bien réfléchir à la nom de cet opérateur. OU exclusif, de sorte que le nom, type de, suggère, la réponse est que va être 1 si les entrées sont exclusifs, exclusivement différente. Donc, voici les entrées sont les même, de sorte que la sortie est de 0. Ici, les entrées sont le même, de sorte que la sortie est de 0. Voici les sorties sont différents, ils sont exclusifs, et donc la sortie est 1. Il est donc très similaire à Et, il est très similaire, ou plutôt il est très similaire à OU, mais seulement d'une manière exclusive. Celui-ci est plus un 1, parce que nous avons deux de 1, et non pas exclusivement, un seul d'entre eux. Bien. Qu'en est-il des autres? Eh bien, le tilde, quant à lui, est effectivement agréable et simple, heureusement. Et ceci est un unaire opérateur, ce qui signifie il est appliqué à une seule entrée, l'un des opérandes, pour ainsi dire. Non à une gauche et une droite. En d'autres termes, si vous prenez de tilde 0, la réponse sera le contraire. Et si vous prenez tilde de 1, la Réponse Il sera le contraire. Donc, l'opérateur tilde est une façon de nier un peu, ou de retournement un peu de 0 à 1, ou 1-0. 

Et cela nous laisse enfin avec seulement deux opérateurs finaux, Le soi-disant décalage à gauche, et de la dite opérateur de décalage à droite. Jetons un regard sur la façon dont ces travaux. L'opérateur de décalage à gauche, écrite avec deux équerres de ce genre, fonctionne comme suit. Si mon entrée, ou mon opérande, à gauche opérateur de décalage est tout simplement un 1. Et je puis dire que l'ordinateur décalage à gauche que 1, disons sept places, le résultat est comme si je prendre que 1, et le déplacer sept emplacements sur la gauche, et par défaut, nous allons supposer que l'espace vers la droite va être complétée par des zéros. En d'autres termes, 1 Maj gauche 7 va de me donner que 1, suivi par 1, 2, 3, 4, 5, 6, 7 zéros. Donc dans un sens, il vous permet de prendre un petit nombre comme 1, et de faire clairement beaucoup beaucoup, beaucoup plus grand de cette manière, mais nous allons réellement voir des approches plus intelligentes pour elle à la place, ainsi, 

Bien. Voilà pour trois semaines. Nous vous verrons la prochaine fois. Cela a été CS50. 

[Jouer de la musique] 

ENCEINTE 1: Il était au snack- bar de manger un hot fudge sundae. Il avait tout sur son visage. Il porte que le chocolat comme une barbe SPEAKER 2: Que faites-vous? Intervenant 3: Hmmm? Quoi? 

SPEAKER 2: Est-ce que vous venez de double dip? Vous double plongé la puce. Intervenant 3: Excusez-moi. SPEAKER 2: Vous plongé la puce, vous a pris une bouchée, et vous plongé à nouveau. Intervenant 3: SPEAKER 2: Voilà comme mettre votre droit de la bouche tout dans la trempette. La prochaine fois que vous prenez une puce, il suffit de tremper une fois, et y mettre fin. 

Intervenant 3: Vous savez quoi, Dan? Vous trempez la façon dont vous voulez plonger. Je vais tremper la manière que je veux plonger.