1 00:00:00,000 --> 00:00:11,100 >> [Muziek] 2 00:00:11,100 --> 00:00:11,490 >> DAVID J. Malan: Oke. 3 00:00:11,490 --> 00:00:12,170 Dus welkom terug. 4 00:00:12,170 --> 00:00:15,180 Dit is CS50, en het is het einde van de week drie. 5 00:00:15,180 --> 00:00:17,770 >> Dus herinneren in de afgelopen weken, we zijn uitgaven nogal een beetje 6 00:00:17,770 --> 00:00:20,820 tijd op C, op de programmering, op syntax. 7 00:00:20,820 --> 00:00:24,680 En het is heel normaal, als je nog bent worstelen met Probleemverzameling 2, te zijn 8 00:00:24,680 --> 00:00:25,950 bonken met je hoofd tegen de muur. 9 00:00:25,950 --> 00:00:28,310 Het is cryptisch ogende foutmeldingen en bugs die je 10 00:00:28,310 --> 00:00:29,220 kan niet helemaal achterna te zitten. 11 00:00:29,220 --> 00:00:32,310 Want, er zeker van zijn, dat in slechts een tijd enkele weken zult u terugkijken op 12 00:00:32,310 --> 00:00:35,930 dingen zoals Caesar, en [? V-Genair,?] misschien zelfs Crack, en 13 00:00:35,930 --> 00:00:40,050 beseffen hoe ver je bent gekomen in een korte tijd. 14 00:00:40,050 --> 00:00:43,670 Dus als dat een troost, hangen daar voor nu. 15 00:00:43,670 --> 00:00:46,610 >> Vandaag, echter, beginnen we aan de overgang om dingen hoger niveau. 16 00:00:46,610 --> 00:00:49,820 En we beginnen om voor lief nemen dat jullie weten hoe te programmeren, of op 17 00:00:49,820 --> 00:00:52,090 minste het begin van dat comfort niveau. 18 00:00:52,090 --> 00:00:56,520 En we beginnen na te gaan hoe we kunnen gaan over het ontwerpen van programma's meer 19 00:00:56,520 --> 00:00:57,440 effectief. 20 00:00:57,440 --> 00:01:01,090 Hoe we kunnen gaan over het optimaliseren van de efficiency van algoritmes, en 21 00:01:01,090 --> 00:01:03,110 over het algemeen het oplossen van meer interessante problemen. 22 00:01:03,110 --> 00:01:06,850 En beginnen om voor lief nemen dat, als we wilden, konden we coderen up van alle 23 00:01:06,850 --> 00:01:08,350 van de voorbeelden die we in gedachten hebben. 24 00:01:08,350 --> 00:01:11,430 Dus vandaag hebben we niet het toetsenbord aanraken voor enige vorm van code. 25 00:01:11,430 --> 00:01:15,150 Het zal veel hoger niveau, en uiteindelijk, over het oplossen van problemen. 26 00:01:15,150 --> 00:01:20,490 >> Dus om naar dat punt, laat me voorstellen de volgende zeven 27 00:01:20,490 --> 00:01:24,290 rechthoeken geven zeven deuren, achter die een hele hoop van zijn 28 00:01:24,290 --> 00:01:26,340 getallen, waaronder het getal 50. 29 00:01:26,340 --> 00:01:30,470 Laat mij projecteren dit op deze scherm hier ook. 30 00:01:30,470 --> 00:01:36,770 En stel dat we een vrijwilliger om helpen bij het vinden me een aantal voor 31 00:01:36,770 --> 00:01:38,140 het internet hier te zien. 32 00:01:38,140 --> 00:01:40,755 Kom maar naar boven, in de roze. 33 00:01:40,755 --> 00:01:43,050 Oke. 34 00:01:43,050 --> 00:01:43,930 Wat is je naam? 35 00:01:43,930 --> 00:01:44,850 >> JENNIFER: [onverstaanbaar] 36 00:01:44,850 --> 00:01:45,170 >> DAVID J. Malan: Sorry? 37 00:01:45,170 --> 00:01:45,860 >> JENNIFER: Jennifer. 38 00:01:45,860 --> 00:01:46,390 >> DAVID J. Malan: Jennifer. 39 00:01:46,390 --> 00:01:46,980 Oke, Jennifer. 40 00:01:46,980 --> 00:01:47,630 Leuk u te ontmoeten. 41 00:01:47,630 --> 00:01:48,370 Kom maar naar boven. 42 00:01:48,370 --> 00:01:52,430 Dus deze hier zijn zeven deuren, en wat Ik wil graag dat je hier voor ons doen, 43 00:01:52,430 --> 00:01:56,560 voor al je klasgenoten, is het vinden van ons het nummer, 50. 44 00:01:56,560 --> 00:02:00,860 Om een ​​nummer te vinden, kunt u kijkje achter een van deze deuren door simpelweg te tikken 45 00:02:00,860 --> 00:02:03,030 op een van de deuren, en wordt het nummer onthullen. 46 00:02:03,030 --> 00:02:06,080 En laten we zien hoe snel je kunt ons vinden het nummer, 50. 47 00:02:06,080 --> 00:02:09,979 48 00:02:09,979 --> 00:02:11,229 >> 15. 49 00:02:11,229 --> 00:02:13,110 50 00:02:13,110 --> 00:02:14,360 16. 51 00:02:14,360 --> 00:02:16,270 52 00:02:16,270 --> 00:02:16,530 50. 53 00:02:16,530 --> 00:02:17,350 Mooi gedaan. 54 00:02:17,350 --> 00:02:18,040 Oke. 55 00:02:18,040 --> 00:02:19,906 Applaus voor Jennifer. 56 00:02:19,906 --> 00:02:21,530 >> [Applaus] 57 00:02:21,530 --> 00:02:22,320 >> Oke. 58 00:02:22,320 --> 00:02:25,254 Dus wat was uw strategie voor het vinden van het nummer, 50? 59 00:02:25,254 --> 00:02:27,222 >> JENNIFER: Um, ik dacht misschien als - 60 00:02:27,222 --> 00:02:27,714 [Onverstaanbaar] 61 00:02:27,714 --> 00:02:28,206 >> DAVID J. Malan: Oh. 62 00:02:28,206 --> 00:02:29,630 Geef het een seconde. 63 00:02:29,630 --> 00:02:32,420 Dus was uw strategie voor het vinden van het nummer, 50? 64 00:02:32,420 --> 00:02:34,760 >> JENNIFER: Dus ik beginnen bij de beginnen te zien wat het eerste nummer 65 00:02:34,760 --> 00:02:38,590 was, en toen dacht ik, misschien als ze gesorteerd, zal ik gewoon blijven 66 00:02:38,590 --> 00:02:39,970 hogere tikken up? 67 00:02:39,970 --> 00:02:40,140 >> DAVID J. Malan: OK. 68 00:02:40,140 --> 00:02:42,910 En we lijken te hebben gevonden dat voor het geval. 69 00:02:42,910 --> 00:02:45,670 Hoewel, laten we afpellen van de lagen gewoon een beetje, en je wilt gaan 70 00:02:45,670 --> 00:02:47,640 vooruit en onthullen de andere deuren je had kunnen kiezen? 71 00:02:47,640 --> 00:02:50,400 72 00:02:50,400 --> 00:02:51,712 >> JENNIFER: Oh, dear. 73 00:02:51,712 --> 00:02:53,128 >> DAVID J. Malan: Ah. 74 00:02:53,128 --> 00:02:54,280 >> JENNIFER: Dus ik heb gewoon geluk gehad. 75 00:02:54,280 --> 00:02:55,270 >> DAVID J. Malan: Dus je hebt geluk. 76 00:02:55,270 --> 00:02:55,710 Oke. 77 00:02:55,710 --> 00:02:56,795 Dus niet slecht. 78 00:02:56,795 --> 00:02:58,750 Maar dat is een interessante inzicht, toch? 79 00:02:58,750 --> 00:03:01,870 Als je aangenomen, en je kreeg, inderdaad, een beetje geluk daar. 80 00:03:01,870 --> 00:03:05,350 Maar als je aangenomen dat de aantallen waren gesorteerd, kunt u preciezer 81 00:03:05,350 --> 00:03:08,750 hoe die beïnvloed je gedrag? 82 00:03:08,750 --> 00:03:11,715 >> JENNIFER: Dus als ze gesorteerd waren, ik dacht misschien klein naar groot. 83 00:03:11,715 --> 00:03:11,970 >> DAVID J. Malan: OK. 84 00:03:11,970 --> 00:03:15,260 >> JENNIFER: Of als deze eindigde als echt groot, dan is groot naar klein. 85 00:03:15,260 --> 00:03:15,540 >> DAVID J. Malan: OK. 86 00:03:15,540 --> 00:03:18,170 Zo groot naar klein, of kleinste tot de grootste. 87 00:03:18,170 --> 00:03:21,990 Maar laat me stellen, stel dat je had gekregen pech, en veronderstellen dat zij 88 00:03:21,990 --> 00:03:26,840 niet, in feite, gesorteerd, hoeveel die deuren zou je hebt gehad te gluren 89 00:03:26,840 --> 00:03:28,590 achter in dat ergste geval? 90 00:03:28,590 --> 00:03:29,860 >> JENNIFER: Allemaal. 91 00:03:29,860 --> 00:03:30,420 >> DAVID J. Malan: Allemaal. 92 00:03:30,420 --> 00:03:31,740 Dus laten we generaliseren dat als n. 93 00:03:31,740 --> 00:03:34,790 Er gebeurt te zijn 7, maar laten we meer over het algemeen zeggen dat er is n deuren op de 94 00:03:34,790 --> 00:03:35,650 scherm hier. 95 00:03:35,650 --> 00:03:40,110 Dus in het ergste geval, zou je moeten om een ​​kijkje achter 7 deuren, of n deuren. 96 00:03:40,110 --> 00:03:44,140 En dus dit is echt, het is een beetje geluk vandaag, maar het is echt een lineaire 97 00:03:44,140 --> 00:03:46,440 algoritme van soorten, ook al heb je waren soort overslaan rond. 98 00:03:46,440 --> 00:03:47,080 Is dat eerlijk? 99 00:03:47,080 --> 00:03:47,500 >> JENNIFER: Yeah. 100 00:03:47,500 --> 00:03:50,000 >> DAVID J. MALAN: Nou, laat me zien of uw strategie verandert als ik ons ​​om te verhuizen 101 00:03:50,000 --> 00:03:52,190 onze tweede voorbeeld hier met 7 verschillende deuren. 102 00:03:52,190 --> 00:03:55,240 Dezelfde nummers, maar moment dat ze worden gesorteerd. 103 00:03:55,240 --> 00:03:58,350 Wat is uw strategie hier gaat worden, proberen te zetten van je geest wat 104 00:03:58,350 --> 00:03:59,310 de andere nummers waren - 105 00:03:59,310 --> 00:03:59,930 >> JENNIFER: OK. 106 00:03:59,930 --> 00:04:02,290 >> DAVID J. Malan: - eerder? 107 00:04:02,290 --> 00:04:03,180 >> JENNIFER: Laten we beginnen met de eerste. 108 00:04:03,180 --> 00:04:03,540 >> DAVID J. Malan: Oke. 109 00:04:03,540 --> 00:04:05,190 Beginnen met de eerste. 110 00:04:05,190 --> 00:04:05,960 4. 111 00:04:05,960 --> 00:04:08,810 Nu waar je heen te gaan, en waarom? 112 00:04:08,810 --> 00:04:10,040 >> JENNIFER: 4 is echt klein. 113 00:04:10,040 --> 00:04:12,500 Dus als ze sorteren misschien kleinste het grootste, het moet 114 00:04:12,500 --> 00:04:13,290 twee keer dat en -. 115 00:04:13,290 --> 00:04:13,670 >> DAVID J. Malan: OK. 116 00:04:13,670 --> 00:04:15,990 Laten we eens kijken, wat je denkt? 117 00:04:15,990 --> 00:04:19,050 >> JENNIFER: Probeer de laatste. 118 00:04:19,050 --> 00:04:19,500 Leuk. 119 00:04:19,500 --> 00:04:20,880 >> DAVID J. Malan: Zeer mooi gedaan. 120 00:04:20,880 --> 00:04:21,860 Oke. 121 00:04:21,860 --> 00:04:23,010 >> [Applaus] 122 00:04:23,010 --> 00:04:24,310 >> DAVID J. Malan: OK. 123 00:04:24,310 --> 00:04:26,790 Dus je bent eigenlijk dit doen verschrikkelijk, want je bent 124 00:04:26,790 --> 00:04:27,700 doet het heel goed. 125 00:04:27,700 --> 00:04:31,150 Die laat ons niet in staat om maken bepaalde punten. 126 00:04:31,150 --> 00:04:32,565 Dus laten we proberen om hier terug te rollen. 127 00:04:32,565 --> 00:04:34,560 >> JENNIFER: OK. 128 00:04:34,560 --> 00:04:35,980 >> DAVID J. Malan: Zeer goed gedaan, toch. 129 00:04:35,980 --> 00:04:39,060 Dus je begon bij het begin, je zag dat het 4, dan heb je 130 00:04:39,060 --> 00:04:40,240 verplaatst naar het einde. 131 00:04:40,240 --> 00:04:42,320 Maar stel dat je niet krijgen geluk daar, en veronderstellen 50 132 00:04:42,320 --> 00:04:42,890 ergens anders was. 133 00:04:42,890 --> 00:04:46,190 Wat uw derde stap zijn geweest? 134 00:04:46,190 --> 00:04:47,680 >> JENNIFER: Ga terug naar het begin. 135 00:04:47,680 --> 00:04:48,320 >> DAVID J. Malan: Ga terug aan het begin. 136 00:04:48,320 --> 00:04:51,320 OK, dus je zou hebben aangeraakt deze deur, die was 8. 137 00:04:51,320 --> 00:04:51,660 Oke. 138 00:04:51,660 --> 00:04:52,650 Dus dat is niet 50. 139 00:04:52,650 --> 00:04:55,380 Waar zou u de volgende keer hebt gekeken? 140 00:04:55,380 --> 00:04:56,720 >> JENNIFER: Als ik niet weten ze losten. 141 00:04:56,720 --> 00:04:57,005 >> DAVID J. Malan: Correct. 142 00:04:57,005 --> 00:04:58,490 Nou, als je dat deed weet ze gesorteerd - 143 00:04:58,490 --> 00:04:58,700 >> JENNIFER: Oh, wist, ja. 144 00:04:58,700 --> 00:05:00,910 >> DAVID J. Malan: - maar je deed niet weet nog niet waar 50 was? 145 00:05:00,910 --> 00:05:01,785 >> JENNIFER: Gewoon doorgaan. 146 00:05:01,785 --> 00:05:02,130 >> DAVID J. Malan: Oke. 147 00:05:02,130 --> 00:05:02,520 OK. 148 00:05:02,520 --> 00:05:03,800 Blijven gaan. 149 00:05:03,800 --> 00:05:05,270 OK, dat ik kan werken. 150 00:05:05,270 --> 00:05:05,610 >> JENNIFER: OK. 151 00:05:05,610 --> 00:05:07,210 >> DAVID J. MALAN: Nu, als je gewoon gaan om door te gaan, wat is uw 152 00:05:07,210 --> 00:05:09,680 algoritme delegeren gesteund in. 153 00:05:09,680 --> 00:05:10,740 >> JENNIFER: De lineaire -. 154 00:05:10,740 --> 00:05:11,820 >> DAVID J. Malan: Het is soort van lineair. 155 00:05:11,820 --> 00:05:13,480 Maar laat me voorstellen, laat me voor het blok gezet. 156 00:05:13,480 --> 00:05:14,900 Laat ik vernieuw de pagina. 157 00:05:14,900 --> 00:05:17,120 hetzelfde nummer, dezelfde opstelling, Dezelfde deuren. 158 00:05:17,120 --> 00:05:21,350 Maar denk terug aan die eerste dag in klas toen we scheurde een telefoonboek in 159 00:05:21,350 --> 00:05:25,480 helft, soort van, en wat was onze strategie daar? 160 00:05:25,480 --> 00:05:26,450 >> JENNIFER: Begin bij het midden. 161 00:05:26,450 --> 00:05:26,690 >> DAVID J. Malan: OK. 162 00:05:26,690 --> 00:05:27,610 Dus beginnen bij het midden. 163 00:05:27,610 --> 00:05:28,790 Dus laten we verder gaan en simuleren dat. 164 00:05:28,790 --> 00:05:30,720 Begin in het midden van onthullend die deur. 165 00:05:30,720 --> 00:05:31,660 Dus het nummer 16. 166 00:05:31,660 --> 00:05:35,290 Dus wat zou de sterke man hebben gedaan, wie het telefoonboek scheurde in tweeën, 167 00:05:35,290 --> 00:05:38,450 om naar de volgende gok? 168 00:05:38,450 --> 00:05:39,400 >> JENNIFER: Ga heen in deze helft. 169 00:05:39,400 --> 00:05:41,700 >> DAVID J. Malan: En waarom naar rechts? 170 00:05:41,700 --> 00:05:43,900 >> JENNIFER: Als ze soort van kleinste het grootste, dan 50 moet 171 00:05:43,900 --> 00:05:44,720 aan dat uiteinde. 172 00:05:44,720 --> 00:05:44,920 >> DAVID J. Malan: Good. 173 00:05:44,920 --> 00:05:45,390 Volstrekt redelijk. 174 00:05:45,390 --> 00:05:48,380 Dus als een telefoonboek, ga je naar de recht tegenover links, maar hier 175 00:05:48,380 --> 00:05:49,500 is de sleutel mee te nemen. 176 00:05:49,500 --> 00:05:53,930 U kunt nu weggooien, of scheuren, helft van dit probleem, zodat u niet 177 00:05:53,930 --> 00:05:55,970 met 7 deuren, maar echt met slechts 3. 178 00:05:55,970 --> 00:05:57,870 Dat is ongeveer de helft van de grootte van het probleem. 179 00:05:57,870 --> 00:05:58,350 Oke. 180 00:05:58,350 --> 00:06:01,890 Dus nu wat je zou moeten gedaan nadat je goed gaan? 181 00:06:01,890 --> 00:06:05,870 >> JENNIFER: Dus 16 is nog vrij klein, ten opzichte van 50, dus misschien zal ik proberen, 182 00:06:05,870 --> 00:06:06,700 zoals, deze. 183 00:06:06,700 --> 00:06:07,890 >> DAVID J. Malan: Oke. 184 00:06:07,890 --> 00:06:08,720 42. 185 00:06:08,720 --> 00:06:10,830 Oke, dus nu wat is uw instinct vertelt je? 186 00:06:10,830 --> 00:06:12,100 >> JENNIFER: Ik kan weggooien dit en dan gewoon - 187 00:06:12,100 --> 00:06:12,360 >> DAVID J. Malan: OK. 188 00:06:12,360 --> 00:06:14,212 Goed, je kunt weggooien de linkerhelft daar. 189 00:06:14,212 --> 00:06:14,890 >> JENNIFER: - kies deze. 190 00:06:14,890 --> 00:06:15,530 >> DAVID J. Malan: En de rechter. 191 00:06:15,530 --> 00:06:15,760 >> JENNIFER: Yeah. 192 00:06:15,760 --> 00:06:17,820 >> DAVID J. Malan: Dus ook al is het moeilijk tot misschien zien, als er alleen 193 00:06:17,820 --> 00:06:21,320 7 deuren, denken, nu, de consistentie van de 194 00:06:21,320 --> 00:06:22,620 -algoritme je gewoon toegepast. 195 00:06:22,620 --> 00:06:24,510 In het vorige geval, je deed geluk, wat geweldig was. 196 00:06:24,510 --> 00:06:26,540 Maar je hebt gebruikt een heuristische, Ik zou zeggen. 197 00:06:26,540 --> 00:06:29,150 Je gebruikte soort van je instincten, en weten gesorteerd, als het is vrij 198 00:06:29,150 --> 00:06:31,600 klein in het begin, natuurlijk, we hebben moet meer naar rechts. 199 00:06:31,600 --> 00:06:34,990 Maar in zekere zin, heb je geluk, want misschien was dit het nummer 100, 200 00:06:34,990 --> 00:06:36,220 en misschien 50 was meer in het midden. 201 00:06:36,220 --> 00:06:37,910 Misschien 50 was zelfs hier. 202 00:06:37,910 --> 00:06:40,960 >> Maar wat je anders een beetje deed deze keer was, je hetzelfde deed 203 00:06:40,960 --> 00:06:42,150 weer. 204 00:06:42,150 --> 00:06:45,310 En ik zou zeggen dat wat je net heeft, hoewel beïnvloed door de telefoon 205 00:06:45,310 --> 00:06:48,100 boek bijvoorbeeld, is iets veel meer algoritmische, en veel 206 00:06:48,100 --> 00:06:49,930 minder bijzonder ingesloten. 207 00:06:49,930 --> 00:06:51,620 Veel minder instinctief. 208 00:06:51,620 --> 00:06:57,160 Dus in het einde van de dag, hoe zou u de efficiëntie van de beschreven 209 00:06:57,160 --> 00:07:00,530 eerste algoritme, waar je ging links naar rechts ten opzichte van de 210 00:07:00,530 --> 00:07:03,430 tweede algoritme hier? 211 00:07:03,430 --> 00:07:06,460 >> JENNIFER: Dit moet men, net als, misschien halveren van de tijd, of zelfs meer, ja. 212 00:07:06,460 --> 00:07:07,320 >> DAVID J. MALAN: OK, misschien zelfs meer. 213 00:07:07,320 --> 00:07:10,150 Laten we duwen een beetje harder op dat. 214 00:07:10,150 --> 00:07:13,030 Wat echt, als we dit voortzetten logica, we zeker gehalveerd het 215 00:07:13,030 --> 00:07:15,830 lopende tijd met dit tweede algoritme door het weggooien van de helft van de 216 00:07:15,830 --> 00:07:18,470 getallen, maar wat hebben we gedaan op de volgende iteratie, wanneer Jennifer onthulde 217 00:07:18,470 --> 00:07:20,615 het tweede nummer? 218 00:07:20,615 --> 00:07:22,830 >> We halveerde het aantal deuren weer. 219 00:07:22,830 --> 00:07:25,270 En wat hebben we gedaan na dat, indien er waren meer deuren te spelen? 220 00:07:25,270 --> 00:07:27,520 We zouden hen halveren, en opnieuw, en opnieuw, en opnieuw. 221 00:07:27,520 --> 00:07:30,420 En dit was net als jullie allemaal staan ​​in de eerste week van 222 00:07:30,420 --> 00:07:33,000 klasse, de helft van je zitten, de helft van je zitten, de helft van je 223 00:07:33,000 --> 00:07:35,440 zitten, totdat een eenzame ziel stond. 224 00:07:35,440 --> 00:07:39,050 En we zeiden dat de looptijd van de dat, het aantal stappen duurde het was 225 00:07:39,050 --> 00:07:40,430 in de orde van wat? 226 00:07:40,430 --> 00:07:41,230 >> LUIDSPREKER 1: [onverstaanbaar] 227 00:07:41,230 --> 00:07:43,970 >> DAVID J. Malan: Dus log basis 2 van n, of gewoon meer gewoon, log van n. 228 00:07:43,970 --> 00:07:45,060 Zo iets logaritmische. 229 00:07:45,060 --> 00:07:48,380 En de grafiek is geen rechte lijn die net erger en erger, het was 230 00:07:48,380 --> 00:07:52,490 deze interessante curve die dat niet deden krijg zo slecht in de tijd. 231 00:07:52,490 --> 00:07:53,910 Dus laten we vasthouden aan dit idee. 232 00:07:53,910 --> 00:07:54,690 Laten we danken Jennifer. 233 00:07:54,690 --> 00:07:56,150 Hartelijk dank voor uw komst op maximaal. 234 00:07:56,150 --> 00:07:57,400 En, een sec. 235 00:07:57,400 --> 00:08:00,170 236 00:08:00,170 --> 00:08:02,925 Geen bureaulampen vandaag, maar we hebben CS50 stress ballen. 237 00:08:02,925 --> 00:08:03,420 >> JENNIFER: Yay. 238 00:08:03,420 --> 00:08:04,410 >> DAVID J. Malan: Oke, hier. 239 00:08:04,410 --> 00:08:06,545 Dank u voor het aangaan van de stress hier boven. 240 00:08:06,545 --> 00:08:07,350 Oke. 241 00:08:07,350 --> 00:08:10,620 Dus laten we kijken of we kunnen nu niet formaliseren dit een beetje meer. 242 00:08:10,620 --> 00:08:14,820 Dus nogmaals, wat we net deden was in wezen hetzelfde als we deden 243 00:08:14,820 --> 00:08:16,660 in die eerste week. 244 00:08:16,660 --> 00:08:23,780 Maar eerder dan eind met slechts een lineaire algoritme dat we afgebeeld 245 00:08:23,780 --> 00:08:27,210 eerder als deze rechte lijn, waarbij, als we nog een deur aan 246 00:08:27,210 --> 00:08:29,610 het scherm en Jennifer zou hebben gehad om te kijken, potentieel, 247 00:08:29,610 --> 00:08:30,600 achter nog een deur. 248 00:08:30,600 --> 00:08:33,490 Als we nog twee deuren, zou ze hebben naar achter kijken nog twee deuren. 249 00:08:33,490 --> 00:08:35,990 >> En ja, er was deze lineaire relatie tussen de grootte van de 250 00:08:35,990 --> 00:08:39,059 probleem, bijvoorbeeld de x-as, en de hoeveelheid tijd die het kost om 251 00:08:39,059 --> 00:08:40,440 lossen op de y. 252 00:08:40,440 --> 00:08:43,330 Maar het beeld dat ik werd gezinspeeld op eerder was deze groene lijn. 253 00:08:43,330 --> 00:08:45,970 Groene opzet, omdat het voelde gewoon beter. 254 00:08:45,970 --> 00:08:49,790 In theorie, het algoritme, toen we deden het met het telefoonboek, toen we deden het 255 00:08:49,790 --> 00:08:52,420 met jullie tellen van elkaar, en in het tweede geval, wanneer Jennifer net 256 00:08:52,420 --> 00:08:55,250 deed het hier, het was een soort van fundamenteel beter. 257 00:08:55,250 --> 00:08:57,180 Want het was niet alleen twee keer zo snel. 258 00:08:57,180 --> 00:08:58,870 Het was zelfs vier maal zo snel. 259 00:08:58,870 --> 00:09:03,290 Het was volledig afhankelijk van wat de grootte van de ingang was, aan hoeveel 260 00:09:03,290 --> 00:09:05,220 stappen het uiteindelijk duurde. 261 00:09:05,220 --> 00:09:08,040 >> En dus dit eenvoudige idee dat we alle namen voor verleend met het telefoonboek, 262 00:09:08,040 --> 00:09:10,200 kunnen eveneens worden toegepast om iets als dit. 263 00:09:10,200 --> 00:09:12,380 En dit zou meer terloops zijn bekend als, zoals je misschien 264 00:09:12,380 --> 00:09:13,940 stel, verdeel en heers. 265 00:09:13,940 --> 00:09:16,390 Niet in tegenstelling tot wat we gedaan hebben, natuurlijk, met het telefoonboek. 266 00:09:16,390 --> 00:09:18,300 >> Maar de pseudocode, rappel, was dit. 267 00:09:18,300 --> 00:09:21,800 Zodat we niet weer doen, maar herinneren die eerste week, van ons allemaal opgestaan 268 00:09:21,800 --> 00:09:25,140 en dan de helft van je ging zitten, de helft van je ging zitten, de helft van je ging zitten. 269 00:09:25,140 --> 00:09:29,280 Dit algoritme is in een uitvoering beetje een vals manier, in dat, het 270 00:09:29,280 --> 00:09:32,870 was niet alleen een van mij tellen, fundamenteel, efficiënter. 271 00:09:32,870 --> 00:09:35,830 In dat geval werd ik hefboomwerking een secundaire bron. 272 00:09:35,830 --> 00:09:39,470 Soort, meerdere CPU's, meerdere hersenen, meerdere slimme mensen in de 273 00:09:39,470 --> 00:09:42,740 kamer hielpen me van iets lineaire iets 274 00:09:42,740 --> 00:09:45,190 logaritmische, van iets rood naar iets groens. 275 00:09:45,190 --> 00:09:48,650 >> Maar in dit geval, Jennifer alleen kan fundamenteel verbeteren van de 276 00:09:48,650 --> 00:09:52,370 prestaties van haar eerste algoritme door, nogmaals, net te denken een beetje harder. 277 00:09:52,370 --> 00:09:56,650 En nu, wanneer het tijd is om te implementeren deze dingen, uitzoeken 278 00:09:56,650 --> 00:10:00,670 welke regels code u dergelijke kan schrijven dat u ze weer kunt herhalen, en 279 00:10:00,670 --> 00:10:03,350 opnieuw, en opnieuw, soort in een looping mode. 280 00:10:03,350 --> 00:10:06,370 Want je bent niet van plan om het hebben luxe, net als Jennifer deed in eerste instantie, om 281 00:10:06,370 --> 00:10:10,460 gewoon een hele hoop mitsen en zeggen: hmm, als dit eerste getal is 4, 282 00:10:10,460 --> 00:10:11,800 laat me springen helemaal tot het einde. 283 00:10:11,800 --> 00:10:14,180 Ooh, als dat aantal is te groot, laat me willekeurig terug te gaan 284 00:10:14,180 --> 00:10:15,220 het tweede element. 285 00:10:15,220 --> 00:10:18,210 Je zult zien dat het gaat om een ​​stuk te zijn moeilijker te formaliseren wat wij mensen 286 00:10:18,210 --> 00:10:21,270 voor lief nemen als zeer redelijk heuristiek, maar een computer is slechts 287 00:10:21,270 --> 00:10:23,260 gaat doen wat je hem vertelt wat te doen. 288 00:10:23,260 --> 00:10:25,280 >> Nu heeft deze zeer interessante implicaties. 289 00:10:25,280 --> 00:10:29,950 Deze grafiek is soort bedoeld om een ​​soort van overweldigen visueel, maar mededeling, waar 290 00:10:29,950 --> 00:10:32,230 is de rechte lijn in deze grafiek? 291 00:10:32,230 --> 00:10:35,330 Waar is de lineaire grafiek dat noemen we n? 292 00:10:35,330 --> 00:10:37,580 Nou, het is een soort van naar de onderkant van deze foto, toch? 293 00:10:37,580 --> 00:10:40,500 Dus alles wat we hebben gedaan is we hebben soort van hebt om de x-as en de 294 00:10:40,500 --> 00:10:44,780 y-as om te proberen een gevoel van wat krijgen andere soorten bochten eruit. 295 00:10:44,780 --> 00:10:47,760 >> En de details van de wiskundige uitdrukkingen vandaag zal niet zo toe 296 00:10:47,760 --> 00:10:52,440 veel, maar merken dat er veel algoritmen die zijn veel erger dan 297 00:10:52,440 --> 00:10:53,470 iets dat lineair. 298 00:10:53,470 --> 00:10:55,410 Inderdaad, n blokjes ziet er vrij slecht. 299 00:10:55,410 --> 00:10:58,400 2 tot de n ziet er vrij slecht. n kwadraat ziet er vrij slecht. 300 00:10:58,400 --> 00:11:01,630 En we zullen zien wat sommige van die misschien wel in de werkelijkheid van vandaag. 301 00:11:01,630 --> 00:11:05,430 En log n voelt zich niet zo slecht, maar beter dan n log basis van 2 n. 302 00:11:05,430 --> 00:11:08,080 Maar weet je, het zou zijn zelfs meer verbazingwekkend als Jennifer, of als we, 303 00:11:08,080 --> 00:11:12,910 die eerste week, was met gekomen iets dat log van log van n. 304 00:11:12,910 --> 00:11:15,880 >> Dus met andere woorden, er is een hele scala aan mogelijke oplossingen voor 305 00:11:15,880 --> 00:11:18,570 problemen, maar zelfs hier, bericht wat er gaat gebeuren. 306 00:11:18,570 --> 00:11:22,910 Toen ik uit te zoomen, welke van deze curven zal blijken te zijn de absolute 307 00:11:22,910 --> 00:11:26,630 ergste van degenen die op het scherm nu? 308 00:11:26,630 --> 00:11:28,680 Zo n blokjes ziet er vrij slecht op het moment. 309 00:11:28,680 --> 00:11:32,470 Maar als we uitzoomen en zie meer van de x en de y-as, wie gaat 310 00:11:32,470 --> 00:11:34,550 domineren uiteindelijk? 311 00:11:34,550 --> 00:11:37,120 Zodat het eigenlijk blijkt dat 2 de n, en u kunt dit uit door gewoon 312 00:11:37,120 --> 00:11:39,990 inpluggen in een aantal steeds groter nummers, en je zult zien dat 2 op de 313 00:11:39,990 --> 00:11:42,070 n inderdaad groter wordt veel sneller. 314 00:11:42,070 --> 00:11:45,530 Als we echt uit te zoomen, een 2 om de n algoritme absoluut zuigt. 315 00:11:45,530 --> 00:11:48,170 Ik bedoel dit gaat duren heel wat tijd voor de 316 00:11:48,170 --> 00:11:49,460 computer om churn door. 317 00:11:49,460 --> 00:11:52,500 >> Maar je zult zien in de tijd, met name met toekomstige probleem sets en zelfs 318 00:11:52,500 --> 00:11:55,600 afstudeerprojecten, is uw gegevens set krijgt grote, oke? 319 00:11:55,600 --> 00:11:58,300 Zelfs in de eerste versie van Facebook, als het aantal vrienden, en de 320 00:11:58,300 --> 00:12:01,840 aantal geregistreerde gebruikers heeft grote, u kunt sorteren van de telefoon in en 321 00:12:01,840 --> 00:12:05,530 implementeren iets met lineaire zoeken, of een zeer eenvoudige sortering 322 00:12:05,530 --> 00:12:07,030 algoritme, zoals we zullen zien vandaag. 323 00:12:07,030 --> 00:12:09,280 Je moet gaan denken harder en harder over deze problemen. 324 00:12:09,280 --> 00:12:12,070 En de aard van de problemen plaatsen als Facebook en Google en Microsoft, 325 00:12:12,070 --> 00:12:16,350 en anderen werken aan precies deze soort van big data soort vragen 326 00:12:16,350 --> 00:12:18,530 steeds meer van deze dagen. 327 00:12:18,530 --> 00:12:18,900 >> Oke. 328 00:12:18,900 --> 00:12:23,800 Dus succes van Jennifer's in die tweede algoritme, eerlijk gezegd, deed ze verbazingwekkend 329 00:12:23,800 --> 00:12:26,110 ook de eerste keer, maar laten we schrijf het uit als geluk, zodat we 330 00:12:26,110 --> 00:12:27,000 kan dit punt te maken. 331 00:12:27,000 --> 00:12:30,970 In het tweede geval, ze leveraged een algoritme dat nog eens herhaald en 332 00:12:30,970 --> 00:12:34,670 weer, maar ze nam voor verleend een bepaalde veronderstelling dat we mogen 333 00:12:34,670 --> 00:12:39,370 haar, maar ze uitgebuit enig detail de tweede keer dat ze niet over de 334 00:12:39,370 --> 00:12:39,840 eerste keer. 335 00:12:39,840 --> 00:12:41,800 Die was wat? 336 00:12:41,800 --> 00:12:43,050 >> Dat de lijst gesorteerd was. 337 00:12:43,050 --> 00:12:46,350 Dus zodra de lijst gesorteerd was, we beweren dat Jennifer in staat was om te doen 338 00:12:46,350 --> 00:12:47,480 fundamenteel beter. 339 00:12:47,480 --> 00:12:51,450 7 deuren, ja, is dat niet interessant, maar veronderstel dat we zijn 7 miljoen deuren. 340 00:12:51,450 --> 00:12:54,080 Logboek van n is zeker gaat te veel, veel te voeren 341 00:12:54,080 --> 00:12:55,610 sneller op de lange termijn. 342 00:12:55,610 --> 00:12:58,880 Maar ze moest het hebben deuren gesorteerd voor haar. 343 00:12:58,880 --> 00:13:02,320 Nu, nam ik de vrijheid om dat te doen vooraf op het computerscherm 344 00:13:02,320 --> 00:13:05,160 hier, maar stel dat Jennifer moest dat zelf doen? 345 00:13:05,160 --> 00:13:10,120 Stel dat de deuren betrokken vertegenwoordigd gegevens in een database, of 346 00:13:10,120 --> 00:13:14,260 vrienden geregistreerd voor Facebook, of alle webpagina's op het internet die 347 00:13:14,260 --> 00:13:16,880 verschillende websites zou kunnen hebben te indexeren of zoek voorbij. 348 00:13:16,880 --> 00:13:20,940 >> Stel dat je net een ruwe data ingesteld en werd het aan u, of om 349 00:13:20,940 --> 00:13:23,010 Jennifer dat sortering doen? 350 00:13:23,010 --> 00:13:26,950 Dat, in plaats van, vereist dat we beantwoorden de vraag, nou ja, hoeveel tijd 351 00:13:26,950 --> 00:13:31,080 zou Jennifer, of zelfs mij, hebben genomen om die nummers te sorteren op voorhand, zodat 352 00:13:31,080 --> 00:13:32,680 dat ze konden profiteren van dat? 353 00:13:32,680 --> 00:13:32,880 Rechts? 354 00:13:32,880 --> 00:13:36,620 Omdat de implicatie, natuurlijk als het duurt me een tijdje om te sorteren 355 00:13:36,620 --> 00:13:40,800 de cijfers, die de heck cares dat u kan een getal als 50 vinden zo snel, 356 00:13:40,800 --> 00:13:44,850 zoals in het geval Jennifer, indien we meer dan overweldigd het bedrag van de totale tijd 357 00:13:44,850 --> 00:13:46,920 het duurde door het sorteren dingen op voorhand? 358 00:13:46,920 --> 00:13:49,320 >> Dus laten we kijken of we kunnen niet de verf hier de foto. 359 00:13:49,320 --> 00:13:51,370 Ik heb een hele hoop meer spanning ballen, als dat helpt 360 00:13:51,370 --> 00:13:52,270 het ijs te breken hier. 361 00:13:52,270 --> 00:13:55,690 En als je het niet erg zou vinden, we moet zeven vrijwilliger - 362 00:13:55,690 --> 00:13:57,060 op, OK. 363 00:13:57,060 --> 00:13:57,240 Wow. 364 00:13:57,240 --> 00:13:59,250 Zodat we niet hoeven te besteden op bureaulampen, lijkt het. 365 00:13:59,250 --> 00:13:59,690 Oke. 366 00:13:59,690 --> 00:14:01,530 Dus hoe zit je twee aan de voorkant. 367 00:14:01,530 --> 00:14:04,160 Hoe zit het met jullie twee aan de achterkant. 368 00:14:04,160 --> 00:14:04,870 Dus dat is vier. 369 00:14:04,870 --> 00:14:09,890 Hoe zit je aan de voorkant vijf, zes en zeven. 370 00:14:09,890 --> 00:14:10,320 Daar. 371 00:14:10,320 --> 00:14:13,260 Je vriend heeft wijzen je uit, dus je krijgt de prijs. 372 00:14:13,260 --> 00:14:13,700 >> Oke. 373 00:14:13,700 --> 00:14:14,410 Kom maar naar boven. 374 00:14:14,410 --> 00:14:17,120 En waarom niet wij u jongens kom eens hier. 375 00:14:17,120 --> 00:14:18,960 Ik ga u elk een nummer te geven. 376 00:14:18,960 --> 00:14:22,150 En ga je gang en leg uzelf identiek aan wat er 377 00:14:22,150 --> 00:14:25,180 afgebeeld op het scherm. 378 00:14:25,180 --> 00:14:26,530 >> [Onderbreekt hem VOICES] 379 00:14:26,530 --> 00:14:28,160 >> DAVID J. MALAN: Oop, sorry. 380 00:14:28,160 --> 00:14:30,210 Bug. 381 00:14:30,210 --> 00:14:32,180 Oke. 382 00:14:32,180 --> 00:14:32,750 Nou, daar gaan we. 383 00:14:32,750 --> 00:14:34,180 Nummer vijf. 384 00:14:34,180 --> 00:14:35,136 Nummer zes. 385 00:14:35,136 --> 00:14:37,770 Een, twee, drie, vier, vijf, zes, zeven. 386 00:14:37,770 --> 00:14:39,410 Oh, dit is onhandig. 387 00:14:39,410 --> 00:14:41,210 >> SPEAKER 2: Ik zal gewoon een -. 388 00:14:41,210 --> 00:14:41,900 >> DAVID J. Malan: Good deal. 389 00:14:41,900 --> 00:14:43,130 Oke. 390 00:14:43,130 --> 00:14:44,611 Bedankt voor uw deelname. 391 00:14:44,611 --> 00:14:47,200 >> [Applaus] 392 00:14:47,200 --> 00:14:48,580 >> OK. 393 00:14:48,580 --> 00:14:48,860 Oke. 394 00:14:48,860 --> 00:14:51,970 Dus hebben we vier, twee, zes, een, drie, zeven, vijf. 395 00:14:51,970 --> 00:14:56,010 Perfect dus we hebben zeven vrijwilligers Hier die even breed de 396 00:14:56,010 --> 00:14:57,430 array die we spelen met de eerdere. 397 00:14:57,430 --> 00:14:59,470 En ik koos zeven redenen dat zal net 398 00:14:59,470 --> 00:15:00,840 handig in een klein beetje. 399 00:15:00,840 --> 00:15:04,400 En ik ga eerst voor te stellen dat We sorteren van deze zeven vrijwilligers. 400 00:15:04,400 --> 00:15:06,786 Als je wilt, de eerste, om hallo wel. zeggen 401 00:15:06,786 --> 00:15:08,970 Aangezien dit gaat worden een onhandige enkele minuten. 402 00:15:08,970 --> 00:15:10,370 Introduceer jezelf. 403 00:15:10,370 --> 00:15:10,980 >> GRACE: Hoi, ik ben Grace. 404 00:15:10,980 --> 00:15:14,190 Ik ben een tweedejaars in Leverett House. 405 00:15:14,190 --> 00:15:14,620 >> BRANSON: Hi. 406 00:15:14,620 --> 00:15:15,620 Ik ben Branson. 407 00:15:15,620 --> 00:15:16,920 Ik ben een eerstejaars in Weld. 408 00:15:16,920 --> 00:15:19,755 409 00:15:19,755 --> 00:15:20,230 >> GABE: Hi. 410 00:15:20,230 --> 00:15:21,040 Ik ben Gabe. 411 00:15:21,040 --> 00:15:22,300 Ik ben een junior in Cabot. 412 00:15:22,300 --> 00:15:24,826 413 00:15:24,826 --> 00:15:25,980 >> NEIL: Ik ben Neil. 414 00:15:25,980 --> 00:15:29,090 Ik ben een eerstejaars in Matthews. 415 00:15:29,090 --> 00:15:29,550 >> JASON: Ik ben Jason. 416 00:15:29,550 --> 00:15:32,816 Ik ben een eerstejaars in Greenough. 417 00:15:32,816 --> 00:15:33,700 >> MIKE: Ik ben Mike. 418 00:15:33,700 --> 00:15:37,360 Ik ben een eerstejaars in Grays. 419 00:15:37,360 --> 00:15:37,990 >> JESS: Ik ben Jess. 420 00:15:37,990 --> 00:15:40,313 Ik ben een tweedejaars in Leverett. 421 00:15:40,313 --> 00:15:41,300 >> DAVID J. Malan: Excellent. 422 00:15:41,300 --> 00:15:41,850 Oke. 423 00:15:41,850 --> 00:15:44,190 Nou, bedankt voor al onze vrijwilligers hier tot nu toe. 424 00:15:44,190 --> 00:15:47,110 En de uitdaging bij de hand nu gaat om te sorteren van deze jongens, maar dan 425 00:15:47,110 --> 00:15:50,250 We gaan te hebben om een ​​beetje denken hard over hoe efficiënt we eigenlijk 426 00:15:50,250 --> 00:15:51,110 geordend. 427 00:15:51,110 --> 00:15:52,580 Dus laten we eerst proberen dit. 428 00:15:52,580 --> 00:15:55,970 Jullie kunnen elkaars nummers te zien , alleen maar door in de hoeken. 429 00:15:55,970 --> 00:15:59,380 Ga je gang en neem een ​​paar seconden, en sorteer zelven uit kleinste op de 430 00:15:59,380 --> 00:16:01,240 links naar grootste aan de rechterkant. 431 00:16:01,240 --> 00:16:02,490 Gaan. 432 00:16:02,490 --> 00:16:07,010 433 00:16:07,010 --> 00:16:07,530 >> OK. 434 00:16:07,530 --> 00:16:08,030 Goed. 435 00:16:08,030 --> 00:16:09,370 Dat was echt darn snel. 436 00:16:09,370 --> 00:16:14,040 Nu iemand hier, wat was het algoritme dat deze jongens toegepast? 437 00:16:14,040 --> 00:16:14,900 >> LUIDSPREKER 1: minst naar grootst. 438 00:16:14,900 --> 00:16:15,000 >> DAVID J. Malan: OK. 439 00:16:15,000 --> 00:16:18,070 Minst naar meest is echt soort van de doelstelling, maar ik ben niet zeker dat is 440 00:16:18,070 --> 00:16:18,890 echt een algoritme. 441 00:16:18,890 --> 00:16:21,810 Minst naar meest vertelt niet me stap-voor-stap wat te doen. 442 00:16:21,810 --> 00:16:22,833 Yeah? 443 00:16:22,833 --> 00:16:24,083 >> LUIDSPREKER 1: [onverstaanbaar] 444 00:16:24,083 --> 00:16:26,010 445 00:16:26,010 --> 00:16:26,280 >> DAVID J. Malan: OK. 446 00:16:26,280 --> 00:16:28,920 Dus als je een persoon kleiner dan uw nummer, ga dan naar 447 00:16:28,920 --> 00:16:29,680 Rechts er. 448 00:16:29,680 --> 00:16:32,800 Dus dat is nu steeds meer expressief, meer als een algoritme, omdat u 449 00:16:32,800 --> 00:16:35,410 kan zeggen, als dit, dan dat. 450 00:16:35,410 --> 00:16:37,050 Dus we hebben een soort van conditionele construct. 451 00:16:37,050 --> 00:16:39,700 En deze jongens leek dat een paar doen tijden, omdat sommige van jullie bewogen een beetje 452 00:16:39,700 --> 00:16:40,420 van een afstand. 453 00:16:40,420 --> 00:16:43,410 Dus er was vermoedelijk een soort van looping gaande is in hun gedachten. 454 00:16:43,410 --> 00:16:44,610 >> Maar laten we proberen te formaliseren dat. 455 00:16:44,610 --> 00:16:47,540 Als jullie terug kon resetten deze regeling. 456 00:16:47,540 --> 00:16:50,650 Laten we eens kijken of we niet kunnen formaliseren dit een beetje, en dan de vraag stellen, maar 457 00:16:50,650 --> 00:16:51,580 hoe efficiënt is dit? 458 00:16:51,580 --> 00:16:54,220 Natuurlijk, wanneer we dit doen langzamer, het gaat zo goed van te voelen 459 00:16:54,220 --> 00:16:57,210 een algoritme, maar laten we eens kijken of we kunnen zetten onze vingers op de precieze stappen. 460 00:16:57,210 --> 00:16:58,670 >> Zodat je twee jongens zijn vier en twee. 461 00:16:58,670 --> 00:17:01,020 Of je juist of onjuist orde? 462 00:17:01,020 --> 00:17:01,900 Uiteraard ingevuld. 463 00:17:01,900 --> 00:17:02,710 Dus we verwisseld. 464 00:17:02,710 --> 00:17:05,170 Nu ga ik opzij bewegen hier en zeg, 4-6. 465 00:17:05,170 --> 00:17:06,240 Bent u juist of onjuist? 466 00:17:06,240 --> 00:17:06,599 >> GABE: Correct. 467 00:17:06,599 --> 00:17:07,180 >> DAVID J. Malan: Correct. 468 00:17:07,180 --> 00:17:08,300 Zes en een? 469 00:17:08,300 --> 00:17:08,609 Nope. 470 00:17:08,609 --> 00:17:09,630 Swap. 471 00:17:09,630 --> 00:17:10,490 Dus dat is twee swaps. 472 00:17:10,490 --> 00:17:11,710 Zes en drie? 473 00:17:11,710 --> 00:17:11,980 Nope. 474 00:17:11,980 --> 00:17:13,000 Swap. 475 00:17:13,000 --> 00:17:13,930 Zes en zeven? 476 00:17:13,930 --> 00:17:14,630 Ziet er goed uit. 477 00:17:14,630 --> 00:17:15,396 Zeven en vijf? 478 00:17:15,396 --> 00:17:16,150 >> JESS: [onverstaanbaar] 479 00:17:16,150 --> 00:17:17,089 >> DAVID J. MALAN: OK, swap. 480 00:17:17,089 --> 00:17:19,770 En gesorteerd. 481 00:17:19,770 --> 00:17:19,980 Oke. 482 00:17:19,980 --> 00:17:21,440 Dus natuurlijk niet, toch? 483 00:17:21,440 --> 00:17:22,470 Dus er meer aan de hand is op. 484 00:17:22,470 --> 00:17:24,920 Maar, inderdaad, deze jongens, zelfs gewoon instinctief. 485 00:17:24,920 --> 00:17:25,450 beweging gehouden. 486 00:17:25,450 --> 00:17:27,710 Ze hebben niet alleen te stoppen, als ze eenmaal gecorrigeerd een probleem. 487 00:17:27,710 --> 00:17:27,839 So. 488 00:17:27,839 --> 00:17:29,390 Inderdaad, ik ga moeten om hetzelfde te doen. 489 00:17:29,390 --> 00:17:32,720 Ik ga te hebben om een ​​soort van terugspoelen terug aan het begin van dit probleem, 490 00:17:32,720 --> 00:17:35,630 of het begin van deze reeks van mensen, laten we beginnen ze te roepen. 491 00:17:35,630 --> 00:17:38,366 >> En nu, wat moet mijn algoritme Bij de tweede beweging zijn? 492 00:17:38,366 --> 00:17:39,220 >> LUIDSPREKER 1: Hetzelfde. 493 00:17:39,220 --> 00:17:39,940 >> DAVID J. Malan: Hetzelfde. 494 00:17:39,940 --> 00:17:41,460 En dit, ik ben beginnen te vinden, toch? 495 00:17:41,460 --> 00:17:44,720 Zodra u merkt dat je doet hetzelfde opnieuw en opnieuw, dat is 496 00:17:44,720 --> 00:17:47,890 steeds meer als een algoritme, en minder menselijk instinct. 497 00:17:47,890 --> 00:17:48,680 >> Dus nu, daar gaan we weer. 498 00:17:48,680 --> 00:17:49,870 Twee en vier? 499 00:17:49,870 --> 00:17:50,220 Nee. 500 00:17:50,220 --> 00:17:51,050 Vier en een? 501 00:17:51,050 --> 00:17:53,380 Ah, was er inderdaad een aantal werk nog gedaan moet worden. 502 00:17:53,380 --> 00:17:53,620 Voor en drie? 503 00:17:53,620 --> 00:17:54,572 Goed. 504 00:17:54,572 --> 00:17:56,000 Vier en zes? 505 00:17:56,000 --> 00:17:58,380 Zes en vijf? 506 00:17:58,380 --> 00:17:59,470 Zes en zeven? 507 00:17:59,470 --> 00:18:00,970 OK, nu, gedaan. 508 00:18:00,970 --> 00:18:01,550 OK, nee. 509 00:18:01,550 --> 00:18:02,710 Ik heb om terug te gaan. 510 00:18:02,710 --> 00:18:05,130 >> Dus nu, nogmaals, dat we dit doen een beetje meer bewust. 511 00:18:05,130 --> 00:18:08,700 En nu, er is gewoon een brein uitvoeren van dit algoritme. 512 00:18:08,700 --> 00:18:10,290 Een CPU, als je wil. 513 00:18:10,290 --> 00:18:13,090 En eerlijk gezegd, dat is de enige bron gaan we toegang tot hebben. 514 00:18:13,090 --> 00:18:16,280 En zodra we terug gaan naar een toetsenbord en hebben iets als C bij ons 515 00:18:16,280 --> 00:18:19,600 verwijdering, we alleen maar het schrijven van een programma dat een ding kan doen op een moment. 516 00:18:19,600 --> 00:18:22,900 Overwegende dat deze jongens een moment geleden, hebben we leveraged hun collectieve denkkracht 517 00:18:22,900 --> 00:18:24,180 zoals jullie deden in week nul. 518 00:18:24,180 --> 00:18:24,980 Dus laten we dit blijven doen. 519 00:18:24,980 --> 00:18:26,260 >> Twee en een. 520 00:18:26,260 --> 00:18:26,945 Twee en drie. 521 00:18:26,945 --> 00:18:27,460 Drie en vier. 522 00:18:27,460 --> 00:18:28,310 Vier en vijf. 523 00:18:28,310 --> 00:18:28,620 Vijf en zes. 524 00:18:28,620 --> 00:18:30,510 Zes en zeven. 525 00:18:30,510 --> 00:18:31,880 Gedaan? 526 00:18:31,880 --> 00:18:34,560 Dus ik ben, maar laat me spelen advocaat van de duivel. 527 00:18:34,560 --> 00:18:37,950 Heb ik, het soort computer die net maakte een pass door deze array van 528 00:18:37,950 --> 00:18:40,225 mensen, weten dat ik klaar ben? 529 00:18:40,225 --> 00:18:40,670 >> LUIDSPREKER 1: No 530 00:18:40,670 --> 00:18:41,050 >> DAVID J. Malan: Waarom? 531 00:18:41,050 --> 00:18:46,900 Wat zou ik moeten doen om concluderen resoluut dat ik klaar ben? 532 00:18:46,900 --> 00:18:48,230 Waarschijnlijk een meer door. 533 00:18:48,230 --> 00:18:48,430 Rechts? 534 00:18:48,430 --> 00:18:51,760 Want alles wat ik weet van die eerdere pas is dat ik gecorrigeerd een fout. 535 00:18:51,760 --> 00:18:53,920 En dat betekent, misschien is er nog een andere fout 536 00:18:53,920 --> 00:18:54,840 die ik moet corrigeren. 537 00:18:54,840 --> 00:18:58,680 Dus ik kan alleen zeker zijn door terugspoelen, en dan controleren, 1-2, twee en 538 00:18:58,680 --> 00:19:00,940 drie, drie en vier, vier en vijf, vijf en zes, zes en zeven. 539 00:19:00,940 --> 00:19:02,510 OK, nu heb ik geen werk. 540 00:19:02,510 --> 00:19:05,990 >> Ik kan zeker herinneren dat ik deed geen werken met iets als een variabele, 541 00:19:05,990 --> 00:19:06,975 als een int. 542 00:19:06,975 --> 00:19:12,490 Noem het swaps, en als swaps is 0 keer I krijgen hier, en het begon op 0, dan 543 00:19:12,490 --> 00:19:15,520 Ik zou gewoon dom zijn om door te gaan heen en weer, opnieuw controleren, en 544 00:19:15,520 --> 00:19:16,450 opnieuw, en opnieuw, toch? 545 00:19:16,450 --> 00:19:18,450 Omdat je vastzit in een aantal soort van oneindige lus. 546 00:19:18,450 --> 00:19:21,250 Dus zodra er 0 swaps, we kunnen beweren dat dit 547 00:19:21,250 --> 00:19:23,810 algoritme is inderdaad voltooid. 548 00:19:23,810 --> 00:19:25,400 >> Nu, laten we een naam op deze. 549 00:19:25,400 --> 00:19:28,930 Het algoritme dat ik voorstel dat we gewoon geïmplementeerd is iets genaamd bubble 550 00:19:28,930 --> 00:19:32,800 soort, als zodanig bekend in de zin dat de getallen die groter zijn soort 551 00:19:32,800 --> 00:19:37,990 bubble hun weg naar de top, of maximaal aan het einde van de reeks getallen. 552 00:19:37,990 --> 00:19:40,270 Maar hoe efficiënt was dit algoritme? 553 00:19:40,270 --> 00:19:44,600 Hoeveel stappen heb ik fysiek moet nemen, bijvoorbeeld om deze te sorteren 554 00:19:44,600 --> 00:19:45,850 zeven mensen? 555 00:19:45,850 --> 00:19:48,560 556 00:19:48,560 --> 00:19:49,550 >> Vier tot vijf? 557 00:19:49,550 --> 00:19:51,420 OK, te veel is uiteindelijk gaan naar het antwoord. 558 00:19:51,420 --> 00:19:54,960 Maar zelfs dan, het specifieke nummer is niet zo interessant. 559 00:19:54,960 --> 00:19:56,670 Laten we generaliseren het als n. 560 00:19:56,670 --> 00:20:00,520 Dus als ik had n mensen hier, en ze waren, soort van, in willekeurige volgorde op de 561 00:20:00,520 --> 00:20:02,180 beginnen, in die oorspronkelijke volgorde. 562 00:20:02,180 --> 00:20:04,910 Nou, hoeveel stappen moest ik te nemen op de eerste pas? 563 00:20:04,910 --> 00:20:09,810 Het was een, twee, drie, vier, vijf, zes, en ze zijn zeven mensen, dus 564 00:20:09,810 --> 00:20:13,670 dat is zeven, zes -, dus dat is n min een stappen de eerste keer. 565 00:20:13,670 --> 00:20:16,280 >> Nu, hoeveel stappen moest ik te nemen wanneer ik teruggespoeld? 566 00:20:16,280 --> 00:20:19,310 Nou, we konden eigenlijk verdubbelen dat als we echt wilden, maar voor nu, ben ik 567 00:20:19,310 --> 00:20:22,300 gewoon om te zeggen, oke, andere n minus 1. 568 00:20:22,300 --> 00:20:25,240 Zodat het n minus 1 gaat krijgen vervelend om bij te houden, dus laten we 569 00:20:25,240 --> 00:20:26,400 net om iets omhoog. 570 00:20:26,400 --> 00:20:27,770 Dus 2n stappen. 571 00:20:27,770 --> 00:20:29,310 Dus 14 stappen, geven of te nemen. 572 00:20:29,310 --> 00:20:31,930 >> Hoe vaak heb ik een stap de volgende keer? 573 00:20:31,930 --> 00:20:33,740 Nou, het is 3n. 574 00:20:33,740 --> 00:20:34,510 echt. 575 00:20:34,510 --> 00:20:37,920 Nu, in het slechtste geval voor Bijvoorbeeld, hoe vaak zou ik 576 00:20:37,920 --> 00:20:41,730 gegaan heen en weer, heen en weer, uitvoeren van dit algoritme swapping 577 00:20:41,730 --> 00:20:44,620 mensen op elke pas, ruwweg? 578 00:20:44,620 --> 00:20:47,720 579 00:20:47,720 --> 00:20:50,010 Het is eigenlijk n kwadraat, toch? 580 00:20:50,010 --> 00:20:53,000 >> Want in het ergste geval, je kan soort van denken over dit intuïtief, 581 00:20:53,000 --> 00:20:54,800 ook al is het een beetje zou kunnen nemen beetje tijd om te bezinken 582 00:20:54,800 --> 00:20:57,590 In het slechtste geval, wat zou deze zeven mensen gekeken hebben als, in 583 00:20:57,590 --> 00:21:00,230 voorwaarden van de overeenkomst van hun nummers? 584 00:21:00,230 --> 00:21:01,460 Volledig achteruit, toch? 585 00:21:01,460 --> 00:21:02,815 En alleen te simuleren dat, Wat was je naam ook alweer? 586 00:21:02,815 --> 00:21:03,360 >> MIKE: Mike. 587 00:21:03,360 --> 00:21:03,640 >> DAVID J. Malan: Mike? 588 00:21:03,640 --> 00:21:08,100 OK, Mike, kun je gewoon bij me over hier voor slechts een seconde? 589 00:21:08,100 --> 00:21:08,880 Eigenlijk niet. 590 00:21:08,880 --> 00:21:10,150 Sorry Mike, laten we terugspoelen. 591 00:21:10,150 --> 00:21:10,910 Hoe heet je ook alweer? 592 00:21:10,910 --> 00:21:11,180 >> NEIL: Neil. 593 00:21:11,180 --> 00:21:11,640 >> DAVID J. Malan: Neil. 594 00:21:11,640 --> 00:21:13,750 OK, Neil, kom je met me, als je het niet erg vindt. 595 00:21:13,750 --> 00:21:17,150 Dus ik ga voorstellen, alleen voor eenvoud, dat Neil nu in zijn 596 00:21:17,150 --> 00:21:18,510 slechtst denkbare geval. 597 00:21:18,510 --> 00:21:20,720 Maar herinneren hoe ik geïmplementeerd mijn algoritme. 598 00:21:20,720 --> 00:21:24,530 Ik vergelijk, vergelijken vergelijken vergelijken, vergelijken, oh. 599 00:21:24,530 --> 00:21:26,640 Nu zijn deze jongens uit van orde, dus ik fix. 600 00:21:26,640 --> 00:21:27,980 Dus jullie ruilen. 601 00:21:27,980 --> 00:21:31,630 Maar denk nu, hoe veel verder hoeft Neil moeten gaan? 602 00:21:31,630 --> 00:21:32,690 Het is ruwweg n. 603 00:21:32,690 --> 00:21:33,570 Je weet wel, het is niet echt n. 604 00:21:33,570 --> 00:21:36,040 Het is als, n minus 1, maar ik krijg geërgerd bijhouden van de kleine 605 00:21:36,040 --> 00:21:37,550 nummer, dus laten we gewoon noemen het n. 606 00:21:37,550 --> 00:21:42,860 >> Dus als Neil beweegt een stap maximaal elkaar tijd, en Neil een stap te verplaatsen, 607 00:21:42,860 --> 00:21:46,580 Ik moet dit echt vervelend pas maken heen en weer, wat ruwweg 608 00:21:46,580 --> 00:21:52,080 Daarbij n stappen in totaal n maal, want het gaat me te nemen 609 00:21:52,080 --> 00:21:55,820 dat vele stappen naar Neil allemaal de weg waar hij behoort. 610 00:21:55,820 --> 00:21:58,620 Laat staan ​​iedereen anders als jullie waren allemaal verkeerd bestelde ook. 611 00:21:58,620 --> 00:22:01,100 >> Dus laten we noemen bubble sort n kwadraat. 612 00:22:01,100 --> 00:22:04,860 De looptijd van dit algoritme, de prestaties van dit algoritme, de 613 00:22:04,860 --> 00:22:07,120 efficiëntie van dit algoritme, we zullen gewoon beschrijven meer 614 00:22:07,120 --> 00:22:08,800 algemeen als n kwadraat. 615 00:22:08,800 --> 00:22:11,650 Dat is leuk, want ik kon doen het Hetzelfde voorbeeld met acht mensen, negen 616 00:22:11,650 --> 00:22:15,450 mensen, een miljoen mensen, en dat antwoord is niet van plan om te veranderen. 617 00:22:15,450 --> 00:22:18,870 >> Dus als jullie het niet erg vindt, laten we reset je naar waar je begon. 618 00:22:18,870 --> 00:22:22,510 En laten we proberen twee andere benaderingen en zien of we niet fundamenteel kunnen doen 619 00:22:22,510 --> 00:22:23,820 beter dan deze. 620 00:22:23,820 --> 00:22:27,130 Dus deze keer, ga ik voorstellen een soort ander algoritme. 621 00:22:27,130 --> 00:22:29,950 Dat was heel slim van ons vorige keer, en jullie hadden gelijk aan het hebben 622 00:22:29,950 --> 00:22:32,470 juiste instincten van gewoon een soort van swapping paarsgewijze. 623 00:22:32,470 --> 00:22:36,500 Maar als ik echt wilde deze te benaderen gewoon, en mijn doel is om te bewegen 624 00:22:36,500 --> 00:22:39,800 alle kleine aantallen deze manier, en Duw alle van de grote getallen die 625 00:22:39,800 --> 00:22:43,030 Trouwens, waarom niet ik dat alleen in de meest naïeve manier mogelijk te maken en te zien of ik 626 00:22:43,030 --> 00:22:45,730 kan beter dan wat was doen vrij complex algoritme? 627 00:22:45,730 --> 00:22:46,620 >> Dus laten we eens kijken. 628 00:22:46,620 --> 00:22:48,940 Vier is een vrij klein aantal, dus ik ben ga je daar laten ogenblik. 629 00:22:48,940 --> 00:22:50,610 Ooh, nummer twee is nog beter. 630 00:22:50,610 --> 00:22:52,230 Zo kunt u gewoon stap voorwaarts voor een moment? 631 00:22:52,230 --> 00:22:55,670 Dit is momenteel mijn kleinste genummerde kandidaat, en ik ga om te onthouden 632 00:22:55,670 --> 00:22:57,000 dat met, zoals, een variabele. 633 00:22:57,000 --> 00:22:57,930 Maar ik ga blijven controleren. 634 00:22:57,930 --> 00:22:59,890 Is er iemand wiens getal is kleiner? 635 00:22:59,890 --> 00:23:00,460 Six, nee. 636 00:23:00,460 --> 00:23:01,390 Oh, is er Neil weer. 637 00:23:01,390 --> 00:23:04,050 >> Dus ik ga u terug te duwen soort conceptueel. 638 00:23:04,050 --> 00:23:05,120 Neil zal naar voren komen. 639 00:23:05,120 --> 00:23:08,440 En nu, de variabele die ik gebruik om bijhouden wie de kleinste heeft 640 00:23:08,440 --> 00:23:11,390 nummer wordt bijgewerkt om bevatten Locatie Neil's. 641 00:23:11,390 --> 00:23:12,110 Nou, laten we eens kijken. 642 00:23:12,110 --> 00:23:13,960 Drie, zeven, vijf. 643 00:23:13,960 --> 00:23:15,590 OK, ik weet dat Neil was de kleinste. 644 00:23:15,590 --> 00:23:18,110 Wat is de eenvoudigste zaak voor mij om nu te doen? 645 00:23:18,110 --> 00:23:21,410 Ik ben niet van plan om mijn tijd te verspillen door gewoon borrelende Neil ene plek naar links. 646 00:23:21,410 --> 00:23:25,350 Waarom heb ik niet gewoon Neil waar hij behoort, die natuurlijk Abuse 647 00:23:25,350 --> 00:23:26,160 >> Helemaal aan het begin. 648 00:23:26,160 --> 00:23:27,720 Dus Neil, kom met me mee. 649 00:23:27,720 --> 00:23:28,910 En wat was je naam ook alweer? 650 00:23:28,910 --> 00:23:29,310 >> GRACE: Grace. 651 00:23:29,310 --> 00:23:29,710 >> DAVID J. Malan: Grace. 652 00:23:29,710 --> 00:23:29,920 OK. 653 00:23:29,920 --> 00:23:32,490 Dus Grace, helaas, je bent soort in de weg. 654 00:23:32,490 --> 00:23:34,290 Dus hoe kunnen we dit probleem oplossen? 655 00:23:34,290 --> 00:23:34,490 Rechts? 656 00:23:34,490 --> 00:23:37,500 Indien een array, er slechts zeven locaties. 657 00:23:37,500 --> 00:23:40,830 Bedenk dat, met Rob, we spraken over verklaren leeftijden, en we hadden alleen een 658 00:23:40,830 --> 00:23:41,740 eindig aantal leeftijden? 659 00:23:41,740 --> 00:23:42,535 Hetzelfde idee hier. 660 00:23:42,535 --> 00:23:44,300 We hebben slechts een eindig aantal ints. 661 00:23:44,300 --> 00:23:47,590 Grace is een soort van in onze manier, dus hoe kunnen we oplossen? 662 00:23:47,590 --> 00:23:49,555 >> De eenvoudigste manier is als, Genade, sorry. 663 00:23:49,555 --> 00:23:51,870 Je gaat te hebben om over te gaan daar dus kunnen we ruimte maken. 664 00:23:51,870 --> 00:23:55,290 Nu, als je van deze, misschien we net het probleem erger. 665 00:23:55,290 --> 00:23:58,510 En misschien hebben we gedaan, want wat als Genade waren op de juiste plaats? 666 00:23:58,510 --> 00:24:01,730 Maar we weten dat ze niet, want anders, zou ze zijn geweest 667 00:24:01,730 --> 00:24:03,980 staande vooruit in plaats van Neil in deze tijd, toch? 668 00:24:03,980 --> 00:24:05,550 We hebben al controleerde haar nummer uit. 669 00:24:05,550 --> 00:24:05,770 >> Oke. 670 00:24:05,770 --> 00:24:09,110 Dus nu, Neil is op de juiste plaats, en Ik kan een lichte optimalisatie te doen. 671 00:24:09,110 --> 00:24:11,740 Voor de volgende minuut, ga ik negeer Neil allemaal samen, zodat geen 672 00:24:11,740 --> 00:24:15,280 zijn tijd verdoen, of per ongeluk swap hem naar de verkeerde plaats. 673 00:24:15,280 --> 00:24:17,805 Dus nu, hoe krijg ik het volgende te vinden element dat is kleinst? 674 00:24:17,805 --> 00:24:18,480 Twee. 675 00:24:18,480 --> 00:24:20,225 Dat is een vrij goed nummer, indien je wilt naar voren en 676 00:24:20,225 --> 00:24:21,100 Ik zal je niet vergeten. 677 00:24:21,100 --> 00:24:21,980 Zes, niet goed. 678 00:24:21,980 --> 00:24:24,820 Vier, drie, zeven, vijf, niet goed. 679 00:24:24,820 --> 00:24:26,800 Dus laat me bewegen om uw juiste plek. 680 00:24:26,800 --> 00:24:28,470 En we zijn net geluk dit keer. 681 00:24:28,470 --> 00:24:31,350 >> Nu, ik ga deze negeren twee jongens, en nu doen een meer 682 00:24:31,350 --> 00:24:32,260 passeren dit. 683 00:24:32,260 --> 00:24:33,490 Zes, dat een vrij klein aantal. 684 00:24:33,490 --> 00:24:34,300 Kom op vooruit. 685 00:24:34,300 --> 00:24:35,220 Oh, sorry. 686 00:24:35,220 --> 00:24:37,640 Grace's nummer is beter, dus stap op vooruit. 687 00:24:37,640 --> 00:24:38,260 Four. 688 00:24:38,260 --> 00:24:39,120 Sorry, Grace. 689 00:24:39,120 --> 00:24:39,950 Ga weer terug. 690 00:24:39,950 --> 00:24:41,550 Nummer drie is beter. 691 00:24:41,550 --> 00:24:42,290 Zeven. 692 00:24:42,290 --> 00:24:42,720 Vijf. 693 00:24:42,720 --> 00:24:43,550 En wat nu heet je ook alweer? 694 00:24:43,550 --> 00:24:44,000 >> JASON: Jason. 695 00:24:44,000 --> 00:24:44,420 >> DAVID J. Malan: Jason. 696 00:24:44,420 --> 00:24:47,050 Dus Jason is nu de kleinste element dat ik heb geselecteerd. 697 00:24:47,050 --> 00:24:49,160 Waar gaat hij heen? 698 00:24:49,160 --> 00:24:50,380 Dus waar zes is. 699 00:24:50,380 --> 00:24:51,210 En uw naam is weer? 700 00:24:51,210 --> 00:24:51,710 >> GABE: Gabe. 701 00:24:51,710 --> 00:24:52,340 >> DAVID J. Malan: Gabe. 702 00:24:52,340 --> 00:24:53,220 Gabe is in de weg. 703 00:24:53,220 --> 00:24:54,640 Wat is de makkelijkste om te doen? 704 00:24:54,640 --> 00:24:58,390 Verwissel deze twee jongens en doorgaan. 705 00:24:58,390 --> 00:24:59,020 Dus laten we nu zien. 706 00:24:59,020 --> 00:25:00,170 Wie is de kleinste? 707 00:25:00,170 --> 00:25:01,030 Four. 708 00:25:01,030 --> 00:25:01,990 Laat me gewoon een soort cheat. 709 00:25:01,990 --> 00:25:03,090 Vijf gaat om de kleinste te zijn. 710 00:25:03,090 --> 00:25:05,220 Ik vind de volgende, als je wilt stappen vooruit, wat heb ik te maken met 711 00:25:05,220 --> 00:25:06,820 deze jongens, met Gabe? 712 00:25:06,820 --> 00:25:08,450 Opnieuw wisselen. 713 00:25:08,450 --> 00:25:10,740 Dus nu, nog steeds licht buiten de orde. 714 00:25:10,740 --> 00:25:14,140 Ik vond Gabe het laagste is, zo Ik pop hem uit, beweeg je jongens overgenomen. 715 00:25:14,140 --> 00:25:15,190 En gedaan. 716 00:25:15,190 --> 00:25:17,200 >> Dus antwoord is hetzelfde. 717 00:25:17,200 --> 00:25:18,600 Het eindresultaat is hetzelfde. 718 00:25:18,600 --> 00:25:22,730 Welke van deze twee algoritmen is beter? 719 00:25:22,730 --> 00:25:23,500 De tweede, hoorde ik. 720 00:25:23,500 --> 00:25:24,252 Waarom? 721 00:25:24,252 --> 00:25:25,900 >> SPEAKER 3: Het is n stappen [onverstaanbaar]. 722 00:25:25,900 --> 00:25:27,600 >> DAVID J. Malan: Het is n stappen bij de meeste. 723 00:25:27,600 --> 00:25:28,490 Interessant. 724 00:25:28,490 --> 00:25:30,610 Dus is het wel? 725 00:25:30,610 --> 00:25:33,630 Dus hoe vind ik de kleinste element? 726 00:25:33,630 --> 00:25:37,060 Hoeveel stappen heb ik moeten nemen het het kleinste element vinden? 727 00:25:37,060 --> 00:25:39,220 Ik had een kijk helemaal op het einde, toch? 728 00:25:39,220 --> 00:25:41,530 Want dan worst case, welke Als Neil waren hierheen? 729 00:25:41,530 --> 00:25:45,700 Dus gewoon het vinden van het kleinste element neemt me n stappen, of n minus 1. 730 00:25:45,700 --> 00:25:46,100 Maar, OK. 731 00:25:46,100 --> 00:25:46,980 Dus fix Neil. 732 00:25:46,980 --> 00:25:48,740 Vergeet niet dat, een minuut of zo geleden. 733 00:25:48,740 --> 00:25:51,680 >> Maar hoe heb ik het volgende te vinden kleinste element? 734 00:25:51,680 --> 00:25:54,830 Het is n minus 1, of n min 2 echt, van het aantal stappen. 735 00:25:54,830 --> 00:25:55,440 Nou ja. 736 00:25:55,440 --> 00:25:57,390 Dus ik heb n minus 2. 737 00:25:57,390 --> 00:25:57,600 Oke. 738 00:25:57,600 --> 00:25:59,130 Dus dat voelt een beetje beter. 739 00:25:59,130 --> 00:25:59,730 Oke. 740 00:25:59,730 --> 00:26:03,270 Hoeveel stappen de volgende keer naar nummer drie vinden? 741 00:26:03,270 --> 00:26:04,420 Zo n min 4. 742 00:26:04,420 --> 00:26:07,670 Dus het is dalende, een minder stap op elke iteratie. 743 00:26:07,670 --> 00:26:08,740 Dus dit voelt beter, toch? 744 00:26:08,740 --> 00:26:13,450 Als laatste keer was ongeveer n keer n, dit keer is het n min 1, plus n minus 745 00:26:13,450 --> 00:26:16,500 2, plus n min 3, plus n min 4, puntje, puntje, puntje. 746 00:26:16,500 --> 00:26:18,750 Maar als u zich herinneren van je middelbare school leerboeken, de kleine cheat 747 00:26:18,750 --> 00:26:24,380 plaat aan de achterkant die formules heeft, indien je optelt deze reeks getallen, 748 00:26:24,380 --> 00:26:31,280 wat het totale aantal stappen gaat zijn dat ik hier? 749 00:26:31,280 --> 00:26:36,580 >> Dit is een van die, als, n minus 1 maal n, gedeeld door 2. 750 00:26:36,580 --> 00:26:39,040 Dus laat me zien of ik kan trekken dit voor slechts een moment. 751 00:26:39,040 --> 00:26:42,230 En nogmaals, ik ben soort van afronding sommige aantallen alleen maar om ons leven eenvoudig te houden, 752 00:26:42,230 --> 00:26:47,830 maar als ik me goed herinner, het is zoiets als Ik doe n minus 1 dingen, dan n minus 753 00:26:47,830 --> 00:26:53,570 2, dan is n min 3, het is grofweg zoiets als dit dan 2, en als ik 754 00:26:53,570 --> 00:26:55,510 vermenigvuldig dit uit, dat is eigenlijk n plein. 755 00:26:55,510 --> 00:26:58,940 Dat is niet al te goed voelen. n minus n meer dan 2. 756 00:26:58,940 --> 00:27:00,350 >> Maar hier is het ding. 757 00:27:00,350 --> 00:27:03,720 In de informatica, toen de problemen beginnen te krijgen interessant is wanneer n 758 00:27:03,720 --> 00:27:04,700 wordt echt groot. 759 00:27:04,700 --> 00:27:08,110 En als n wordt echt groot, die van deze waarden gaat alles domineren 760 00:27:08,110 --> 00:27:09,750 van de anderen? 761 00:27:09,750 --> 00:27:10,990 Het is een soort van de n kwadraat, toch? 762 00:27:10,990 --> 00:27:13,340 Ja, delen door 2 is vrij goed. 763 00:27:13,340 --> 00:27:16,740 Maar als je praat over miljarden van stukjes data, of triljoenen 764 00:27:16,740 --> 00:27:18,700 stukken gegevens, OK, dus je bent twee keer zo snel. 765 00:27:18,700 --> 00:27:22,440 Maar die echt cares als dat groot getal, Als deze factor is wat krijgt 766 00:27:22,440 --> 00:27:23,040 groter en groter. 767 00:27:23,040 --> 00:27:25,990 En voorwaar, het maakt meer van een verschil dan deze man. 768 00:27:25,990 --> 00:27:29,120 Dus zelfs al jullie hebben gelijk, de tweede algoritme, zullen we het noemen 769 00:27:29,120 --> 00:27:32,970 selectie sorteren, is in de echte wereld, een iets sneller potentieel, want ik ben 770 00:27:32,970 --> 00:27:35,360 nemen steeds minder stappen elke keer. 771 00:27:35,360 --> 00:27:37,340 >> Het is niet echt fundamenteel sneller. 772 00:27:37,340 --> 00:27:41,430 Want als we daadwerkelijk deze spelen uit voor grote waarden van n, eind 773 00:27:41,430 --> 00:27:44,750 de dag, voor groot genoeg n, het is nog steeds gaat vrij traag te voelen. 774 00:27:44,750 --> 00:27:46,770 Nou, laat me een laatste pas op dat. 775 00:27:46,770 --> 00:27:48,920 Dat is wat ik zou noemen selectie sorteren. 776 00:27:48,920 --> 00:27:51,040 Kunnen jullie resetten jezelf een laatste keer? 777 00:27:51,040 --> 00:27:53,550 En in dit laatste geval, ik ga om iets voor te stellen 778 00:27:53,550 --> 00:27:54,970 riep insertion sort. 779 00:27:54,970 --> 00:27:57,470 Insertion sort zijnde, conceptueel, een beetje anders. 780 00:27:57,470 --> 00:28:00,980 >> In plaats van heen en weer en selecteren van het kleinste element, ik ben 781 00:28:00,980 --> 00:28:05,030 gewoon om te gaan met elk van deze jongens zoals ik ze tegenkomt, en steek 782 00:28:05,030 --> 00:28:06,850 ze in hun juiste plaats. 783 00:28:06,850 --> 00:28:10,160 Dus ik ga gewoon beginnen met Grace, en ik zie dat ze is nummer vier. 784 00:28:10,160 --> 00:28:11,720 Waar komt nummer vier behoort? 785 00:28:11,720 --> 00:28:14,940 Ik heb niet begonnen iets te sorteren, dus Grace krijgt om daar te blijven. 786 00:28:14,940 --> 00:28:18,355 En nu ga ik te beweren, als je kon neem een ​​stap naar rechts, dit 787 00:28:18,355 --> 00:28:21,650 mijn gesorteerde lijst, dit is mijn ongesorteerde resterende lijst. 788 00:28:21,650 --> 00:28:23,260 Dus nu ga ik volgende gaan, en wat is je naam ook alweer? 789 00:28:23,260 --> 00:28:23,700 >> Branson:. 790 00:28:23,700 --> 00:28:24,150 >> DAVID J. Malan: Branson. 791 00:28:24,150 --> 00:28:25,375 Dus Branson is nummer twee. 792 00:28:25,375 --> 00:28:27,490 Dus ik ga om u te nemen uit voor een moment. 793 00:28:27,490 --> 00:28:30,940 En nu, waar moet je horen in deze array? 794 00:28:30,940 --> 00:28:32,360 Dus om het recht van genade. 795 00:28:32,360 --> 00:28:35,670 Dus nogmaals, we zijn soort van het maken Grace doet een hoop werk hier. 796 00:28:35,670 --> 00:28:37,290 Waar laten we u? 797 00:28:37,290 --> 00:28:40,120 Dus we gaan je schuiven naar de links, en steek Branson daar. 798 00:28:40,120 --> 00:28:41,680 Maar nu beweren dat ik jullie zijn klaar. 799 00:28:41,680 --> 00:28:43,240 Maar let op, ik ben niet met behulp van extra ruimte. 800 00:28:43,240 --> 00:28:45,130 Het is nog steeds 2 elementen hier, 5 dan hier. 801 00:28:45,130 --> 00:28:47,910 Totale array size is 7, dus ik ben niet bedriegen, oke? 802 00:28:47,910 --> 00:28:51,950 >> Dus nu hebben we, met Gabe hier, het nummer zes, waar hoor je thuis? 803 00:28:51,950 --> 00:28:52,650 Je hebt weer geluk. 804 00:28:52,650 --> 00:28:53,820 Dus je krijgt om daar te blijven. 805 00:28:53,820 --> 00:28:57,210 Neem gewoon een lichte stap naar rechts alleen maar om duidelijk te maken dat je naargelang bent. 806 00:28:57,210 --> 00:29:00,520 En nu hebben we Neil weer, nummer men, waar ga je heen? 807 00:29:00,520 --> 00:29:03,540 En nu is waar we zullen beginnen om dat te zien Dit algoritme, maar in het eerste 808 00:29:03,540 --> 00:29:05,950 blik, voelt behoorlijk slim, kijken wat er gaat gebeuren. 809 00:29:05,950 --> 00:29:07,370 Als je vooruit kon stappen. 810 00:29:07,370 --> 00:29:09,260 >> Waar willen we naar Neil zetten? 811 00:29:09,260 --> 00:29:11,830 Zo duidelijk hier, dus hoe komen we daar Neil? 812 00:29:11,830 --> 00:29:12,970 Laten we deze stap-voor-stap. 813 00:29:12,970 --> 00:29:15,620 Gabe, waar heb je nodig om te gaan? 814 00:29:15,620 --> 00:29:19,590 Yep, dus neem een ​​grote stap, of twee halve stappen om ervoor te 815 00:29:19,590 --> 00:29:20,820 een stap daar. 816 00:29:20,820 --> 00:29:21,750 Genade, waar je heen gaat? 817 00:29:21,750 --> 00:29:22,510 Goed. 818 00:29:22,510 --> 00:29:23,500 Dus weer een stap. 819 00:29:23,500 --> 00:29:24,960 Tenslotte Branson? 820 00:29:24,960 --> 00:29:25,460 Een andere stap. 821 00:29:25,460 --> 00:29:27,190 En nu kunnen we Neil zetten in plaats. 822 00:29:27,190 --> 00:29:28,440 >> Dus nu, blijft deze logica. 823 00:29:28,440 --> 00:29:32,420 Ook al zijn we niet verschuiven Neil over, en dan, en dan, om hem 824 00:29:32,420 --> 00:29:36,420 waar hij gaat, in het ergste geval, de volgende nummer we zouden tegenkomen konden 825 00:29:36,420 --> 00:29:42,220 'het aantal, zeg, was er een aantal nul, dan gaan we allemaal verschuiven 826 00:29:42,220 --> 00:29:42,730 deze jongens. 827 00:29:42,730 --> 00:29:44,950 Stel dat er een aantal, negatieve men, dan hebben we te verschuiven 828 00:29:44,950 --> 00:29:46,080 al deze jongens. 829 00:29:46,080 --> 00:29:48,500 Dus we zijn eigenlijk gewoon een soort van flippen het probleem rond, zodanig dat we 830 00:29:48,500 --> 00:29:52,620 het overbrengen van de lasten van de selectieproces zodat het inbrengen 831 00:29:52,620 --> 00:29:56,930 proces, zodanig dat jullie net aan ruwweg n minus iets bewegen 832 00:29:56,930 --> 00:29:57,940 aantal stappen. 833 00:29:57,940 --> 00:30:01,200 En dat aantal stappen is alleen maar te verhogen als ik meer nummers te selecteren, 834 00:30:01,200 --> 00:30:04,730 als ik moet blijven duwen jullie terug, en weer terug, en weer terug. 835 00:30:04,730 --> 00:30:08,320 >> Dus het trieste is nu al deze algoritmen zijn n kwadraat. 836 00:30:08,320 --> 00:30:10,570 Laten we verder gaan en dankzij deze jongens, en visualiseer deze een beetje 837 00:30:10,570 --> 00:30:11,090 anders. 838 00:30:11,090 --> 00:30:12,312 Zeer goed gedaan. 839 00:30:12,312 --> 00:30:14,120 >> [Applaus] 840 00:30:14,120 --> 00:30:15,030 >> Oke. 841 00:30:15,030 --> 00:30:16,280 Daar ga je. 842 00:30:16,280 --> 00:30:18,390 843 00:30:18,390 --> 00:30:18,470 Bedankt voor het - 844 00:30:18,470 --> 00:30:19,190 >> BRANSON: [onverstaanbaar] houden de nummers. 845 00:30:19,190 --> 00:30:21,990 >> DAVID J. MALAN: Nee, dat mag je houden de nummers ook. 846 00:30:21,990 --> 00:30:23,440 Oke. 847 00:30:23,440 --> 00:30:24,100 Mooi gedaan. 848 00:30:24,100 --> 00:30:25,300 Oke. 849 00:30:25,300 --> 00:30:30,510 Dus laten we kijken of we kunnen nu niet samenvatten sneller en meer visueel, 850 00:30:30,510 --> 00:30:33,410 precies wat er net gebeurd hier volgt. 851 00:30:33,410 --> 00:30:36,510 852 00:30:36,510 --> 00:30:38,770 Ik ga om te gaan en trek Firefox. 853 00:30:38,770 --> 00:30:41,310 We zullen deze demonstratie koppelen op de website van de cursus. 854 00:30:41,310 --> 00:30:43,870 Java is een beetje vervelend om te werken in sommige browsers deze dagen. 855 00:30:43,870 --> 00:30:46,760 Dus als je het spelen met deze thuis, beseft dat je nodig zou kunnen hebben om Firefox te gebruiken 856 00:30:46,760 --> 00:30:47,990 om het werkend te krijgen. 857 00:30:47,990 --> 00:30:50,440 En wat ik ga doen met deze demonstratie is de volgende. 858 00:30:50,440 --> 00:30:54,875 >> Aan de onderkant, ik heb een hele hoop menu-opties, waaronder een start en een 859 00:30:54,875 --> 00:30:55,840 stopknop. 860 00:30:55,840 --> 00:30:59,450 Ook, als een terzijde, lijkt er een bug in deze programma's, waarbij je 861 00:30:59,450 --> 00:31:03,720 kan eigenlijk niet zien de start of stop knop tenzij je houd Command of Alt 862 00:31:03,720 --> 00:31:06,560 plus-en inzoomen, wat merkwaardig laat je meer knoppen. 863 00:31:06,560 --> 00:31:09,090 Dus gewoon FYI als je speelt met deze thuis. 864 00:31:09,090 --> 00:31:12,870 Nu ga ik om te klikken op Start in slechts een Momenteel, na het opgeven van een vertraging van, 865 00:31:12,870 --> 00:31:16,810 zoals, 200 milliseconden hier, net zodat we kunnen zien wat er gebeurt. 866 00:31:16,810 --> 00:31:20,180 >> Dus ik beweren dat dit een visualisatie van het eerste algoritme 867 00:31:20,180 --> 00:31:23,730 deze jongens deden, bubble sort, waarbij We wisselden mensen pair-wise. 868 00:31:23,730 --> 00:31:27,490 De sleutel tot dit inzicht visualisatie dat de hoogte van de staven 869 00:31:27,490 --> 00:31:30,510 geeft de grootte van het getal. 870 00:31:30,510 --> 00:31:32,210 Zodat het langer de balk, de Hoe groter het getal. 871 00:31:32,210 --> 00:31:33,680 Korter de balk, kleiner het getal. 872 00:31:33,680 --> 00:31:38,630 En als je merkt, we gaan door de eerste variant van dit algoritme, 873 00:31:38,630 --> 00:31:42,620 swapping grote en kleine aantallen, zodat het geringe aantal op de eerste plaats en 874 00:31:42,620 --> 00:31:44,280 het grote aantal gaat naar rechts. 875 00:31:44,280 --> 00:31:48,770 >> En zodra we het einde van de array van veel meer nummers dan zeven, zijn we 876 00:31:48,770 --> 00:31:49,900 gaan terug naar het begin. 877 00:31:49,900 --> 00:31:51,140 En te anticiperen op deze. 878 00:31:51,140 --> 00:31:54,860 Op de uiterst links, is dat ventje gaan om te wisselen naar de zijkant, en dit 879 00:31:54,860 --> 00:31:56,010 proces herhaalt. 880 00:31:56,010 --> 00:31:59,450 Nu deze visualisatie snel weer saai, dus laat ik doorgaan en stoppen 881 00:31:59,450 --> 00:32:04,170 het, verander de vertraging iets veel sneller gewoon om nu te krijgen, een gevoel voor 882 00:32:04,170 --> 00:32:05,060 dit algoritme. 883 00:32:05,060 --> 00:32:07,840 >> Dus ook al heb ik versneld het op, dit is zoals het upgraden mijn processor, kopen 884 00:32:07,840 --> 00:32:08,580 een nieuwe computer. 885 00:32:08,580 --> 00:32:12,980 Ik heb niet fundamenteel veranderd mijn algoritme, maar je kunt wel meer zien 886 00:32:12,980 --> 00:32:16,800 duidelijk dan bij mensen, dat de grote nummers zijn borrelen tot aan de top, 887 00:32:16,800 --> 00:32:20,900 en de kleine aantallen borrelen naar beneden. 888 00:32:20,900 --> 00:32:22,390 En nu dit ding hier gesorteerd. 889 00:32:22,390 --> 00:32:25,260 En als een terzijde, op de pleinen, is er slechts enkele boekhouding daar te 890 00:32:25,260 --> 00:32:28,010 helpen tellen hoeveel vergelijkingen, of hoeveel swaps hebben 891 00:32:28,010 --> 00:32:28,950 daadwerkelijk zijn gedaan. 892 00:32:28,950 --> 00:32:30,750 >> Nou, laten we proberen een van de anderen die we zagen. 893 00:32:30,750 --> 00:32:37,116 Laat ik klik op bubble sort hier, en laat me kiezen, en deze hele webpagina 894 00:32:37,116 --> 00:32:38,936 is een beetje buggy. 895 00:32:38,936 --> 00:32:41,155 Laten we accepteren het risico en voer het opnieuw. 896 00:32:41,155 --> 00:32:44,560 897 00:32:44,560 --> 00:32:45,030 Daar gaan we. 898 00:32:45,030 --> 00:32:47,180 Dus laten we doen selectie sorteren. 899 00:32:47,180 --> 00:32:49,140 Ik weet niet waarom het menu verschijnt daar. 900 00:32:49,140 --> 00:32:54,070 Laten we inzoomen om dat te verhelpen bug, verandert dit naar 50. 901 00:32:54,070 --> 00:32:56,020 Ach, laten we eigenlijk doen dat veel sneller. 902 00:32:56,020 --> 00:32:59,160 Vijf milliseconden of zo, en Start. 903 00:32:59,160 --> 00:33:00,470 >> Dus dit is selectie sorteren. 904 00:33:00,470 --> 00:33:03,070 Dus nogmaals, na te denken over wat we deed met de mensen hier. 905 00:33:03,070 --> 00:33:08,490 We gingen door de array en geselecteerd opnieuw het kleinste element, 906 00:33:08,490 --> 00:33:09,250 en opnieuw, en opnieuw. 907 00:33:09,250 --> 00:33:11,110 Nu ik beweren dat nog steeds vrij slecht was. 908 00:33:11,110 --> 00:33:15,010 Het was nog steeds n kwadraat, geven of te nemen, maar het was, in de echte wereld, wat 909 00:33:15,010 --> 00:33:18,280 sneller, want ik was inderdaad het nemen van iets minder stappen elke keer. 910 00:33:18,280 --> 00:33:19,800 Maar we praten alleen wat? 911 00:33:19,800 --> 00:33:21,830 Misschien 40 of zo bars hier? 912 00:33:21,830 --> 00:33:23,200 We praten niet 40 miljoen. 913 00:33:23,200 --> 00:33:27,430 Dus het is niet helemaal duidelijk voor mij dat was inderdaad een belangrijke aanwinst. 914 00:33:27,430 --> 00:33:32,530 >> Laat me nu terug te gaan en te veranderen naar onze derde algoritme, dat werd selecteer 915 00:33:32,530 --> 00:33:33,180 insertion sort. 916 00:33:33,180 --> 00:33:36,380 En nu is het echt buggy omdat de menu moet echt niet daar beneden. 917 00:33:36,380 --> 00:33:40,840 Dus nu zullen we hier terug te scrollen en start dit algoritme. 918 00:33:40,840 --> 00:33:43,270 Whoop, starten en stoppen. 919 00:33:43,270 --> 00:33:47,160 Dus deze ene soort heeft een mooi patroon om het, waardoor we weer 920 00:33:47,160 --> 00:33:50,240 inbrengen van de mens, of casu de staven in 921 00:33:50,240 --> 00:33:52,620 hun juiste locatie. 922 00:33:52,620 --> 00:33:55,430 En het is al eerder gedaan Ik draaide me om. 923 00:33:55,430 --> 00:33:58,940 Maar deze ook, in theorie, is nog steeds n kwadraat. 924 00:33:58,940 --> 00:34:01,430 >> Dus laten we kijken of we niet kunnen vatten deze als volgt. 925 00:34:01,430 --> 00:34:04,750 Ik ga om te gaan en gewoon te geven ons soort van een gemeenschappelijke manier van praten 926 00:34:04,750 --> 00:34:08,489 over deze dingen, laat me even gewoon een beetje notatie hier. 927 00:34:08,489 --> 00:34:12,480 Je staat op het punt om te zien iets groots geroepen O, omdat het letterlijk een grote 928 00:34:12,480 --> 00:34:16,320 O. En dit is een manier die een computer wetenschapper of een wiskundige zelfs gebruikt 929 00:34:16,320 --> 00:34:19,230 aan de lopende tijd beschrijven sommige algoritme. 930 00:34:19,230 --> 00:34:21,400 Hoeveel stappen werkt het eigenlijk nemen? 931 00:34:21,400 --> 00:34:25,080 >> Nu ga ik mezelf in verlegenheid te brengen met mijn handschrift hier in slechts een moment. 932 00:34:25,080 --> 00:34:29,020 Maar laat me gaan en zeggen dat Dit zal grote O zijn hierheen. 933 00:34:29,020 --> 00:34:33,610 En laat me even een andere symbool, een hoofdletter omega. 934 00:34:33,610 --> 00:34:37,080 Omega gaat het tegenovergestelde, wezen, van grote O. Overwegende grote O 935 00:34:37,080 --> 00:34:40,790 middelen, in het ergste geval, hoeveel tijd misschien wat algoritme te nemen, in 936 00:34:40,790 --> 00:34:43,480 termen van n, wordt omega gaat worden hoeveel tijd zou het 937 00:34:43,480 --> 00:34:45,409 nemen in het beste geval. 938 00:34:45,409 --> 00:34:48,090 En we zullen zien wat we bedoelen met best case in slechts een moment. 939 00:34:48,090 --> 00:34:49,940 >> Dus laten we beginnen met iets eenvoudigs. 940 00:34:49,940 --> 00:34:54,719 Laat ik beginnen met een lineaire zoekopdracht. 941 00:34:54,719 --> 00:34:55,679 Dus niet sorteren. 942 00:34:55,679 --> 00:34:58,000 We zullen deze lineaire zoekopdracht noemen. 943 00:34:58,000 --> 00:35:01,140 En nu, maak een beetje tabel uit deze. 944 00:35:01,140 --> 00:35:06,600 Nu, in het geval van lineaire search, in het ergste geval, hoeveel stappen is 945 00:35:06,600 --> 00:35:11,770 het gaat me naar een vondst aantal willekeurige keuze? 946 00:35:11,770 --> 00:35:14,540 En er is n totaal deuren of n totaal nummers. 947 00:35:14,540 --> 00:35:15,940 Worst case. 948 00:35:15,940 --> 00:35:18,800 Hoeveel stappen ga ik moeten naar het nummer 50 vinden in een array 949 00:35:18,800 --> 00:35:20,830 van n deuren? 950 00:35:20,830 --> 00:35:21,410 En waarom? 951 00:35:21,410 --> 00:35:23,680 Omdat het misschien wel alle weg over naar het einde. 952 00:35:23,680 --> 00:35:27,120 Zoveel als Jennifer ondervonden, de nummer 50 in was helemaal over, zodat 953 00:35:27,120 --> 00:35:30,760 het ergste geval lineaire zoekopdracht is big O van n, zullen we zeggen. 954 00:35:30,760 --> 00:35:33,430 >> Hoe zit het met het beste geval, als je echt geluk? 955 00:35:33,430 --> 00:35:36,200 Het gaat gewoon om een ​​stap te nemen, of een constant aantal stappen. 956 00:35:36,200 --> 00:35:37,830 Dus we dat omschrijven als 1. 957 00:35:37,830 --> 00:35:39,010 Dit is dus vrij goed. 958 00:35:39,010 --> 00:35:41,210 Nu, wat als we iets deden als binary search? 959 00:35:41,210 --> 00:35:43,860 960 00:35:43,860 --> 00:35:47,846 Dus binary search, in het slechtste geval, nam hoeveel tijd? 961 00:35:47,846 --> 00:35:49,250 >> [Onderbreekt hem VOICES] 962 00:35:49,250 --> 00:35:51,310 >> DAVID J. Malan: Dus eigenlijk, ik hoorde het in een paar plaatsen. 963 00:35:51,310 --> 00:35:56,390 Dus het is eigenlijk te loggen n, geven of te nemen, want zoals we verdelen de lijst in de helft 964 00:35:56,390 --> 00:36:00,730 opnieuw, en opnieuw, en opnieuw, zijn we in staat vinden, uiteindelijk, de waarde, 965 00:36:00,730 --> 00:36:04,750 Als het er is, maar er is een catch. 966 00:36:04,750 --> 00:36:08,590 Wat is de veronderstelling dat we moeten voor lief nemen voor binary search? 967 00:36:08,590 --> 00:36:09,700 Het moet worden gesorteerd. 968 00:36:09,700 --> 00:36:12,770 Het is niet gesorteerd, kunt u de zaak te splitsen in de helft opnieuw en opnieuw, en u 969 00:36:12,770 --> 00:36:15,490 kan naar links, en je kunt gelijk gaan, en je kunt gaan links en rechts, maar je bent 970 00:36:15,490 --> 00:36:18,070 niet van plan om het element indien vinden de lijst is niet gesorteerd, omdat de 971 00:36:18,070 --> 00:36:18,790 je zou missen. 972 00:36:18,790 --> 00:36:22,120 Omdat uw heuristische, voor het gaan naar links of rechts zal worden ontsierd als het 973 00:36:22,120 --> 00:36:23,420 inderdaad niet gesorteerd. 974 00:36:23,420 --> 00:36:26,110 Dus er is een soort van verborgen kosten om met behulp van iets als dit. 975 00:36:26,110 --> 00:36:29,250 >> Nu, laten we gaan in onze sortering algoritmen niet zoeken - 976 00:36:29,250 --> 00:36:31,140 oh, eigenlijk laten we gaan in deze blanco. 977 00:36:31,140 --> 00:36:33,190 Binair zoeken in het beste geval? 978 00:36:33,190 --> 00:36:36,290 Het is ook 1 als het gebeurt gewoon te zijn in het midden van de array, of 979 00:36:36,290 --> 00:36:37,810 het midden van het telefoonboek. 980 00:36:37,810 --> 00:36:39,710 Laten we nu een bubble sort. 981 00:36:39,710 --> 00:36:42,570 Dus nogmaals, nu zijn we het invoeren van de soorten, niet de zoekopdrachten. 982 00:36:42,570 --> 00:36:47,220 >> In het ergste geval, hoeveel stappen deden we vordering bubble sort gaat duren? 983 00:36:47,220 --> 00:36:48,410 n kwadraat. 984 00:36:48,410 --> 00:36:49,200 Dus ik ga om te tekenen dat. 985 00:36:49,200 --> 00:36:51,710 Ooh, mijn handschrift ziet er nog slechter wanneer het wordt voorspeld dat grote. 986 00:36:51,710 --> 00:36:52,510 Oke. 987 00:36:52,510 --> 00:36:53,570 Dus dat is n kwadraat. 988 00:36:53,570 --> 00:36:59,460 En in het beste geval van bubble sort, hoeveel stappen gaat dat duren? 989 00:36:59,460 --> 00:37:00,980 1, hoorde ik. 990 00:37:00,980 --> 00:37:01,760 >> LUIDSPREKER 1: n. 991 00:37:01,760 --> 00:37:03,286 >> DAVID J. MALAN: n, hoorde ik. 992 00:37:03,286 --> 00:37:04,200 >> LUIDSPREKER 1: 2. 993 00:37:04,200 --> 00:37:05,010 >> DAVID J. MALAN: 2, hoorde ik. 994 00:37:05,010 --> 00:37:06,670 Hoor ik 3? 995 00:37:06,670 --> 00:37:07,080 Oke. 996 00:37:07,080 --> 00:37:11,390 Dus ik heb gehoord 1, n, 2, maar laten plukken elkaar ten minste de eerste van deze 997 00:37:11,390 --> 00:37:12,330 suggesties 1. 998 00:37:12,330 --> 00:37:15,370 Het is geen slechte instinct, want het soort volgt een patroon hier. 999 00:37:15,370 --> 00:37:19,670 Maar als het duurt maar 1 stap, hoe in de wereld kon ik beweren dat de lijst 1000 00:37:19,670 --> 00:37:22,900 wordt gesorteerd, want als ik alleen toegestaan tot en met 1 stap, hoeveel elementen nemen 1001 00:37:22,900 --> 00:37:25,230 kon ik eigenlijk controleren om er zeker van? 1002 00:37:25,230 --> 00:37:28,270 Nou ja, gewoon 1, wat betekent dat er n minus 1 elementen die kunnen worden uit 1003 00:37:28,270 --> 00:37:31,310 orde, en ik ben gewoon gaan over het geloof na bekeken 1 element dat de 1004 00:37:31,310 --> 00:37:31,850 ding wordt gesorteerd. 1005 00:37:31,850 --> 00:37:33,930 Dus 1 is hier niet te corrigeren. 1006 00:37:33,930 --> 00:37:35,710 Dus minimaal, hoeveel moet ik naar kijken? 1007 00:37:35,710 --> 00:37:36,680 >> [Onderbreekt hem VOICES] 1008 00:37:36,680 --> 00:37:40,160 >> DAVID J. Malan: n minus 1, of eigenlijk, n, want ik moet kijken naar elke 1009 00:37:40,160 --> 00:37:42,190 element ervoor zorgen dat het is niet in de juiste volgorde. 1010 00:37:42,190 --> 00:37:44,750 Maar nogmaals, we soort van wave onze handen bij de kleinere aantallen en 1011 00:37:44,750 --> 00:37:47,100 gaan ervan uit dat, als n groot wordt, zijn ze oninteressant toch. 1012 00:37:47,100 --> 00:37:48,380 Dus dat is bubble sort. 1013 00:37:48,380 --> 00:37:49,830 En nu, laten we deze laatste twee. 1014 00:37:49,830 --> 00:37:53,520 Selectie sorteren, en dan zullen we doen insertion sort. 1015 00:37:53,520 --> 00:37:57,160 En dan zullen wij uw blazen geest met iets veel 1016 00:37:57,160 --> 00:37:58,926 beter dan deze. 1017 00:37:58,926 --> 00:38:00,410 Oke. 1018 00:38:00,410 --> 00:38:04,700 >> Wat is het ergste geval loopt tijdstip van de selectie sorteren? 1019 00:38:04,700 --> 00:38:05,680 >> SPEAKER 4: n kwadraat. 1020 00:38:05,680 --> 00:38:06,710 >> DAVID J. Malan: n vierkant, ik hoor. 1021 00:38:06,710 --> 00:38:09,790 Maar waarom n kwadraat, intuïtief? 1022 00:38:09,790 --> 00:38:11,170 >> SPEAKER 4: Omdat we deden het gewoon. 1023 00:38:11,170 --> 00:38:12,260 >> DAVID J. Malan: Omdat we deden het gewoon. 1024 00:38:12,260 --> 00:38:12,550 OK. 1025 00:38:12,550 --> 00:38:13,380 Goed antwoord. 1026 00:38:13,380 --> 00:38:16,660 Maar intuïtief, waarom is selectie sorteer n kwadraat? 1027 00:38:16,660 --> 00:38:18,980 Wat hebben we moeten doen opnieuw en opnieuw? 1028 00:38:18,980 --> 00:38:22,570 We moesten scannen via te houden, zijn u de kleinste, bent u de 1029 00:38:22,570 --> 00:38:24,020 kleinste, bent u de kleinste. 1030 00:38:24,020 --> 00:38:27,480 En verleend, waren we in staat om n te nemen stappen, dan n minus 1, dan is n minus 2. 1031 00:38:27,480 --> 00:38:30,700 Maar als je soort die allemaal optellen, of neem het op het geloof dat ik heb toegevoegd 1032 00:38:30,700 --> 00:38:34,810 ze van tevoren, krijgen we grofweg n kwadraat minus enkele kleinere aantallen. 1033 00:38:34,810 --> 00:38:36,730 Dus ik ga dit n kwadraat noemen. 1034 00:38:36,730 --> 00:38:39,530 Maar met de selectie sorteren in de beste geval is, hoeveel stappen is het 1035 00:38:39,530 --> 00:38:40,632 gaat me te nemen? 1036 00:38:40,632 --> 00:38:41,840 >> SPEAKER 5: [onverstaanbaar] 1037 00:38:41,840 --> 00:38:44,350 >> DAVID J. Malan: Het is helaas nog n kwadraat, toch? 1038 00:38:44,350 --> 00:38:49,590 Want als ik de keuze van de kleinste element, en we hadden zeven mensen hier, 1039 00:38:49,590 --> 00:38:53,280 Ik weet alleen, zodra ik aan de zeer einde, dat ik heb de kleinste gevonden 1040 00:38:53,280 --> 00:38:55,670 nummer, waar hij of ze kan zijn. 1041 00:38:55,670 --> 00:38:58,820 Maar hoe kan ik het volgende vinden kleinste getal? 1042 00:38:58,820 --> 00:39:00,160 Ik moet nog een keer doen. 1043 00:39:00,160 --> 00:39:04,810 Dus in het beste geval, wat is de input voor selectie sorteren? 1044 00:39:04,810 --> 00:39:07,830 Het is een reeds soort lijst, nummer een, nummer twee, nummer drie, nummer vier. 1045 00:39:07,830 --> 00:39:08,600 Maar ik ben een computer. 1046 00:39:08,600 --> 00:39:10,190 Ik kan alleen maar kijken naar een ding tegelijk. 1047 00:39:10,190 --> 00:39:12,465 Ik kan niet sorteren van een stap terug als een mens en zeggen: 1048 00:39:12,465 --> 00:39:14,030 ooh, dit ziet er correct. 1049 00:39:14,030 --> 00:39:17,580 >> Ik kan alleen maar oordelen correctheid in selectie sorteren door het selecteren van de 1050 00:39:17,580 --> 00:39:18,370 kleinste getal. 1051 00:39:18,370 --> 00:39:21,390 Maar zelfs als ik vind nummer een eerste, als ik niet iets anders over weten 1052 00:39:21,390 --> 00:39:24,460 de andere nummers, wat ik niet doe, alles wat ik weten dat ik heb ingeleverd een array 1053 00:39:24,460 --> 00:39:27,930 of een stel deuren waarachter nummers, de enige manier waarop ik weet dat een 1054 00:39:27,930 --> 00:39:28,680 was de kleinste? 1055 00:39:28,680 --> 00:39:32,440 Als ik helemaal hier en realiseren, damn, was inderdaad het kleinst. 1056 00:39:32,440 --> 00:39:34,870 >> Maar hoe kan ik dan bepalen dat twee is de volgende kleinste? 1057 00:39:34,870 --> 00:39:38,350 Door hetzelfde te doen inefficiëntie weer. 1058 00:39:38,350 --> 00:39:42,210 Dus eindelijk, met insertion sort, hoe, in het ergste geval, 1059 00:39:42,210 --> 00:39:44,990 hadden we het zeggen presteert? 1060 00:39:44,990 --> 00:39:49,100 Het ook is n kwadraat. 1061 00:39:49,100 --> 00:39:53,020 En hoe zit het met de beste zaak? 1062 00:39:53,020 --> 00:39:56,282 We laten dat als een cliffhanger. 1063 00:39:56,282 --> 00:40:00,090 We zullen in die lege volgende keer vullen, maar eerst laat ik stel voor dat we 1064 00:40:00,090 --> 00:40:02,620 fundamenteel beter doen dan al deze, oke? 1065 00:40:02,620 --> 00:40:05,220 >> Dus denk zelf wat inbrengen soort gaat worden. 1066 00:40:05,220 --> 00:40:06,910 Nou, dat was niet erg dramatisch, want ik ben de enige 1067 00:40:06,910 --> 00:40:08,970 dat zag de verandering. 1068 00:40:08,970 --> 00:40:09,620 Wow. 1069 00:40:09,620 --> 00:40:10,420 OK. 1070 00:40:10,420 --> 00:40:12,615 Dus hier hebben we een wat verschillende demonstratie. 1071 00:40:12,615 --> 00:40:16,580 Als ik in te zoomen hier, zult u zien dat op de linkerkant hebben we bubble sort, in de 1072 00:40:16,580 --> 00:40:20,740 midden hebben we selectie sorteren, en op Uiterst rechts, we iets hebben wij 1073 00:40:20,740 --> 00:40:23,380 heb niet gekeken naar nog riep samenvoegen sorteren. 1074 00:40:23,380 --> 00:40:26,080 Maar nadenken over wat we hebben hier tot nu toe vandaag. 1075 00:40:26,080 --> 00:40:29,200 Toen Jennifer kwam voor het eerst op het podium, We gingen door de matrix van getallen 1076 00:40:29,200 --> 00:40:33,750 opnieuw, en opnieuw, met lineaire zoeken, en we kregen lineaire lopende tijd, big O 1077 00:40:33,750 --> 00:40:35,100 van n, zo te zeggen. 1078 00:40:35,100 --> 00:40:41,000 >> Wanneer beschouwen we de eerste week van klasse, toen we hadden verdeel en heers, 1079 00:40:41,000 --> 00:40:43,740 en we hadden het telefoonboek scheuren, en Jennifer, en we collectief 1080 00:40:43,740 --> 00:40:47,500 leveraged dat belangrijk inzicht, dat was om steeds weer herhalen jezelf door 1081 00:40:47,500 --> 00:40:50,930 een of andere manier weg te gooien, weg te gooien, weggooien, de helft van het probleem of 1082 00:40:50,930 --> 00:40:55,320 algemeen, delen een probleem in half, en vervolgens behandelen van de kleinere stuk 1083 00:40:55,320 --> 00:40:59,630 het probleem als conceptueel gelijkwaardig de andere, we hebben ergens 1084 00:40:59,630 --> 00:41:00,910 fundamenteel beter. 1085 00:41:00,910 --> 00:41:04,720 Maar met bubble sort, met selectie soort, met insertion sort, hebben we kunnen 1086 00:41:04,720 --> 00:41:06,560 geen dergelijke inzichten die Jennifer deed. 1087 00:41:06,560 --> 00:41:10,220 We vrijwel alleen liep terug en weer een hele hoop tijd, en we 1088 00:41:10,220 --> 00:41:12,650 tweaked dingen een beetje, ruilen in deze volgorde, misschien 1089 00:41:12,650 --> 00:41:13,730 invoegen of selecteren. 1090 00:41:13,730 --> 00:41:16,950 Maar aan het eind van de dag, heb ik veel van onhandige lopen heen en weer. 1091 00:41:16,950 --> 00:41:21,160 We hebben niet echt iets leverage smart als Jennifer deed zoals het verdelen 1092 00:41:21,160 --> 00:41:22,040 en veroveren. 1093 00:41:22,040 --> 00:41:25,620 >> Dus samenvoegen sorteren, daarentegen, waardoor we zal niet te zien tot volgende week, het gaat 1094 00:41:25,620 --> 00:41:29,540 om gebruik te maken dat de belangrijkste idee door te delen de ingang, en dan halveren, en vervolgens 1095 00:41:29,540 --> 00:41:30,580 halveren, en dan halveren. 1096 00:41:30,580 --> 00:41:34,590 En elke iteratie van de loop, sorteren van de linkerhelft en de juiste 1097 00:41:34,590 --> 00:41:38,200 helft, dan de linkerhelft van linkerdeel en de rechterhelft van de linker, dan 1098 00:41:38,200 --> 00:41:40,990 de linkerhelft van de rechterhelft en de rechterhelft van de rechterhelft. 1099 00:41:40,990 --> 00:41:42,840 En het herhalen weer. 1100 00:41:42,840 --> 00:41:46,170 >> Dus zie je dit visueel te zien, maar dit is wat ons te wachten staat volgende week. 1101 00:41:46,170 --> 00:41:49,760 En in het algemeen, als we denken een beetje beetje harder op dergelijke problemen. 1102 00:41:49,760 --> 00:41:52,435 1103 00:41:52,435 --> 00:41:57,970 We n kwadraat links, n kwadraat in het midden, en n 1104 00:41:57,970 --> 00:41:59,400 log n aan de rechterkant. 1105 00:41:59,400 --> 00:42:00,590 Dus er is je echte cliffhanger. 1106 00:42:00,590 --> 00:42:02,040 We zien je op maandag. 1107 00:42:02,040 --> 00:42:05,163 >> [Applaus]