1 00:00:00,000 --> 00:00:00,990 2 00:00:00,990 --> 00:00:02,970 >> [MUSIC JOC] 3 00:00:02,970 --> 00:00:10,400 4 00:00:10,400 --> 00:00:12,550 >> David J. MALAN: Aceasta este CS50. 5 00:00:12,550 --> 00:00:14,612 Și aceasta este începutul săptămânii trei. 6 00:00:14,612 --> 00:00:16,820 Deci avem o mulțime de interesant lucruri pentru a acoperi astăzi. 7 00:00:16,820 --> 00:00:20,160 O mulțime de oportunități pentru voluntari pe scena. 8 00:00:20,160 --> 00:00:22,780 Și în cele din urmă, astăzi este nu despre codul deloc. 9 00:00:22,780 --> 00:00:24,820 Dar este vorba despre idei, și este vorba despre algoritmi, 10 00:00:24,820 --> 00:00:28,420 și de fapt, aducerea înapoi o parte din lecțiile învățate din săptămână la zero, 11 00:00:28,420 --> 00:00:31,910 care amintesc, am a introdus acest monstruozitate. 12 00:00:31,910 --> 00:00:33,880 Și inspirație de împrumut la care, pentru a începe 13 00:00:33,880 --> 00:00:36,879 pentru a rezolva tot mai sofisticate Probleme algoritmic. 14 00:00:36,879 --> 00:00:38,420 Dar mai întâi, o pereche de anunțuri. 15 00:00:38,420 --> 00:00:42,020 Deci unul, dacă doriți să se alăture Personal și colegii lui la pranz CS50 16 00:00:42,020 --> 00:00:44,670 vineri, atât aici, cât și în Cambridge, și în New Haven, 17 00:00:44,670 --> 00:00:48,060 va rugam sa vizitati cursului site, în cazul în care un URL poate fi găsită. 18 00:00:48,060 --> 00:00:50,390 Curs miercuri va să nu fie aici, în Sanders. 19 00:00:50,390 --> 00:00:53,610 Acesta va fi doar online, astfel încât tune în la site-ul CS50 lui, 20 00:00:53,610 --> 00:00:55,850 dacă aici în Cambridge sau New Haven, de asemenea. 21 00:00:55,850 --> 00:00:58,110 >> Și apoi problemă stabilit două este deja în mâinile tale. 22 00:00:58,110 --> 00:01:03,067 Dacă nu ați scufundat încă, permiteți-mi pentru a oferi sugestia puternic cuprins 23 00:01:03,067 --> 00:01:05,150 că, mai ales acum, ca problema seturi avans, 24 00:01:05,150 --> 00:01:08,669 tu chiar nu doriți să începeți acum, dacă nu se ocupa un pic pe week-end sau înainte 25 00:01:08,669 --> 00:01:10,710 atunci când merg în primul rând pe Vineri, pentru că veți 26 00:01:10,710 --> 00:01:14,380 constată că ei nu sunt în mod necesar obtinerea mai sau mai provocatoare pe 27 00:01:14,380 --> 00:01:14,950 se. 28 00:01:14,950 --> 00:01:17,575 Cred că veți descoperi că, în general, ele tind să ia aproximativ 29 00:01:17,575 --> 00:01:18,892 în jurul valorii de aceeași perioadă de timp. 30 00:01:18,892 --> 00:01:20,850 Dar aceasta depinde cu siguranță pe student, și 31 00:01:20,850 --> 00:01:22,880 depinde de mentalitatea cu care l-ați apropie. 32 00:01:22,880 --> 00:01:24,910 Dar invariabil, te duci pentru a rula împotriva unele perete, 33 00:01:24,910 --> 00:01:26,350 și ai de gând să lovi unele bug, si tu esti doar 34 00:01:26,350 --> 00:01:27,950 nu va fi în măsură să treci peste asta la un moment dat. 35 00:01:27,950 --> 00:01:31,380 Și este extrem de valoros pentru a putea la pasul departe, întoarce a doua zi, 36 00:01:31,380 --> 00:01:35,286 du-te la ore de birou, post pe CS50 Discuta sau altele asemenea, pentru a obține de fapt, deblocat. 37 00:01:35,286 --> 00:01:36,160 Astfel încât să păstreze în minte. 38 00:01:36,160 --> 00:01:40,830 Incepand mai devreme posibil este cel mai bun lucru care le puteți face. 39 00:01:40,830 --> 00:01:44,160 Deci, aici e unde am plecat clasa, peste in saptamana zero. 40 00:01:44,160 --> 00:01:47,441 Și putem obține un voluntar aici să mă ajute să găsească microfoane? 41 00:01:47,441 --> 00:01:47,940 BINE. 42 00:01:47,940 --> 00:01:48,900 Picioare deja. 43 00:01:48,900 --> 00:01:50,080 Haide sus. 44 00:01:50,080 --> 00:01:53,707 Cred că e modul în care aceasta va funcționa. 45 00:01:53,707 --> 00:01:54,415 Care e numele tău? 46 00:01:54,415 --> 00:01:55,570 ALAN ESTRADA: Alan Estrada. 47 00:01:55,570 --> 00:01:56,778 David J. MALAN: Alan Estrada. 48 00:01:56,778 --> 00:01:57,910 Haide sus. 49 00:01:57,910 --> 00:01:58,619 Îmi pare bine să te cunosc. 50 00:01:58,619 --> 00:01:59,910 ALAN ESTRADA: Mă bucur să te cunosc. 51 00:01:59,910 --> 00:02:02,772 David J. MALAN: Și tu erai aici cu noi în săptămâna zero desigur. 52 00:02:02,772 --> 00:02:03,028 ALAN ESTRADA: Am fost. 53 00:02:03,028 --> 00:02:03,160 Am fost. 54 00:02:03,160 --> 00:02:05,868 >> David J. MALAN: Deci ar putea merge înainte și de a găsi pentru noi Mike Smith, 55 00:02:05,868 --> 00:02:08,639 la fel de repede ca tine poate? 56 00:02:08,639 --> 00:02:10,639 La fel de repede ca tine poate. 57 00:02:10,639 --> 00:02:13,756 Ruperea literalmente problema în jumătate ca ai nevoie sa. 58 00:02:13,756 --> 00:02:15,130 >> ALAN ESTRADA: Um. 59 00:02:15,130 --> 00:02:17,380 David J. MALAN: Literalmente ruperea problema în jumătate. 60 00:02:17,380 --> 00:02:20,210 61 00:02:20,210 --> 00:02:22,083 >> ALAN ESTRADA: Oh. 62 00:02:22,083 --> 00:02:22,583 Mm. 63 00:02:22,583 --> 00:02:23,300 Foarte bine. 64 00:02:23,300 --> 00:02:23,700 >> David J. MALAN: OK. 65 00:02:23,700 --> 00:02:24,200 Bine. 66 00:02:24,200 --> 00:02:24,701 Multumesc. 67 00:02:24,701 --> 00:02:25,700 ALAN ESTRADA: Foarte bine. 68 00:02:25,700 --> 00:02:26,210 BINE. 69 00:02:26,210 --> 00:02:27,610 >> David J. MALAN: Și așa acum, le-ați diminuate până 70 00:02:27,610 --> 00:02:29,320 la jumătate din dimensiunea problemei. 71 00:02:29,320 --> 00:02:31,267 Acum, suntem în jos la un sfert. 72 00:02:31,267 --> 00:02:33,475 Ești atent la care parte suntem păstrarea? 73 00:02:33,475 --> 00:02:34,405 >> [Rîzînd] 74 00:02:34,405 --> 00:02:35,970 >> ALAN ESTRADA: Da, am think-- 75 00:02:35,970 --> 00:02:37,594 >> David J. MALAN: Ce secțiune suntem in? 76 00:02:37,594 --> 00:02:39,150 ALAN ESTRADA: Amortizoare, așa. 77 00:02:39,150 --> 00:02:39,941 >> David J. MALAN: OK. 78 00:02:39,941 --> 00:02:42,810 Dar Mike Smith este de gând să fie după Amortizoare. 79 00:02:42,810 --> 00:02:44,130 Asa ca-- 80 00:02:44,130 --> 00:02:48,180 >> [Rîzînd] 81 00:02:48,180 --> 00:02:48,742 >> In regula. 82 00:02:48,742 --> 00:02:50,200 ALAN ESTRADA: În cazul în care ne uităm? 83 00:02:50,200 --> 00:02:52,049 David J. MALAN: Mike Smith. 84 00:02:52,049 --> 00:02:53,090 ALAN ESTRADA: Mike Smith. 85 00:02:53,090 --> 00:02:54,760 David J. MALAN: Acum, suntem în chirurgicale. 86 00:02:54,760 --> 00:02:57,840 Acum, medicii. 87 00:02:57,840 --> 00:02:58,340 Now-- 88 00:02:58,340 --> 00:02:59,856 >> ALAN ESTRADA: Let's- să mergem cu adevărat. 89 00:02:59,856 --> 00:03:00,370 Real. 90 00:03:00,370 --> 00:03:00,970 >> David J. MALAN: Real. 91 00:03:00,970 --> 00:03:01,470 BINE. 92 00:03:01,470 --> 00:03:03,700 Dacă aveți nevoie de Real. 93 00:03:03,700 --> 00:03:05,250 Acum, ce fel este Mike Smith? 94 00:03:05,250 --> 00:03:06,250 >> ALAN ESTRADA: acest fel. 95 00:03:06,250 --> 00:03:07,333 >> David J. MALAN: Care drum? 96 00:03:07,333 --> 00:03:08,240 ALAN ESTRADA: Stai. 97 00:03:08,240 --> 00:03:08,790 M este-- corect? 98 00:03:08,790 --> 00:03:09,110 Am început aplice: 99 00:03:09,110 --> 00:03:10,090 >> David J. MALAN: Da. 100 00:03:10,090 --> 00:03:10,650 Sunt plecat. 101 00:03:10,650 --> 00:03:11,430 Dreapta ta. 102 00:03:11,430 --> 00:03:11,710 >> ALAN ESTRADA: Da. 103 00:03:11,710 --> 00:03:13,126 >> David J. MALAN: Deci lui Mike aici. 104 00:03:13,126 --> 00:03:13,990 ALAN ESTRADA: Ce? 105 00:03:13,990 --> 00:03:14,665 >> [Rîzînd] 106 00:03:14,665 --> 00:03:17,365 107 00:03:17,365 --> 00:03:18,330 >> Bad exemplu, băieți. 108 00:03:18,330 --> 00:03:18,830 Scuze. 109 00:03:18,830 --> 00:03:21,610 David J. MALAN: Aceasta va învăța să sari din scaun. 110 00:03:21,610 --> 00:03:22,318 >> ALAN ESTRADA: Oh. 111 00:03:22,318 --> 00:03:22,890 Oh. 112 00:03:22,890 --> 00:03:23,390 Te-am prins. 113 00:03:23,390 --> 00:03:24,670 Te-am prins. 114 00:03:24,670 --> 00:03:25,170 Oh. 115 00:03:25,170 --> 00:03:25,669 Oh. 116 00:03:25,669 --> 00:03:26,812 Acest este-- OK, te-am prins. 117 00:03:26,812 --> 00:03:27,520 Smith aici? 118 00:03:27,520 --> 00:03:28,894 >> David J. MALAN: Smith, vă mulțumesc. 119 00:03:28,894 --> 00:03:30,535 Așa că voi ține uita în sus Smith? 120 00:03:30,535 --> 00:03:30,790 >> ALAN ESTRADA: Oh, da. 121 00:03:30,790 --> 00:03:31,340 Nu Nu NU. 122 00:03:31,340 --> 00:03:31,600 Oh nu. 123 00:03:31,600 --> 00:03:31,940 Aceasta este a mea. 124 00:03:31,940 --> 00:03:32,580 >> David J. MALAN: Oh, ai Smith. 125 00:03:32,580 --> 00:03:33,415 BINE. 126 00:03:33,415 --> 00:03:34,040 >> ALAN ESTRADA: Da, am ajuns Smith chiar aici. 127 00:03:34,040 --> 00:03:34,700 Îmi pare rău, băieți. 128 00:03:34,700 --> 00:03:35,860 M-am gândit Michael-- ne au fost cautati pentru Michael. 129 00:03:35,860 --> 00:03:36,550 Scuze. 130 00:03:36,550 --> 00:03:37,550 >> David J. MALAN: E OK. 131 00:03:37,550 --> 00:03:39,950 Bine, acum suntem în Paccini and Sons. 132 00:03:39,950 --> 00:03:41,242 >> ALAN ESTRADA: Paccini și fiii. 133 00:03:41,242 --> 00:03:43,158 David J. MALAN: Doar tu și cu mine suntem în asta. 134 00:03:43,158 --> 00:03:44,050 BINE. 135 00:03:44,050 --> 00:03:45,130 Găsiți-ne Mike Smith. 136 00:03:45,130 --> 00:03:45,830 Smith. 137 00:03:45,830 --> 00:03:46,310 >> ALAN ESTRADA: Smith. 138 00:03:46,310 --> 00:03:46,750 >> David J. MALAN: Smith. 139 00:03:46,750 --> 00:03:47,728 Suntem în R pentru gunoi. 140 00:03:47,728 --> 00:03:48,644 ALAN ESTRADA: gunoi. 141 00:03:48,644 --> 00:03:50,096 Oh. 142 00:03:50,096 --> 00:03:52,480 Acest lucru se va lua un timp. 143 00:03:52,480 --> 00:03:54,340 >> [Rîzînd] 144 00:03:54,340 --> 00:03:55,804 145 00:03:55,804 --> 00:03:56,720 David J. MALAN: incaltaminte. 146 00:03:56,720 --> 00:03:58,080 Suntem în pantofi. 147 00:03:58,080 --> 00:04:00,210 >> ALAN ESTRADA: Acum suntem gonna-- 148 00:04:00,210 --> 00:04:01,105 >> David J. MALAN: Nisa. 149 00:04:01,105 --> 00:04:01,980 ALAN ESTRADA: Which-- 150 00:04:01,980 --> 00:04:03,620 [Rîzînd] 151 00:04:03,620 --> 00:04:05,440 Oh, acest lucru este mare. 152 00:04:05,440 --> 00:04:06,910 [Rîzînd] 153 00:04:06,910 --> 00:04:08,380 154 00:04:08,380 --> 00:04:09,390 >> David J. MALAN: E OK. 155 00:04:09,390 --> 00:04:11,365 >> ALAN ESTRADA: Oh, acest lucru este bun. 156 00:04:11,365 --> 00:04:14,425 Nu cred că am de gând să au prieteni PSAT după asta. 157 00:04:14,425 --> 00:04:15,300 David J. MALAN: Bine. 158 00:04:15,300 --> 00:04:16,078 Sporting. 159 00:04:16,078 --> 00:04:17,036 ALAN ESTRADA: Sporting. 160 00:04:17,036 --> 00:04:18,668 Um, L, M, N, O, P. 161 00:04:18,668 --> 00:04:19,459 David J. MALAN: OK. 162 00:04:19,459 --> 00:04:21,600 Așa că haideți să rupe acest în jumătate. 163 00:04:21,600 --> 00:04:22,270 E bine. 164 00:04:22,270 --> 00:04:25,606 Acest lucru se termină prost oricum, pentru că Mike Smith nu va fi în paginile galbene. 165 00:04:25,606 --> 00:04:26,430 >> ALAN ESTRADA: Aw. 166 00:04:26,430 --> 00:04:27,140 >> David J. MALAN: Nu, e în regulă. 167 00:04:27,140 --> 00:04:28,930 Dar să pretindem ca e de pe această pagină. 168 00:04:28,930 --> 00:04:33,260 Deci, acum, ai diminuate problema jos la o pagină, și am găsit pe Mike Smith. 169 00:04:33,260 --> 00:04:35,180 >> [Aplauze] 170 00:04:35,180 --> 00:04:35,757 171 00:04:35,757 --> 00:04:36,340 Bine multumesc. 172 00:04:36,340 --> 00:04:40,700 173 00:04:40,700 --> 00:04:41,200 BINE. 174 00:04:41,200 --> 00:04:43,646 Asta a fost extraordinar. 175 00:04:43,646 --> 00:04:45,954 Dar era încă mai rapid decât căutarea liniară, 176 00:04:45,954 --> 00:04:47,870 în care vom începe de la începutul cărții, 177 00:04:47,870 --> 00:04:51,210 și ne-am muta modul nostru de la stânga la dreapta, în cele din urmă în căutarea Mike Smith. 178 00:04:51,210 --> 00:04:53,540 Și astfel, în cazul în care cartea de telefon a avut, poate, 1.000 de pagini, 179 00:04:53,540 --> 00:04:56,300 Poate că ar fi luat ne 10 sau cam asa ceva de pagini lacrimi. 180 00:04:56,300 --> 00:04:59,380 >> Dar este posibil să fi efect de levier atins o presupunere 181 00:04:59,380 --> 00:05:03,602 în timpul toate acestea, ceea ce este de a spune că cartea de telefon în prealabil a fost ce? 182 00:05:03,602 --> 00:05:04,310 Audiența: Sortat. 183 00:05:04,310 --> 00:05:05,000 David J. MALAN: E sortate. 184 00:05:05,000 --> 00:05:05,160 Dreapta? 185 00:05:05,160 --> 00:05:07,909 Este sortate în ordine alfabetică, astfel încât că toate aceste nume și numere 186 00:05:07,909 --> 00:05:11,230 sunt clasificate în funcție de A la Lui Z, și în ordine alfabetică în între. 187 00:05:11,230 --> 00:05:13,100 Dar astăzi, acum cerem întrebarea, bine, 188 00:05:13,100 --> 00:05:16,170 cum a făcut Verizon sau telefonul companie-l în această stare? 189 00:05:16,170 --> 00:05:19,560 >> Pentru că e un lucru să impulsioneze această presupunere, și prin urmare, 190 00:05:19,560 --> 00:05:22,570 rezolva o problemă cu un algoritm mai eficient. 191 00:05:22,570 --> 00:05:24,900 Dar noi niciodată cu adevărat întrebă în săptămâna zero,, ei bine, 192 00:05:24,900 --> 00:05:27,790 cât de mult a costat Verizon sau altcineva 193 00:05:27,790 --> 00:05:29,620 pentru a obține cartea de telefon, pentru sortat? 194 00:05:29,620 --> 00:05:29,780 >> Dreapta? 195 00:05:29,780 --> 00:05:31,529 Nu contează dacă uita în sus Mike Smith 196 00:05:31,529 --> 00:05:35,190 este super rapid, în cazul în care aveți nevoie de un an pentru a sorta paginile inițial. 197 00:05:35,190 --> 00:05:35,690 Dreapta? 198 00:05:35,690 --> 00:05:38,620 Ai putea la fel de bine doar trece printr-o carte de telefon randomizat, 199 00:05:38,620 --> 00:05:40,690 în cazul în care va fi super- scump să-l sorta. 200 00:05:40,690 --> 00:05:42,350 Deci, dacă putem avea un alt voluntar. 201 00:05:42,350 --> 00:05:46,350 Să aruncăm o privire aici la cum ne-am might-- haide up-- cum 202 00:05:46,350 --> 00:05:48,100 am putea merge despre sortarea acestora. 203 00:05:48,100 --> 00:05:51,990 >> Și dacă Jordan ar putea de fapt alaturi de noi aici pe scenă. 204 00:05:51,990 --> 00:05:55,100 Haide pentru o clipă. 205 00:05:55,100 --> 00:05:56,359 Care e numele tău? 206 00:05:56,359 --> 00:05:57,150 CAROLINE: Caroline. 207 00:05:57,150 --> 00:05:58,691 David J. MALAN: Caroline, haide sus. 208 00:05:58,691 --> 00:06:02,070 Și veți fi uniți de mine și Iordania aici. 209 00:06:02,070 --> 00:06:03,800 Caroline, vă mulțumesc. 210 00:06:03,800 --> 00:06:04,300 In regula. 211 00:06:04,300 --> 00:06:08,330 Deci, ce avem aici pentru Caroline este de 26 de cărți albastre 212 00:06:08,330 --> 00:06:10,747 care FAS foloseste pentru a administra anumite examene finale. 213 00:06:10,747 --> 00:06:13,330 Acestea devin greu de găsit, dar ceea ce am făcut în prealabil 214 00:06:13,330 --> 00:06:15,800 este că ne-am pus numele cuiva pe partea din față a fiecăruia dintre aceste, 215 00:06:15,800 --> 00:06:18,133 dar am păstrat-l simplu de apoi punerea în numele complete. 216 00:06:18,133 --> 00:06:22,720 Asa ca am ar pune persoana cu numele L, D, J, B, tot drumul la A la Z, 217 00:06:22,720 --> 00:06:24,090 dar sunt în ordine aleatorie. 218 00:06:24,090 --> 00:06:26,890 Și așa că, dacă ar fi, vorbind dvs. drum prin problema ca tine 219 00:06:26,890 --> 00:06:31,620 Do It, poate merge mai departe și sorta aceste pentru noi, de la A la Z. 220 00:06:31,620 --> 00:06:34,070 >> Audiența: OK, deci L este ca, la mijloc. 221 00:06:34,070 --> 00:06:35,050 C începe. 222 00:06:35,050 --> 00:06:42,410 B. J înainte L. B, Q. 223 00:06:42,410 --> 00:06:45,140 >> David J. MALAN: Ține care gândit pentru o secundă. 224 00:06:45,140 --> 00:06:48,910 Deoarece în caz contrar, aceasta este doar interesant pentru tine, mă, și Iordania. 225 00:06:48,910 --> 00:06:49,724 Nu mergem. 226 00:06:49,724 --> 00:06:50,640 Audiența: [neauzit]. 227 00:06:50,640 --> 00:06:57,299 R. 228 00:06:57,299 --> 00:06:58,090 David J. MALAN: OK. 229 00:06:58,090 --> 00:06:59,310 Ce faci? 230 00:06:59,310 --> 00:07:01,730 >> CAROLINE: M vine după O. 231 00:07:01,730 --> 00:07:02,564 >> David J. MALAN: OK. 232 00:07:02,564 --> 00:07:03,064 >> CAROLINE: O. 233 00:07:03,064 --> 00:07:04,120 David J. MALAN: O, bine. 234 00:07:04,120 --> 00:07:04,970 >> CAROLINE: E. 235 00:07:04,970 --> 00:07:06,730 >> David J. MALAN: E, F. Da. 236 00:07:06,730 --> 00:07:07,620 >> CAROLINE: T, U, V 237 00:07:07,620 --> 00:07:10,689 >> David J. MALAN: V, T, U, V Deci, se pare ca esti making-- continui. 238 00:07:10,689 --> 00:07:12,730 Se pare că faci o gramada mare aici, 239 00:07:12,730 --> 00:07:13,910 și un fel de o grămadă mare acolo. 240 00:07:13,910 --> 00:07:16,230 Deci prima jumătate a alfabetului, a doua jumătate a alfabetului. 241 00:07:16,230 --> 00:07:16,460 BINE. 242 00:07:16,460 --> 00:07:16,960 Bine. 243 00:07:16,960 --> 00:07:19,680 Un fel de divizare a problemei în două. 244 00:07:19,680 --> 00:07:21,771 M, N, X. Da. 245 00:07:21,771 --> 00:07:22,270 CAROLINE: K. 246 00:07:22,270 --> 00:07:22,980 David J. MALAN: OK. 247 00:07:22,980 --> 00:07:25,070 K. Deci un fel de selectare le una după alta, 248 00:07:25,070 --> 00:07:27,620 inscrie fie la stânga sau la dreapta, sau Z se întâmplă pe podea. 249 00:07:27,620 --> 00:07:28,012 BINE. 250 00:07:28,012 --> 00:07:29,190 >> CAROLINE: Z se întâmplă pe podea. 251 00:07:29,190 --> 00:07:29,360 >> David J. MALAN: OK. 252 00:07:29,360 --> 00:07:30,920 Y se întâmplă pe podea. 253 00:07:30,920 --> 00:07:31,735 Acum putem pune X. 254 00:07:31,735 --> 00:07:32,409 >> CAROLINE: G. 255 00:07:32,409 --> 00:07:33,700 David J. MALAN: G au poftit la stânga. 256 00:07:33,700 --> 00:07:36,017 S merge bine. 257 00:07:36,017 --> 00:07:37,642 Bine, o va tot drumul din stânga. 258 00:07:37,642 --> 00:07:38,790 >> CAROLINE: A, B, C, D. 259 00:07:38,790 --> 00:07:39,873 >> David J. MALAN: Acum, bun. 260 00:07:39,873 --> 00:07:43,260 Avem A, B, C. W se întâmplă acolo. 261 00:07:43,260 --> 00:07:45,566 În regulă, T. 262 00:07:45,566 --> 00:07:46,611 >> CAROLINE: H, I, J. 263 00:07:46,611 --> 00:07:47,860 David J. MALAN: H, I, J bun. 264 00:07:47,860 --> 00:07:49,160 CAROLINE: In centru, am gonna-- 265 00:07:49,160 --> 00:07:50,000 David J. MALAN: OK. 266 00:07:50,000 --> 00:07:52,375 Deci, acum, vom fel de îmbinare aceste diferite hemoroizi. 267 00:07:52,375 --> 00:08:00,730 Deci, o prin C, apoi văd D, și E, și F, și G, și H, și I. Nisa. 268 00:08:00,730 --> 00:08:05,540 J, K. Și apoi, acest morman este cu susul în jos, dar e OK. 269 00:08:05,540 --> 00:08:06,040 Sigur. 270 00:08:06,040 --> 00:08:07,240 Putem reduce unele colțuri. 271 00:08:07,240 --> 00:08:07,950 BINE. 272 00:08:07,950 --> 00:08:10,530 Și apoi avem nevoie de W, X, Y, Z. 273 00:08:10,530 --> 00:08:11,250 >> CAROLINE: Da. 274 00:08:11,250 --> 00:08:11,880 >> David J. MALAN: Excelent. 275 00:08:11,880 --> 00:08:14,122 Deci, un mare MULTUMESC pentru Caroline de sortare acestea. 276 00:08:14,122 --> 00:08:15,030 >> [Aplauze] 277 00:08:15,030 --> 00:08:17,287 >> Multumesc. 278 00:08:17,287 --> 00:08:18,120 Multumesc foarte mult. 279 00:08:18,120 --> 00:08:22,910 Deci, acum să ia în considerare pentru un moment cum Caroline a mers cu privire la a face asta, 280 00:08:22,910 --> 00:08:26,040 si ce anume ne au putut sa-- cum am 281 00:08:26,040 --> 00:08:28,409 au fost in masura pentru a rezolva această problemă atunci când am fost doar 282 00:08:28,409 --> 00:08:29,950 dat o grămadă de intrări aleatoare. 283 00:08:29,950 --> 00:08:31,610 >> Ei bine, se pare ca acolo a fost un pic de un sistem acolo? 284 00:08:31,610 --> 00:08:32,110 Dreapta. 285 00:08:32,110 --> 00:08:34,495 Deci, literele anterioare în alfabetul, ea 286 00:08:34,495 --> 00:08:37,120 a fost punerea la stânga, și litere mai târziu în alfabetul, 287 00:08:37,120 --> 00:08:38,270 ea a fost punerea în dreapta. 288 00:08:38,270 --> 00:08:40,500 Și de îndată ce a aflat unele litere proximale, Ones 289 00:08:40,500 --> 00:08:43,124 care merg chiar lângă celălalt, ea ar pune cele în ordine. 290 00:08:43,124 --> 00:08:46,750 Și astfel am avut un fel de aceste mici grămezi de intrări sortate apar. 291 00:08:46,750 --> 00:08:50,540 >> Și așa că e destul ca ceea ce cele mai multe dintre noi, oamenii ar face. 292 00:08:50,540 --> 00:08:53,530 Ne-ar trece prin fel de ea, și am un fel de au un mecanism. 293 00:08:53,530 --> 00:08:56,930 Dar ar putea fi greu să scrie l jos într-o formulă în sine. 294 00:08:56,930 --> 00:08:59,010 M-am simtit un pic mai organic decât atât. 295 00:08:59,010 --> 00:09:02,560 Așa că haideți să vedem dacă putem acum legat problema cu mai puține intrări. 296 00:09:02,560 --> 00:09:05,170 >> În loc de 26, să face ceva mult mai putine 297 00:09:05,170 --> 00:09:09,890 cu doar spun, șapte, în spatele aceste uși, ca să spunem așa. 298 00:09:09,890 --> 00:09:11,300 Există doar șapte numere? 299 00:09:11,300 --> 00:09:15,240 Și dacă obiectivul acum la mână este de a găsi o valoare, 300 00:09:15,240 --> 00:09:17,850 să vedem cât de eficient putem merge despre a face acest lucru. 301 00:09:17,850 --> 00:09:22,460 Și să vedem dacă putem acum începe să se aplice unele numere, 302 00:09:22,460 --> 00:09:26,310 sau a unor formule cu care să descrie eficiența cartea nostru de telefon 303 00:09:26,310 --> 00:09:31,060 algoritm, algoritmul nostru de carte examen, și mai general, găsirea informațiilor. 304 00:09:31,060 --> 00:09:34,770 >> Deci, pentru aceasta, permiteți-mi să mergeți mai departe, și pe ecranul tactil aici, 305 00:09:34,770 --> 00:09:41,100 pune un browser web care are exact aceste șapte uși. 306 00:09:41,100 --> 00:09:46,670 Și dacă am putea obține un alt voluntar să vină pe aici, 307 00:09:46,670 --> 00:09:48,480 Am pus aceleași uși aici. 308 00:09:48,480 --> 00:09:49,170 Voluntar rapid. 309 00:09:49,170 --> 00:09:51,130 >> Acest Unu demo-uri sunt de gând la o mai rapida si mai rapid acum. 310 00:09:51,130 --> 00:09:51,600 Haide jos. 311 00:09:51,600 --> 00:09:52,308 Care e numele tău? 312 00:09:52,308 --> 00:09:53,040 TREVOR: Trevor. 313 00:09:53,040 --> 00:09:53,998 >> David J. MALAN: Trevor? 314 00:09:53,998 --> 00:09:55,770 Bine, Trevor, vino jos. 315 00:09:55,770 --> 00:09:59,212 Deci, Trevor sa oferit voluntar aici pentru a face o problemă similară, dar una care este 316 00:09:59,212 --> 00:10:02,170 restrânsă în domeniul de aplicare, și că se întâmplă pentru a ne permite să încercăm să formalizeze acum 317 00:10:02,170 --> 00:10:03,970 procesul de sortare aceste numere. 318 00:10:03,970 --> 00:10:05,500 >> Deci Trevor, bucur să te cunosc. 319 00:10:05,500 --> 00:10:08,720 Deci, aici este o matrice, astfel încât să vorbesc, o listă de șapte uși. 320 00:10:08,720 --> 00:10:10,327 Du-te și ne găsi numărul 50. 321 00:10:10,327 --> 00:10:12,410 Și apoi, după faptul, spune-ne cum ai găsit-o. 322 00:10:12,410 --> 00:10:19,124 323 00:10:19,124 --> 00:10:20,040 Ar trebui să be-- în regulă. 324 00:10:20,040 --> 00:10:21,945 Da, aceasta este cea de aici? 325 00:10:21,945 --> 00:10:24,680 Uh-oh. 326 00:10:24,680 --> 00:10:25,560 BINE. 327 00:10:25,560 --> 00:10:26,680 Ați făcut clic asta. 328 00:10:26,680 --> 00:10:28,690 Bine. 329 00:10:28,690 --> 00:10:29,780 >> Și de bună. 330 00:10:29,780 --> 00:10:30,970 Acum ați făcut clic pe asta. 331 00:10:30,970 --> 00:10:34,060 Și permiteți-mi să vă dau microfonul, astfel încât să-l aibă într-o clipă. 332 00:10:34,060 --> 00:10:37,000 Dă-i drumul și faceți clic pe alături pe care intenționați. 333 00:10:37,000 --> 00:10:39,812 Da bine. 334 00:10:39,812 --> 00:10:41,020 TREVOR: Pot debifați o ușă? 335 00:10:41,020 --> 00:10:42,620 David J. MALAN: Nu, nu poți debifați. 336 00:10:42,620 --> 00:10:43,119 TREVOR: OK. 337 00:10:43,119 --> 00:10:43,974 Aceasta. 338 00:10:43,974 --> 00:10:45,640 David J. MALAN: Unde vrei să mergi? 339 00:10:45,640 --> 00:10:46,410 Care? 340 00:10:46,410 --> 00:10:47,230 >> TREVOR: Asta. 341 00:10:47,230 --> 00:10:48,042 >> David J. MALAN: Nu. 342 00:10:48,042 --> 00:10:48,450 >> TREVOR: OK. 343 00:10:48,450 --> 00:10:48,735 Aceasta. 344 00:10:48,735 --> 00:10:49,020 >> David J. MALAN: Da. 345 00:10:49,020 --> 00:10:49,700 A fost bine. 346 00:10:49,700 --> 00:10:50,380 In regula. 347 00:10:50,380 --> 00:10:53,900 Deci, ceea ce a fost algoritm sau Procedura pentru a face acest lucru, Trevor? 348 00:10:53,900 --> 00:10:56,149 >> TREVOR: Am trecut prin Uși până când am găsit un 50. 349 00:10:56,149 --> 00:10:56,940 David J. MALAN: OK. 350 00:10:56,940 --> 00:10:58,150 Excelent algoritm. 351 00:10:58,150 --> 00:10:59,540 Deci asta e bine. 352 00:10:59,540 --> 00:11:03,120 Pentru că, de fapt, dacă aș dezvălui ceea ce este în spatele acestor două alte uși, ceea ce 353 00:11:03,120 --> 00:11:06,954 vom găsi aici este faptul că avem doar de intrare aleatoare. 354 00:11:06,954 --> 00:11:08,870 Astfel că a fost de fapt la fel de de bun ca ai putea lua. 355 00:11:08,870 --> 00:11:12,509 Și, de fapt, ai mai bine decât căutarea exhaustiv întreaga matrice, 356 00:11:12,509 --> 00:11:15,300 pentru că ar fi fost foarte ghinionist daca ai fi lovit numărul 357 00:11:15,300 --> 00:11:16,604 50 în ultimul ușă. 358 00:11:16,604 --> 00:11:18,520 Dar dacă am loc ți-a dat o presupunere. 359 00:11:18,520 --> 00:11:20,630 Să presupunem că un fel de toate aceste uși în jurul valorii de, 360 00:11:20,630 --> 00:11:23,500 astfel încât să aibă Numerele sortate de data aceasta, 361 00:11:23,500 --> 00:11:29,730 dar de data aceasta este de fapt un different-- de data aceasta, 362 00:11:29,730 --> 00:11:32,640 este de fapt sortate pentru tine. 363 00:11:32,640 --> 00:11:35,380 Iar acum obiectivul la îndemână este de a lovi numărul 50. 364 00:11:35,380 --> 00:11:36,090 >> TREVOR: OK. 365 00:11:36,090 --> 00:11:37,670 >> David J. MALAN: Ce este algoritmul dvs. va fi? 366 00:11:37,670 --> 00:11:39,628 >> TREVOR: Ei bine, dacă e sortate, e fie merge 367 00:11:39,628 --> 00:11:42,710 a be-- dacă cel mai mare cel mai mare, descendent, va fi primul, 368 00:11:42,710 --> 00:11:44,751 sau dacă este opusul, acesta va fi ultima. 369 00:11:44,751 --> 00:11:48,897 Așa că vom atinge doar ușa, și apoi apăsați doar ultima ușă. 370 00:11:48,897 --> 00:11:49,980 David J. MALAN: Excelent. 371 00:11:49,980 --> 00:11:50,270 In regula. 372 00:11:50,270 --> 00:11:51,150 Așa că am găsit numărul 50. 373 00:11:51,150 --> 00:11:52,970 Deci, de îndată ce ai știut acestea au fost sortate, am 374 00:11:52,970 --> 00:11:55,040 au fost capabili să impulsioneze această ipoteză. 375 00:11:55,040 --> 00:11:57,040 Astfel încât acestea sunt prea mult ca exemplul cartea de telefon. 376 00:11:57,040 --> 00:11:59,540 De îndată ce ai, chiar cu o mică problemă de acest fel, 377 00:11:59,540 --> 00:12:02,380 intrările dvs. de pre-sortate, putem găsi de fapt, valoarea, fără îndoială, 378 00:12:02,380 --> 00:12:03,130 mai eficient. 379 00:12:03,130 --> 00:12:05,800 >> Și nu l-ai spune dacă era sortate mic la mare, sau de mare pentru a mici, 380 00:12:05,800 --> 00:12:08,080 și așa a fost foarte rezonabil să înceapă la un capăt sau altul 381 00:12:08,080 --> 00:12:09,750 pentru a găsi de fapt, această valoare-țintă. 382 00:12:09,750 --> 00:12:11,400 Deci, mulțumesc pentru Trevor, de asemenea. 383 00:12:11,400 --> 00:12:13,260 Și voi propose-- bine făcut. 384 00:12:13,260 --> 00:12:16,960 Avem un mic clip, de fapt, că se numără printre momentele noastre preferate din CS50, 385 00:12:16,960 --> 00:12:19,700 care, uneori, aceste demo-uri Nu prea merge conform planului. 386 00:12:19,700 --> 00:12:22,050 Și într-adevăr, chiar acum, am tras în sus interfața greșit 387 00:12:22,050 --> 00:12:23,508 cu care să utilizeze ecranul tactil. 388 00:12:23,508 --> 00:12:24,660 Astfel că a fost vina mea acolo. 389 00:12:24,660 --> 00:12:26,600 >> Deci, acest lucru va face pentru clip de anul viitor ca 390 00:12:26,600 --> 00:12:28,570 de ce am fost clic pe cont propriu ecran. 391 00:12:28,570 --> 00:12:31,390 Dar haideți să aruncăm o privire rapidă la ceea ce sa întâmplat anul trecut 392 00:12:31,390 --> 00:12:34,770 cu Jay, care a venit, mai mult ca Trevor aici, sa oferit voluntar, 393 00:12:34,770 --> 00:12:39,380 și în acest scurt clip, veți vedea cum același demo nu prea 394 00:12:39,380 --> 00:12:41,074 dezvăluie aceleași lecțiile învățate. 395 00:12:41,074 --> 00:12:41,740 [VIDEO PLAYBACK] 396 00:12:41,740 --> 00:12:45,360 -Toate Vreau să faci acum este pentru a găsi pentru mine, și pentru noi, 397 00:12:45,360 --> 00:12:51,674 într-adevăr, numărul 50 cu pasi marunti. 398 00:12:51,674 --> 00:12:52,450 >> -Numărul 50? 399 00:12:52,450 --> 00:12:53,190 >> -Numărul 50. 400 00:12:53,190 --> 00:12:55,356 Și puteți dezvălui ceea ce este în spatele fiecare dintre aceste uși 401 00:12:55,356 --> 00:12:58,540 pur și simplu prin atingerea cu un deget. 402 00:12:58,540 --> 00:13:00,910 La naiba. 403 00:13:00,910 --> 00:13:02,870 >> [Rîzînd] 404 00:13:02,870 --> 00:13:03,806 >> [END PLAYBACK] 405 00:13:03,806 --> 00:13:05,430 David J. MALAN: Așa că a mers foarte bine. 406 00:13:05,430 --> 00:13:06,796 Acestea au fost ușile nesortate. 407 00:13:06,796 --> 00:13:08,670 Și Jay, desigur, găsit-o prea repede. 408 00:13:08,670 --> 00:13:12,910 Trevor a facut o treaba mult mai bine în ceea ce privește o clipă docil, 409 00:13:12,910 --> 00:13:15,850 ca să spunem așa, în acest an, în durează mai mult să-l găsiți. 410 00:13:15,850 --> 00:13:17,950 Desigur, atunci ne-am dat Jay a doua șansă, 411 00:13:17,950 --> 00:13:20,320 prin care am sortat ușile, la fel cum am făcut-o pentru Trevor, 412 00:13:20,320 --> 00:13:22,300 și Trevor a făcut super-bine de data asta. 413 00:13:22,300 --> 00:13:26,124 Dar Jay a făcut pe jumătate la fel de repede. 414 00:13:26,124 --> 00:13:26,790 [VIDEO PLAYBACK] 415 00:13:26,790 --> 00:13:29,650 -cele Scopul este acum de a, de asemenea, ne găsi numărul 50, 416 00:13:29,650 --> 00:13:33,030 dar o fac algoritmic, și spune-ne cum ai de gând cu privire la aceasta. 417 00:13:33,030 --> 00:13:33,660 >> -BINE. 418 00:13:33,660 --> 00:13:35,604 >> -Și Dacă îl găsiți, vă păstrați filmul. 419 00:13:35,604 --> 00:13:37,228 Dacă nu-l găsiți, vă-l dea înapoi. 420 00:13:37,228 --> 00:13:38,044 >> Omule. 421 00:13:38,044 --> 00:13:38,860 >> Oh! 422 00:13:38,860 --> 00:13:40,800 >> - [Neauzit] OK. 423 00:13:40,800 --> 00:13:46,236 Deci, am de gând să verifice capete în primul rând pentru a stabili dacă there's-- Oh. 424 00:13:46,236 --> 00:13:48,646 >> [Aplauze] 425 00:13:48,646 --> 00:13:53,948 426 00:13:53,948 --> 00:13:55,729 >> [END PLAYBACK] 427 00:13:55,729 --> 00:13:56,520 David J. MALAN: OK. 428 00:13:56,520 --> 00:13:59,760 Deci, în mod clar de sortare usi conduce la o mai mare eficiență. 429 00:13:59,760 --> 00:14:01,680 Și astfel, două ori mai repede este ceea ce am vrut să spun acolo. 430 00:14:01,680 --> 00:14:03,270 Și așa Jay avut noroc atât de ori. 431 00:14:03,270 --> 00:14:06,685 Și el, de asemenea, avut noroc în ultima an, am comandat unele discuri Blu-ray 432 00:14:06,685 --> 00:14:07,560 pentru a da de fapt afară. 433 00:14:07,560 --> 00:14:09,768 Îmi pare rău în acest an, ne-am nu au avut la fel, Trevor. 434 00:14:09,768 --> 00:14:11,540 Dar mai bine era cu câțiva ani în urmă. 435 00:14:11,540 --> 00:14:14,820 Și unii dintre voi s-ar putea ști acest colegi, Sean, care când era în CS50, 436 00:14:14,820 --> 00:14:17,780 a fost contestat cu exact aceeași problemă, deși în SD, 437 00:14:17,780 --> 00:14:19,360 după cum veți vedea în curând, din nou în a doua zi. 438 00:14:19,360 --> 00:14:22,622 Și veți găsi că nu numai că el ia un pic mai mult decât Jay, 439 00:14:22,622 --> 00:14:25,580 un pic mai mult decât Trevor, a fost de fapt, această oportunitate minunata 440 00:14:25,580 --> 00:14:29,820 de a se angaja aproape toată lumea în mulțimea a la prețul este corect, încurajând 441 00:14:29,820 --> 00:14:31,889 l pentru a găsi numărul am fost în căutarea. 442 00:14:31,889 --> 00:14:32,930 Să. arunca o privire rapidă. 443 00:14:32,930 --> 00:14:33,320 >> [VIDEO PLAYBACK] 444 00:14:33,320 --> 00:14:33,820 >> -BINE. 445 00:14:33,820 --> 00:14:36,680 Deci, sarcina dumneavoastră aici, Sean, este următoarea. 446 00:14:36,680 --> 00:14:40,860 Am ascuns în spatele acestor usi numărul șapte. 447 00:14:40,860 --> 00:14:45,120 Dar ascuns în unele dintre aceste uși precum și alte numere negative. 448 00:14:45,120 --> 00:14:47,500 Și de obiectivul dvs. este de a gândi din acest rând top de numere 449 00:14:47,500 --> 00:14:50,390 ca doar o matrice, sau pur și simplu secvență de bucăți de hârtie 450 00:14:50,390 --> 00:14:51,510 cu numere spatele lor. 451 00:14:51,510 --> 00:14:55,540 Și obiectivul dvs. este, folosind doar partea de sus matrice aici, mi găsesc numărul șapte. 452 00:14:55,540 --> 00:14:58,570 Și noi suntem de gând să critice apoi cum te duci despre a face aceasta. 453 00:14:58,570 --> 00:14:59,070 -In regula. 454 00:14:59,070 --> 00:15:00,850 Găsește-ne la numărul șapte, vă rugăm. 455 00:15:00,850 --> 00:15:10,500 456 00:15:10,500 --> 00:15:11,000 Nu. 457 00:15:11,000 --> 00:15:15,050 458 00:15:15,050 --> 00:15:18,550 Cinci, 19, 13. 459 00:15:18,550 --> 00:15:22,240 460 00:15:22,240 --> 00:15:24,770 >> [Rîzînd] 461 00:15:24,770 --> 00:15:25,910 >> Nu este o întrebare capcană. 462 00:15:25,910 --> 00:15:29,410 463 00:15:29,410 --> 00:15:29,910 Unul. 464 00:15:29,910 --> 00:15:33,218 465 00:15:33,218 --> 00:15:34,695 >> [Rîzînd] 466 00:15:34,695 --> 00:15:37,861 În acest moment, scorul nu este foarte bine, asa ca s-ar putea la fel de bine continua. 467 00:15:37,861 --> 00:15:40,610 468 00:15:40,610 --> 00:15:41,110 Trei. 469 00:15:41,110 --> 00:15:43,890 470 00:15:43,890 --> 00:15:45,378 >> [Rîzînd] 471 00:15:45,378 --> 00:15:46,370 472 00:15:46,370 --> 00:15:47,774 >> Continuă. 473 00:15:47,774 --> 00:15:50,690 Sincer, eu nu pot ajuta, dar întreb la ce te gândești chiar, deci-- 474 00:15:50,690 --> 00:15:51,959 >> [Rîzînd] 475 00:15:51,959 --> 00:15:53,229 476 00:15:53,229 --> 00:15:55,020 Numai rândul de sus, astfel încât ai trei stângă. 477 00:15:55,020 --> 00:15:56,200 Deci mă găsească șapte. 478 00:15:56,200 --> 00:15:59,700 479 00:15:59,700 --> 00:16:02,167 >> [Rîzînd] 480 00:16:02,167 --> 00:16:14,870 481 00:16:14,870 --> 00:16:15,370 17. 482 00:16:15,370 --> 00:16:25,675 483 00:16:25,675 --> 00:16:26,946 Șapte. 484 00:16:26,946 --> 00:16:28,780 >> [Aplauze] 485 00:16:28,780 --> 00:16:29,426 >> In regula. 486 00:16:29,426 --> 00:16:30,360 >> [END PLAYBACK] 487 00:16:30,360 --> 00:16:31,840 >> David J. MALAN: asa ca am putea viziona aceste lung toată ziua. 488 00:16:31,840 --> 00:16:34,090 Și, desigur, unele dintre demo-uri din acest an, probabil, 489 00:16:34,090 --> 00:16:36,330 se va termina acum în viitor video de an, precum. 490 00:16:36,330 --> 00:16:39,040 Deci, acum să fapt concentreze asupra algoritmilor 491 00:16:39,040 --> 00:16:42,140 aici, și să vedem dacă nu putem acum începe pentru a formaliza 492 00:16:42,140 --> 00:16:46,650 cum putem merge cu privire la obținerea de date nostru în această stare, care este sortate, 493 00:16:46,650 --> 00:16:50,054 astfel încât în ​​cele din urmă, putem de fapt căutare-l mai eficient. 494 00:16:50,054 --> 00:16:52,470 Și chiar dacă vom pentru a folosi seturi de date destul de mici, 495 00:16:52,470 --> 00:16:54,511 ca WE opt numere avem aici de pe bord, 496 00:16:54,511 --> 00:16:58,230 în cele din urmă ar putea aplica aceleași idei la 1.000 de intrări, un milion de intrări, 497 00:16:58,230 --> 00:17:02,100 4 miliarde de intrări, deoarece algoritmii vor fi fundamental la fel. 498 00:17:02,100 --> 00:17:05,359 >> Și astfel încât acesta este ultimul nostru oportunitate pentru voluntari astăzi, 499 00:17:05,359 --> 00:17:09,790 dar, probabil, cel mai implicat, pentru care avem nevoie de opt voluntari 500 00:17:09,790 --> 00:17:12,960 de a veni și de mers pe jos ne prin proces de sortare ce va fi în curând 501 00:17:12,960 --> 00:17:15,212 fie pe aceste muzică standuri aici. 502 00:17:15,212 --> 00:17:16,170 Permiteți-mi să începe aici. 503 00:17:16,170 --> 00:17:19,692 >> Deci, unul din verde turquoise-- este? 504 00:17:19,692 --> 00:17:21,130 Ești comiterea? 505 00:17:21,130 --> 00:17:21,630 Două. 506 00:17:21,630 --> 00:17:23,069 Haide jos. 507 00:17:23,069 --> 00:17:23,569 BINE. 508 00:17:23,569 --> 00:17:24,420 Trei. 509 00:17:24,420 --> 00:17:25,400 Patru. 510 00:17:25,400 --> 00:17:27,247 Să mine-- OK, cinci. 511 00:17:27,247 --> 00:17:28,830 Ești desemnat de prietenul tău. 512 00:17:28,830 --> 00:17:31,340 Șase, șapte, opt. 513 00:17:31,340 --> 00:17:32,130 Haide sus. 514 00:17:32,130 --> 00:17:32,630 In regula. 515 00:17:32,630 --> 00:17:33,190 Multumesc foarte mult. 516 00:17:33,190 --> 00:17:33,689 Haide sus. 517 00:17:33,689 --> 00:17:34,790 Haide sus. 518 00:17:34,790 --> 00:17:35,330 >> In regula. 519 00:17:35,330 --> 00:17:38,890 Deci, ce avem here-- și acest este printre cele mai incomode, 520 00:17:38,890 --> 00:17:42,390 deoarece acest lucru va necesita să umor mi doar un pic de timp. 521 00:17:42,390 --> 00:17:43,442 Tu trebuie să fie numărul unu. 522 00:17:43,442 --> 00:17:44,150 Care e numele tău? 523 00:17:44,150 --> 00:17:44,610 >> Annan: Annan. 524 00:17:44,610 --> 00:17:45,526 >> David J. MALAN: Annan. 525 00:17:45,526 --> 00:17:46,092 David. 526 00:17:46,092 --> 00:17:46,800 Care e numele tău? 527 00:17:46,800 --> 00:17:47,140 >> JOSEPH: Joseph. 528 00:17:47,140 --> 00:17:49,190 >> David J. MALAN: Joseph, ești numărul doi. 529 00:17:49,190 --> 00:17:52,260 >> SERENA: Serena, numărul trei. 530 00:17:52,260 --> 00:17:53,722 Stefan, numărul patru. 531 00:17:53,722 --> 00:17:54,430 CYNTHIA: Cynthia. 532 00:17:54,430 --> 00:17:57,548 David J. MALAN: Cynthia, numărul cinci. 533 00:17:57,548 --> 00:17:58,452 [Inaudibil] 534 00:17:58,452 --> 00:17:59,618 David J. MALAN: [neauzit]. 535 00:17:59,618 --> 00:18:00,391 David, numărul șase. 536 00:18:00,391 --> 00:18:00,890 MATT: Matt. 537 00:18:00,890 --> 00:18:02,160 David J. MALAN: Matt numărul șapte. 538 00:18:02,160 --> 00:18:02,850 Și? 539 00:18:02,850 --> 00:18:03,210 >> WAVERLY: Waverly. 540 00:18:03,210 --> 00:18:04,470 >> David J. MALAN: Waverly, numărul opt. 541 00:18:04,470 --> 00:18:04,970 In regula. 542 00:18:04,970 --> 00:18:06,510 Dacă ați putea-- Hopa. 543 00:18:06,510 --> 00:18:08,820 Dacă tot, ca dvs. în primul rând provocare, acolo 544 00:18:08,820 --> 00:18:10,820 opt standuri de muzică aici se confruntă publicul. 545 00:18:10,820 --> 00:18:14,200 Dacă ai putea pune numerele pe acestea muzică stă în așa fel 546 00:18:14,200 --> 00:18:16,560 pe care le aliniază cu aceleași numere de pe bord. 547 00:18:16,560 --> 00:18:19,560 Deci, asigurați-vă arăta așa de pune numerele de pe aceste muzică 548 00:18:19,560 --> 00:18:21,960 standuri aici. 549 00:18:21,960 --> 00:18:25,980 Excelent până acum. 550 00:18:25,980 --> 00:18:26,600 >> Excelent. 551 00:18:26,600 --> 00:18:26,890 BINE. 552 00:18:26,890 --> 00:18:29,556 Deci, acum, vom cere întrebare în câteva moduri diferite. 553 00:18:29,556 --> 00:18:31,610 Cum putem merge cu privire la sortarea acesti oameni aici? 554 00:18:31,610 --> 00:18:34,500 Pentru că am avut câteva abordări mai devreme, prin care am fost 555 00:18:34,500 --> 00:18:36,360 fel de a face două găleți diferite. 556 00:18:36,360 --> 00:18:38,842 Și apoi am fost, în general, piecing lucruri împreună. 557 00:18:38,842 --> 00:18:41,050 De îndată ce am văzut două numere care a aparținut, împreună, 558 00:18:41,050 --> 00:18:41,975 am le-a pus împreună. 559 00:18:41,975 --> 00:18:43,350 Două scrisori care aparțin împreună. 560 00:18:43,350 --> 00:18:45,058 >> Dar să vedem dacă ne nu se poate formaliza acest lucru, 561 00:18:45,058 --> 00:18:48,044 astfel încât să avem în cele din urmă unele pseudo-cod va fi, 562 00:18:48,044 --> 00:18:49,710 cu care puteți rezolva aceste probleme. 563 00:18:49,710 --> 00:18:51,870 Asa ca acum, caut afară la aceste numere de aici. 564 00:18:51,870 --> 00:18:55,030 Și văd o grămadă de greșeli. 565 00:18:55,030 --> 00:18:57,750 În cele din urmă, vreau una la stânga și opt pe dreapta. 566 00:18:57,750 --> 00:19:00,650 >> Și așa mă uit la aceste două, patru și două. 567 00:19:00,650 --> 00:19:02,930 Și care-i problema, în mod evident? 568 00:19:02,930 --> 00:19:04,261 Da. 569 00:19:04,261 --> 00:19:04,760 Asa ca. 570 00:19:04,760 --> 00:19:07,160 Două evident vine înainte patru, astfel încât să știi ce? 571 00:19:07,160 --> 00:19:10,210 Lasă-mă să ia mai întâi o abordare lacom, dacă vreți, la fel ca și problema 572 00:19:10,210 --> 00:19:13,790 set Unu dacă vă amintiți de la Standard Edition problemei Set One, 573 00:19:13,790 --> 00:19:16,820 în cazul în care doar am rezolva la nivel local problema care este chiar aici în fața mea 574 00:19:16,820 --> 00:19:17,690 și a vedea unde mă duce. 575 00:19:17,690 --> 00:19:17,870 >> BINE. 576 00:19:17,870 --> 00:19:20,161 Deci, doi și patru, lasă-mă să merg înainte și pe care tocmai ați schimba doi. 577 00:19:20,161 --> 00:19:22,400 Dacă puteți muta fizic voi înșivă și hârtie, 578 00:19:22,400 --> 00:19:25,040 Se pare că au ajuns lista într-o stare mai bună. 579 00:19:25,040 --> 00:19:26,330 >> Acum, ei sunt bine. 580 00:19:26,330 --> 00:19:28,480 Am de gând să se mute departe, patru și șase, arată bine. 581 00:19:28,480 --> 00:19:29,110 Nici o problema. 582 00:19:29,110 --> 00:19:30,440 Șase și opt, OK. 583 00:19:30,440 --> 00:19:31,860 Opt și unul, o altă problemă. 584 00:19:31,860 --> 00:19:34,750 Pentru că ceea ce este adevărat despre opt și unul? 585 00:19:34,750 --> 00:19:36,990 Vine înainte de opt, și așa mai departe ceea ce ar trebui să facem? 586 00:19:36,990 --> 00:19:38,090 Să schimb aceste două. 587 00:19:38,090 --> 00:19:39,316 Unul și opt. 588 00:19:39,316 --> 00:19:40,690 Și acum, am de gând să continui. 589 00:19:40,690 --> 00:19:42,030 Am de gând să continui să cauți mai departe. 590 00:19:42,030 --> 00:19:42,840 Și să vedem ce se întâmplă. 591 00:19:42,840 --> 00:19:44,680 Opt și trei, de Desigur, din ordine. 592 00:19:44,680 --> 00:19:45,815 Să swap. 593 00:19:45,815 --> 00:19:46,940 Opt și șapte, desigur. 594 00:19:46,940 --> 00:19:47,481 Scos din uz. 595 00:19:47,481 --> 00:19:48,280 Să swap. 596 00:19:48,280 --> 00:19:49,940 Opt și cinci, desigur, să swap. 597 00:19:49,940 --> 00:19:50,560 In regula. 598 00:19:50,560 --> 00:19:51,880 Lista este sortata. 599 00:19:51,880 --> 00:19:53,060 da? 600 00:19:53,060 --> 00:19:54,280 >> OK, evident, nu. 601 00:19:54,280 --> 00:19:55,860 Dar este un pic mai bine, nu? 602 00:19:55,860 --> 00:19:57,270 Deoarece o notificare ce sa întâmplat. 603 00:19:57,270 --> 00:20:01,749 De fiecare dată când am realizat un swap, un mic Numărul fel de filtrate în acest fel, 604 00:20:01,749 --> 00:20:03,790 și un număr mai mare percolat acest fel, sau vom 605 00:20:03,790 --> 00:20:06,880 începe spunând barbotat la la stânga sau la dreapta barbotat. 606 00:20:06,880 --> 00:20:10,080 >> Acum, nu e de ajuns, pentru că cel mai bun la un număr s-ar putea 607 00:20:10,080 --> 00:20:11,990 s-au mutat un singur loc înainte, sau în cel mai rău, 608 00:20:11,990 --> 00:20:13,880 un număr ar putea avea mutat încă o pată. 609 00:20:13,880 --> 00:20:16,369 Deci, știi ce, acest tip de lucrat destul de bine până acum. 610 00:20:16,369 --> 00:20:17,410 Lasă-mă doar să încercați din nou. 611 00:20:17,410 --> 00:20:18,880 Două și patru, sunt OK. 612 00:20:18,880 --> 00:20:20,180 Patru și șase, sunt OK. 613 00:20:20,180 --> 00:20:21,790 Șase și unul, în ordine. 614 00:20:21,790 --> 00:20:23,007 Așa că haideți să vă doi schimb. 615 00:20:23,007 --> 00:20:25,840 Și acum, observa problemei incepand de a obține un pic mai bine din nou. 616 00:20:25,840 --> 00:20:27,006 Șase și trei, în ordine. 617 00:20:27,006 --> 00:20:28,100 Să voi doi schimb. 618 00:20:28,100 --> 00:20:29,730 Șase și șapte, ești bun. 619 00:20:29,730 --> 00:20:32,230 Șapte și cinci, desigur, din ordine. 620 00:20:32,230 --> 00:20:33,920 Șapte și opt, în ordine. 621 00:20:33,920 --> 00:20:36,470 Și acum, s-ar putea nevoie pentru a face acest lucru de câteva ori mai mult. 622 00:20:36,470 --> 00:20:39,830 Și, de fapt, cred că pentru voi înșivă probabil de câte ori maxim 623 00:20:39,830 --> 00:20:41,330 s-ar putea am să meargă înainte și înapoi? 624 00:20:41,330 --> 00:20:42,390 >> Vom reveni la asta. 625 00:20:42,390 --> 00:20:43,700 Deci, două și patru sunt încă OK. 626 00:20:43,700 --> 00:20:44,940 Patru și unu, nope. 627 00:20:44,940 --> 00:20:45,747 Deci, să swap. 628 00:20:45,747 --> 00:20:47,830 Și din nou, observa vizual unul este un fel de barbotare 629 00:20:47,830 --> 00:20:49,163 la stânga, în cazul în care ar trebui să fie. 630 00:20:49,163 --> 00:20:50,010 Patru și trei de swap. 631 00:20:50,010 --> 00:20:51,330 Patru și șase. 632 00:20:51,330 --> 00:20:53,100 Șase și cinci de swap. 633 00:20:53,100 --> 00:20:53,959 Șase și șapte. 634 00:20:53,959 --> 00:20:55,000 Șapte și opt sunt bune. 635 00:20:55,000 --> 00:20:55,500 >> Bine. 636 00:20:55,500 --> 00:20:58,460 Primim chiar mai bine. 637 00:20:58,460 --> 00:20:59,130 Deci, să vedem. 638 00:20:59,130 --> 00:21:00,940 Acum, avem două și unul. 639 00:21:00,940 --> 00:21:02,520 Desigur, schimb. 640 00:21:02,520 --> 00:21:07,520 Două și trei, trei si patru, patru și cinci, șase și șapte, șapte și opt. 641 00:21:07,520 --> 00:21:08,020 Bine. 642 00:21:08,020 --> 00:21:08,730 Și știi ce? 643 00:21:08,730 --> 00:21:11,190 Pentru că am făcut o schimbare acolo, lasa-ma sa fac o verificare bun-simț. 644 00:21:11,190 --> 00:21:13,023 Lasă-mă să merg până la capăt înapoi la început. 645 00:21:13,023 --> 00:21:13,680 BINE. 646 00:21:13,680 --> 00:21:14,750 Unul, two-- Da, vezi? 647 00:21:14,750 --> 00:21:15,870 Ceva a fost greșit. 648 00:21:15,870 --> 00:21:18,420 Trei, patru, cinci, șase, șapte, opt. 649 00:21:18,420 --> 00:21:21,920 Și în această ultimă trecere, sunt vă confortabil cu meu acum 650 00:21:21,920 --> 00:21:23,830 susținând că este sortata? 651 00:21:23,830 --> 00:21:24,330 BINE. 652 00:21:24,330 --> 00:21:25,880 Vizual, e absolut adevărat. 653 00:21:25,880 --> 00:21:28,410 Dar funcțional, ce sa, de asemenea, se intampla doar 654 00:21:28,410 --> 00:21:31,870 în ultimul pasă care vă permite să confirme că această listă este într-adevăr 655 00:21:31,870 --> 00:21:32,660 sortate? 656 00:21:32,660 --> 00:21:34,477 >> Ce am făcut sau nu acest ultim pasă? 657 00:21:34,477 --> 00:21:35,810 Audiența: Nu au existat modificări. 658 00:21:35,810 --> 00:21:36,120 David J. MALAN: Ne pare rău? 659 00:21:36,120 --> 00:21:37,070 Audiența: Nici o schimbare. 660 00:21:37,070 --> 00:21:38,653 David J. MALAN: Nu au existat modificări. 661 00:21:38,653 --> 00:21:41,947 Deci, ar fi o prostie din partea mea să face din nou același algoritm 662 00:21:41,947 --> 00:21:43,780 dacă nu am nici schimbă prima oară. 663 00:21:43,780 --> 00:21:45,160 Iar statul nu sa schimbat. 664 00:21:45,160 --> 00:21:47,576 Cu siguranță, eu nu am de gând să facă schimbă orice a doua oară. 665 00:21:47,576 --> 00:21:49,820 Și așa, e sigur acum să spun, Lista este sortata. 666 00:21:49,820 --> 00:21:52,069 >> Și într-adevăr, acest lucru este acum ceva că vom general 667 00:21:52,069 --> 00:21:56,900 apel cu bule fel, prin perechi, te corecta greșelile din nou, 668 00:21:56,900 --> 00:22:00,210 și din nou, și din nou, și tu mergi înainte și înapoi, 669 00:22:00,210 --> 00:22:03,370 și înainte și înapoi, până când nu fac nici o astfel de swap-uri, la care punctul de 670 00:22:03,370 --> 00:22:07,089 puteți fi sigur, da, terminat de stabilire toate greșelile. 671 00:22:07,089 --> 00:22:08,630 Să reset și încerca o altă abordare. 672 00:22:08,630 --> 00:22:11,590 Dacă voi putea întoarce în ordinea în care au fost în urmă cu o clipă, 673 00:22:11,590 --> 00:22:13,780 care arata ca acest lucru. 674 00:22:13,780 --> 00:22:17,640 Acum, haideți să aruncăm o abordare o pic mai mult ca carte examen, 675 00:22:17,640 --> 00:22:21,122 prin care am fost în mod constant selectarea literă a alfabetului 676 00:22:21,122 --> 00:22:22,830 pe care le fel de dorit pentru a face față în continuare. 677 00:22:22,830 --> 00:22:26,420 Poate că a fost o scrisoare de mare, cum ar fi A, sau un Z. scăzut scrisoare 678 00:22:26,420 --> 00:22:28,170 >> Astfel încât toată lumea sa întors în această ordine. 679 00:22:28,170 --> 00:22:29,800 Și acum lasă-mă să fac asta. 680 00:22:29,800 --> 00:22:34,880 Să vedem Știu că am opt numere aici. 681 00:22:34,880 --> 00:22:37,410 Am de gând să merg mai departe și selectați doar în mod deliberat 682 00:22:37,410 --> 00:22:38,520 cele mai mici elemente. 683 00:22:38,520 --> 00:22:38,760 Dreapta? 684 00:22:38,760 --> 00:22:39,801 Acest lucru pare intuitivă. 685 00:22:39,801 --> 00:22:42,560 De ce nu mi se pare cel mai mic Element, pune-l în cazul în care acesta face parte, 686 00:22:42,560 --> 00:22:45,280 apoi ajunge în următorii mai mic element, a pus aceasta în cazul în care acesta face parte, si doar se repetă. 687 00:22:45,280 --> 00:22:46,820 >> Pentru că intuitiv, că ar trebui să funcționeze prea. 688 00:22:46,820 --> 00:22:48,441 Deci patru, asta este un număr destul de mic. 689 00:22:48,441 --> 00:22:49,940 Am de gând să-mi amintesc unde acest lucru este. 690 00:22:49,940 --> 00:22:50,523 Asteapta un minut. 691 00:22:50,523 --> 00:22:51,577 Două este mai mic. 692 00:22:51,577 --> 00:22:53,910 Permiteți-mi să amintesc acum unde doi este, si uita de patru. 693 00:22:53,910 --> 00:22:55,050 Ne vom ocupa de asta mai târziu. 694 00:22:55,050 --> 00:22:56,460 Șase, nu mă interesează. 695 00:22:56,460 --> 00:22:57,810 Opt, nu sunt interesat de. 696 00:22:57,810 --> 00:22:59,780 Una dintre ele este noul meu număr mic. 697 00:22:59,780 --> 00:23:01,470 Deci, am de gând să-mi amintesc unde unul este. 698 00:23:01,470 --> 00:23:02,534 Trei, nu sunt interesat. 699 00:23:02,534 --> 00:23:03,450 Șapte, nu sunt interesat. 700 00:23:03,450 --> 00:23:04,530 Cinci, nu sunt interesat. 701 00:23:04,530 --> 00:23:07,390 >> Deci, fără a cădea de pe etapa din acest an, 702 00:23:07,390 --> 00:23:09,890 Am de gând să apuca numărul Unu și ceea ce a fost din nou numele tău? 703 00:23:09,890 --> 00:23:10,150 >> Annan: Annan. 704 00:23:10,150 --> 00:23:11,220 >> David J. MALAN: Annan. 705 00:23:11,220 --> 00:23:13,540 Și dacă ai putea să mi se alăture la începutul listei, 706 00:23:13,540 --> 00:23:14,870 Să te pun unde ți-e locul. 707 00:23:14,870 --> 00:23:16,080 Unfortunately-- care e numele tău? 708 00:23:16,080 --> 00:23:16,650 >> STEFAN: Stefan. 709 00:23:16,650 --> 00:23:18,191 >> David J. MALAN: Stefan este in drum. 710 00:23:18,191 --> 00:23:23,490 Deci, înainte de Stefan rezolvă această problemă, ceea ce ar trebui să facem? 711 00:23:23,490 --> 00:23:25,412 Ce facem cu Stefan? 712 00:23:25,412 --> 00:23:27,269 >> Audiența: [neauzit]. 713 00:23:27,269 --> 00:23:28,060 David J. MALAN: OK. 714 00:23:28,060 --> 00:23:28,850 Deci, am putea face asta. 715 00:23:28,850 --> 00:23:31,730 Am putea lua un fel de Stefan si lui patru, și doar a pus într-o variabilă 716 00:23:31,730 --> 00:23:33,530 și țineți pe ea pentru o anumită cantitate de timp, 717 00:23:33,530 --> 00:23:35,220 făcând astfel loc pentru numărul unu. 718 00:23:35,220 --> 00:23:36,280 Și asta nu e rău. 719 00:23:36,280 --> 00:23:39,270 Aș putea sugera, de ce nu ne-am pus Stefan aici? 720 00:23:39,270 --> 00:23:41,610 De ce s-ar putea incalca aceasta din ideile pe care le au început 721 00:23:41,610 --> 00:23:44,830 vorbesc despre ultima dată, săptămâna trecută? 722 00:23:44,830 --> 00:23:45,330 Da? 723 00:23:45,330 --> 00:23:45,740 >> Audiența: [neauzit]. 724 00:23:45,740 --> 00:23:46,860 >> David J. MALAN: Nu există index pentru ea. 725 00:23:46,860 --> 00:23:49,735 Dacă credeți că de acest lucru, într-adevăr, ca un matrice, acest lucru este ca un negativ, 726 00:23:49,735 --> 00:23:52,900 astfel încât nu există nici o memorie de fapt aici dacă acest lucru este într-adevăr un tablou, 727 00:23:52,900 --> 00:23:55,090 ca și cum am declarat săptămâna trecută în curs. 728 00:23:55,090 --> 00:23:56,250 Deci, noi nu trebuie să facem acest lucru. 729 00:23:56,250 --> 00:23:57,340 S-ar putea stoca intr-o variabila. 730 00:23:57,340 --> 00:23:57,820 >> Sau știi ce? 731 00:23:57,820 --> 00:23:59,153 Am auzit pe cineva sa il sugeram. 732 00:23:59,153 --> 00:24:01,020 Ce altceva am putea face cu Stefan? 733 00:24:01,020 --> 00:24:03,770 De ce nu ne-am să-l evacueze și l-au pus pe unde numărul unu a fost. 734 00:24:03,770 --> 00:24:05,170 Deci, dacă vrei să mergi acolo. 735 00:24:05,170 --> 00:24:07,300 Și într-adevăr, aceasta este o soluție destul de bine. 736 00:24:07,300 --> 00:24:10,480 Acum, pe de o parte, am un fel a făcut problema mai rău. 737 00:24:10,480 --> 00:24:13,650 Patru este acum mai departe de unde ar trebui să fie. 738 00:24:13,650 --> 00:24:14,900 Ar trebui să fie față de această jumătate. 739 00:24:14,900 --> 00:24:16,100 >> Dar știi ce? 740 00:24:16,100 --> 00:24:17,630 Care ar fi putut fi ghinion. 741 00:24:17,630 --> 00:24:18,822 Poate număr de opt fost aici. 742 00:24:18,822 --> 00:24:20,530 Și astfel, poate că ar fi au ajuns norocos, 743 00:24:20,530 --> 00:24:22,460 și împins de opt mai aproape de capătul. 744 00:24:22,460 --> 00:24:24,710 Deci, în final a zilei, un fel de toate mediile din. 745 00:24:24,710 --> 00:24:26,085 Nu avem nevoie să aibă grijă cu privire la patru. 746 00:24:26,085 --> 00:24:29,400 Totul mă interesează acum este selectarea cel mai mic element. 747 00:24:29,400 --> 00:24:32,030 >> Și acum, ce am de gând să faci este uitați despre numărul unu 748 00:24:32,030 --> 00:24:35,160 permanent, pentru că știu Lista spatele meu este acum sortate. 749 00:24:35,160 --> 00:24:36,720 Deci lista mea a fost anterior dimensiune opt. 750 00:24:36,720 --> 00:24:37,720 Acum, e de dimensiuni șapte. 751 00:24:37,720 --> 00:24:40,340 Deci, problema mea este obtinerea mai mici, deși liniar. 752 00:24:40,340 --> 00:24:43,022 Asa ca acum, am de gând pentru a selecta mai mic element curent, două. 753 00:24:43,022 --> 00:24:46,520 Șase, opt, patru, trei, șapte, cinci. 754 00:24:46,520 --> 00:24:47,770 Acesta a fost cel mai mic element. 755 00:24:47,770 --> 00:24:49,416 Deci, ce am de gând să fac aplice: ceea ce a fost din nou numele tău? 756 00:24:49,416 --> 00:24:49,760 >> JOSEPH: Joseph. 757 00:24:49,760 --> 00:24:50,085 >> David J. MALAN: Joseph? 758 00:24:50,085 --> 00:24:52,000 Vom lăsa în locul lui Iosif. 759 00:24:52,000 --> 00:24:54,842 Acum, am de gând să mă prefac că tipii ăștia are-- bine, 760 00:24:54,842 --> 00:24:56,550 Știu că aceste două sunt deja sortate. 761 00:24:56,550 --> 00:24:58,424 Să acum se concentrează asupra restul listei. 762 00:24:58,424 --> 00:25:00,080 Șase este cel mai mic curent. 763 00:25:00,080 --> 00:25:01,190 Opt este mai mare. 764 00:25:01,190 --> 00:25:02,970 Patru este acum cel mai mic curent. 765 00:25:02,970 --> 00:25:04,762 Trei este acum cel mai mic curent. 766 00:25:04,762 --> 00:25:07,720 Și așa acum, am de gând să selectați trei, care este-- ce e numele tău? 767 00:25:07,720 --> 00:25:08,190 SERENA: Serena. 768 00:25:08,190 --> 00:25:10,620 David J. MALAN: Serena, dacă ai putea apuca numărul și de swap aplice: 769 00:25:10,620 --> 00:25:11,550 KALSANG: Kalsang. 770 00:25:11,550 --> 00:25:12,940 David J. MALAN: Kalsang. 771 00:25:12,940 --> 00:25:15,220 Vino înapoi, iar noi suntem O să schimb cei doi. 772 00:25:15,220 --> 00:25:17,360 Și acum, să punem asta pe pilot automat. 773 00:25:17,360 --> 00:25:21,589 Am de gând să meargă și lăsați-l la voi pentru a selecta următoarele elemente mai mici. 774 00:25:21,589 --> 00:25:22,380 Dun, dun, dun, dun. 775 00:25:22,380 --> 00:25:24,560 Numărul patru, ceea ce ar trebui să faci? 776 00:25:24,560 --> 00:25:26,261 Excelent. 777 00:25:26,261 --> 00:25:27,760 Acum, am de gând să facă o altă trecere. 778 00:25:27,760 --> 00:25:28,590 Dun, dun, dun, dun. 779 00:25:28,590 --> 00:25:31,465 Văd cinci este cel mai mic următoare. 780 00:25:31,465 --> 00:25:32,840 Acum, am de gând să ia o altă trecere. 781 00:25:32,840 --> 00:25:33,631 Dun, dun, dun, dun. 782 00:25:33,631 --> 00:25:34,880 Șase este cel mai mic. 783 00:25:34,880 --> 00:25:35,520 Bine. 784 00:25:35,520 --> 00:25:36,585 Șapte este cel mai mic. 785 00:25:36,585 --> 00:25:37,085 Nicio schimbare. 786 00:25:37,085 --> 00:25:38,630 Opt este cel mai mic. 787 00:25:38,630 --> 00:25:39,170 Efectuat. 788 00:25:39,170 --> 00:25:43,900 >> Deci, ceea ce tocmai am făcut de iterativ selectarea unui element după alta 789 00:25:43,900 --> 00:25:47,230 se pune în aplicare ceva ce suntem O să formalizeze ca selectarea fel. 790 00:25:47,230 --> 00:25:49,120 Și e poate chiar simplu pentru a explica, 791 00:25:49,120 --> 00:25:51,310 în care literalmente tot ce doriți să faceți este să păstreze doar 792 00:25:51,310 --> 00:25:54,700 merge înainte și înapoi prin lista selectarea, următorul mai mic element, 793 00:25:54,700 --> 00:25:55,720 până ați terminat. 794 00:25:55,720 --> 00:25:58,650 >> Deci e mai simplu, poate intuitiv, decât ultima. 795 00:25:58,650 --> 00:26:00,020 Să încercăm o ultima. 796 00:26:00,020 --> 00:26:03,060 Dacă voi putea voi reseta în următoarele poziții 797 00:26:03,060 --> 00:26:08,600 ultima oară, să vedem dacă nu putem formaliza acum o altă abordare. 798 00:26:08,600 --> 00:26:12,857 De fapt, ar fi cineva acolo ca să propună 799 00:26:12,857 --> 00:26:14,440 Cum altfel am putea merge despre a face acest lucru? 800 00:26:14,440 --> 00:26:17,439 Fără clatina din buzzwords sau fel de răspunsuri care sunt deja cunoscute, 801 00:26:17,439 --> 00:26:19,689 doar intuitiv, ceea ce am putea face? 802 00:26:19,689 --> 00:26:21,635 >> Audiența: [neauzit]. 803 00:26:21,635 --> 00:26:22,510 David J. MALAN: Da. 804 00:26:22,510 --> 00:26:24,620 Deci, există niște intuitie mare acolo. 805 00:26:24,620 --> 00:26:28,020 Lucrurile bune par să se întâmple până în prezent în informatică, atunci când ne-am împărți 806 00:26:28,020 --> 00:26:30,832 și cuceri problema de divizare l în jumătate și jumătate și jumătate. 807 00:26:30,832 --> 00:26:32,540 Și astfel, într-adevăr, ne-am ar putea începe să facă asta. 808 00:26:32,540 --> 00:26:35,754 Și, de fapt, că va fi, vom a se vedea, unul dintre cele mai bune soluții noastră încă. 809 00:26:35,754 --> 00:26:37,420 Dar să revenim la asta înainte de mult timp. 810 00:26:37,420 --> 00:26:40,500 De fapt, vom face că un pic mai târziu în această săptămână. 811 00:26:40,500 --> 00:26:42,180 Ce altceva s-ar putea face pentru a rezolva noi acest lucru? 812 00:26:42,180 --> 00:26:44,647 Astfel încât toată lumea de aici este în Pentru aparent aleatorie. 813 00:26:44,647 --> 00:26:45,230 Știi ce? 814 00:26:45,230 --> 00:26:48,320 Mai degrabă decât du-te înainte și înapoi, înainte și înapoi, înainte și înapoi 815 00:26:48,320 --> 00:26:50,624 de fiecare dată, acest lucru se simte ca Fac o mulțime de mers pe jos. 816 00:26:50,624 --> 00:26:52,790 De ce nu doar încep de la începutul listei, 817 00:26:52,790 --> 00:26:54,960 și doar a pus patru în cazul în care acesta face parte? 818 00:26:54,960 --> 00:26:59,680 Deci lasă-mă să presupunem pentru moment că lista mea este doar acest prim element. 819 00:26:59,680 --> 00:27:04,937 Este de patru sortate în acest moment în timp, dacă tot mă interesează este totul aici? 820 00:27:04,937 --> 00:27:06,520 Aceasta este un fel de trivial adevărat, nu? 821 00:27:06,520 --> 00:27:10,000 Ca și lista conține un singur număr, și că numărul patru este, evident, sortate. 822 00:27:10,000 --> 00:27:13,070 >> Deci, permiteți-mi să prevadă că această listă este sortată. 823 00:27:13,070 --> 00:27:15,090 Dar acum am restul acestei liste. 824 00:27:15,090 --> 00:27:17,240 Așa că acum, am întâlni două. 825 00:27:17,240 --> 00:27:21,690 În cazul în care nu două, evident, aparțin în ceea ce privește patru? 826 00:27:21,690 --> 00:27:22,580 Înainte de patru. 827 00:27:22,580 --> 00:27:23,862 Deci, ce pot face aici? 828 00:27:23,862 --> 00:27:24,820 Care e numele tău din nou? 829 00:27:24,820 --> 00:27:25,090 >> JOSEPH: Joseph. 830 00:27:25,090 --> 00:27:26,030 >> David J. MALAN: Joseph, daca ai putea pas înapoi 831 00:27:26,030 --> 00:27:27,790 pentru o clipă cu numărul dumneavoastră. 832 00:27:27,790 --> 00:27:31,130 Și acum ce ar trebui Stefan fac aici? 833 00:27:31,130 --> 00:27:33,720 Să schimbe Stefan aici. 834 00:27:33,720 --> 00:27:35,520 Și acum, să Joseph veni aici. 835 00:27:35,520 --> 00:27:39,660 Și acum, permiteți-mi să susțin că totul aici este sortata. 836 00:27:39,660 --> 00:27:42,474 Deci, rezultat similar, dar o abordare fundamental diferită. 837 00:27:42,474 --> 00:27:44,140 Nici măcar nu am uitat ce e acolo. 838 00:27:44,140 --> 00:27:46,310 Mă tot iau elementele ca acestea sunt predate la mine, 839 00:27:46,310 --> 00:27:47,240 și să se ocupe cu ei. 840 00:27:47,240 --> 00:27:48,330 >> Așa că acum, am vedea numărul șase. 841 00:27:48,330 --> 00:27:51,110 În cazul în care nu numărul șase aparține? 842 00:27:51,110 --> 00:27:53,250 Avem două, patru, șase. 843 00:27:53,250 --> 00:27:54,800 Exact unde e acum. 844 00:27:54,800 --> 00:27:57,750 Deci, haideți să plece că numai, iar acum susțin că această parte a listei 845 00:27:57,750 --> 00:27:58,772 este acum sortate. 846 00:27:58,772 --> 00:28:01,230 Și astfel, acest lucru se simte fundamental diferit în care eu sunt doar 847 00:28:01,230 --> 00:28:05,230 miscandu-se prin lista de aici liniar, și mă niciodată dublarea înapoi. 848 00:28:05,230 --> 00:28:05,730 Da. 849 00:28:05,730 --> 00:28:06,230 In regula. 850 00:28:06,230 --> 00:28:08,190 Deci opt, în cazul în care nu vă aparțin? 851 00:28:08,190 --> 00:28:08,730 Chiar aici. 852 00:28:08,730 --> 00:28:09,310 Perfect. 853 00:28:09,310 --> 00:28:10,210 Deci, acum, unul. 854 00:28:10,210 --> 00:28:10,900 Uh-oh. 855 00:28:10,900 --> 00:28:13,010 Acest lucru se simte ca și cum ar O să fie scump. 856 00:28:13,010 --> 00:28:15,690 Acum, în algoritmul anterior, Am schimbat oameni. 857 00:28:15,690 --> 00:28:18,648 Deci, s-ar putea să-l pun tot drumul de la la început, dar apoi sa mutat Joseph. 858 00:28:18,648 --> 00:28:21,450 Dar dacă am muta Iosif, acum ce se va fi greșit? 859 00:28:21,450 --> 00:28:24,250 >> Acum, am un fel de undone-- Am luate un pas înainte și apoi 860 00:28:24,250 --> 00:28:26,300 un pas înapoi, pentru că acum Joseph ar fi defect. 861 00:28:26,300 --> 00:28:26,830 Deci, hai sa facem acest lucru. 862 00:28:26,830 --> 00:28:29,150 Dacă ai putea lua numarul unu și pas înapoi pentru un moment. 863 00:28:29,150 --> 00:28:30,490 Cum putem put-- ce a fost din nou numele tău? 864 00:28:30,490 --> 00:28:31,130 >> Annan: Annan. 865 00:28:31,130 --> 00:28:32,610 >> David J. MALAN: Annan in loc? 866 00:28:32,610 --> 00:28:36,091 Ce trebuie să se întâmple cu respect la două, patru, șase, opt? 867 00:28:36,091 --> 00:28:37,570 Ei au nevoie de toate pentru a comuta. 868 00:28:37,570 --> 00:28:42,590 Deci, dacă opt-ar dori să schimbe în primul rând, apoi șase, apoi patru, apoi doi. 869 00:28:42,590 --> 00:28:45,380 Și apoi Annan, dacă ai fi dori să vină aici, bine. 870 00:28:45,380 --> 00:28:47,760 Dar aici, tocmai am un fel de plătit un preț 871 00:28:47,760 --> 00:28:49,510 la un alt punct în algoritmul. 872 00:28:49,510 --> 00:28:52,550 Întrucât ultima dată cu selecție sortare, și chiar cu bule de sortare, 873 00:28:52,550 --> 00:28:54,700 Mă întorc și de mers pe jos mai departe, înainte și înapoi, 874 00:28:54,700 --> 00:28:58,360 care este cu siguranță însumarea timp înțelept, și literalmente trepte. 875 00:28:58,360 --> 00:29:00,660 >> Fel de inserție, la prima scurt, se pare ca e 876 00:29:00,660 --> 00:29:05,150 super-inteligent, în care eu sunt doar face progrese lente, incremental, 877 00:29:05,150 --> 00:29:07,120 dar eu nu am de gând această înainte și înapoi. 878 00:29:07,120 --> 00:29:09,410 Dar dacă cineva este într-adevăr din ordin, aviz 879 00:29:09,410 --> 00:29:10,840 toate lucrările am avut de a face. 880 00:29:10,840 --> 00:29:14,750 A trebuit să se mute jumătate a listei doar pentru a face loc pentru numărul unu. 881 00:29:14,750 --> 00:29:16,790 Deci e aceeași sumă de muncă până în prezent aceasta 882 00:29:16,790 --> 00:29:18,690 se simte, doar un alt tip de muncă. 883 00:29:18,690 --> 00:29:19,370 >> Hai sa continuăm. 884 00:29:19,370 --> 00:29:22,657 Deci, acum știm că toată lumea între unul și opt sunt sortate. 885 00:29:22,657 --> 00:29:23,740 Aici, am numărul trei. 886 00:29:23,740 --> 00:29:25,864 Dacă vă place să ridic numărul trei, un pas înapoi un. 887 00:29:25,864 --> 00:29:28,260 Și ce voi trebuie să faceți? 888 00:29:28,260 --> 00:29:28,760 Da. 889 00:29:28,760 --> 00:29:33,070 Deci asta e alta, doi, trei etape. 890 00:29:33,070 --> 00:29:36,010 Trei unități de timp care costa doar ma, pentru ca trei pot potrivi acum. 891 00:29:36,010 --> 00:29:37,460 În cele din urmă, șapte. 892 00:29:37,460 --> 00:29:39,730 >> Să mergem mai departe și au luați un pas înapoi. 893 00:29:39,730 --> 00:29:42,780 Aceasta este doar o să ne coste o unitate de timp, dar asta e în regulă. 894 00:29:42,780 --> 00:29:44,170 Și acum, cinci de gând să fi un pic mai scump. 895 00:29:44,170 --> 00:29:45,340 Dacă doriți să pas înapoi. 896 00:29:45,340 --> 00:29:48,380 Avem nevoie pentru a muta opt, și șapte, și șase. 897 00:29:48,380 --> 00:29:50,749 Și apoi toată lumea este acum sortate. 898 00:29:50,749 --> 00:29:52,290 Deci, o mână mare de a voluntarilor noștri de aici. 899 00:29:52,290 --> 00:29:53,554 Multumesc foarte mult. 900 00:29:53,554 --> 00:29:56,220 >> [Aplauze] 901 00:29:56,220 --> 00:29:56,860 >> Va multumesc tuturor. 902 00:29:56,860 --> 00:29:57,520 Va multumesc tuturor. 903 00:29:57,520 --> 00:30:02,940 Să vedem acum cât de costisitoare tot ce era. 904 00:30:02,940 --> 00:30:06,210 Să considerăm, probabil, simplă dintre acestea, un fel de bule. 905 00:30:06,210 --> 00:30:09,950 Și eu spun mai simplu, doar pentru că puteți rezolva cu lăcomie de doar 906 00:30:09,950 --> 00:30:11,660 rezolva problema perechi aici. 907 00:30:11,660 --> 00:30:13,720 Rezolva problema perechi aici, iar și iar 908 00:30:13,720 --> 00:30:17,680 și din nou, repetând cât mai multe ori ca ai nevoie de fapt să. 909 00:30:17,680 --> 00:30:21,050 >> Deci, se dovedește că cu un fel de bule, bine, 910 00:30:21,050 --> 00:30:25,820 câți pași nu am să-și asume prima trecere de care algoritm? 911 00:30:25,820 --> 00:30:30,850 S-ar putea să take-- see-- unul, doi, trei, patru, cinci, șase, șapte. 912 00:30:30,850 --> 00:30:32,190 Și există opt elemente de aici. 913 00:30:32,190 --> 00:30:35,280 Deci e ca și cum n minus 1 Pași pentru obține de la începutul listei 914 00:30:35,280 --> 00:30:36,380 la sfârșitul listei. 915 00:30:36,380 --> 00:30:41,350 >> Dar cu selecție fel, amintesc că eu sunt selectarea nou și din nou elementele 916 00:30:41,350 --> 00:30:44,590 și din nou că este cel mai mic, Am o pune în loc, 917 00:30:44,590 --> 00:30:46,616 dar atunci eu nu sunt cauta în spatele meu din nou. 918 00:30:46,616 --> 00:30:49,490 Deci, eu cred că e un pic mai clar apoi că prima dată, am putea 919 00:30:49,490 --> 00:30:52,680 trebuie să ia toate n minus 1 etape pentru a găsi cel mai mic element. 920 00:30:52,680 --> 00:30:55,920 Apoi le-am pus în loc, și eu evacua oricine era aici anterior. 921 00:30:55,920 --> 00:30:57,500 >> Dar atunci nu am să Ți privirea de la acest element, 922 00:30:57,500 --> 00:30:59,040 pentru că știu că e deja cel mai mic. 923 00:30:59,040 --> 00:31:01,581 Deci acum, mă pot uita la doar șapte Elemente, apoi șase elemente, 924 00:31:01,581 --> 00:31:03,290 apoi cinci elemente, apoi patru elemente. 925 00:31:03,290 --> 00:31:06,900 Și astfel matematic, dacă n este numărul de elemente sau numere 926 00:31:06,900 --> 00:31:11,990 că am început cu, vă puteți imagina că aceasta este la fel ca n minus 1, 927 00:31:11,990 --> 00:31:14,250 plus minus n 2 etape, plus minus 3 n trepte, 928 00:31:14,250 --> 00:31:16,780 plus minus n 4 trepte, toate mod de până la doar un pas. 929 00:31:16,780 --> 00:31:18,160 Și eu sunt pe ultima mea persoană. 930 00:31:18,160 --> 00:31:20,650 >> Și dacă vă reamintesc faptul că o mulțime de Statistica cărți sau cărți matematica 931 00:31:20,650 --> 00:31:24,730 au aceste formule pe Hardcover spate sau fata lor, 932 00:31:24,730 --> 00:31:27,690 se dovedește că această serie poate fi exprimat mai simplu 933 00:31:27,690 --> 00:31:28,857 ca de n ori n minus 1 peste 2. 934 00:31:28,857 --> 00:31:31,273 Și este în regulă dacă nu e în fruntea mintea ta. 935 00:31:31,273 --> 00:31:32,420 Dar acest lucru este adevărat. 936 00:31:32,420 --> 00:31:34,449 Asta e doar un mod mai simplu de a scrie aceasta. 937 00:31:34,449 --> 00:31:36,240 Și apoi, dacă credeți Înapoi la școală grad, 938 00:31:36,240 --> 00:31:38,698 când doar începi înmulțirea lucrurile, această desigur, 939 00:31:38,698 --> 00:31:41,820 este doar n pătrat minus n împărțit la 2. 940 00:31:41,820 --> 00:31:44,772 Tot ce am făcut este extinde expresiile de acolo. 941 00:31:44,772 --> 00:31:46,730 Și Să rescrie acest un pic diferit. 942 00:31:46,730 --> 00:31:49,780 Asta pătrat n împărțit la 2 minus n / 2. 943 00:31:49,780 --> 00:31:53,270 >> Deci, din nou, eu sunt doar un fel de a aplica unele aritmetică reguli acolo. 944 00:31:53,270 --> 00:31:57,140 Dar observați acum că cea mai mare pe termen în această expresie, ca să spunem așa, 945 00:31:57,140 --> 00:31:58,540 este că n pătrat. 946 00:31:58,540 --> 00:32:02,910 Deci, da, e n pătrat împărțit la 2, minus n / 2. 947 00:32:02,910 --> 00:32:05,080 >> Dar, în general, în cazul în care n este Va fi o valoare mare, 948 00:32:05,080 --> 00:32:08,740 Am de gând să pretind că n pătrat va fi factorul dominant. 949 00:32:08,740 --> 00:32:10,490 E doar de gând să fie o contribuție mai mare 950 00:32:10,490 --> 00:32:12,877 la numărul de pași ca n / 2. 951 00:32:12,877 --> 00:32:13,960 Deci, ce vreau sa spun prin asta? 952 00:32:13,960 --> 00:32:16,795 Să încercăm un exemplu simplu, chiar deși matematica devine un pic mai mare. 953 00:32:16,795 --> 00:32:20,210 >> Deci, să presupunem că am avut 1 milion de oameni pe scenă, sau 1 milion de lucruri 954 00:32:20,210 --> 00:32:21,320 care ne-o dorim pentru a sorta. 955 00:32:21,320 --> 00:32:23,730 Să conectați un milion în exact această formulă 956 00:32:23,730 --> 00:32:27,230 pentru a vedea cât de multe etape este nevoie totale pentru a sorta un milion de elemente cu ajutorul zicem, 957 00:32:27,230 --> 00:32:28,560 fel de selecție. 958 00:32:28,560 --> 00:32:30,760 >> Deci, vom avea aceeași formulă ca înainte. 959 00:32:30,760 --> 00:32:34,120 Aș conectați un milion, astfel că am obține un milion de pătrat împărțit la 2, 960 00:32:34,120 --> 00:32:35,990 minus un milion împărțit la 2. 961 00:32:35,990 --> 00:32:40,180 Dacă fac asta matematică în avans aici, avem 500 de miliarde 962 00:32:40,180 --> 00:32:47,460 minus 500000, care ne dă 499999500000, 963 00:32:47,460 --> 00:32:49,270 care este destul de darn mare. 964 00:32:49,270 --> 00:32:54,370 >> De fapt, dacă veți compara acum 499000000000, 999000000, 965 00:32:54,370 --> 00:33:01,210 500.000 împotriva valoarea noastră originală, 500 de miliarde de, e al naibii de aproape așa. 966 00:33:01,210 --> 00:33:06,850 Dreapta? n pătrat împărțit la 2 dă us-- sau mai degrabă, n pătrat împărțit la 2 967 00:33:06,850 --> 00:33:08,370 ne-a dat 500 de miliarde. 968 00:33:08,370 --> 00:33:13,510 Asta e al naibii de aproape destul de la 499999500000, 969 00:33:13,510 --> 00:33:17,970 adică scăderea off 500000, sau mai general, scăzând off 970 00:33:17,970 --> 00:33:20,010 n pătrat, nu într-adevăr o afacere mare. 971 00:33:20,010 --> 00:33:22,490 N pătrat face acestea Numerele cresc foarte repede. 972 00:33:22,490 --> 00:33:25,790 >> Acum, aceasta este doar în măsura în care importantă ca noi, ca oameni de stiinta de calculator, 973 00:33:25,790 --> 00:33:29,350 sunt, în general, nu se va pasa atat de mult despre nuante de aceste formule 974 00:33:29,350 --> 00:33:31,400 și exact ceea ce răspunsuri precise sunt. 975 00:33:31,400 --> 00:33:33,390 Ne pasă doar că, știi ce? 976 00:33:33,390 --> 00:33:37,810 La sfârșitul zilei, această formulă este de ordinul a n pătrat. 977 00:33:37,810 --> 00:33:39,350 >> Da, suntem împărțirea de 2 acolo. 978 00:33:39,350 --> 00:33:41,360 Da, suntem scăzând off n minus 2. 979 00:33:41,360 --> 00:33:46,860 Dar la sfârșitul zilei, termenul că într-adevăr ne doare și ne costă 980 00:33:46,860 --> 00:33:48,995 o mulțime de pași este că termenul pătrat. 981 00:33:48,995 --> 00:33:51,370 Și așa mai departe ceea ce un om de stiinta de calculator este de gând să facă, în general, 982 00:33:51,370 --> 00:33:54,160 este ignora tuturor celor termeni de ordine mai mici, 983 00:33:54,160 --> 00:33:56,900 și doar uita-te la cel care contribuie cel mai mult la costul. 984 00:33:56,900 --> 00:34:00,530 >> Și acest lucru este frumos, pentru că putem acum vorbesc în mult mai mare de generalitate 985 00:34:00,530 --> 00:34:02,470 despre algoritmi, și le poate compara. 986 00:34:02,470 --> 00:34:04,550 Și faptul că eu sunt folosirea acestui O este deliberată. 987 00:34:04,550 --> 00:34:06,680 Când spun pe ordinea de, sunt în mod special 988 00:34:06,680 --> 00:34:09,560 referindu-se la ceva numita mare O. Și mare O 989 00:34:09,560 --> 00:34:14,090 este o notație care un computer om de știință utilizează pentru a descrie 990 00:34:14,090 --> 00:34:16,710 superioară o legat pe ceva. 991 00:34:16,710 --> 00:34:21,150 >> Așa că, dacă spun că un algoritm este în mare O de n pătrat, 992 00:34:21,150 --> 00:34:23,380 cum mi-am propus doar o clipă în urmă, înseamnă că 993 00:34:23,380 --> 00:34:27,710 că, în ceea ce privește funcționarea sa timp sau eficiența, 994 00:34:27,710 --> 00:34:30,090 este nevoie de pe ordinea de n pătrat pași. 995 00:34:30,090 --> 00:34:31,420 Poate mai mult, poate mai puțin. 996 00:34:31,420 --> 00:34:33,435 Dar este pe ordinea de n pătrat. 997 00:34:33,435 --> 00:34:34,560 Și asta e hotarul de sus. 998 00:34:34,560 --> 00:34:36,530 Nu va fi mai dureros decât atât. 999 00:34:36,530 --> 00:34:40,800 Nu va fi n tocata, sau 2 la N, sau ceva mult mai mare. 1000 00:34:40,800 --> 00:34:43,800 Aceasta este legat un superior pe orice că cost este. 1001 00:34:43,800 --> 00:34:46,150 Deci dat fiind faptul că, hai să ia în considerare doar câteva exemple. 1002 00:34:46,150 --> 00:34:49,820 Și aceasta este doar o listă finită ori de foarte frecvente care rulează 1003 00:34:49,820 --> 00:34:52,870 pentru algoritmi care este menit să fie ilustrative unele lucruri le-am 1004 00:34:52,870 --> 00:34:53,600 văzut deja. 1005 00:34:53,600 --> 00:34:58,060 >> Deci, de exemplu, în cazul selecție fel, ceea ce eu pretind aici 1006 00:34:58,060 --> 00:35:02,250 este de rulare ca selectia fel de timpul este pe ordinea de n pătrat. 1007 00:35:02,250 --> 00:35:06,260 În cel mai rău caz, am de gând să aibă o grămadă de numere aleatoare aici. 1008 00:35:06,260 --> 00:35:08,600 Și, după cum am văzut matematic, dacă am păstra de mers pe jos 1009 00:35:08,600 --> 00:35:11,310 prin listă, prin lista, selectarea următoarea cea mai mică 1010 00:35:11,310 --> 00:35:14,410 element de nou și din nou, dacă îmi de fapt, scrie toate etapele 1011 00:35:14,410 --> 00:35:18,750 Iau ca mi-am propus formulaically înainte, e pe ordinea de n pătrat 1012 00:35:18,750 --> 00:35:20,370 măsuri care sunt luati. Am 1013 00:35:20,370 --> 00:35:24,520 >> Și se pare că bule sortare și sortare prin inserție 1014 00:35:24,520 --> 00:35:27,370 sunt la fel de lent în cel mai rău caz. 1015 00:35:27,370 --> 00:35:32,040 Luați în considerare, de exemplu, sortare prin inserție, ultimul algoritmul ne-am ocupat cu, 1016 00:35:32,040 --> 00:35:35,500 care a avut ne uităm la element, și apoi introduceți-l în cazul în care acesta face parte. 1017 00:35:35,500 --> 00:35:38,720 Și apoi ne-am uitat la elementul următor, și introdus în cazul în care acesta face parte. 1018 00:35:38,720 --> 00:35:40,990 >> Deci ia în considerare cel mai bun scenariu posibil. 1019 00:35:40,990 --> 00:35:45,590 Să presupunem că am avut de voluntari linia mea de până literalmente ca aceasta, o prin opt, 1020 00:35:45,590 --> 00:35:47,440 deja sortate. 1021 00:35:47,440 --> 00:35:51,300 Câți pași este sortare prin inserție de gând să ia pentru a sorta opt persoane, 1022 00:35:51,300 --> 00:35:55,640 în cazul în care sosesc pe scena aratand ca acest lucru? 1023 00:35:55,640 --> 00:35:57,410 >> Opt persoane sortate deja. 1024 00:35:57,410 --> 00:35:58,760 Și am folosi sortare prin inserție. 1025 00:35:58,760 --> 00:36:02,180 Că ultima a algoritmilor. 1026 00:36:02,180 --> 00:36:03,640 Ei bine, hai să reconstitui rapid reală. 1027 00:36:03,640 --> 00:36:05,504 Deci, dacă am începe aici, văd unul. 1028 00:36:05,504 --> 00:36:06,420 Unde se aparține? 1029 00:36:06,420 --> 00:36:07,730 Ea aparține chiar aici. 1030 00:36:07,730 --> 00:36:08,330 Văd două. 1031 00:36:08,330 --> 00:36:09,660 În cazul în care nu aparține doi? 1032 00:36:09,660 --> 00:36:10,260 Chiar aici. 1033 00:36:10,260 --> 00:36:10,900 Văd trei. 1034 00:36:10,900 --> 00:36:11,920 În cazul în care nu trei aparține? 1035 00:36:11,920 --> 00:36:12,480 Chiar aici. 1036 00:36:12,480 --> 00:36:13,100 >> Văd patru. 1037 00:36:13,100 --> 00:36:13,600 Chiar aici. 1038 00:36:13,600 --> 00:36:15,660 Cinci, șase, șapte, opt. 1039 00:36:15,660 --> 00:36:17,320 Nu e nici un motiv să mă repet. 1040 00:36:17,320 --> 00:36:21,260 Și astfel, cât de mulți pași este că, în ceea ce privește n? 1041 00:36:21,260 --> 00:36:23,870 E pe ordinea de n pași, nu? n minus 1. 1042 00:36:23,870 --> 00:36:27,567 Dar am luat o serie liniară de pași, iar acum am terminat. 1043 00:36:27,567 --> 00:36:28,900 Deci, asta e cel mai bun caz, totuși. 1044 00:36:28,900 --> 00:36:29,983 Ce despre cel mai rău caz? 1045 00:36:29,983 --> 00:36:32,730 Care opt au fost acolo, și șapte au fost acolo, 1046 00:36:32,730 --> 00:36:35,840 și unu și doi au fost aici, așa că lista a fost cu adevărat inversat? 1047 00:36:35,840 --> 00:36:38,300 >> Ei bine, într-adevăr, ceea ce se întâmplă dacă acest lucru este numărul? 1048 00:36:38,300 --> 00:36:41,300 Și vom face doar câteva exemple. 1049 00:36:41,300 --> 00:36:49,300 Ce se întâmplă dacă, într-adevăr, numărul opt este aici, iar Hopa number--. 1050 00:36:49,300 --> 00:36:52,660 1051 00:36:52,660 --> 00:36:56,430 Și ce dacă, într-adevăr, numărul opt este tot drumul până aici, 1052 00:36:56,430 --> 00:36:57,790 și eu sunt, folosind sortare prin inserție? 1053 00:36:57,790 --> 00:36:58,290 >> BINE. 1054 00:36:58,290 --> 00:37:00,280 Am susțin în acest moment este în loc. 1055 00:37:00,280 --> 00:37:03,152 Dar acum, seven-- cazul în care nu merge șapte? 1056 00:37:03,152 --> 00:37:04,360 Desigur, merge aici. 1057 00:37:04,360 --> 00:37:06,760 Așa că trebuie să se mute opt peste un loc. 1058 00:37:06,760 --> 00:37:08,554 Acum șase, unde se duce? 1059 00:37:08,554 --> 00:37:09,220 Ei bine, în regulă. 1060 00:37:09,220 --> 00:37:13,150 Acum, trebuie să se mute peste opt un loc, și șapte pe un loc, 1061 00:37:13,150 --> 00:37:14,440 și apoi am Plop în jos șase. 1062 00:37:14,440 --> 00:37:16,870 >> Deci, prima dată, costul mi un pas pentru a remedia lucrurile, 1063 00:37:16,870 --> 00:37:18,570 atunci ma costat două etape pentru a remedia lucrurile. 1064 00:37:18,570 --> 00:37:20,370 Câți pași este de gând să ia pentru a remedia 1065 00:37:20,370 --> 00:37:22,720 lucruri pentru a pune cinci în locul potrivit? 1066 00:37:22,720 --> 00:37:23,340 Trei. 1067 00:37:23,340 --> 00:37:29,520 Pentru că acum trebuie să muta unul, doi, trei. 1068 00:37:29,520 --> 00:37:32,430 Câte măsuri se merge să ia pentru a pune patru în locul potrivit? 1069 00:37:32,430 --> 00:37:36,040 4 plus 5, plus 6, plus 7. 1070 00:37:36,040 --> 00:37:40,260 >> Și așa e matematic identică cu ceea ce am descris pentru selectarea fel. 1071 00:37:40,260 --> 00:37:42,130 Avem această serie care este doar în creștere. 1072 00:37:42,130 --> 00:37:45,650 1 plus 2, plus 3 plus 4, sau invers, 7 plus 6 1073 00:37:45,650 --> 00:37:52,610 plus 5 plus 4 adaugă pentru astăzi scopuri, de ordinul a n pătrat. 1074 00:37:52,610 --> 00:37:57,640 >> Deci lasă-mă să stipuleze de asemenea, că bubble sort este, de asemenea, în n pătrat. 1075 00:37:57,640 --> 00:38:01,340 Deoarece cu bule fel, fiecare când mă duc prin lista, 1076 00:38:01,340 --> 00:38:03,100 Iau aproximativ cât de mulți pași? 1077 00:38:03,100 --> 00:38:06,260 De fiecare dată când literalmente de mers pe jos de acolo până acolo? 1078 00:38:06,260 --> 00:38:07,960 Aproximativ n pași. 1079 00:38:07,960 --> 00:38:12,650 Dar de câte ori s-ar putea să trebuie să treacă prin lista de? 1080 00:38:12,650 --> 00:38:13,920 >> Ei bine, aproximativ n timp. 1081 00:38:13,920 --> 00:38:15,680 Poate n minus 1, dar aproximativ de N ori. 1082 00:38:15,680 --> 00:38:16,430 Ei bine, de ce este asta? 1083 00:38:16,430 --> 00:38:19,560 Ei bine, cu bule fel, în cazul în care vom începe cu bule fel, 1084 00:38:19,560 --> 00:38:23,570 cu lista în cel mai rău posibil situație, care din nou este complet 1085 00:38:23,570 --> 00:38:25,550 înapoi, ce se va întâmpla? 1086 00:38:25,550 --> 00:38:28,830 Mă duc prin lista, și numărul o parte tot drumul de acolo. 1087 00:38:28,830 --> 00:38:33,280 >> Dar, cu bule fel, nu cât de departe unul muta pe prima mea trecere prin lista? 1088 00:38:33,280 --> 00:38:36,620 Câte locuri are el obține mai aproape de locul corect? 1089 00:38:36,620 --> 00:38:37,240 Doar unul. 1090 00:38:37,240 --> 00:38:40,281 Deci, dacă un fel de motiv, prin acest lucru, de fiecare dată, prin acest algoritm, 1091 00:38:40,281 --> 00:38:41,880 Luând aproximativ n pași lui David. 1092 00:38:41,880 --> 00:38:44,940 Dar cum de multe treceri prin lista este 1093 00:38:44,940 --> 00:38:49,060 de gând să ia pentru o să bule la stânga în cazul în care acesta face parte? 1094 00:38:49,060 --> 00:38:51,840 >> Are să se miște cum ar fi, n spații acest fel. 1095 00:38:51,840 --> 00:38:57,960 Deci, doar pentru a face sortarea listei, Trebuie să meargă înainte și înapoi de n ori. 1096 00:38:57,960 --> 00:39:01,540 Și de fiecare dată, sunt uita la n elemente. 1097 00:39:01,540 --> 00:39:05,410 Deci, nu n lucruri de N ori pe ordinea de n pătrat. 1098 00:39:05,410 --> 00:39:07,220 >> Acum, vom vedea într-un de pantaloni scurți care 1099 00:39:07,220 --> 00:39:10,440 sunt încorporate în viitor problema CS50 lui set, o altă abordare la aceste, 1100 00:39:10,440 --> 00:39:13,490 dar pentru moment, să ia în considerare doar a alteori de funcționare, 1101 00:39:13,490 --> 00:39:16,840 mai ales în cazul în care cele de sortare ia un pic de timp să se scufunde în. 1102 00:39:16,840 --> 00:39:21,790 Ce este un algoritm am văzut deja care ia pe ordinea de n pași? 1103 00:39:21,790 --> 00:39:27,560 >> Ce ar trebui să ia o serie liniară de pași pe care le-am văzut până acum? 1104 00:39:27,560 --> 00:39:29,350 Ce-i asta? 1105 00:39:29,350 --> 00:39:30,480 Căutare director de telefon. 1106 00:39:30,480 --> 00:39:31,390 Primul algoritm. 1107 00:39:31,390 --> 00:39:31,560 Dreapta? 1108 00:39:31,560 --> 00:39:33,650 În cazul în care suntem liniar căutarea Mike Smith? 1109 00:39:33,650 --> 00:39:34,150 Intr-adevar. 1110 00:39:34,150 --> 00:39:37,180 De la o săptămână la zero, atunci când am început de cotitură o pagină la un moment dat, 1111 00:39:37,180 --> 00:39:40,095 și am chiar a spus că a fost un fel unui algoritm sentiment liniar, 1112 00:39:40,095 --> 00:39:42,720 și am avut ca imaginea de pe bord cu linia roșie dreaptă 1113 00:39:42,720 --> 00:39:44,678 și drept galben line, acestea au fost într-adevăr 1114 00:39:44,678 --> 00:39:46,810 algoritmi care sunt în O mare de n. 1115 00:39:46,810 --> 00:39:50,680 >> Deoarece pentru a găsi Mike Smith într-un telefon carte de n pagini, în cel mai rău caz, 1116 00:39:50,680 --> 00:39:52,422 mi n pași s-ar putea lua. 1117 00:39:52,422 --> 00:39:53,630 Ce zici de a lua prezență? 1118 00:39:53,630 --> 00:39:55,790 Unu doi trei patru cinci șase. 1119 00:39:55,790 --> 00:39:59,420 Care este timpul de rulare a acestei algoritm pentru a lua participarea? 1120 00:39:59,420 --> 00:40:03,070 O mare de n, pentru că în teorie I Trebuie să subliniez toată lumea din sală. 1121 00:40:03,070 --> 00:40:05,861 >> Acum ca o paranteza, ceea ce despre alte optimizare de la zero, săptămâna? 1122 00:40:05,861 --> 00:40:08,117 Doi, patru, șase, opt, 10, 12. 1123 00:40:08,117 --> 00:40:10,200 Un om de stiinta de calculator ar realiza, așteptați un minut, 1124 00:40:10,200 --> 00:40:12,320 care este pe ordinea de n împărțit la doi pași. 1125 00:40:12,320 --> 00:40:12,820 Dreapta? 1126 00:40:12,820 --> 00:40:14,444 Pentru că fac doi oameni la un moment dat. 1127 00:40:14,444 --> 00:40:17,015 Dar am de gând să ignore acei termeni ordin inferior, 1128 00:40:17,015 --> 00:40:19,140 si noi suntem doar de gând să arunca decalajului de 2, 1129 00:40:19,140 --> 00:40:21,830 și doar spun, O mare de n pentru că algoritmul de asemenea. 1130 00:40:21,830 --> 00:40:22,760 >> Ce zici de asta? 1131 00:40:22,760 --> 00:40:26,170 Vom sari peste unele dintre acestea, dar ceea ce Acesta este un algoritm care a fost log de n? 1132 00:40:26,170 --> 00:40:29,900 Care a avut log aproximativ n pași? 1133 00:40:29,900 --> 00:40:30,870 Decalajului și să cucerească. 1134 00:40:30,870 --> 00:40:31,369 Exact. 1135 00:40:31,369 --> 00:40:33,900 Ca și exemplu de carte de telefon în săptămână zero și mai devreme, 1136 00:40:33,900 --> 00:40:36,191 în cazul în care ne-am impartit problema din nou și din nou și din nou. 1137 00:40:36,191 --> 00:40:39,070 Am atras de pe placa de saptamana zero, ca o linie verde curbat, 1138 00:40:39,070 --> 00:40:41,460 și am spus în acea zi a fost un algoritm logaritmică. 1139 00:40:41,460 --> 00:40:44,970 >> Și într-adevăr, numărul de pași IT ia pentru a efectua divide și stăpânește, 1140 00:40:44,970 --> 00:40:48,610 sau de căutare binară ca vom începe numindu-l, la fel ca în cartea de telefon, 1141 00:40:48,610 --> 00:40:50,680 este de ordinul a jurnalului și etape. 1142 00:40:50,680 --> 00:40:52,470 Și aceasta este un pic de un ciudat. 1143 00:40:52,470 --> 00:40:54,910 >> Ce face un pas, sau mai precis 1144 00:40:54,910 --> 00:40:56,240 un număr constant de pași? 1145 00:40:56,240 --> 00:40:58,865 Poate că e de două, poate e de trei, dar un om de stiinta de calculator doar 1146 00:40:58,865 --> 00:41:01,423 simplifică l ca O mare de 1, unele număr constant de pași. 1147 00:41:01,423 --> 00:41:04,256 Ce e ceva ce ar putea face asta ia un număr constant de pași? 1148 00:41:04,256 --> 00:41:08,030 1149 00:41:08,030 --> 00:41:10,930 >> Care este timpul de rulare a aclama? 1150 00:41:10,930 --> 00:41:11,920 Constantă de timp. 1151 00:41:11,920 --> 00:41:12,420 Dreapta? 1152 00:41:12,420 --> 00:41:15,490 Cum ar fi, ce-i timpul de rulare a face nimic care să ia doar o 1153 00:41:15,490 --> 00:41:18,570 operare, cum ar fi imprimarea F Hello World. 1154 00:41:18,570 --> 00:41:24,110 Care ar putea fi spus să fie timp constant, cu excepția cazului în mai puțin caz colț cu print F, 1155 00:41:24,110 --> 00:41:28,260 Ce ar putea timp de funcționare de imprimare F fi de fapt? 1156 00:41:28,260 --> 00:41:28,790 Și de ce? 1157 00:41:28,790 --> 00:41:30,550 Ce este n măsură în acest caz? 1158 00:41:30,550 --> 00:41:32,251 >> Audiența: [neauzit]. 1159 00:41:32,251 --> 00:41:33,250 David J. MALAN: Exact. 1160 00:41:33,250 --> 00:41:34,900 Numărul de caractere vrem să imprimați. 1161 00:41:34,900 --> 00:41:36,191 Deci, este foarte sensibile la context. 1162 00:41:36,191 --> 00:41:39,910 Astăzi, ne-am concentrat foarte mult pe litere și numere de aici de pe bord. 1163 00:41:39,910 --> 00:41:43,540 Dar ar putea fi, de asemenea, caractere în un șir actuale. 1164 00:41:43,540 --> 00:41:46,420 Deci, se dovedește că un alt măsură care va începe pese, 1165 00:41:46,420 --> 00:41:48,530 și asta e opusul de mare O, ca să spunem așa. 1166 00:41:48,530 --> 00:41:50,120 >> Asta e notație Omega. 1167 00:41:50,120 --> 00:41:53,380 Întrucât mare O înseamnă ceea ce, The superior legat la timp de funcționare? 1168 00:41:53,380 --> 00:41:55,580 Maxim, cât de mult timp s-ar putea să ia ceva? 1169 00:41:55,580 --> 00:41:59,250 Omega-- pare rău acest lucru ține vine up-- este opusul care, 1170 00:41:59,250 --> 00:42:02,960 prin care este o limită inferioară, pe de perioada de timp ceva s-ar putea lua. 1171 00:42:02,960 --> 00:42:10,480 >> Asa ca. De exemplu, ceea ce este un algoritm care ia măsuri mereu n patrat? 1172 00:42:10,480 --> 00:42:15,600 Ei bine, unul dintre algoritmii am văzut astăzi, de fapt, s-ar putea să fie la fel de bine. 1173 00:42:15,600 --> 00:42:16,720 Fel de selecție. 1174 00:42:16,720 --> 00:42:18,270 Selecție fel e destul de prost. 1175 00:42:18,270 --> 00:42:21,760 Chiar dacă algorithm-- Ne pare rău, chiar dacă matricea este deja sortate, 1176 00:42:21,760 --> 00:42:24,150 Selecția fel se va păstrează de mers pe jos prin listă 1177 00:42:24,150 --> 00:42:28,907 pentru a vă asigura că are cel mai mic element de nou și din nou și din nou. 1178 00:42:28,907 --> 00:42:31,740 Și chiar dacă oameni in public stiu ca, așteptați un minut, 1179 00:42:31,740 --> 00:42:33,948 ai trecut deja cel mai mic element calculatorul 1180 00:42:33,948 --> 00:42:37,300 nu știe că până se pare tot drumul prin lista. 1181 00:42:37,300 --> 00:42:40,240 In mod similar, o limită inferioară care ar putea fi, de asemenea, luate în considerare 1182 00:42:40,240 --> 00:42:42,000 ar putea fi timpul liniar. 1183 00:42:42,000 --> 00:42:48,260 >> Cât timp este nevoie pentru a fel n elemente din cele mai bune 1184 00:42:48,260 --> 00:42:52,420 caz, folosind ceva de genul bubble fel? 1185 00:42:52,420 --> 00:42:54,280 Să presupunem că lista este deja sortate. 1186 00:42:54,280 --> 00:42:56,696 Am spus bubble sort ia pe ordinea de n pătrat pași. 1187 00:42:56,696 --> 00:42:59,640 Dar dacă e deja sortate? 1188 00:42:59,640 --> 00:43:02,310 Ce se întâmplă dacă îți dai seama după o singură trecere prin matrice 1189 00:43:02,310 --> 00:43:03,540 care le-ați făcut nici o swap-uri? 1190 00:43:03,540 --> 00:43:05,970 Ai nevoie pentru a păstra face mai multe treceri? 1191 00:43:05,970 --> 00:43:06,470 >> Nu. 1192 00:43:06,470 --> 00:43:10,340 Deci, o limită inferioară de pe bubble sort ar fi spus să fie liniar. 1193 00:43:10,340 --> 00:43:11,830 Omega de n. 1194 00:43:11,830 --> 00:43:14,450 Si ne putem uita la altele ale acestora, precum și. 1195 00:43:14,450 --> 00:43:17,990 Deci, haideți să aruncăm o privire rapidă la doar o vizualizare aici 1196 00:43:17,990 --> 00:43:20,790 pentru a vedea modul în care acestea se disting. 1197 00:43:20,790 --> 00:43:24,592 Am de gând să meargă în jos aici, în această Pagina care este disponibil pe site-ul C50 de, 1198 00:43:24,592 --> 00:43:27,550 dar va fi o durere pentru a obține de lucru, deoarece foloseste o tehnologie numita 1199 00:43:27,550 --> 00:43:30,560 Applet-uri Java, care este un în mare măsură neacceptat in aceste zile, 1200 00:43:30,560 --> 00:43:32,730 cel puțin de Chrome și anumite alții. 1201 00:43:32,730 --> 00:43:37,070 >> Și lasă-mă să merg mai departe și de a accelera acest și să explice ce se întâmplă. 1202 00:43:37,070 --> 00:43:40,840 Aceasta este o demonstrație de balon sortare, primul algoritm ne-am uitat la. 1203 00:43:40,840 --> 00:43:43,950 Și este un vizualizare în care fiecare din aceste bare reprezintă un număr. 1204 00:43:43,950 --> 00:43:45,710 Cu atât mai mare bar, cu atât mai mare numărul. 1205 00:43:45,710 --> 00:43:47,520 Mai mici la bar, este mai mic numărul. 1206 00:43:47,520 --> 00:43:50,353 Și ceea ce se poate vedea vizual, chiar deși acest lucru se întâmplă super rapid, 1207 00:43:50,353 --> 00:43:53,699 este faptul că bara de roșu este ca mine, de mers pe jos înapoi și de stabilire înapoi probleme. 1208 00:43:53,699 --> 00:43:56,740 Puteți vedea că elementele mai mari sunt într-adevăr barbotare până la dreapta, 1209 00:43:56,740 --> 00:43:59,650 și elementele mici sunt barbotare la stânga. 1210 00:43:59,650 --> 00:44:01,870 Și aici, dacă de fapt, uite mai atent, 1211 00:44:01,870 --> 00:44:04,330 putem conta, de fapt, Numărul de comparații și swap-uri 1212 00:44:04,330 --> 00:44:05,350 care au fost făcute. 1213 00:44:05,350 --> 00:44:07,360 >> Dar, în loc, să ne uităm la două algoritmul 1214 00:44:07,360 --> 00:44:11,240 ne-am uitat la mai devreme, cu noastre voluntari, de selecție de sortare. 1215 00:44:11,240 --> 00:44:13,500 Vizual, are o efect foarte diferit. 1216 00:44:13,500 --> 00:44:16,820 Dar e, din nou, foarte intuitiv, în că păstrăm selectarea următoarea cea mai mică 1217 00:44:16,820 --> 00:44:18,660 element și avem un pic de noroc. 1218 00:44:18,660 --> 00:44:20,110 Că a simțit fundamental mai repede. 1219 00:44:20,110 --> 00:44:22,840 Dar dacă am fugit acest nou și din nou și din nou cu o mulțime de intrări, 1220 00:44:22,840 --> 00:44:26,680 am vedea că este într-adevăr încă în O mare de n pătrat. 1221 00:44:26,680 --> 00:44:29,920 >> Să facem o ultimă unul aici, sortare prin inserție, 1222 00:44:29,920 --> 00:44:33,180 care a fost treilea algoritmul ne-am uitat la, și rechemare 1223 00:44:33,180 --> 00:44:36,700 că aceasta se referă la ca elemente le întâlnește, 1224 00:44:36,700 --> 00:44:39,290 dar apoi a, poate, schimburi lucruri pe pentru a face loc, 1225 00:44:39,290 --> 00:44:41,660 inserarea elemente de care apartin. 1226 00:44:41,660 --> 00:44:45,330 >> Și acest lucru se termină prea oferind rezultat final. Acum toate cele trei din cei 1227 00:44:45,330 --> 00:44:46,490 simțit destul de repede. 1228 00:44:46,490 --> 00:44:48,740 Și într-adevăr, le-am fugit la un clip destul de bine. 1229 00:44:48,740 --> 00:44:52,510 Dar fundamental, toate sunt destul de oribil, să fiu sincer. 1230 00:44:52,510 --> 00:44:56,960 Toate aceste algoritmi până acum care rulează în O mare de n pătrat 1231 00:44:56,960 --> 00:44:59,270 ia destul de un pic de timp pentru a rula în cele din urmă. 1232 00:44:59,270 --> 00:45:01,920 >> Și într-adevăr, putem vedea și în cele din urmă se simt acest 1233 00:45:01,920 --> 00:45:04,090 dacă am trage acest demo a treia și ultima. 1234 00:45:04,090 --> 00:45:05,840 Acesta este un alt vizualizare care va 1235 00:45:05,840 --> 00:45:08,500 pentru a arăta bubble sort pe stânga, sort de selecție în mijloc, 1236 00:45:08,500 --> 00:45:13,410 și ceva, ca unul dintre noastre mână ridică sugerat mai devreme, 1237 00:45:13,410 --> 00:45:15,020 merge sort pe dreapta. 1238 00:45:15,020 --> 00:45:16,937 O divizare și cucerire strategia pe dreapta. 1239 00:45:16,937 --> 00:45:19,520 Și asta e, de fapt, ceea ce suntem O să se uite la miercuri. 1240 00:45:19,520 --> 00:45:21,990 Dar să timp acestea să ruleze în paralel. 1241 00:45:21,990 --> 00:45:26,765 Este aproximativ același număr de Elemente, toate rulează în același timp. 1242 00:45:26,765 --> 00:45:30,940 1243 00:45:30,940 --> 00:45:34,440 Bubble sort vs selecție fel vs merge sort. 1244 00:45:34,440 --> 00:45:36,760 >> Acum, toate acestea sunt difuzate în teorie, în același timp. 1245 00:45:36,760 --> 00:45:39,830 Procesorul se execută la aceeași viteză, dar 1246 00:45:39,830 --> 00:45:44,014 pot simți cât de plictisitor este foarte repede va deveni, 1247 00:45:44,014 --> 00:45:45,930 și cât de repede atunci am injecta un pic de săptămână 1248 00:45:45,930 --> 00:45:49,330 algoritmi de zero lui poate am accelera lucrurile. 1249 00:45:49,330 --> 00:45:51,760 >> Și acum să comparăm acestea într-o formă trecut. 1250 00:45:51,760 --> 00:45:55,710 Am de gând să merg mai departe la site-ul CS50, unde 1251 00:45:55,710 --> 00:45:59,020 avem această legătură finală pentru ziua de azi, în cazul în care cineva de pe internet 1252 00:45:59,020 --> 00:46:03,960 amabilitate pune împreună un video care surprinde ceea ce diferit de sortare 1253 00:46:03,960 --> 00:46:07,510 algoritmi suna ca. 1254 00:46:07,510 --> 00:46:09,577 Aceasta este un fel de introducere. 1255 00:46:09,577 --> 00:46:12,072 >> [Bip] 1256 00:46:12,072 --> 00:46:13,070 1257 00:46:13,070 --> 00:46:16,850 >> Prin care aplici o frecvență bazate pe înălțimea barei bar. 1258 00:46:16,850 --> 00:46:19,826 Acest lucru este cu bule fel. 1259 00:46:19,826 --> 00:46:21,822 >> [Bip Warped] 1260 00:46:21,822 --> 00:46:33,299 1261 00:46:33,299 --> 00:46:45,774 >> Urmează este-- vine up următor este-- fel de selecție, 1262 00:46:45,774 --> 00:46:48,820 în cazul în care, din nou, ne selectarea următor mai mic element, 1263 00:46:48,820 --> 00:46:51,820 și putem vedea în creștere de la stânga la dreapta. 1264 00:46:51,820 --> 00:47:01,120 1265 00:47:01,120 --> 00:47:04,000 >> Merge fel, câștigătorul nostru până acum astăzi. 1266 00:47:04,000 --> 00:47:09,659 1267 00:47:09,659 --> 00:47:12,450 Observați cum se împarte lucrurile în [inaudibil] jumătate și sferturi. 1268 00:47:12,450 --> 00:47:17,510 1269 00:47:17,510 --> 00:47:21,660 Fel Gnome, care nu avem a vorbit despre, și creează vizual 1270 00:47:21,660 --> 00:47:24,450 și audally un pic de o diferite forme și sunet. 1271 00:47:24,450 --> 00:47:27,060 1272 00:47:27,060 --> 00:47:30,160 Merge înainte și înapoi, curățare lucrurile. 1273 00:47:30,160 --> 00:47:32,230 De asemenea, a verifica afară heapsort pe site-ul acestui tip. 1274 00:47:32,230 --> 00:47:36,100 1275 00:47:36,100 --> 00:47:36,810 >> Si asta e. 1276 00:47:36,810 --> 00:47:38,210 Vă vom vedea data viitoare. 1277 00:47:38,210 --> 00:47:42,647 1278 00:47:42,647 --> 00:47:48,334 >> [Whooshing ȘI MUZICĂ] 1279 00:47:48,334 --> 00:50:24,839