[Powered by Google Translate] [Section 3 - Plus confortable]
[Rob Bowden - Université de Harvard]
>> [C'est CS50. - CS50.TV]
>> Donc la première question est étrangement rédigée.
GDB vous permet de "debug" un programme, mais, plus précisément, qu'est-ce qu'il te laisser faire?
Je vais répondre à cette question, et je ne sais pas ce que c'est exactement prévu,
donc je pense que c'est quelque chose le long des lignes de celui-ci vous permet, étape par étape
marcher à travers le programme, d'interagir avec lui, les variables de changement, faire toutes ces choses -
essentiellement complètement contrôler l'exécution d'un programme
et inspecter n'importe quelle partie de l'exécution du programme.
Donc, ces fonctionnalités vous permettent de déboguer les choses.
D'accord.
Pourquoi est-ce binaire de recherche exigent que toute une série de trier?
Qui veut répondre à cela?
[L'élève] Parce que ça ne fonctionne pas si elle n'est pas triée. Ouais >>. [Rires]
Si ce n'est pas triée, alors il est impossible de le couper en deux
et je sais que tout ce qui précède est de moins en tout à droite
est supérieure à la valeur moyenne.
Donc, il doit être triée.
D'accord.
Pourquoi est-tri à bulles en O du carré n?
Quelqu'un veux d'abord donner un très rapide aperçu de haut niveau de ce tri à bulles est?
[L'élève] En gros, vous passez par chaque élément et vous vérifiez les éléments des premières années.
Si ils sont hors de l'endroit où vous les permuter, puis vous vérifiez les éléments à venir et ainsi de suite.
Lorsque vous arrivez à la fin, alors vous savez que le plus grand élément est placé à la fin,
si vous ignorez celui-là alors vous continuez à travers,
et chaque fois que vous devez cocher une case moins élément jusqu'à ce que vous n'apportez aucune modification. Ouais >>.
C'est ce qu'on appelle tri à bulles, parce que si vous retournez le tableau sur le côté de sorte qu'il est de haut en bas, vertical,
puis les grandes valeurs vont tomber au fond et les petites valeurs se propagera jusqu'au sommet.
Voilà comment il a obtenu son nom.
Et oui, vous venez de passer.
Vous continuez à travers le réseau, l'échange de la plus grande valeur
Pour obtenir les valeurs les plus élevées au fond.
>> Pourquoi est-il O du carré n?
Tout d'abord, personne ne veux pas dire pourquoi il est de O n carré?
[L'élève] Parce que pour chaque course il va n fois.
Vous ne pouvez être certain que vous avez pris le plus grand élément tout en bas,
alors vous avez à répéter que, pour que de nombreux éléments. Ouais >>.
Donc, gardez à l'esprit ce grand O signifie et quels moyens Omega grands.
Le grand A, c'est comme la limite supérieure de la lenteur qu'il peut réellement fonctionner.
Donc, en disant que c'est du carré O n, il n'est pas O n ou bien elle serait en mesure d'exécuter
en temps linéaire, mais il est de O n en cubes
parce qu'il est borné par O de n cubes.
Si elle est bornée par O de carré n, alors il est délimitée aussi par n cubes.
Donc, il est n au carré, et dans le pire des cas absolue ne peut pas faire mieux que carré n,
C'est pourquoi il est de O n carré.
Alors pour voir les mathématiques légère à la façon dont il sort pour être n au carré,
si nous avons cinq choses dans notre liste, la première fois le nombre de swaps pourrions-nous éventuellement besoin de faire
afin d'obtenir? Nous allons en fait juste -
Combien de swaps que nous allons avoir à faire dans la première manche du tri à bulles à travers le réseau?
[L'élève] n - 1. Ouais >>.
>> S'il ya 5 éléments, nous allons avoir besoin de faire n - 1.
Puis, le second le nombre de swaps que nous allons avoir à faire?
[L'élève] n - 2. Ouais >>.
Et le troisième va être n - 3, puis pour plus de commodité, je vais écrire les deux derniers
que nous allons avoir besoin de faire 2 swaps et 1 swap.
Je suppose que le dernier peut ou ne peut pas réellement besoin de se produire.
Est-il un échange? Je ne sais pas.
Donc, ce sont les montants totaux des swaps ou tout au moins les comparaisons que vous avez à faire.
Même si vous n'avez pas de swap, vous avez encore besoin de comparer les valeurs.
Il ya donc n - 1 comparaisons dans le premier passage dans le tableau.
Si vous réorganisez ces choses, nous allons réellement faire six choses que tant de choses se comparent très bien,
et puis je vais faire 3, 2, 1.
Il suffit donc de réorganiser ces sommes, nous voulons voir combien de comparaisons que nous faisons
dans l'algorithme entier.
Donc, si nous apportons ces gars ici-bas,
alors nous n'en sommes qu'au résumé des comparaisons mais il y avait beaucoup.
Mais si l'on cumule ces derniers et nous résumons ci et nous résumons ci,
c'est toujours le même problème. Nous venons de résumer ces groupes particuliers.
>> Alors maintenant, nous sommes sommateur 3 n de. Il ne s'agit pas seulement de 3 n.
Il va toujours être n / 2 n de.
Donc ici nous arrive d'avoir 6.
Si nous avions 10 choses, alors nous pourrions faire ce regroupement pour 5 paires différentes des choses
et finir avec n + n + n + n + n.
Donc, vous allez toujours obtenir n / 2 n, et donc ce que nous allons le noter sur la n au carré / 2.
Ainsi, même si c'est le facteur de la moitié, ce qui arrive d'entrer en
en raison du fait que, grâce à chaque itération sur le tableau 1 on compare moins
c'est comme ça que nous obtenons le plus 2, mais il est toujours n au carré.
Nous ne se soucient pas le facteur constant de la moitié.
Il ya donc beaucoup de choses importantes O comme celui-ci s'appuie sur tout type de faire ce genre de calcul,
faire des sommes arithmétiques et des trucs série géométrique,
mais la plupart d'entre eux dans ce cours sont assez simples.
D'accord.
Pourquoi le tri par insertion en Oméga de n? Qu'est-ce que omega dire?
[Deux élèves qui parlent à la fois - inintelligibles] >> Oui.
Omega vous pouvez penser que la borne inférieure.
>> Donc, peu importe à quel point votre algorithme de tri par insertion est,
quelle que soit la liste qui est transmis, il doit toujours comparer au moins les choses n
ou il doit effectuer une itération sur les choses n.
Pourquoi est-ce?
[L'élève] Parce que si la liste est déjà trié, puis à travers la première itération
vous ne pouvez garantir que l'élément premier est le moins,
et la seconde itération, vous ne pouvez garantir les deux premiers sont
parce que vous ne savez pas ce que le reste de la liste est triée. Ouais >>.
Si vous passez dans une liste triée complètement, à tout le moins, vous devez passer en revue tous les éléments
de voir que rien ne doit être déplacé.
Ainsi, passant au-dessus de la liste et de dire oh, c'est déjà trié,
il est impossible pour vous de savoir qu'il est trié avant d'avoir vérifié chaque élément
de voir qu'ils sont dans l'ordre.
Ainsi, la borne inférieure sur le tri par insertion est Omega de n.
Ce qui est le cas le plus défavorable temps d'exécution du tri par fusion,
pire des cas étant O grands encore?
Donc, dans le pire des cas, comment tri par fusion de fonctionner?
[L'élève] N log n. Ouais >>.
Le plus rapide des algorithmes de tri généraux sont n log n. Vous ne pouvez pas faire mieux.
>> Il ya des cas particuliers, et si nous avons le temps aujourd'hui - mais nous avons probablement ne le ferai pas -
nous avons pu voir celui qui fait mieux que n log n.
Mais dans le cas général, vous ne pouvez pas faire mieux que n log n.
Et le tri par fusion se trouve être celui que vous devez savoir pour ce cours qui est n log n.
Et donc nous allons effectivement être mise en œuvre aujourd'hui.
Et enfin, en moins de trois phrases, comment fonctionne tri par sélection?
Quelqu'un veut-il répondre, et je vais compter vos phrases
parce que si vous allez sur 3 -
Est-ce que quelqu'un se souvient de tri par sélection?
Tri par sélection est généralement assez facile de se rappeler à partir du nom.
Vous venez de parcourir le tableau, trouver tout ce que la plus grande valeur est la plus petite ou -
l'ordre que vous triez po
Donc, disons que nous sommes le tri du plus petit au plus grand.
Vous itérer sur le tableau, à la recherche de tout ce que l'élément minimum est
sélectionnez-le, puis il suffit d'échanger tout ce qui est en premier lieu.
Et puis lors du deuxième passage sur le tableau, recherchez l'élément minimal de nouveau,
sélectionnez-le, puis l'échanger avec ce qui est dans la deuxième position.
Donc, nous sommes juste sélectionner et de choisir les valeurs minimales
et les insérer dans la face de la matrice jusqu'à ce qu'il soit trié.
Questions à ce sujet?
>> Ceux-ci apparaissent inévitablement dans les formulaires que vous devez remplir lorsque vous soumettez le pset.
Ce sont essentiellement les réponses à celles-ci.
Bon, alors maintenant des problèmes de codage.
J'ai déjà envoyé par e-mail - Quelqu'un at-il pas cet e-mail? D'accord.
J'ai déjà envoyé par e-mail l'espace que nous allons utiliser,
et si vous cliquez sur mon nom - je pense que je vais être à la base
en raison de la r arrière - mais si vous cliquez sur mon nom, vous verrez 2 révisions.
Révision 1 va être je l'ai déjà copié et collé le code dans les espaces
pour la chose recherche que vous allez avoir à mettre en œuvre.
Et Révision 2 sera la chose la sorte que nous mettons en œuvre par la suite.
Ainsi, vous pouvez cliquer sur mon Révision 1 et à partir de là.
Et maintenant, nous voulons mettre en œuvre binaire de recherche.
>> Quelqu'un veut-il simplement donner un pseudo-explication de haut niveau
de ce que nous allons avoir à faire de la recherche? Ouais.
[L'élève] Il suffit de prendre le milieu du tableau et de voir si ce que vous cherchez
est inférieure à celle ou plus.
Et si elle est inférieure, vous allez à la moitié de ce fait moins,
et si ce n'est plus, que vous alliez à la moitié, c'est plus et vous répétez jusqu'à ce que vous obtenez juste une chose.
[Bowden] Ouais.
Notez que notre tableau numbers est déjà trié,
et si cela signifie que nous pouvons tirer profit de cela et nous avons pu vérifier d'abord,
ok, je suis à la recherche pour le nombre 50.
Donc, je peux aller dans le centre.
Orient est difficile de définir le moment où il s'agit d'un nombre pair de choses,
mais disons simplement que nous serons toujours tronquer au milieu.
Nous avons donc ici 8 choses, de sorte que le milieu serait de 16.
Je suis à la recherche de 50, donc 50 est supérieur à 16.
Alors maintenant, je peux traiter mon gros tableau comme ces éléments.
Je peux jeter tout de 16 cours.
Maintenant, mon tableau est juste ces 4 éléments, et je le répète.
Alors je veux trouver au milieu nouveau, ce qui va être 42.
42 est inférieur à 50, afin que je puisse jeter ces deux éléments.
C'est mon tableau restante.
Je vais trouver le milieu nouveau.
Je suppose que 50 est un mauvais exemple parce que j'étais toujours jeter des choses à gauche,
mais par la même mesure, si je suis à la recherche de quelque chose
et c'est au moins la partie que je suis en train de regarder,
alors je vais jeter tout à droite.
Alors maintenant, nous devons mettre en oeuvre.
Notez que nous avons besoin de passer à la taille.
Nous ne pouvons pas non plus besoin de coder en dur la taille.
Donc, si nous nous débarrassons de ce # define -
D'accord.
Comment puis-je bien comprendre ce que la taille du tableau numbers est actuellement?
>> Combien d'éléments sont dans le tableau numbers?
[Étudiants] Numéros, supports,. Longueur?
[Bowden] Cela n'existe pas en C.
Besoin d'. Longueur.
Les tableaux n'ont pas de propriétés, il n'est donc pas propriété de longueur de tableaux
qui vous donnera juste le temps qu'il se trouve.
[L'élève] Voir la quantité de mémoire dont il dispose et diviser par la quantité - >> Oui.
Alors, comment pouvons-nous voir combien de mémoire il a? >> [L'élève] Sizeof. >> Ouais, sizeof.
Sizeof est l'opérateur qui va retourner la taille de la matrice de nombres.
Et ça va être des nombres entiers mais il ya beaucoup de fois la taille d'un entier
puisque c'est combien de mémoire il s'agit en fait de prendre place.
Donc, si je veux que le nombre de choses dans le tableau,
alors je vais vouloir diviser par la taille d'un entier.
D'accord. Alors qui me permet de passer en taille ici.
Pourquoi ai-je besoin de passer à la taille du tout?
Pourquoi ne puis-je pas simplement faire ici int size = sizeof (botte de foin) / sizeof (int)?
Pourquoi ça ne marche pas?
[L'élève] Ce n'est pas une variable globale.
[Bowden] Haystack existe et nous passons en nombre comme botte de foin,
et cela est une sorte de préfiguration de ce qui est à venir. Ouais.
[L'élève] Haystack est juste la référence à lui, donc il serait de retour la taille de cette référence est.
Ouais.
Je doute que dans la conférence que vous avez vu la pile encore vraiment, non?
Nous venons tout juste parlé.
Ainsi, la pile est l'endroit où toutes les variables vont être stockées.
>> Toute mémoire qui est allouée pour les variables locales qui se passe dans la pile,
et chaque fonction obtient son propre espace sur la pile, son cadre propre pile est ce que ça s'appelle.
Alors principale a son stack frame, et à l'intérieur de celui-ci va exister ce tableau numbers,
et il va y avoir de sizeof taille (nombre).
Il va avoir la taille d'un nombre divisé par la taille des éléments,
mais que toutes les vies dans stack frame principale.
Lorsque nous appelons la recherche, la recherche tient son propre cadre de pile,
son propre espace pour stocker toutes ses variables locales.
Mais ces arguments - de sorte botte de foin n'est pas une copie de ce tableau entier.
Nous ne transmettons pas dans le tableau en tant que copie en recherche.
Il passe juste une référence à ce tableau.
Ainsi, la recherche peut accéder à ces numéros par cette référence.
Il est toujours accéder aux choses qui vivent à l'intérieur du cadre de pile principale,
mais au fond, quand on arrive à des pointeurs, qui devrait être bientôt,
c'est ce que les pointeurs sont.
Les pointeurs sont juste des références à des choses, et vous pouvez utiliser des pointeurs pour accéder à des choses
qui sont dans les cadres de pile d'autres choses.
Ainsi, même si le nombre est locale au menu principal, on peut toujours y accéder via ce pointeur.
Mais puisque c'est juste un pointeur et c'est juste une référence,
sizeof (botte de foin) retourne juste la taille de la référence elle-même.
Il ne retourne pas la taille de la chose qu'il pointe vers.
Il ne retourne pas la taille réelle des chiffres.
Et si cela ne va pas travailler comme nous le voulons.
>> Questions à ce sujet?
Pointeurs aura disparu dans beaucoup plus de détails dans le gore dans les semaines à venir.
Et c'est pourquoi beaucoup de choses que vous voyez, des choses ou des choses la plupart des recherches de tri,
ils sont presque tous besoin de prendre la taille réelle de la matrice,
parce que dans C, nous n'avons aucune idée de ce que la taille du tableau est.
Vous devez manuellement passer po
Et vous ne pouvez pas passer manuellement dans le tableau en entier, car vous êtes juste de passage dans la référence
et il ne peut pas obtenir la taille de la référence.
D'accord.
Alors maintenant, nous voulons mettre en œuvre ce qui a été expliqué précédemment.
Vous pouvez travailler sur cela pendant une minute,
et vous n'avez pas à vous soucier de faire tout à la perfection à 100% de travail.
Il suffit d'écrire le pseudo-moitié pour la façon dont vous pensez que cela devrait fonctionner.
D'accord.
Pas besoin d'être complètement fini avec ce moment.
Mais personne ne se sentent à l'aise avec ce qu'ils ont à ce jour,
comme quelque chose que nous pouvons travailler avec ensemble?
Quelqu'un veut-il faire du bénévolat? Ou je vais choisir au hasard.
Il n'a pas besoin d'être juste à côté de toute mesure, mais quelque chose que nous pouvons modifier dans un état opérationnel.
[L'élève] Bien sûr. Ok >>.
Ainsi, vous pouvez enregistrer la révision en cliquant sur la petite icône Enregistrer.
Vous êtes Ramya, non? >> [L'élève] Ouais. >> [Bowden] D'accord.
Alors maintenant, je peux voir votre révision et tout le monde peut tirer jusqu'à la révision.
Et nous avons ici - D'accord.
Donc Ramya allé avec la solution récursive, ce qui est certainement une solution valable.
Il ya deux façons que vous pouvez faire à ce problème.
Vous pouvez soit le faire de manière itérative ou récursive.
La plupart des problèmes que vous rencontrez qui peut être fait de manière récursive peut aussi être fait de manière itérative.
Donc, ici, nous l'avons fait de manière récursive.
>> Quelqu'un veut-il définir ce que signifie faire une fonction récursive?
[L'élève] Lorsque vous avez une fonction appel lui-même
puis s'appeler elle-même jusqu'à ce qu'il ressorte avec une véritable et vrai. Ouais >>.
Une fonction récursive est juste une fonction qui s'appelle elle-même.
Il ya trois grandes choses qui une fonction récursive doit avoir.
Le premier est évidemment, il s'appelle lui-même.
Le second est le cas de base.
Donc, à un certain moment la fonction doit cesser de se nommant,
et c'est ce qui est le cas de base pour.
Donc, ici, nous savons que nous devrions arrêter, nous devrions abandonner dans notre recherche
lorsque le démarrage est égal à la fin - et nous allons passer en revue ce que cela signifie.
Mais finalement, la dernière chose qui est important pour les fonctions récursives:
les fonctions doivent en quelque sorte l'approche du cas de base.
Comme si vous n'êtes pas réellement mettre à jour quoi que ce soit lorsque vous faites le deuxième appel récursif,
si vous êtes littéralement juste d'appeler la fonction à nouveau avec les mêmes arguments
et aucune des variables globales ont changé ou quoi que ce soit,
vous n'atteindrez jamais le scénario de référence, dans ce cas, c'est mauvais.
Ce sera une récursion infinie et un débordement de pile.
Mais ici, nous voyons que la mise à jour se passe, puisque nous mettons à jour start + fin / 2,
nous mettons à jour l'argument final ici, nous mettons à jour l'argument start ici.
Donc, dans tous les appels récursifs nous mettons à jour quelque chose. D'accord.
Voulez-vous nous expliquer votre solution? >> Bien sûr.
J'utilise SearchHelp de sorte que chaque fois que je fais cet appel de fonction
J'ai le début de l'endroit où je suis à la recherche de l'agencement et la fin
d'où je suis à la recherche du tableau.
>> A chaque étape où il est dit que c'est l'élément central, qui est de début + fin / 2,
c'est équivalent à ce que nous recherchons?
Et si c'est le cas, nous l'avons trouvé, et je suppose qui est passé les niveaux de récursivité.
Et si ce n'est pas vrai, alors nous vérifions si cette valeur milieu du tableau est trop grand,
Dans ce cas, nous regardons la moitié gauche du tableau en allant du début à l'indice du milieu.
Et sinon, nous ne la demi final.
[Bowden] D'accord.
Ça a l'air bien.
Ok, donc un couple des choses, et en fait, c'est une chose très haut niveau
que vous n'aurez jamais besoin de savoir pour ce cours, mais il est vrai.
Les fonctions récursives, vous entendez toujours qu'ils sont une mauvaise affaire
parce que si vous vous appeler récursivement trop de fois, vous obtenez un débordement de pile
puisque, comme je l'ai dit précédemment, chaque fonction obtient son cadre propre pile.
Ainsi, chaque appel de la fonction récursive obtient son cadre propre pile.
Donc, si vous faites des appels récursifs 1000, vous obtenez 1.000 images de la pile,
et rapidement vous amener à avoir des frames de pile trop de choses et tout casser.
C'est pour cela que les fonctions récursives sont généralement mauvais.
Mais il est bien un sous-ensemble des fonctions récursives appelé queue-récursives,
et cela arrive à être un exemple de celui où si le compilateur le remarque
et il se doit, je pense - en Clang si vous lui passez le drapeau-O2
puis il s'en apercevra est récursive et rendre les choses bien.
>> Il va réutiliser le même frame de pile maintes et maintes fois pour chaque appel récursif.
Et donc puisque vous utilisez le même frame de pile, vous n'avez pas besoin de s'inquiéter
jamais empiler débordement, et en même temps, comme vous l'avez dit,
où une fois que vous revenez vrai, alors il doit retourner jusqu'à l'ensemble de ces cadres de pile
et le 10e appel à SearchHelp doit retourner à la 9e, doit retourner à la 8e.
Donc, qui n'a pas besoin de se produire lorsque les fonctions sont récursive.
Et si ce qui rend cette queue fonction récursive est remarquerez que, pour tout appel donné à SearchHelp
l'appel récursif qu'il a fait est ce qu'il est de retour.
Ainsi, dans le premier appel à SearchHelp, soit nous retourner immédiatement faux,
immédiatement renvoie true, sinon on fait un appel récursif à SearchHelp
où ce que nous sommes de retour est ce que cet appel est de retour.
Et nous ne pouvions pas le faire si nous avons fait quelque chose comme int x = SearchHelp, return x * 2,
quelques-unes changement aléatoire.
>> Alors maintenant, cet appel récursif, cette int x = SearchHelp appel récursif,
n'est plus récursive car il a bel et bien de revenir
retour à un cadre de pile précédente de sorte que cet appel à la fonction précédente
peut alors faire quelque chose avec la valeur de retour.
Donc, ce n'est pas récursive terminale, mais ce que nous avions avant est bien récursive. Ouais.
[Étudiants] ne devrait pas le cas la deuxième base être vérifié en premier
parce qu'il pourrait y avoir une situation où lorsque vous lui transmettez l'argument
vous avez commencer à la fin =, mais ils sont la valeur aiguille.
La question a été ne peut pas nous lancer dans le cas où la fin est la valeur aiguille
ou commencer à la fin =, de manière appropriée, commencer à la fin =
et vous n'avez pas fait vérifier cette valeur particulière encore,
puis commencer à la fin + / 2 va juste être la même valeur.
Mais nous avons déjà retourné false et nous n'avons jamais réellement vérifié la valeur.
Donc, à tout le moins, dans le premier appel, si la taille est 0, alors nous voulons retourner faux.
Mais si la taille est 1, puis départ ne va pas jusqu'à la fin de l'égalité,
et nous allons vérifier au moins l'un des éléments.
Mais je pense que vous avez raison dans ce que nous pouvons retrouver dans un cas où commencer fin + / 2,
début finit par être le même que celui de début + fin / 2,
mais nous n'avons jamais réellement vérifié cet élément.
>> Donc, si nous vérifions d'abord est l'élément central de la valeur que nous recherchons,
alors nous pouvons immédiatement retourner vrai.
Sinon, si ils sont égaux, alors il n'y a pas lieu de poursuivre
puisque nous allons juste mettre à jour au cas où nous sommes sur un tableau à un seul élément.
Si ce seul élément n'est pas celle que nous recherchons,
alors tout est faux. Ouais.
[L'élève] Le fait est que puisque la taille est en fait plus grand que le nombre d'éléments dans le tableau,
il ya déjà un décalage - >> Il en sera de taille -
[L'élève] Dis: si le tableau était de taille 0, alors le SearchHelp sera effectivement vérifier botte de foin de 0
au premier appel.
Le tableau a une taille de 0, de sorte que le 0 est - >> Oui.
Il ya une autre chose qui - il pourrait être bon. Réfléchissons.
Donc, si le tableau avait 10 éléments et celui du milieu que nous allons faire est de vérifier l'index 5,
si nous vérifions 5, et disons que la valeur est inférieure.
Nous sommes donc en jetant tout de suite de 5 en avant.
Donc, commencer à la fin + / 2 va être notre nouveau,
alors oui, il va toujours rester au-delà de la fin du tableau.
Si c'est une affaire si elle était pair ou impair, alors nous vérifions, disons, 4,
mais nous sommes toujours jeter -
Alors oui, la fin est toujours va être au-delà de la fin réelle de la matrice.
Ainsi, les éléments que nous nous concentrons sur la fin est toujours va être celle d'après.
Et donc si le démarrage ne jamais finir égales par ailleurs, nous sommes dans un tableau de taille 0.
>> L'autre chose que je pensais, c'est que nous mettons à jour début à la fin start + / 2,
si c'est le cas que je vais avoir des ennuis avec, d'où partent + fin / 2
est l'élément nous vérifions.
Disons que nous avons eu ce tableau de 10 éléments. Peu importe.
Donc, commencer à la fin + / 2 va être quelque chose comme celui-ci,
et si ce n'est pas la valeur, disons que nous voulons mettre à jour.
La valeur est supérieure, si nous voulons regarder cette moitié du tableau.
Alors, comment nous mettons à jour début, nous mettons à jour début à maintenant cet élément.
Mais cela peut encore travailler, ou à tout le moins, vous pouvez le faire début + fin / 2 + 1.
[L'élève] Vous n'avez pas besoin d'être commencer à la fin + [inaudible] >> Oui.
Nous avons déjà vérifié cet élément et sais que ce n'est pas celui que nous recherchons.
Donc, nous n'avons pas besoin de mettre à jour début pour être cet élément.
Nous ne pouvons tout simplement l'ignorer et mettre à jour commence à être de cet élément.
Et y at-il jamais un cas, disons que ce sont fin,
oui, alors commencer serait cela, démarrez + fin / 2 ne serait-ce,
commencer à la fin + - Ouais, je pense que ça peut se retrouver dans une récursion infinie.
Disons que c'est juste un tableau de taille 2 ou un tableau de taille 1. Je pense que cela va fonctionner.
Donc, actuellement, c'est que l'élément de départ et de fin est de 1 au-delà.
Ainsi, l'élément que nous allons faire est de vérifier celui-ci,
et puis quand nous mettons à jour début, nous mettons à jour début à 0 + 1/2,
qui va nous finir de retour avec départ étant cet élément.
>> Donc, nous vérifions le même élément, encore et encore.
C'est donc le cas où chaque appel récursif doit effectivement mettre à jour quelque chose.
Nous avons donc besoin de faire start + fin / 2 + 1, ou bien il s'agit d'un cas
où nous ne sommes pas réellement la mise à jour de départ.
Tout le monde voit que?
D'accord.
Quelqu'un at-il des questions sur cette solution ou d'autres commentaires?
D'accord. Quelqu'un at-il une solution itérative que nous pouvons tous regarder?
Avons-nous tous le faire de manière récursive?
Ou aussi, je suppose que si vous sienne ouverte, alors vous pourriez avoir annulé le précédent.
Est-ce qu'il enregistre automatiquement? Je ne suis pas positif.
Quelqu'un at-il itérative?
Nous pouvons marcher à travers elle même si elle n'est pas.
L'idée va être la même chose.
Solution itérative.
Nous allons vouloir faire essentiellement la même idée
où nous voulons garder la trace de la nouvelle extrémité de la barrette et le nouveau départ de la matrice
et cela à plusieurs reprises.
Et si ce qu'on garde une trace de que le début et la fin se croisent jamais,
alors nous n'avons pas à le trouver et nous pouvons renvoyer false.
Alors, comment puis-je faire cela? N'importe qui ont des suggestions ou des codes pour me tirer vers le haut?
[L'élève] Faites une boucle while. Ouais >>.
Vous allez avoir à faire une boucle.
>> Avez-vous eu le code que je pouvais tirer vers le haut, ou ce que tu allais à suggérer?
[L'élève] Je pense que oui. Tous droits >>. Cela rend les choses plus faciles. Quel est votre nom?
[L'élève] Lucas.
Révision 1. D'accord.
Low est ce que nous appelons commencer avant.
Up est pas tout à fait ce que nous avons appelé avant la fin.
En fait, la fin est maintenant dans le tableau. C'est un élément que nous devrions prendre en considération.
Si bas, c'est 0, c'est la taille du tableau - 1,
et maintenant nous sommes en boucle, et nous vérifions -
Je suppose que vous pouvez marcher à travers elle.
Quel était votre pensée à travers ce? Nous parcourir votre code.
[L'élève] Bien sûr. Regardez la valeur botte de foin au milieu et le comparer à l'aiguille.
Donc, si elle est supérieure à l'aiguille, alors vous voulez - oh, en fait, ce devrait être à l'envers.
Vous allez avoir à jeter la moitié droite, et alors oui, que devrait être l'inverse.
[Bowden] Donc, cela devrait être moins? Est-ce que vous avez dit? >> [L'élève] Ouais.
[Bowden] D'accord. Moins.
Donc, si ce que nous cherchons est inférieur à ce que nous voulons,
alors oui, nous voulons jeter la moitié gauche,
ce qui signifie que nous mettons à jour tout ce que nous envisageons
en déplaçant bas à droite de la matrice.
Cela semble bon.
Je pense qu'il a le même problème que nous avons dit sur le précédent,
où si faible est 0 et est en hausse de 1, puis bas + haut / 2 va être mis en place pour la même chose.
>> Et même si ce n'est pas le cas, il est encore plus efficace à tout le moins
accepter de perdre l'élément que nous venons d'examiner que nous savons être faux.
Si bas + haut / 2 + 1 - >> [l'élève] Cela devrait être l'inverse.
[Bowden] Ou cela devrait être - 1 et l'autre doit être de + 1.
[L'élève] Et il devrait y avoir un double signe égal. >> [Bowden] Ouais.
[L'élève] Ouais.
D'accord.
Et enfin, maintenant que nous avons ce 1 + - 1 chose,
est-il - il ne serait pas - est-il jamais possible à faible de se retrouver avec une valeur supérieure à neuf?
Je pense que la seule façon qui puisse arriver - Est-il possible? >> [L'élève] Je ne sais pas.
Mais si elle devient tronqué et puis obtient moins que 1, puis - >> Oui.
[L'élève] Il serait peut-être manquant.
Je pense que ça devrait être bon seulement parce que
pour elle de se retrouver plus faible qu'ils doivent être égaux, je pense.
Mais si elles sont égales, alors nous n'aurions pas pu faire la boucle while pour commencer
et nous venons aurait retourné la valeur. Donc, je pense que nous sommes bien maintenant.
Notez que même si ce problème n'est plus récursive,
le même genre d'idées applicables où l'on peut voir comment cela si facilement se prête
à une solution récursive par le fait que nous ne faisons que mettre à jour les indices maintes et maintes fois,
nous faisons le problème plus en plus petits, nous mettons l'accent sur un sous-ensemble du tableau.
[L'élève] Si faible est de 0 et plus est 1, ils seraient tous les deux 0 + 1/2, ce qui irait à 0,
puis on serait + 1, on serait - 1.
[L'élève] Où allons-nous vérifier l'égalité?
Comme si le milieu est en fait l'aiguille?
Nous ne sommes pas en train de faire cela? Oh!
Si C'est -
Oui. Nous ne pouvons pas faire le test ici parce que disons que le milieu en premier -
[L'élève] Il s'agit en fait n'aime pas jeter la borne.
Donc, si vous jetez la limite, il faut d'abord vérifier ou autre.
Ah. Ouais. >> [L'élève] Ouais.
Alors maintenant, nous avons jeté celui que nous avons actuellement regardé,
ce qui signifie que nous avons maintenant besoin d'avoir aussi
if (botte de foin [(bas + haut) / 2] == aiguille), alors on peut retourner la valeur true.
Et si je mets autre ou tout simplement si, il signifie littéralement la même chose
parce que cela aurait renvoyé true.
Donc, je vais mettre d'autre si, mais ce n'est pas grave.
>> Donc, d'autre si cela, sinon cela, et c'est une chose commune que je fais
où même si c'est le cas, où tout est bon ici,
comme faible ne peut jamais être supérieur à toi, c'est pas un raisonnement vaut pour savoir si c'est vrai.
Ainsi, vous pouvez tout aussi bien dire tout bas est inférieur ou égal à
ou alors faible est inférieur à
si elles ne sont jamais égales ou faible qui se passe pour la laisser passer,
alors nous pouvons sortir de cette boucle.
Questions, préoccupations, commentaires?
D'accord. Cela semble bon.
Maintenant, nous voulons faire de tri.
Si nous passons à mon deuxième révision, nous voyons ces mêmes chiffres,
mais maintenant ils ne sont plus dans l'ordre.
Et nous voulons mettre en œuvre trier par n'importe quel algorithme en O de n log n.
Ainsi, l'algorithme pensez-vous que nous devrions mettre en œuvre ici? >> [L'élève] Tri par fusion.
[Bowden] Ouais. Le tri par fusion est en O (n log n), et c'est ce que nous allons faire.
Et le problème va être assez similaire,
où il se prête facilement à une solution récursive.
Nous pouvons également venir avec une solution itérative si l'on veut,
mais la récursivité sera plus facile ici et que nous devrions faire la récursivité.
Je suppose que nous allons traverser tri par fusion d'abord,
bien qu'il y ait une belle vidéo sur le tri par fusion déjà. [Rires]
Ainsi, le tri par fusion il ya - je perds tellement de ce document.
Oh, il n'en reste qu'un.
Donc fusionner.
Oh, 1, 3, 5.
D'accord.
Merge prend deux tableaux distincts.
Individuellement ces deux tableaux sont tous deux classés.
Donc ce tableau, 1, 3, 5, triées. Ce tableau, 0, 2, 4, triées.
Maintenant, ce que la fusion devrait faire est de les combiner en un seul module qui est elle-même triée.
Nous voulons donc un tableau de taille 6 qui va avoir ces éléments à l'intérieur de celui-ci
dans l'ordre.
>> Et afin que nous puissions profiter du fait que ces deux tableaux sont triés
pour ce faire dans un temps linéaire,
sens du temps linéaire si ce tableau est de taille x et y c'est la taille,
alors l'algorithme global doit être O (x + y). D'accord.
Alors suggestions.
[L'élève] Pourrions-nous commencer par la gauche?
Alors vous allez mettre le 0 en bas d'abord, puis le 1, puis là, vous êtes à la 2.
Donc, c'est un peu comme vous avez un onglet qui se déplace vers la droite. >> [Bowden] Ouais.
Pour ces deux tableaux si on se concentre sur l'élément le plus à gauche.
Parce que les deux tableaux sont triés, nous savons que ces 2 éléments
sont les éléments les plus petits dans les deux ensemble.
Cela signifie donc que 1 de ces 2 éléments doivent être le plus petit élément dans notre tableau fusionné.
Il se trouve que le plus petit est celui sur la droite cette fois.
Donc, nous prenons 0, l'insérer sur la gauche, parce que 0 est inférieur à 1,
de sorte que 0, l'insérer dans notre première position, puis nous mettons à jour cette
à concentrer maintenant sur le premier élément.
Et maintenant, nous le répétons.
Alors maintenant, nous comparons 2 et 1. 1 est plus petit, donc nous allons insérer 1.
Nous mettons à jour ce pointeur pour pointer vers ce type.
Maintenant, nous le faisons à nouveau, donc 2. Cela mettra à jour, comparez ces 2, 3.
Cette mise à jour, puis 4 et 5.
Donc, c'est la fusion.
>> Il devrait être assez évident qu'il est temps linéaire, puisque nous venons de traverser chaque élément une fois.
Et c'est le plus grand pas à mettre en œuvre le tri par fusion fait cela.
Et ce n'est pas si dur.
Un couple de choses à s'inquiéter pour est, disons nous étions fusion 1, 2, 3, 4, 5, 6.
Dans ce cas, nous nous retrouvons dans la situation où celui-ci va être plus petit,
puis nous mettons à jour ce pointeur, celui-ci va être plus petit, mettre à jour ce,
celui-ci est plus petit, et maintenant il faut reconnaître
quand vous avez fait fonctionner à partir d'éléments de comparaison.
Comme nous avons déjà utilisé ce tableau entier,
tout dans ce tableau est maintenant venez d'insérer dans ici.
Donc, si jamais nous lancer dans le point où l'un de nos tableaux est déjà complètement fusionné,
alors que nous venons de prendre tous les éléments de l'autre réseau et les insérer dans la fin du tableau.
Afin que nous puissions vous suffit d'insérer 4, 5, 6. D'accord.
C'est une chose à surveiller.
La mise en œuvre qui devrait être l'étape 1.
Fusionner les trier ensuite sur cette base, il est à 2 pas, à 2 pas stupides.
Donnons ce tableau.
Ainsi, le tri par fusion, étape 1 consiste à casser de manière récursive le tableau en deux moitiés.
Donc diviser ce tableau en deux moitiés.
Nous avons maintenant 4, 15, 16, 50 et 8, 23, 42, 108.
Et maintenant nous le faisons à nouveau et nous avons partagé ces en deux moitiés.
Je vais le faire de ce côté.
Donc, 4, 15 et 16, 50.
Nous ferions la même chose ici.
Et maintenant, nous l'avons divisé en deux moitiés à nouveau.
Et nous en avons 4, 15, 16, 50.
Voilà donc notre scénario de base.
Une fois les tableaux sont de taille 1, puis nous nous arrêtons avec la scission en deux moitiés.
>> Maintenant, que faisons-nous avec ça?
Nous finissons ce sera aussi le décomposer en 8, 23, 42, et 108.
Alors, maintenant que nous sommes à ce point, maintenant la deuxième étape de tri par fusion est tout simplement la fusion de paires sur les listes.
Donc, nous voulons fusionner celles-ci. Il suffit d'appeler fusionner.
Nous savons fusion sera de retour ceux-ci dans l'ordre.
4, 15.
Maintenant, nous voulons fusionner ceux-ci, et qui retournera une liste avec ceux de l'ordre de tri,
16, 50.
Nous fusionnons ceux - Je ne peux pas écrire - 8, 23 et 42, 108.
Nous avons donc paires fusionnées fois.
Maintenant que nous venons de fusionner à nouveau.
Notez que chacune de ces listes est triée par lui-même,
et alors nous pouvons simplement fusionner ces listes pour obtenir une liste de taille 4 qui est triée
et de fusionner ces deux listes pour obtenir une liste de taille 4 qui est trié.
Et enfin, nous pouvons fusionner ces deux listes de taille 4 pour obtenir une liste de taille 8 qui est trié.
Donc, pour voir que c'est l'ensemble n log n, nous avons déjà vu que la fusion est linéaire,
alors quand nous avons affaire à fusionner ceux-ci, si semblable au coût global de la fusion
pour ces deux listes est à seulement 2 parce que -
Ou bien, c'est O de n, mais n ici est juste ces 2 éléments, il est donc 2.
Et ces 2 sera 2 et ces 2 sera 2 et ces 2 sera 2,
donc sur l'ensemble des fusions que nous devons faire, nous finissons par faire n.
Comme 2 + 2 + 2 + 2 est 8, qui est n,
de sorte que le coût de la fusion dans cette série est n.
Et puis la même chose ici.
Nous allons fusionner ces 2, alors ces 2 et individuellement cette fusion aura quatre opérations,
Cette fusion aura quatre opérations, mais encore une fois, entre tous ceux-ci,
nous finissent par se confondre n choses ensemble, et si cette étape a n.
Ainsi, chaque niveau a n éléments étant fusionnées.
>> Et combien de niveaux sont-ils?
A chaque niveau, notre gamme augmente de taille 2.
Voici nos tableaux sont de taille 1, ici ils sont de taille 2, ici ils sont de taille 4,
et enfin, ils sont de taille 8.
Donc, puisqu'il est doublé, il va y avoir un total de log n de ces niveaux.
Donc, avec log n niveaux, chaque niveau de l'individu en prenant n l'ensemble des opérations,
nous obtenons un algorithme log n n.
Des questions?
Les gens ont déjà fait des progrès sur la façon de mettre en œuvre?
Quelqu'un est-il déjà dans un état où je peux tirer vers le haut leur code?
Je peux vous donner une minute.
Celui-ci va être plus long.
Je recommande fortement récurrentes -
Vous n'avez pas à faire la récursivité pour fusion
parce que faire la récursivité pour de fusion, vous allez devoir passer un tas de différentes tailles.
Vous pouvez, mais c'est ennuyeux.
Mais la récursivité pour le tri lui-même est assez facile.
Vous avez juste littéralement appeler un tri sur la moitié gauche, en quelque sorte sur la moitié droite. D'accord.
Quelqu'un at-il quelque chose que je peux tirer vers le haut encore?
Ou bien je vais vous donner une minute.
D'accord.
Quelqu'un at-il quelque chose que nous pouvons travailler avec?
Ou bien nous allons travailler avec cette puis développez partir de là.
>> Quelqu'un at-il plus que ce que je peux tirer vers le haut?
[L'élève] Ouais. Vous pouvez tirer vers le haut le mien. Tous droits >>.
Oui!
[L'élève] Il y avait beaucoup de conditions. >> Oh, mince. Pouvez-vous -
[Étudiants] je dois le sauver. Ouais >>.
Donc, nous avons fait la fusion séparément.
Oh, mais ce n'est pas si mal que ça.
D'accord.
Alors tri est lui-même juste appeler mergeSortHelp.
Expliquez-nous ce mergeSortHelp fait.
[L'élève] MergeSortHelp assez fait bien les deux étapes principales,
qui consiste à trier chaque moitié de la matrice, puis à fusionner les deux.
[Bowden] Bon, alors donnez-moi une seconde.
Je pense que c'est - >> [l'élève] J'ai besoin de -
Ouais. Il me manque quelque chose.
En fusion, je me rends compte que j'ai besoin de créer un nouveau tableau
parce que je ne pouvais pas le faire à la place. Oui >>. Vous ne pouvez pas. Corrigez.
[L'élève] Donc je crée un nouveau tableau.
J'ai oublié à la fin de fusionner pour re-changer.
D'accord. Nous avons besoin d'un nouveau tableau.
Dans tri par fusion, ce qui est presque toujours le cas.
Une partie du coût d'un meilleur algorithme en temps-sage
est presque toujours besoin d'utiliser la mémoire un peu plus.
Donc, ici, peu importe comment vous faites le tri par fusion,
Vous ne manquerait pas besoin d'utiliser de la mémoire supplémentaire.
Il ou elle a créé un nouveau tableau.
Et puis vous dire à la fin nous avons juste besoin de copier nouveau tableau dans le tableau original.
[L'élève] Je crois, oui.
Je ne sais pas si cela fonctionne en termes de comptage par référence ou autre -
Ouais, ça va marcher. >> [L'élève] D'accord.
Avez-vous essayé d'exécuter ce? >> [L'élève] Non, pas encore. Ok >>.
Essayez de l'exécuter, et puis je vais en parler pendant une seconde.
[L'élève] J'ai besoin d'avoir tous les prototypes de fonctions et tout, hein?
Les prototypes de fonctions. Oh, tu veux dire comme - Oui.
Trier appelle mergeSortHelp.
>> Donc, pour que sorte d'appeler mergeSortHelp, mergeSortHelp doivent soit avoir été définie
avant de trier ou nous avons juste besoin du prototype. Il suffit de copier et coller cela.
Et de même, mergeSortHelp appelle fusionner,
mais la fusion n'a pas encore été défini, afin que nous puissions laisser savoir mergeSortHelp
que c'est ce qui va fusionner ressembler, et c'est tout.
Donc mergeSortHelp.
Nous avons un problème ici, où nous n'avons pas le cas de base.
MergeSortHelp est récursive, de sorte que toute fonction récursive
va avoir besoin d'une sorte de scénario de base pour savoir quand s'arrêter lui-même récursivement appel.
Quel est notre scénario de base vont être ici? Ouais.
[L'élève] Si la taille est de 1? >> [Bowden] Oui.
Donc, comme nous l'avons vu là, nous nous sommes arrêtés tableaux de fractionnement
une fois arrivés dans des tableaux de taille 1, qui, inévitablement, sont eux-mêmes classés.
Donc, si la taille est égale à 1, nous savons que le tableau est déjà trié,
afin que nous puissions simplement retourner.
>> Notez que c'est vide, donc nous ne retournons pas quelque chose de particulier, nous venons de revenir.
D'accord. Donc, c'est notre scénario de base.
Je suppose que notre scénario de base pourraient également être s'il nous arrive d'être fusionner un tableau de taille 0,
nous voulons probablement s'arrêter à un moment donné,
si nous pouvons simplement dire taille inférieure à 2 ou inférieur ou égal à 1
de telle sorte que cela fonctionne pour n'importe quel ensemble maintenant.
D'accord.
Donc, c'est notre scénario de base.
Maintenant, voulez-vous nous expliquer de fusion?
Qu'est-ce que tous ces arrêts?
Là-haut, nous faisons juste la même idée, le -
[L'élève] J'ai besoin d'être en passant la taille de tous les appels mergeSortHelp.
J'ai ajouté la taille comme un primaire supplémentaire et il n'est pas là, comme la taille / 2.
[Bowden] Oh, la taille / 2, taille / 2. >> [Élève] Oui, et aussi dans la fonction ci-dessus ainsi.
[Bowden] ici? >> [L'élève] Juste taille. >> [Bowden] Oh. Taille, la taille? >> [L'élève] Ouais.
[Bowden] D'accord.
Laissez-moi réfléchir une seconde.
Ne nous nous heurtons à un problème?
Nous sommes toujours à traiter la gauche de 0. >> [L'élève] No.
C'est faux aussi. Désolé. Il devrait être mis en marche. Ouais.
[Bowden] D'accord. J'aime mieux cela.
Et à la fin. D'accord.
Alors maintenant, voulez-vous nous expliquer de fusion? >> [L'élève] D'accord.
Je suis juste marcher à travers ce nouveau tableau que j'ai créé.
Sa taille est la taille de la portion de tableau que nous voulons être triés
et essayer de trouver l'élément que je devrais mettre dans l'étape nouvelle matrice.
Donc, pour ce faire, d'abord je vérifie si la moitié gauche du tableau continue d'avoir des éléments, pas plus,
et si elle n'est pas, alors vous allez vers le bas pour que l'état de chose, qui dit simplement
ok, il doit être dans le tableau de droite, et nous allons le mettre dans l'index actuel de newArray.
>> Et puis sinon, je vérifie si le côté droit du tableau est également terminé,
dans ce cas, je viens de mettre dans la gauche.
C'est peut-être pas vraiment nécessaire. Je ne suis pas sûr.
Mais de toute façon, les deux autres chèques qui des deux sont plus petits dans la gauche ou la droite.
Et aussi, dans chaque cas, je suis d'incrémentation selon placeholder je incrémenter.
[Bowden] D'accord.
Ça a l'air bon.
Quelqu'un at-il des commentaires ou des préoccupations ou des questions?
Ainsi, les quatre cas que nous devons mettre les choses en étant juste - ou il ressemble à cinq -
mais nous devons nous demander si le tableau gauche n'a plus de choses que nous devons fusionner,
si le tableau à droite est à court de choses que nous devons fusionner -
Je signale à rien.
Donc, si le tableau de gauche a plus de choses ou le tableau de droite est à court de choses.
Ce sont deux cas.
Nous devons aussi le cas trivial de savoir si la chose gauche est inférieure à la bonne chose.
Ensuite, nous voulons choisir la bonne chose à gauche.
Ce sont les cas.
Donc, ce fut bien, alors c'est tout.
Tableau gauche. Il est 1, 2, 3. D'accord. Alors oui, ce sont les quatre choses que nous pourrions vouloir faire.
Et nous n'irons pas plus une solution itérative.
Je ne recommanderais pas -
Le tri par fusion est un exemple d'une fonction qui est à la fois non récursive,
il n'est pas facile de le faire récursive,
mais aussi ce n'est pas très facile de le faire itératif.
C'est très facile.
Cette mise en œuvre du tri par fusion,
fusionner, peu importe ce que vous faites, vous allez construire de fusion.
>> Ainsi, le tri par fusion construite au-dessus de fusion est récursivement juste ces trois lignes.
Itérative, il est plus ennuyeux et plus difficile à penser.
Mais remarquez que ce n'est pas récursive terminale car mergeSortHelp - quand il appelle lui-même -
il a encore besoin de faire des choses après ce retour de l'appel récursif.
Donc ce frame de pile doit continuer d'exister même après l'appel de cette.
Et puis, quand vous appelez cela, le cadre de pile doit continuer d'exister
parce que même après cet appel, nous avons encore besoin de fusionner.
Et il n'est pas triviale pour faire de cette récursive.
Des questions?
Très bien.
Pour en revenir à trier - oh, il ya deux choses que je veux montrer. D'accord.
Pour en revenir à trier, nous allons le faire rapidement.
Ou chercher. Trier? Trier. Ouais.
Pour en revenir aux débuts de la sorte.
Nous voulons créer un algorithme qui trie le tableau en utilisant un algorithme
en O de n.
Alors, comment est-ce possible? Quelqu'un at-il un quelconque -
J'ai fait allusion auparavant à -
Si nous sommes sur le point de s'améliorer à partir de n log n O n,
nous avons amélioré notre algorithme en temps-sage,
ce qui signifie que ce que nous allons avoir besoin de faire pour rattraper ça?
[L'élève] Space. Ouais >>. Nous allons utiliser plus d'espace.
Et même pas un peu plus d'espace, c'est l'espace exponentiellement plus.
Je pense donc que ce type d'algorithme est quelque chose de pseudo, polynôme pseudo -
pseudo - je ne me souviens pas. Pseudo quelque chose.
Mais c'est parce que nous avons besoin d'utiliser autant d'espace
que cela est réalisable, mais pas réaliste.
>> Et comment pouvons-nous y parvenir?
Nous pouvons y parvenir si nous garantir que tel ou tel élément dans le tableau
est inférieur à une certaine taille.
Alors disons simplement que la taille est 200,
n'importe quel élément dans un tableau ci-dessous est la taille 200.
Et c'est effectivement très réaliste.
Vous pouvez très facilement avoir un tableau que vous savez tout ce qu'il
sera inférieur à un certain nombre.
Comme si vous avez un certain vecteur absolument massive ou quelque chose
mais vous savez que tout va être comprise entre 0 et 5,
alors ça va être beaucoup plus rapide de faire cela.
Et la borne sur l'un des éléments est 5,
si cette limite, c'est la quantité de mémoire que vous allez utiliser.
Ainsi, la limite est de 200.
En théorie, il ya toujours un bond depuis un entier ne peut atteindre 4 milliards d'euros,
mais ce n'est pas réaliste car alors nous serions en utilisant l'espace
de l'ordre de 4 milliards d'euros. Donc, c'est irréaliste.
Mais ici, nous allons dire que notre limite est de 200.
L'astuce pour le faire en temps O de n est nous faisons un autre tableau appelé compte de la taille BOUND.
Donc en fait, il s'agit d'un raccourci pour - En fait, je ne sais pas si cela Clang.
Mais dans GCC à tout le moins - je Clang en supposant qu'il fait trop -
ce sera juste initialiser le tableau entier soit 0.
Donc, si je ne veux pas le faire, alors je pourrais le faire séparément for (int i = 0;
i <BOUND; i + +) et compte [i] = 0;
Alors maintenant, tout est initialisé à 0.
Je itérer sur mon tableau,
et ce que je fais, c'est que je compte le nombre de chaque - Descendons ici.
Nous disposons de 4, 15, 16, 50, 8, 23, 42, 108.
Qu'est-ce que je compte est le nombre d'occurrences de chacun de ces éléments.
Nous allons effectivement ajouter un couple de plus ici avec quelques répétitions.
Ainsi, la valeur que nous avons ici, la valeur de ce qui se passe à tableau [i].
Donc val pourrait être 4 ou 8 ou autre.
Et maintenant, je compte combien de valeur que j'ai vu,
donc compte [val] + +;
Après cela, les comptages va ressembler à 0001.
Faisons compte [val] - LIÉ + 1.
>> Maintenant, c'est juste pour tenir compte du fait que nous sommes en partant de 0.
Donc, si 200 est va être notre plus grand nombre,
puis de 0 à 200 est de 201 choses.
Donc, compte, ça va ressembler 00001 parce que nous avons un 4.
Ensuite, nous aurons 0001 où nous aurons un 1 dans l'index de comptage 8.
Nous allons avoir un 2 dans l'index 23 de comptage.
Nous aurons un 2 dans l'indice 42e chef d'accusation.
Ainsi, nous pouvons utiliser count.
Donc num_of_item = compte [i].
Et si num_of_item est de 2, cela signifie que nous voulons insérer 2 du nombre i
dans notre tableau trié.
Nous avons donc besoin de garder une trace de combien nous sommes loin dans le tableau.
= Indice So 0.
Array - Je vais l'écrire.
Compteurs -
array [index + +] = i;
Est-ce que je veux? Je pense que c'est ce que je veux.
Oui, ça a l'air bon. D'accord.
Donc tout le monde ne comprends quel est le but de mon tableau compte, c'est?
On compte le nombre d'occurrences de chacun de ces nombres.
Ensuite, je suis itération sur ce tableau compte,
et la position i dans le tableau compte
est le nombre de i est qui doit apparaître dans mon tableau trié.
C'est pourquoi comptaient 4 va être 1
et les décomptes de 8 va être de 1, les dénombrements de 23 va être 2.
C'est comme ça que beaucoup d'entre eux que je veux insérer dans mon tableau trié.
Alors je viens de le faire.
Je suis en insérant num_of_item i est dans mon tableau trié.
>> Des questions?
Et de nouveau, c'est le temps linéaire, puisque nous sommes juste itération sur cette fois,
mais c'est aussi linéaire dans ce nombre se trouve être,
et il dépend fortement de ce que votre limite est.
D'un bond de 200, ce n'est pas si mal que ça.
Si votre borne se passe à 10.000, alors c'est un peu moins bien,
mais si votre limite va être de 4 milliards de dollars, c'est complètement irréaliste
et ce tableau va devoir être de taille 4 milliards de dollars, ce qui est irréaliste.
Donc, c'est tout. Des questions?
[Réponse de l'élève inaudible] >> OK.
J'ai réalisé une autre chose quand nous allions passer.
Je pense que le problème était de Lucas et probablement tous un seul que nous avons vu.
J'ai complètement oublié.
La seule chose que je voulais dire, c'est que lorsque vous avez affaire à des choses comme les indices,
vous n'avez jamais vraiment voir quand vous écrivez une boucle for,
mais techniquement, chaque fois que vous faites affaire avec ces indices,
vous devriez quasiment toujours faire face à des entiers non signés.
La raison à cela est lorsque vous faites affaire avec des entiers signés,
donc si vous avez 2 entiers signés et que vous les additionnez
et ils finissent trop grand, alors vous vous retrouvez avec un nombre négatif.
C'est donc ce que débordement d'entier est.
>> Si j'ajoute 2 milliards et 1 milliard, je me retrouve avec solde négatif de 1 milliard de dollars.
Voilà comment travailler sur des ordinateurs entiers.
Donc, le problème avec l'aide -
C'est très bien, sauf si bas arrive à 2 milliards de dollars et se place à 1 milliard,
alors cela va être négatif 1 milliard et puis nous allons diviser ce par 2
et finissent par un solde négatif de 500 millions.
Donc, c'est un problème que si vous arrive d'être à la recherche à travers un réseau
des milliards de choses.
Mais si + bas arrive à débordement, alors c'est un problème.
Dès que nous les rendre non signé, puis 2 milliards de dollars plus 1 milliard 3 milliards.
3 milliards divisé par 2 est de 1,5 milliards d'euros.
Donc, dès qu'ils sont signés, tout est parfait.
Et donc c'est aussi un problème lorsque vous écrivez votre pour les boucles,
et en fait, il n'est probablement automatiquement.
Il fait juste hurler à vous.
Donc, si ce nombre est trop grand pour être juste un entier, mais il pourrait tenir dans un entier non signé,
il crie après vous, c'est pour ça que vous n'avez jamais vraiment courir sur la question.
Vous pouvez voir que l'indice ne va jamais être négatif,
et donc quand vous itérer sur un tableau,
vous pouvez presque toujours dire unsigned int i, mais vous n'avez pas vraiment besoin.
Les choses vont assez bien pour travailler tout aussi bien.
D'accord. [Chuchote] Quelle heure est-il?
La dernière chose que je voulais montrer - et je vais le faire très rapidement.
Vous savez comment nous avons # define afin que nous puissions # define MAX comme 5 ou quelque chose?
Il ne faut pas faire MAX. # Define LIÉ que 200. C'est ce que nous avons fait avant.
Qui définit une constante, qui va tout simplement être copié et collé
partout où nous nous trouvons pour écrire BOUND.
>> Nous pouvons donc faire plus avec # define.
Nous pouvons définir des fonctions #.
Ils ne sont pas vraiment des fonctions, mais nous les appellerons fonctions.
Un exemple serait quelque chose comme MAX (x, y) est défini par (x <y y: x). D'accord.
Donc, vous devriez être habitué à la syntaxe opérateur ternaire,
mais il est inférieur à y x? Retour y, else return x.
Donc vous pouvez voir que vous pouvez faire cette fonction distincte,
et la fonction pourrait être comme bool MAX prend 2 arguments, retourner ce.
C'est l'un des plus communs que je vois fait comme ça. Nous les appelons les macros.
Il s'agit d'une macro.
C'est juste la syntaxe pour cela.
Vous pouvez écrire une macro pour faire ce que vous voulez.
Vous voyez souvent des macros de débogage printfs et d'autres choses.
Ainsi, un type de printf, il ya des constantes spéciales en C comme Souligné Ligne de soulignement,
2 underscores LINE soulignent,
et il ya aussi, je pense que 2 souligne FUNC. C'est peut-être cela. Quelque chose comme ça.
Ces choses seront remplacés par le nom de la fonction
ou le numéro de la ligne que vous êtes sur.
Souvent, vous écrivez printfs débogage qui ici-bas je pourrais alors simplement écrire
DEBUG et il affichera le numéro de la ligne et de la fonction que je me trouve être en
qu'il a rencontré cette déclaration DEBUG.
Et vous pouvez également imprimer d'autres choses.
Donc, une chose que vous devriez regarder dehors pour est, s'il m'arrive de # define DOUBLE_MAX
quelque chose comme 2 * 2 * y et x.
Donc, pour une raison quelconque, vous arrive de faire beaucoup de choses.
Donc faire une macro.
Il s'agit en fait rompu.
Je voudrais l'appeler par faire quelque chose comme DOUBLE_MAX (3, 6).
Que faudrait-il de retour?
[L'élève] 12.
Oui, 12 doit être retourné, et 12 est renvoyé.
3 sera remplacé par x, 6 sera remplacé par y, et nous retournons 2 * 6, qui est de 12.
Maintenant, qu'en est-il cela? Que faut-il de retour?
[L'élève] 14. Idéalement >>, 14.
Le problème est que la façon dont hachage définit le travail, n'oubliez pas qu'il s'agit d'une copie littérale et coller
d'à peu près tout, donc ce que cela va être interprété comme
est de 3 moins de 1 + 6, 2 fois 1 plus 6, 2 fois 3.
>> Donc, pour cette raison, vous devrez presque toujours envelopper tout entre parenthèses.
Toute variable vous envelopper presque toujours entre parenthèses.
Il ya des cas où vous n'avez pas à, comme je sais que je n'ai pas besoin de le faire ici
parce que moins est à peu près toujours juste aller au travail,
bien que cela pourrait même ne pas être vrai.
S'il ya quelque chose de ridicule comme DOUBLE_MAX (1 == 2),
alors que va se faire remplacée par 3 est égal à moins de 1 est égal à 2,
et oui, alors ça va faire 3 inférieur à 1, est-ce que 2 égal,
ce qui n'est pas ce que nous voulons.
Ainsi, afin d'éviter tout problème de priorité des opérateurs,
toujours envelopper entre parenthèses.
D'accord. Et c'est tout, 5:30.
Si vous avez des questions sur le jeu de processeurs, laissez-nous savoir.
Il doit être un plaisir, et l'édition pirate est aussi beaucoup plus réaliste
que l'édition pirate de l'an dernier, et nous espérons que beaucoup d'entre vous l'essayer.
L'année dernière a été très accablante.
>> [CS50.TV]