1 00:00:00,000 --> 00:00:11,100 >> [Музички] 2 00:00:11,100 --> 00:00:11,490 >> Дејвид Џ MALAN: Во ред. 3 00:00:11,490 --> 00:00:12,170 Па добредојде назад. 4 00:00:12,170 --> 00:00:15,180 Ова е CS50, и е на крајот од третата седмица. 5 00:00:15,180 --> 00:00:17,770 >> Па се потсетиме во последните неколку недели, ние сме биле трошење доста 6 00:00:17,770 --> 00:00:20,820 време на C, на програмирање, на синтакса. 7 00:00:20,820 --> 00:00:24,680 И тоа е сосема нормално, ако сте уште бори со проблемот Постави 2, за да биде 8 00:00:24,680 --> 00:00:25,950 удира главата од ѕидот. 9 00:00:25,950 --> 00:00:28,310 Тоа е криптичната изглед пораки за грешки и грешки кои ви 10 00:00:28,310 --> 00:00:29,220 не може сосема потера надолу. 11 00:00:29,220 --> 00:00:32,310 Бидејќи, остатокот увери, дека во само неколку недели "време ќе се погледне назад на 12 00:00:32,310 --> 00:00:35,930 работи како Цезар, и [? V-genair,?] можеби дури и Crack, и 13 00:00:35,930 --> 00:00:40,050 сфаќаат колку далеку си дојден во краток временски период. 14 00:00:40,050 --> 00:00:43,670 Па ако тоа е некаква утеха, висат во таму сега за сега. 15 00:00:43,670 --> 00:00:46,610 >> Денес, иако, да почнеме да транзиција да работи на повисоко ниво. 16 00:00:46,610 --> 00:00:49,820 И ние почнуваме да се земе здраво за готово дека вие момци знаат како да програма, или во 17 00:00:49,820 --> 00:00:52,090 барем почетоците на дека удобност ниво. 18 00:00:52,090 --> 00:00:56,520 И ќе почнеме да се разгледа како можеме да одат за дизајнирање на програми повеќе 19 00:00:56,520 --> 00:00:57,440 ефективно. 20 00:00:57,440 --> 00:01:01,090 Како можеме да одиме за оптимизирање на ефикасноста на нашите алгоритми, и 21 00:01:01,090 --> 00:01:03,110 генерално решавање на повеќе интересни проблеми. 22 00:01:03,110 --> 00:01:06,850 И почнува да се земе здраво за готово дека, ако сакавме да, би можеле да се код на која било 23 00:01:06,850 --> 00:01:08,350 од примерите што ја имаме во умот. 24 00:01:08,350 --> 00:01:11,430 Така, денес, ние не допирајте ја тастатурата за било каква форма на код. 25 00:01:11,430 --> 00:01:15,150 Тоа ќе биде многу повисоко ниво, а во крајна линија, за решавање на проблемите. 26 00:01:15,150 --> 00:01:20,490 >> Па да се дојде до тој момент, дозволете ми да предложат дека следните седум 27 00:01:20,490 --> 00:01:24,290 правоаголници претставуваат седум врати, зад кои се цел куп 28 00:01:24,290 --> 00:01:26,340 броеви, меѓу кои е бројот 50. 29 00:01:26,340 --> 00:01:30,470 Дозволете ми да проектираат тоа на овој екран и тука. 30 00:01:30,470 --> 00:01:36,770 И предложи дека ние треба волонтер за да ми помогне да најдете голем број пред 31 00:01:36,770 --> 00:01:38,140 на интернет тука за да ја видите. 32 00:01:38,140 --> 00:01:40,755 Ајде горе, во розова. 33 00:01:40,755 --> 00:01:43,050 Сите во право. 34 00:01:43,050 --> 00:01:43,930 Што е вашето име? 35 00:01:43,930 --> 00:01:44,850 >> JENNIFER: [нечујни] 36 00:01:44,850 --> 00:01:45,170 >> Дејвид Џ MALAN: Молам? 37 00:01:45,170 --> 00:01:45,860 >> JENNIFER: Џенифер. 38 00:01:45,860 --> 00:01:46,390 >> Дејвид Џ MALAN: Џенифер. 39 00:01:46,390 --> 00:01:46,980 Сите во право, Џенифер. 40 00:01:46,980 --> 00:01:47,630 Убаво да ви се исполнат. 41 00:01:47,630 --> 00:01:48,370 Ајде горе. 42 00:01:48,370 --> 00:01:52,430 Па овие тука се седум порти, и она што Би сакал да го стори за нас овде, 43 00:01:52,430 --> 00:01:56,560 пред сите на своите соученици, ни се најде бројот, 50. 44 00:01:56,560 --> 00:02:00,860 Да се ​​најдат голем број, можете да ѕиркаат зад било која од овие врати со едноставно прислушување 45 00:02:00,860 --> 00:02:03,030 на една од вратите, и тоа ќе се открие нејзиниот број. 46 00:02:03,030 --> 00:02:06,080 И да видиме колку брзо ќе може да ни се најде бројот, 50. 47 00:02:06,080 --> 00:02:09,979 48 00:02:09,979 --> 00:02:11,229 >> 15. 49 00:02:11,229 --> 00:02:13,110 50 00:02:13,110 --> 00:02:14,360 16. 51 00:02:14,360 --> 00:02:16,270 52 00:02:16,270 --> 00:02:16,530 50. 53 00:02:16,530 --> 00:02:17,350 Убаво направено. 54 00:02:17,350 --> 00:02:18,040 Сите во право. 55 00:02:18,040 --> 00:02:19,906 Аплауз за Џенифер. 56 00:02:19,906 --> 00:02:21,530 >> [Аплауз] 57 00:02:21,530 --> 00:02:22,320 >> Сите во право. 58 00:02:22,320 --> 00:02:25,254 Значи она што беше вашата стратегија за наоѓање на бројот, 50? 59 00:02:25,254 --> 00:02:27,222 >> JENNIFER: Хм, мислев дека можеби ако - 60 00:02:27,222 --> 00:02:27,714 [Нечујни] 61 00:02:27,714 --> 00:02:28,206 >> Дејвид Џ MALAN: О. 62 00:02:28,206 --> 00:02:29,630 Го даде една секунда. 63 00:02:29,630 --> 00:02:32,420 Така беше вашата стратегија за наоѓање на бројот, 50? 64 00:02:32,420 --> 00:02:34,760 >> JENNIFER: Па јас само започне во почнуваат да се види она што го првиот број 65 00:02:34,760 --> 00:02:38,590 беше, и тогаш си помислив, можеби ако тие се подредени, јас само ќе ги задржи 66 00:02:38,590 --> 00:02:39,970 прислушување повисоко? 67 00:02:39,970 --> 00:02:40,140 >> Дејвид Џ MALAN: OK. 68 00:02:40,140 --> 00:02:42,910 И се чини дека го пронашле дека за да биде случај. 69 00:02:42,910 --> 00:02:45,670 Иако, ајде да лупам назад на слоеви само малку, а вие сакате да одите 70 00:02:45,670 --> 00:02:47,640 напред и да открие други врати можете да ја одбрале? 71 00:02:47,640 --> 00:02:50,400 72 00:02:50,400 --> 00:02:51,712 >> JENNIFER: Ох, драга. 73 00:02:51,712 --> 00:02:53,128 >> Дејвид Џ MALAN: Ах. 74 00:02:53,128 --> 00:02:54,280 >> JENNIFER: Па јас само се насмевна. 75 00:02:54,280 --> 00:02:55,270 >> Дејвид Џ MALAN: Значи ли среќа. 76 00:02:55,270 --> 00:02:55,710 Сите во право. 77 00:02:55,710 --> 00:02:56,795 Па не е лошо. 78 00:02:56,795 --> 00:02:58,750 Но тоа е интересна увид, нели? 79 00:02:58,750 --> 00:03:01,870 Ако се претпоставува, а ти не добие, навистина, малку среќа таму. 80 00:03:01,870 --> 00:03:05,350 Но ако се претпостави дека броеви беа сортирани, можете да бидете попрецизни 81 00:03:05,350 --> 00:03:08,750 за тоа како тоа влијаело вашето однесување? 82 00:03:08,750 --> 00:03:11,715 >> JENNIFER: Значи, ако тие беа подредени, јас дека можеби најмалите до најголемите. 83 00:03:11,715 --> 00:03:11,970 >> Дејвид Џ MALAN: OK. 84 00:03:11,970 --> 00:03:15,260 >> JENNIFER: Или ако тоа заврши се навистина голема, а потоа најголемиот до најмалиот. 85 00:03:15,260 --> 00:03:15,540 >> Дејвид Џ MALAN: OK. 86 00:03:15,540 --> 00:03:18,170 Па најголемиот до најмалиот, или најмалите до најголемите. 87 00:03:18,170 --> 00:03:21,990 Но, дозволете ми предложи, да претпоставиме дека имале добивано и несреќен, и претпоставувам дека тие 88 00:03:21,990 --> 00:03:26,840 не беа, всушност, подредени, колку од тие врати може да сте имале да ѕиркаат 89 00:03:26,840 --> 00:03:28,590 зад себе во кој најлош случај? 90 00:03:28,590 --> 00:03:29,860 >> JENNIFER: Сите од нив. 91 00:03:29,860 --> 00:03:30,420 >> Дејвид Џ MALAN: Сите од нив. 92 00:03:30,420 --> 00:03:31,740 Па ајде да се генерализира дека како n. 93 00:03:31,740 --> 00:03:34,790 Таму се случува да биде 7, но ајде повеќе обично велат дека е n врати на 94 00:03:34,790 --> 00:03:35,650 екранот овде. 95 00:03:35,650 --> 00:03:40,110 Па во најлош случај, ќе треба да се погледне зад 7 врати, или n врати. 96 00:03:40,110 --> 00:03:44,140 И така тоа навистина е, тоа е малку среќа денес, но тоа е навистина една линеарна 97 00:03:44,140 --> 00:03:46,440 алгоритам на сорти, дури и ако беа вид на скокнеш наоколу. 98 00:03:46,440 --> 00:03:47,080 Е тоа фер? 99 00:03:47,080 --> 00:03:47,500 >> JENNIFER: Да. 100 00:03:47,500 --> 00:03:50,000 >> Дејвид Џ MALAN: Па, дозволете ми да се види ако вашиот стратегија промени, ако јас се движат од нас да 101 00:03:50,000 --> 00:03:52,190 нашиот втор пример тука со 7 различни врати. 102 00:03:52,190 --> 00:03:55,240 Истите броеви, но ова време тие се подредени. 103 00:03:55,240 --> 00:03:58,350 Која е вашата стратегија тука ќе биде, обидуваат да се стави надвор од вашиот ум она што 104 00:03:58,350 --> 00:03:59,310 другите броеви беа - 105 00:03:59,310 --> 00:03:59,930 >> Џенифер: Добро. 106 00:03:59,930 --> 00:04:02,290 >> Дејвид Џ MALAN: - порано? 107 00:04:02,290 --> 00:04:03,180 >> JENNIFER: Да почнеме со првиот. 108 00:04:03,180 --> 00:04:03,540 >> Дејвид Џ MALAN: Во ред. 109 00:04:03,540 --> 00:04:05,190 Започнете со првиот. 110 00:04:05,190 --> 00:04:05,960 4. 111 00:04:05,960 --> 00:04:08,810 Сега каде ќе одиш, и зошто? 112 00:04:08,810 --> 00:04:10,040 >> JENNIFER: 4 е навистина мал. 113 00:04:10,040 --> 00:04:12,500 Значи, ако тие се вид можеби најмалите до најголемите, што треба 114 00:04:12,500 --> 00:04:13,290 да биде двојно, и -. 115 00:04:13,290 --> 00:04:13,670 >> Дејвид Џ MALAN: OK. 116 00:04:13,670 --> 00:04:15,990 Ајде да видиме, кој мислите? 117 00:04:15,990 --> 00:04:19,050 >> JENNIFER: Обидете последен. 118 00:04:19,050 --> 00:04:19,500 Убаво. 119 00:04:19,500 --> 00:04:20,880 >> Дејвид Џ MALAN: Многу убаво направено. 120 00:04:20,880 --> 00:04:21,860 Сите во право. 121 00:04:21,860 --> 00:04:23,010 >> [Аплауз] 122 00:04:23,010 --> 00:04:24,310 >> Дејвид Џ MALAN: OK. 123 00:04:24,310 --> 00:04:26,790 Па ти си, всушност, го прават тоа ужасно, затоа што ти си 124 00:04:26,790 --> 00:04:27,700 го прават тоа многу добро. 125 00:04:27,700 --> 00:04:31,150 Кои нè остава во состојба да направи одредени точки. 126 00:04:31,150 --> 00:04:32,565 Па ајде да се обидеме да се тркалаат назад тука. 127 00:04:32,565 --> 00:04:34,560 >> Џенифер: Добро. 128 00:04:34,560 --> 00:04:35,980 >> Дејвид Џ MALAN: Многу добро направи, сеедно. 129 00:04:35,980 --> 00:04:39,060 Па ти почна на почетокот, те видов дека тоа беше 4, тогаш 130 00:04:39,060 --> 00:04:40,240 пресели на крајот. 131 00:04:40,240 --> 00:04:42,320 Но да претпоставиме дека не се среќни таму, и да претпоставиме 50 132 00:04:42,320 --> 00:04:42,890 беше некаде на друго место. 133 00:04:42,890 --> 00:04:46,190 Што вашиот Третиот чекор биле? 134 00:04:46,190 --> 00:04:47,680 >> JENNIFER: Врати се на почеток. 135 00:04:47,680 --> 00:04:48,320 >> Дејвид Џ MALAN: Одете назад на почеток. 136 00:04:48,320 --> 00:04:51,320 Добро, така што ќе го допре оваа врата, која беше 8. 137 00:04:51,320 --> 00:04:51,660 Сите во право. 138 00:04:51,660 --> 00:04:52,650 Па тоа не е 50. 139 00:04:52,650 --> 00:04:55,380 Каде што ќе се загледа следно? 140 00:04:55,380 --> 00:04:56,720 >> JENNIFER: Ако јас не знаат дека подредени. 141 00:04:56,720 --> 00:04:57,005 >> Дејвид Џ MALAN: Точни. 142 00:04:57,005 --> 00:04:58,490 Па, ако не знаете тие беа сортирани - 143 00:04:58,490 --> 00:04:58,700 >> JENNIFER: О, знаев, да. 144 00:04:58,700 --> 00:05:00,910 >> Дејвид Џ MALAN: - Но, вие не знаат каде 50 беше уште? 145 00:05:00,910 --> 00:05:01,785 >> JENNIFER: Само продолжувам да одам. 146 00:05:01,785 --> 00:05:02,130 >> Дејвид Џ MALAN: Во ред. 147 00:05:02,130 --> 00:05:02,520 OK. 148 00:05:02,520 --> 00:05:03,800 Продолжувам да одам. 149 00:05:03,800 --> 00:05:05,270 Добро, дека јас може да работи со. 150 00:05:05,270 --> 00:05:05,610 >> Џенифер: Добро. 151 00:05:05,610 --> 00:05:07,210 >> Дејвид Џ MALAN: Сега, ако ти си само случува да Продолжувам да одам, она што е вашиот 152 00:05:07,210 --> 00:05:09,680 алгоритам префрлени поддржани во. 153 00:05:09,680 --> 00:05:10,740 >> JENNIFER: Линеарната -. 154 00:05:10,740 --> 00:05:11,820 >> Дејвид Џ MALAN: Тоа е вид на линеарна. 155 00:05:11,820 --> 00:05:13,480 Но, дозволете ми предложи, ајде да ме стави на самото место. 156 00:05:13,480 --> 00:05:14,900 Дозволете ми да се освежи страница. 157 00:05:14,900 --> 00:05:17,120 истиот број, истиот аранжман, исто врати. 158 00:05:17,120 --> 00:05:21,350 Но се сетам на тој прв ден во класа кога ние раскина телефон книга во 159 00:05:21,350 --> 00:05:25,480 половина, вид на, и она што беше нашата стратегија таму? 160 00:05:25,480 --> 00:05:26,450 >> JENNIFER: Почеток на средината. 161 00:05:26,450 --> 00:05:26,690 >> Дејвид Џ MALAN: OK. 162 00:05:26,690 --> 00:05:27,610 Па почнуваат во средината. 163 00:05:27,610 --> 00:05:28,790 Па ајде да одиме напред и да симулираат тоа. 164 00:05:28,790 --> 00:05:30,720 Започне во средината откривајќи дека вратата. 165 00:05:30,720 --> 00:05:31,660 Така што бројот 16. 166 00:05:31,660 --> 00:05:35,290 Па што би силната дечко го направиле, кој раскина на телефонот книга на половина, 167 00:05:35,290 --> 00:05:38,450 да се стигне до следната претпоставка? 168 00:05:38,450 --> 00:05:39,400 >> JENNIFER: Оди во оваа половина. 169 00:05:39,400 --> 00:05:41,700 >> Дејвид Џ MALAN: И зошто на правото? 170 00:05:41,700 --> 00:05:43,900 >> JENNIFER: Ако тие беа вид на најмалите до најголемите, а потоа 50 треба да биде 171 00:05:43,900 --> 00:05:44,720 во тој крај. 172 00:05:44,720 --> 00:05:44,920 >> Дејвид Џ MALAN: Добро. 173 00:05:44,920 --> 00:05:45,390 Сосема разумни. 174 00:05:45,390 --> 00:05:48,380 Па како телефон книга, ќе се обратите на право, за разлика од левата страна, но тука 175 00:05:48,380 --> 00:05:49,500 е клучот готова брза. 176 00:05:49,500 --> 00:05:53,930 Сега можете да фрлаат, или откине, половина од овој проблем, оставајќи не сте 177 00:05:53,930 --> 00:05:55,970 со 7 врати, но навистина со само 3. 178 00:05:55,970 --> 00:05:57,870 Што е приближно околу половина од големината на проблемот. 179 00:05:57,870 --> 00:05:58,350 Сите во право. 180 00:05:58,350 --> 00:06:01,890 Па сега што ќе треба направи откако ќе одат нели? 181 00:06:01,890 --> 00:06:05,870 >> JENNIFER: Значи 16 се уште е прилично мал, во однос на 50, па можеби и јас ќе се обидам, 182 00:06:05,870 --> 00:06:06,700 како, и оваа. 183 00:06:06,700 --> 00:06:07,890 >> Дејвид Џ MALAN: Во ред. 184 00:06:07,890 --> 00:06:08,720 42. 185 00:06:08,720 --> 00:06:10,830 Добро, па сега она што е вашиот инстинкт ви кажува? 186 00:06:10,830 --> 00:06:12,100 >> JENNIFER: Јас може да се фрлаат ова, а потоа само - 187 00:06:12,100 --> 00:06:12,360 >> Дејвид Џ MALAN: OK. 188 00:06:12,360 --> 00:06:14,212 Добро, може да се фрлаат на левата половина таму. 189 00:06:14,212 --> 00:06:14,890 >> JENNIFER: - Изберете оваа. 190 00:06:14,890 --> 00:06:15,530 >> Дејвид Џ MALAN: И во право. 191 00:06:15,530 --> 00:06:15,760 >> JENNIFER: Да. 192 00:06:15,760 --> 00:06:17,820 >> Дејвид Џ MALAN: Значи, иако тоа е тешко за да го видиш можеби, кога има само 193 00:06:17,820 --> 00:06:21,320 7 врати, се размислува за, сега, конзистентноста на 194 00:06:21,320 --> 00:06:22,620 Алгоритам Вие само применуваат. 195 00:06:22,620 --> 00:06:24,510 Во претходниот случај, ти го направи ќе имаат среќа, која беше одлично. 196 00:06:24,510 --> 00:06:26,540 Но вие не се користи хеуристичка, Јас би рекол. 197 00:06:26,540 --> 00:06:29,150 Сте користеле вид на вашите инстинкти, и знаејќи дека подредени, ако тоа е прилично 198 00:06:29,150 --> 00:06:31,600 мали на почетокот, очигледно, ние сме Мора да одам повеќе на десно. 199 00:06:31,600 --> 00:06:34,990 Но, во извесна смисла, имаш среќа, затоа што можеби ова беше бројот 100, 200 00:06:34,990 --> 00:06:36,220 а можеби и 50 беше повеќе во средината. 201 00:06:36,220 --> 00:06:37,910 Можеби 50 беше дури и овде. 202 00:06:37,910 --> 00:06:40,960 >> Но, она што ти го направи малку поинаку овој пат беше, ти го направи истото 203 00:06:40,960 --> 00:06:42,150 повторно и повторно. 204 00:06:42,150 --> 00:06:45,310 И јас би рекол дека она што сте само се, иако под влијание од страна на телефонот 205 00:06:45,310 --> 00:06:48,100 книга пример, е нешто многу повеќе алгоритамски, и многу 206 00:06:48,100 --> 00:06:49,930 намалена за посебната латински. 207 00:06:49,930 --> 00:06:51,620 Многу помалку инстинктивно. 208 00:06:51,620 --> 00:06:57,160 Па на крајот на денот, како би опишуваат вас на ефикасноста на 209 00:06:57,160 --> 00:07:00,530 првиот алгоритам, каде што ќе отиде лево кон десно, наспроти 210 00:07:00,530 --> 00:07:03,430 вториот алгоритам тука? 211 00:07:03,430 --> 00:07:06,460 >> JENNIFER: Ова треба, како, можеби преполоват време, или дури и повеќе, да. 212 00:07:06,460 --> 00:07:07,320 >> Дејвид Џ MALAN: Добро, можеби дури и повеќе. 213 00:07:07,320 --> 00:07:10,150 Ајде да им помогнам малку потешко за тоа. 214 00:07:10,150 --> 00:07:13,030 Што, навистина, ако продолжиме со ова логика, ние дефинитивно ја преполовиле 215 00:07:13,030 --> 00:07:15,830 трчање време со овој втор алгоритам од фрлањето на половина од 216 00:07:15,830 --> 00:07:18,470 броеви, но она што го правиме на следната повторување, кога Џенифер откри 217 00:07:18,470 --> 00:07:20,615 вториот број? 218 00:07:20,615 --> 00:07:22,830 >> Ние преполовен бројот на врати повторно. 219 00:07:22,830 --> 00:07:25,270 А потоа она што го правиме после тоа, ако имало повеќе врати да си игра со? 220 00:07:25,270 --> 00:07:27,520 Ние ќе ги преполови, и повторно, и повторно, и повторно. 221 00:07:27,520 --> 00:07:30,420 И тоа беше исто како вие момци сите стои во првата недела од 222 00:07:30,420 --> 00:07:33,000 класа, половина од вас седи долу, половина од вас седи долу, половина од вас 223 00:07:33,000 --> 00:07:35,440 седнува, се додека еден осамен душата стоеше. 224 00:07:35,440 --> 00:07:39,050 И ние рече дека трчање време на тоа, бројот на чекори што го зеде беше 225 00:07:39,050 --> 00:07:40,430 од редот на што? 226 00:07:40,430 --> 00:07:41,230 >> ЗВУЧНИК 1: [нечујни] 227 00:07:41,230 --> 00:07:43,970 >> Дејвид Џ MALAN: Значи најавите база 2 од n, или само повеќе, едноставно, се логираат на n. 228 00:07:43,970 --> 00:07:45,060 Па нешто логаритамска. 229 00:07:45,060 --> 00:07:48,380 И графикон не беше права линија дека само што влегов полошо и полошо, тоа беше 230 00:07:48,380 --> 00:07:52,490 овој интересен крива што не добие толку лошо со текот на времето. 231 00:07:52,490 --> 00:07:53,910 Па ајде да се држи до оваа идеја. 232 00:07:53,910 --> 00:07:54,690 Да му заблагодариме на Џенифер. 233 00:07:54,690 --> 00:07:56,150 Благодарение толку многу за доаѓање на до. 234 00:07:56,150 --> 00:07:57,400 И, еден сек. 235 00:07:57,400 --> 00:08:00,170 236 00:08:00,170 --> 00:08:02,925 Нема биро светилки денес, но ние немаат CS50 стрес топки. 237 00:08:02,925 --> 00:08:03,420 >> JENNIFER: Yay. 238 00:08:03,420 --> 00:08:04,410 >> Дејвид Џ MALAN: Добро, тука. 239 00:08:04,410 --> 00:08:06,545 Ви благодариме за incurring на стресот до тука. 240 00:08:06,545 --> 00:08:07,350 Сите во право. 241 00:08:07,350 --> 00:08:10,620 Да видиме дали можеме да го сега формализира ова малку повеќе. 242 00:08:10,620 --> 00:08:14,820 Па уште еднаш, она што ние едноставно го направив беше суштина истото како ние го сторивме 243 00:08:14,820 --> 00:08:16,660 во таа прва недела. 244 00:08:16,660 --> 00:08:23,780 Но, наместо да заврши со само еден линеарен алгоритам, кој ние прикажан 245 00:08:23,780 --> 00:08:27,210 претходно како оваа права линија, при што, ако се стави уште една врата на 246 00:08:27,210 --> 00:08:29,610 на екранот, а потоа Џенифер би имале да се погледне, потенцијално, 247 00:08:29,610 --> 00:08:30,600 зад една врата. 248 00:08:30,600 --> 00:08:33,490 Ако се стави уште две врати, таа може да имаат да се погледне зад две врати. 249 00:08:33,490 --> 00:08:35,990 >> И така, имаше оваа линеарна односот помеѓу големината на 250 00:08:35,990 --> 00:08:39,059 Проблемот на, да речеме, на x-оската, и износот на времето потребно да се 251 00:08:39,059 --> 00:08:40,440 решавање на y. 252 00:08:40,440 --> 00:08:43,330 Но сликата ми беше алудирајќи на порано беше оваа зелена линија. 253 00:08:43,330 --> 00:08:45,970 Зелени намерно, затоа што тоа само се чувствува подобро. 254 00:08:45,970 --> 00:08:49,790 Во теорија, алгоритам, кога ние го сторивме со книгата на телефонот, кога ние го сторивме 255 00:08:49,790 --> 00:08:52,420 со вас момци броење едни со други, и во вториот случај, кога Џенифер само 256 00:08:52,420 --> 00:08:55,250 тоа го правеше до тука, тоа беше вид на фундаментално подобро. 257 00:08:55,250 --> 00:08:57,180 Затоа што тоа не е само два пати побрзо. 258 00:08:57,180 --> 00:08:58,870 Тоа не беше дури четири пати брзо. 259 00:08:58,870 --> 00:09:03,290 Тоа беше целосно зависни од она што големината на влез беше, за тоа како многу 260 00:09:03,290 --> 00:09:05,220 чекори што во крајна линија зеде. 261 00:09:05,220 --> 00:09:08,040 >> И така оваа едноставна идеја дека сите ние се здраво за готово со телефонот книга, 262 00:09:08,040 --> 00:09:10,200 Слично на тоа може да се примени да нешто како ова. 263 00:09:10,200 --> 00:09:12,380 И ова може да биде повеќе патемно познат како, како што може 264 00:09:12,380 --> 00:09:13,940 замисли, поделба и освојување. 265 00:09:13,940 --> 00:09:16,390 Не за разлика од она што го правевме, се разбира, со телефонот книга. 266 00:09:16,390 --> 00:09:18,300 >> Но pseudocode, се потсетиме, беше ова. 267 00:09:18,300 --> 00:09:21,800 Па ние не ќе го направат тоа повторно, но се потсетиме дека првата недела, на сите нас застана 268 00:09:21,800 --> 00:09:25,140 а потоа половина од вас седна, половина од можете седна, половина од вас седна. 269 00:09:25,140 --> 00:09:29,280 Дека алгоритам е реализиран во малку на мамење начин, во тоа, 270 00:09:29,280 --> 00:09:32,870 не беше само една од мене броење, фундаментално, поефикасно. 271 00:09:32,870 --> 00:09:35,830 Во тој случај, јас бев проширува средно ресурс. 272 00:09:35,830 --> 00:09:39,470 На некој начин, повеќе процесори, повеќе мозоци, повеќе паметни луѓе во 273 00:09:39,470 --> 00:09:42,740 соба беа помагање на мене да се добие од нешто линеарно на нешто 274 00:09:42,740 --> 00:09:45,190 логаритамска, од нешто црвена до нешто зелено. 275 00:09:45,190 --> 00:09:48,650 >> Но во овој случај, Џенифер сам може да фундаментално подобрување врз 276 00:09:48,650 --> 00:09:52,370 изведба на нејзиниот прв алгоритам со, повторно, само размислување малку потешко. 277 00:09:52,370 --> 00:09:56,650 И сега, кога станува збор време да се имплементираат овие работи, да пронајдат 278 00:09:56,650 --> 00:10:00,670 она линии на код може да напише како дека можете да ги повтори, и 279 00:10:00,670 --> 00:10:03,350 повторно, и повторно, вид на во looping модата. 280 00:10:03,350 --> 00:10:06,370 Затоа што не си оди за да имаат луксуз, како Џенифер го направи на прво, за да 281 00:10:06,370 --> 00:10:10,460 само имаат целиот куп на IFS и се каже, хм, ако овој прв број е 4, 282 00:10:10,460 --> 00:10:11,800 дозволете ми да скокаат по целиот пат до крај. 283 00:10:11,800 --> 00:10:14,180 Ooh, ако тој број е преголем, дозволете ми да се движат произволно назад 284 00:10:14,180 --> 00:10:15,220 до вториот елемент. 285 00:10:15,220 --> 00:10:18,210 Ќе најдете дека тоа се случува да биде многу потешко да се формализира она што ние, луѓето 286 00:10:18,210 --> 00:10:21,270 земе здраво за готово како многу разумна хеуристичко, но компјутерот е само 287 00:10:21,270 --> 00:10:23,260 случува да направи она што вие го каже да го стори. 288 00:10:23,260 --> 00:10:25,280 >> Сега ова многу интересно импликации. 289 00:10:25,280 --> 00:10:29,950 Овој графикон е вид на замислена за сортирање на победат визуелно, но оглас, каде 290 00:10:29,950 --> 00:10:32,230 е права линија во овој графикон? 291 00:10:32,230 --> 00:10:35,330 Каде е линеарна графикон што ние го нарекуваме N? 292 00:10:35,330 --> 00:10:37,580 Па, тоа е вид на кон дното на оваа слика, нели? 293 00:10:37,580 --> 00:10:40,500 Така што сите ние го направивме е ние сме вид на zoomed надвор на x-оската и 294 00:10:40,500 --> 00:10:44,780 y-оската да се обидат да се добие чувство на она што други видови на криви изгледа. 295 00:10:44,780 --> 00:10:47,760 >> И спецификите на математички изрази денеска не е важно толку 296 00:10:47,760 --> 00:10:52,440 многу, но забележите дека има многу алгоритми кои се далеку полоши од 297 00:10:52,440 --> 00:10:53,470 нешто што е линеарна. 298 00:10:53,470 --> 00:10:55,410 Навистина, n коцки изгледа прилично лошо. 299 00:10:55,410 --> 00:10:58,400 2 до n изгледа прилично лошо. n квадрат изгледа прилично лошо. 300 00:10:58,400 --> 00:11:01,630 И ќе видиме што некои од оние може да биде во денешната реалност. 301 00:11:01,630 --> 00:11:05,430 И да се најавите n не се чувствува како лоша, но подобро отколку n е најавите база 2 од n. 302 00:11:05,430 --> 00:11:08,080 Но, знаете, тоа би биле дури и повеќе зачудувачки ако Џенифер, или, ако ние, 303 00:11:08,080 --> 00:11:12,910 дека првата недела, се дојдени со нешто што е дневник на најавите на n. 304 00:11:12,910 --> 00:11:15,880 >> Значи со други зборови, има целата оваа опсег на можни решенија за 305 00:11:15,880 --> 00:11:18,570 проблеми, но дури и тука, најава што ќе се случи. 306 00:11:18,570 --> 00:11:22,910 Кога јас одзумирате, кој од овие криви се случува да се докаже да биде апсолутна 307 00:11:22,910 --> 00:11:26,630 најлошото од оние на екранот сега? 308 00:11:26,630 --> 00:11:28,680 Значи n коцки изгледа прилично лоша во моментот. 309 00:11:28,680 --> 00:11:32,470 Но ако ние зумирате надвор и види повеќе на x и y-оската, кој ќе 310 00:11:32,470 --> 00:11:34,550 доминираат во крајна линија? 311 00:11:34,550 --> 00:11:37,120 Па тоа всушност излегува дека 2 на n, и можете да дознаам ова со само 312 00:11:37,120 --> 00:11:39,990 приклучување во некои повеќе големи броеви, и ќе видите дека 2 на 313 00:11:39,990 --> 00:11:42,070 n, навистина, станува сè поголемо многу побрзо. 314 00:11:42,070 --> 00:11:45,530 Ако ние навистина одзумирате, 2 до n алгоритам апсолутно смрди. 315 00:11:45,530 --> 00:11:48,170 Мислам ова се случува да се земе доста време за 316 00:11:48,170 --> 00:11:49,460 компјутер за да разпенвам преку. 317 00:11:49,460 --> 00:11:52,500 >> Но ќе видите со текот на времето, особено со идните проблем сетови, па дури и 318 00:11:52,500 --> 00:11:55,600 конечна проекти, вашите податоци сет добива големи, во ред? 319 00:11:55,600 --> 00:11:58,300 Дури и во првата верзија на Фејсбук, како и бројот на пријатели, и 320 00:11:58,300 --> 00:12:01,840 Бројот на регистрирани корисници доби голема, можете да ги подредите на телефонот во и 321 00:12:01,840 --> 00:12:05,530 имплементираат нешто со линеарно пребарување, или многу едноставен сортирање 322 00:12:05,530 --> 00:12:07,030 алгоритам, како што ќе видиме денес. 323 00:12:07,030 --> 00:12:09,280 Што треба да почнам да размислувам потешко и потешко за овие проблеми. 324 00:12:09,280 --> 00:12:12,070 И типови на проблеми места како Фејсбук, и Google и Microsoft, 325 00:12:12,070 --> 00:12:16,350 и други работи на е токму овие вид на големи податоци вид на прашања 326 00:12:16,350 --> 00:12:18,530 повеќе, овие денови. 327 00:12:18,530 --> 00:12:18,900 >> Сите во право. 328 00:12:18,900 --> 00:12:23,800 Значи успехот на Jennifer во таа секунда алгоритам, искрено, таа го направи неверојатно 329 00:12:23,800 --> 00:12:26,110 и прв пат, но ајде напишете го како среќа, така што ние 330 00:12:26,110 --> 00:12:27,000 може да направи оваа точка. 331 00:12:27,000 --> 00:12:30,970 Во вториот случај, таа балон на алгоритам што повторува одново и 332 00:12:30,970 --> 00:12:34,670 повторно, но таа го зеде здраво за готово на извесна претпоставка дека ние дозволено 333 00:12:34,670 --> 00:12:39,370 неа, но таа експлоатираат некои детали втор пат дека таа немала 334 00:12:39,370 --> 00:12:39,840 прв пат. 335 00:12:39,840 --> 00:12:41,800 Кој беше она? 336 00:12:41,800 --> 00:12:43,050 >> Дека листата е подредени. 337 00:12:43,050 --> 00:12:46,350 Па штом листата беше подредени, ние тврдат дека Џенифер беше во можност да го стори 338 00:12:46,350 --> 00:12:47,480 фундаментално подобро. 339 00:12:47,480 --> 00:12:51,450 7 врати, одговорот е да, не е интересно, но тоа претпоставувам ние сме 7.000.000 врати. 340 00:12:51,450 --> 00:12:54,080 Вклучи на n е дефинитивно ќе да се изврши многу, многу 341 00:12:54,080 --> 00:12:55,610 побрзо во долг рок. 342 00:12:55,610 --> 00:12:58,880 Но, таа мораше да имаат врати подредени за неа. 343 00:12:58,880 --> 00:13:02,320 Сега, си зедов слобода тоа да го однапред на екранот на компјутерот 344 00:13:02,320 --> 00:13:05,160 тука, но претпоставувам дека Џенифер мораше да го направи тоа себеси? 345 00:13:05,160 --> 00:13:10,120 Да претпоставиме дека вратите во прашање претставен податоци во базата на податоци, или 346 00:13:10,120 --> 00:13:14,260 пријатели регистрирани за Фејсбук, или било кој веб-страници на интернет што 347 00:13:14,260 --> 00:13:16,880 разни веб-сајтови може да треба да индексира или пребарување завршена. 348 00:13:16,880 --> 00:13:20,940 >> Да претпоставиме дека сте само имаше сурови податоци во собата и беше оставено на вас, или да 349 00:13:20,940 --> 00:13:23,010 Џенифер да го стори тоа сортирање? 350 00:13:23,010 --> 00:13:26,950 Дека, напротив, бара да одговориме на прашањето, добро, колку време 351 00:13:26,950 --> 00:13:31,080 би ги презеле Џенифер, па дури и мене, да го решите тие бројки однапред, така 352 00:13:31,080 --> 00:13:32,680 дека таа може да ги искористат предностите на тоа? 353 00:13:32,680 --> 00:13:32,880 Нели? 354 00:13:32,880 --> 00:13:36,620 Бидејќи импликација, се разбира, е ако тоа ми зема доста време да се најде решение 355 00:13:36,620 --> 00:13:40,800 на броеви, кој е грижам се грижи што ќе може да најдете голем број како 50 толку брзо, 356 00:13:40,800 --> 00:13:44,850 како и во случај на Jennifer, ако ние повеќе од совладан од износот на вкупното време 357 00:13:44,850 --> 00:13:46,920 го зеде од страна на сортирање работите однапред? 358 00:13:46,920 --> 00:13:49,320 >> Да видиме ако не можеме да го наслика слика овде. 359 00:13:49,320 --> 00:13:51,370 Јас имам еден цел куп повеќе стрес топки, ако тоа им помага 360 00:13:51,370 --> 00:13:52,270 се скрши мразот тука. 361 00:13:52,270 --> 00:13:55,690 И ако не би ум, ние треба седум волонтери - 362 00:13:55,690 --> 00:13:57,060 на, ОК. 363 00:13:57,060 --> 00:13:57,240 Wow. 364 00:13:57,240 --> 00:13:59,250 Значи ние не треба да се трошат на биро светилки, се чини. 365 00:13:59,250 --> 00:13:59,690 Сите во право. 366 00:13:59,690 --> 00:14:01,530 Па како за вас две во фронт. 367 00:14:01,530 --> 00:14:04,160 Како за вас две момчиња во грбот. 368 00:14:04,160 --> 00:14:04,870 Па тоа е четири. 369 00:14:04,870 --> 00:14:09,890 Како за вас во пред пет, шест и седум. 370 00:14:09,890 --> 00:14:10,320 Право таму. 371 00:14:10,320 --> 00:14:13,260 Вашиот пријател ќе посочувајќи, па ќе го добиете награда. 372 00:14:13,260 --> 00:14:13,700 >> Сите во право. 373 00:14:13,700 --> 00:14:14,410 Ајде горе. 374 00:14:14,410 --> 00:14:17,120 И зошто да не можеме да си момци дојдат на повеќе тука. 375 00:14:17,120 --> 00:14:18,960 Одам да ви даде на секој број. 376 00:14:18,960 --> 00:14:22,150 И оди напред и да организираме сами идентично на она што е 377 00:14:22,150 --> 00:14:25,180 прикажан на екранот. 378 00:14:25,180 --> 00:14:26,530 >> [INTERPOSING ГЛАСОВИ] 379 00:14:26,530 --> 00:14:28,160 >> Дејвид Џ MALAN: OOP, жалам. 380 00:14:28,160 --> 00:14:30,210 Бубачка. 381 00:14:30,210 --> 00:14:32,180 Сите во право. 382 00:14:32,180 --> 00:14:32,750 Добро, тука ќе одиме. 383 00:14:32,750 --> 00:14:34,180 Број пет. 384 00:14:34,180 --> 00:14:35,136 Бројот шест. 385 00:14:35,136 --> 00:14:37,770 Еден, два, три, четири, пет, шест, седум. 386 00:14:37,770 --> 00:14:39,410 Ох, ова е непријатно. 387 00:14:39,410 --> 00:14:41,210 >> ЗВУЧНИК 2: Јас само ќе добие -. 388 00:14:41,210 --> 00:14:41,900 >> Дејвид Џ MALAN: добра зделка. 389 00:14:41,900 --> 00:14:43,130 Сите во право. 390 00:14:43,130 --> 00:14:44,611 Ви благодариме за учество. 391 00:14:44,611 --> 00:14:47,200 >> [Аплауз] 392 00:14:47,200 --> 00:14:48,580 >> OK. 393 00:14:48,580 --> 00:14:48,860 Сите во право. 394 00:14:48,860 --> 00:14:51,970 Па ние имаме четири, два, шест, еден, три, седум, пет. 395 00:14:51,970 --> 00:14:56,010 Совршен, така имаме седум волонтери тука, кои се еднакви во ширина со 396 00:14:56,010 --> 00:14:57,430 низа што ние навистина свириме со порано. 397 00:14:57,430 --> 00:14:59,470 И јас избра седум причини дека ќе биде само 398 00:14:59,470 --> 00:15:00,840 погодно во малку. 399 00:15:00,840 --> 00:15:04,400 И јас одам да предложи првиот што ние средиме овие седум волонтери. 400 00:15:04,400 --> 00:15:06,786 Ако сакате, прво, да се каже здраво, секако. 401 00:15:06,786 --> 00:15:08,970 Бидејќи ова се случува да биде непријатно неколку минути. 402 00:15:08,970 --> 00:15:10,370 Воведување на себе си. 403 00:15:10,370 --> 00:15:10,980 >> GRACE: Здраво, јас сум Грејс. 404 00:15:10,980 --> 00:15:14,190 Јас сум сафомор во Leverett куќа. 405 00:15:14,190 --> 00:15:14,620 >> BRANSON: Здраво. 406 00:15:14,620 --> 00:15:15,620 Јас сум Бренсон. 407 00:15:15,620 --> 00:15:16,920 Јас сум бруцош во Weld. 408 00:15:16,920 --> 00:15:19,755 409 00:15:19,755 --> 00:15:20,230 >> Gabe: Здраво. 410 00:15:20,230 --> 00:15:21,040 Јас сум Габе. 411 00:15:21,040 --> 00:15:22,300 Јас сум помлад во Кабот. 412 00:15:22,300 --> 00:15:24,826 413 00:15:24,826 --> 00:15:25,980 >> NEIL: Јас сум Нил. 414 00:15:25,980 --> 00:15:29,090 Јас сум бруцош во Метјус. 415 00:15:29,090 --> 00:15:29,550 >> ЈАСОН: Јас сум Џејсон. 416 00:15:29,550 --> 00:15:32,816 Јас сум бруцош во Greenough. 417 00:15:32,816 --> 00:15:33,700 >> МАЈК: Јас сум Мајк. 418 00:15:33,700 --> 00:15:37,360 Јас сум бруцош во сиво. 419 00:15:37,360 --> 00:15:37,990 >> JESS: Јас сум Џес. 420 00:15:37,990 --> 00:15:40,313 Јас сум сафомор во Leverett. 421 00:15:40,313 --> 00:15:41,300 >> Дејвид Џ MALAN: Одлично. 422 00:15:41,300 --> 00:15:41,850 Сите во право. 423 00:15:41,850 --> 00:15:44,190 Па, ти благодарам на сите наши волонтери тука досега. 424 00:15:44,190 --> 00:15:47,110 И предизвикот на дофат на раката сега се случува да биде да се најде на овие момци, но потоа 425 00:15:47,110 --> 00:15:50,250 ние ќе мора да размислуваат малку тешко за тоа како ефикасно ние всушност 426 00:15:50,250 --> 00:15:51,110 сортирани нив. 427 00:15:51,110 --> 00:15:52,580 Па ајде прво се обиде ова. 428 00:15:52,580 --> 00:15:55,970 Вие момци може да се види едни од други броеви само со ставање на околу аглите. 429 00:15:55,970 --> 00:15:59,380 Оди напред и да потрае неколку секунди, а вид себе си од најмалите на 430 00:15:59,380 --> 00:16:01,240 лево кон најголемиот десно. 431 00:16:01,240 --> 00:16:02,490 Одите. 432 00:16:02,490 --> 00:16:07,010 433 00:16:07,010 --> 00:16:07,530 >> OK. 434 00:16:07,530 --> 00:16:08,030 Добар. 435 00:16:08,030 --> 00:16:09,370 Тоа беше навистина ебам брзо. 436 00:16:09,370 --> 00:16:14,040 Сега некој тука, она што беше на алгоритмот дека овие момци се применува? 437 00:16:14,040 --> 00:16:14,900 >> ЗВУЧНИК 1: барем до најголема. 438 00:16:14,900 --> 00:16:15,000 >> Дејвид Џ MALAN: OK. 439 00:16:15,000 --> 00:16:18,070 Барем до најголема е навистина вид на објективен, но не сум сигурен дека тоа е 440 00:16:18,070 --> 00:16:18,890 навистина алгоритам. 441 00:16:18,890 --> 00:16:21,810 Барем до најголема не кажам мене чекор-по-чекор што да прави. 442 00:16:21,810 --> 00:16:22,833 Да? 443 00:16:22,833 --> 00:16:24,083 >> ЗВУЧНИК 1: [нечујни] 444 00:16:24,083 --> 00:16:26,010 445 00:16:26,010 --> 00:16:26,280 >> Дејвид Џ MALAN: OK. 446 00:16:26,280 --> 00:16:28,920 Па ако видите лице помало од вашиот број, а потоа преминете на 447 00:16:28,920 --> 00:16:29,680 правото на нив. 448 00:16:29,680 --> 00:16:32,800 Па тоа е сега се повеќе експресивна, повеќе како алгоритам, затоа што 449 00:16:32,800 --> 00:16:35,410 може да се каже, ако ова, тогаш тоа. 450 00:16:35,410 --> 00:16:37,050 Па ние имаме некој вид на условен конструкција. 451 00:16:37,050 --> 00:16:39,700 И овие момци се чинеше да го стори тоа неколку пати, затоа што некои од вас се пресели малку 452 00:16:39,700 --> 00:16:40,420 на далечина. 453 00:16:40,420 --> 00:16:43,410 Па се претпоставува дека некој вид на looping случува во нивните умови. 454 00:16:43,410 --> 00:16:44,610 >> Но, ајде да се обидеме да го формализира тоа. 455 00:16:44,610 --> 00:16:47,540 Ако вие момци може да ја ресетирате назад на овој аранжман. 456 00:16:47,540 --> 00:16:50,650 Ајде да видиме ако не можеме да го формализира ова малку, а потоа го поставуваме прашањето, само 457 00:16:50,650 --> 00:16:51,580 Како ефикасно е ова? 458 00:16:51,580 --> 00:16:54,220 Се разбира, кога правиме ова повеќе полека, тоа се случува да се чувствуваат како добри на 459 00:16:54,220 --> 00:16:57,210 алгоритам, но ајде да видиме дали можеме да стави нашите прсти на прецизни чекори. 460 00:16:57,210 --> 00:16:58,670 >> Па вие двајца момци се четири и два. 461 00:16:58,670 --> 00:17:01,020 Или можете точни или неточни цел? 462 00:17:01,020 --> 00:17:01,900 Очигледно неточни. 463 00:17:01,900 --> 00:17:02,710 Па ние заменети. 464 00:17:02,710 --> 00:17:05,170 Сега ќе одам да ја тргнам на страна тука и да кажам, 05:56. 465 00:17:05,170 --> 00:17:06,240 Дали сте точни или неточни? 466 00:17:06,240 --> 00:17:06,599 >> Gabe: Точни. 467 00:17:06,599 --> 00:17:07,180 >> Дејвид Џ MALAN: Точни. 468 00:17:07,180 --> 00:17:08,300 Шест и еден? 469 00:17:08,300 --> 00:17:08,609 Не бе. 470 00:17:08,609 --> 00:17:09,630 Разменуваат. 471 00:17:09,630 --> 00:17:10,490 Па тоа е две свопови. 472 00:17:10,490 --> 00:17:11,710 Шест и три? 473 00:17:11,710 --> 00:17:11,980 Не бе. 474 00:17:11,980 --> 00:17:13,000 Разменуваат. 475 00:17:13,000 --> 00:17:13,930 Шест и седум? 476 00:17:13,930 --> 00:17:14,630 Изгледа добро. 477 00:17:14,630 --> 00:17:15,396 Седум и пет? 478 00:17:15,396 --> 00:17:16,150 >> JESS: [нечујни] 479 00:17:16,150 --> 00:17:17,089 >> Дејвид Џ MALAN: Добро, трампа. 480 00:17:17,089 --> 00:17:19,770 И подредени. 481 00:17:19,770 --> 00:17:19,980 Сите во право. 482 00:17:19,980 --> 00:17:21,440 Па очигледно не, нели? 483 00:17:21,440 --> 00:17:22,470 Па таму беше повеќе се случува. 484 00:17:22,470 --> 00:17:24,920 Но, навистина, овие момци, дури и само инстиктивно. 485 00:17:24,920 --> 00:17:25,450 се врткаше. 486 00:17:25,450 --> 00:17:27,710 Тие не само гости, откако тие корегирани еден проблем. 487 00:17:27,710 --> 00:17:27,839 Тоа. 488 00:17:27,839 --> 00:17:29,390 Всушност, јас ќе одам да имаат да го стори истото. 489 00:17:29,390 --> 00:17:32,720 Одам да мора да се најде на премотам касетата назад на почетокот на овој проблем, 490 00:17:32,720 --> 00:17:35,630 или на почетокот од оваа низа на луѓе, да почнеме нарекувајќи ги. 491 00:17:35,630 --> 00:17:38,366 >> И сега што треба да ми алгоритам на вториот помине биде? 492 00:17:38,366 --> 00:17:39,220 >> ЗВУЧНИК 1: истото. 493 00:17:39,220 --> 00:17:39,940 >> Дејвид Џ MALAN: истото. 494 00:17:39,940 --> 00:17:41,460 И ова, јас сум почнуваат да се допаѓа, нели? 495 00:17:41,460 --> 00:17:44,720 Веднаш штом ќе може да се најдат себе си прават истото одново и одново, тоа е 496 00:17:44,720 --> 00:17:47,890 стане повеќе како алгоритам, и помалку човечки инстинкт. 497 00:17:47,890 --> 00:17:48,680 >> Па сега, тука ќе одиме повторно. 498 00:17:48,680 --> 00:17:49,870 Две и четири? 499 00:17:49,870 --> 00:17:50,220 Бр. 500 00:17:50,220 --> 00:17:51,050 Четири и една? 501 00:17:51,050 --> 00:17:53,380 Ах, навистина имало некои уште да се работи да се направи. 502 00:17:53,380 --> 00:17:53,620 За и три? 503 00:17:53,620 --> 00:17:54,572 Добар. 504 00:17:54,572 --> 00:17:56,000 Четири и шест? 505 00:17:56,000 --> 00:17:58,380 Шест и пет? 506 00:17:58,380 --> 00:17:59,470 Шест и седум? 507 00:17:59,470 --> 00:18:00,970 Добро, сега, направено. 508 00:18:00,970 --> 00:18:01,550 Добро, нема. 509 00:18:01,550 --> 00:18:02,710 Морам да се вратам. 510 00:18:02,710 --> 00:18:05,130 >> Па сега, повторно, го правиме ова малку повеќе намерно. 511 00:18:05,130 --> 00:18:08,700 И сега, има само еден мозок извршување на овој алгоритам. 512 00:18:08,700 --> 00:18:10,290 Еден процесор, ако сакате. 513 00:18:10,290 --> 00:18:13,090 И искрено, тоа е единствениот ресурс ние ќе треба да имаат пристап. 514 00:18:13,090 --> 00:18:16,280 И еднаш кога ќе се вратиш на тастатура и да имаат нешто како C во нашата 515 00:18:16,280 --> 00:18:19,600 располагање, ние сме само пишување програма што може да направи една работа во исто време. 516 00:18:19,600 --> 00:18:22,900 Каде што, овие момци пред еден миг, ние балон на нивните колективни интелигенција 517 00:18:22,900 --> 00:18:24,180 дека вие момци го правеше во недела нула. 518 00:18:24,180 --> 00:18:24,980 Па ајде да го задржи тоа. 519 00:18:24,980 --> 00:18:26,260 >> Две и еден. 520 00:18:26,260 --> 00:18:26,945 Два и три. 521 00:18:26,945 --> 00:18:27,460 Три и четири. 522 00:18:27,460 --> 00:18:28,310 Четири и пет. 523 00:18:28,310 --> 00:18:28,620 Пет и шест. 524 00:18:28,620 --> 00:18:30,510 Шест и седум. 525 00:18:30,510 --> 00:18:31,880 Направи? 526 00:18:31,880 --> 00:18:34,560 Па јас сум, но дозволете ми да игра ѓаволот се залагаат. 527 00:18:34,560 --> 00:18:37,950 Дали ми е, вид на компјутер кој само направи помине низ оваа низа на 528 00:18:37,950 --> 00:18:40,225 луѓе, знаат дека јас сум се направи? 529 00:18:40,225 --> 00:18:40,670 >> ЗВУЧНИК 1: Не 530 00:18:40,670 --> 00:18:41,050 >> Дејвид Џ MALAN: Па зошто? 531 00:18:41,050 --> 00:18:46,900 Она што јас ќе треба да направите со цел да се заклучи решително дека јас сум се направи? 532 00:18:46,900 --> 00:18:48,230 Веројатно уште една помине. 533 00:18:48,230 --> 00:18:48,430 Нели? 534 00:18:48,430 --> 00:18:51,760 Затоа сè што знам од кои претходната помине е дека јас коригира грешка. 535 00:18:51,760 --> 00:18:53,920 А тоа значи, можеби има уште една грешка 536 00:18:53,920 --> 00:18:54,840 дека јас треба да се поправи. 537 00:18:54,840 --> 00:18:58,680 Па јас само може да биде сигурен од враќање наназад, и потоа проверка, 01:59, два и 538 00:18:58,680 --> 00:19:00,940 три, три и четири, четири и пет, пет и шест, шест и седум. 539 00:19:00,940 --> 00:19:02,510 Добро, сега го направив без работа. 540 00:19:02,510 --> 00:19:05,990 >> Јас секако може да се сети што го направив не работи со нешто како променлива, 541 00:19:05,990 --> 00:19:06,975 сакал Инт. 542 00:19:06,975 --> 00:19:12,490 Наречи го тоа свопови, и ако свопови е 0 еднаш бев добие тука, а започна на 0, а потоа 543 00:19:12,490 --> 00:19:15,520 Јас само би било глупаво да продолжувам да одам напред и назад, проверка, повторно, и 544 00:19:15,520 --> 00:19:16,450 повторно, и повторно, нели? 545 00:19:16,450 --> 00:19:18,450 Затоа што ви се заглавени во некои вид на бесконечна јамка. 546 00:19:18,450 --> 00:19:21,250 Па штом има 0 свопови, можеме да тврдиме дека оваа 547 00:19:21,250 --> 00:19:23,810 алгоритам е навистина заврши. 548 00:19:23,810 --> 00:19:25,400 >> Сега, ајде да се стави име на ова. 549 00:19:25,400 --> 00:19:28,930 На алгоритам дека јас ќе се предложи само спроведува е нешто што се нарекува меур 550 00:19:28,930 --> 00:19:32,800 вид, познат како такви, во смисла дека на броеви кои се поголеми вид на 551 00:19:32,800 --> 00:19:37,990 меур својот пат до врвот, или до до крајот на низата на броеви. 552 00:19:37,990 --> 00:19:40,270 Но, како ефикасна е овој алгоритам? 553 00:19:40,270 --> 00:19:44,600 Колку чекори никако не можев физички треба да Преземе, на пример, да ги сортирате овие 554 00:19:44,600 --> 00:19:45,850 седум луѓето? 555 00:19:45,850 --> 00:19:48,560 556 00:19:48,560 --> 00:19:49,550 >> Четири до пет? 557 00:19:49,550 --> 00:19:51,420 ОК, премногу е во крајна линија ќе биде одговорот. 558 00:19:51,420 --> 00:19:54,960 Но дури и тогаш, на одреден број не е толку интересно. 559 00:19:54,960 --> 00:19:56,670 Ајде да се генерализира тоа како n. 560 00:19:56,670 --> 00:20:00,520 Значи, ако имав n луѓе до тука, и тие беа, на некој начин, по случаен редослед на 561 00:20:00,520 --> 00:20:02,180 почетокот, во таа оригинална цел. 562 00:20:02,180 --> 00:20:04,910 Па, колку чекори морав да ја преземат првиот помине? 563 00:20:04,910 --> 00:20:09,810 Тоа беше еден, два, три, четири, пет, шест, а тие се седум лица, па 564 00:20:09,810 --> 00:20:13,670 тоа е седум, шест -, па тоа е n минус еден чекори за прв пат. 565 00:20:13,670 --> 00:20:16,280 >> Сега, колку чекори морав да се преземат кога јас собра? 566 00:20:16,280 --> 00:20:19,310 Па, ние всушност би можел двојно дека ако ние навистина сакаше да, но сега за сега, јас сум 567 00:20:19,310 --> 00:20:22,300 само случува да се каже, во ред, Уште еден N минус 1. 568 00:20:22,300 --> 00:20:25,240 Па N минус 1 се случува да се досадни да ги пратите на, па ајде 569 00:20:25,240 --> 00:20:26,400 само зад малку. 570 00:20:26,400 --> 00:20:27,770 Па 2n чекори. 571 00:20:27,770 --> 00:20:29,310 Па 14 чекори, или дава земе. 572 00:20:29,310 --> 00:20:31,930 >> Колку пати си земам чекор, следниот пат? 573 00:20:31,930 --> 00:20:33,740 Па, тоа е 3n. 574 00:20:33,740 --> 00:20:34,510 навистина. 575 00:20:34,510 --> 00:20:37,920 И сега, во најлош случај, на пример, колку пати сум ќе има 576 00:20:37,920 --> 00:20:41,730 качил напред и назад, напред и назад, извршување на овој алгоритам, Замена 577 00:20:41,730 --> 00:20:44,620 луѓе на секоја помине, грубо? 578 00:20:44,620 --> 00:20:47,720 579 00:20:47,720 --> 00:20:50,010 Тоа е всушност n квадрат, нели? 580 00:20:50,010 --> 00:20:53,000 >> Затоа што во најлош случај, може да се вид на мислите за оваа интуитивно, 581 00:20:53,000 --> 00:20:54,800 иако тоа би можело да потрае малку малку време да потоне внатре 582 00:20:54,800 --> 00:20:57,590 Во најлош случај, што би овие седум лица изгледаше како, во 583 00:20:57,590 --> 00:21:00,230 условите на аранжманот на нивните броеви? 584 00:21:00,230 --> 00:21:01,460 Целосно наназад, нели? 585 00:21:01,460 --> 00:21:02,815 И само за да се симулира дека, она што беше вашето име повторно? 586 00:21:02,815 --> 00:21:03,360 >> МАЈК: Мајк. 587 00:21:03,360 --> 00:21:03,640 >> Дејвид Џ MALAN: Мајк? 588 00:21:03,640 --> 00:21:08,100 Добро, Мајк, може да ви само ми се придружат во текот тука за само една секунда? 589 00:21:08,100 --> 00:21:08,880 Всушност, бр. 590 00:21:08,880 --> 00:21:10,150 Жал Мајк, ја премотам касетата, ајде. 591 00:21:10,150 --> 00:21:10,910 Како се викаш повторно? 592 00:21:10,910 --> 00:21:11,180 >> NEIL: Нил. 593 00:21:11,180 --> 00:21:11,640 >> Дејвид Џ MALAN: Нил. 594 00:21:11,640 --> 00:21:13,750 Добро, Нил, ќе дојдеш со мене, ако не ви пречи. 595 00:21:13,750 --> 00:21:17,150 Па ќе одам да предложи, само за едноставност, дека Нил е сега во 596 00:21:17,150 --> 00:21:18,510 најлош можен случај. 597 00:21:18,510 --> 00:21:20,720 Но се потсетиме како се спроведува мојата алгоритам. 598 00:21:20,720 --> 00:21:24,530 Јас сум споредување, споредување, споредување, споредување, споредување, ох. 599 00:21:24,530 --> 00:21:26,640 Сега овие момци се надвор на ред, па јас поправам. 600 00:21:26,640 --> 00:21:27,980 Па вие момци трампа. 601 00:21:27,980 --> 00:21:31,630 Но, сметаат дека сега, колку подалеку не Нил мора да одат? 602 00:21:31,630 --> 00:21:32,690 Тоа е грубо n. 603 00:21:32,690 --> 00:21:33,570 Знаете, тоа не е всушност n. 604 00:21:33,570 --> 00:21:36,040 Тоа е како, н минус 1, но јас сум добивање караше следење на мало 605 00:21:36,040 --> 00:21:37,550 број, па да го наречеме n. 606 00:21:37,550 --> 00:21:42,860 >> Па ако Нил се движи еден чекор максимално секоја време, и да се движат Нил еден чекор, 607 00:21:42,860 --> 00:21:46,580 Морам да се направи ова навистина досадни помине напред и назад, ова е грубо 608 00:21:46,580 --> 00:21:52,080 Правејќи го ова, n чекори, вкупно n пати, затоа што тоа се случува да ме земат 609 00:21:52,080 --> 00:21:55,820 дека многу чекори за да добие Нил сите начинот на кој до каде што припаѓа. 610 00:21:55,820 --> 00:21:58,620 А камоли сите други, ако вие момци сите беа погрешно наредил, како и. 611 00:21:58,620 --> 00:22:01,100 >> Па ајде да ги наречеме меур вид n квадрат. 612 00:22:01,100 --> 00:22:04,860 Трчање време на овој алгоритам, перформансите на овој алгоритам, 613 00:22:04,860 --> 00:22:07,120 ефикасноста на овој алгоритам, ние само ќе го опише повеќе 614 00:22:07,120 --> 00:22:08,800 генерално како n квадрат. 615 00:22:08,800 --> 00:22:11,650 Што е убаво, затоа што не можеше да стори истиот пример со осум луѓе, девет 616 00:22:11,650 --> 00:22:15,450 луѓе, милион луѓе, и дека Одговорот не е ќе се смени. 617 00:22:15,450 --> 00:22:18,870 >> Значи, ако вие момци не би ум, ајде да ресетирање да каде што почна. 618 00:22:18,870 --> 00:22:22,510 И ајде да се обидеме две други пристапи и види дали не можеме да правиме фундаментално 619 00:22:22,510 --> 00:22:23,820 подобро од ова. 620 00:22:23,820 --> 00:22:27,130 Значи ова време, ќе одам да предложи еден вид на различен алгоритам. 621 00:22:27,130 --> 00:22:29,950 Тоа беше многу умен од нас последен пат, а вие момци биле во право да имаат 622 00:22:29,950 --> 00:22:32,470 право инстинкти на само вид на Замена pairwise. 623 00:22:32,470 --> 00:22:36,500 Но, ако јас навистина сакаше да им пријде на ова едноставно, и мојата цел е да се движат 624 00:22:36,500 --> 00:22:39,800 сите на малите броеви на овој начин, и им помогнам на сите од големите броеви кои 625 00:22:39,800 --> 00:22:43,030 начин, зошто да не Јас само го направи тоа во повеќето наивна начин е можно и да видам дали можам 626 00:22:43,030 --> 00:22:45,730 може да го направи подобро од она што беше прилично комплексен алгоритам? 627 00:22:45,730 --> 00:22:46,620 >> Дали ќе видиме. 628 00:22:46,620 --> 00:22:48,940 Четири е прилично мал број, па јас сум ќе те оставам таму момент. 629 00:22:48,940 --> 00:22:50,610 Ooh, број два е дури и подобро. 630 00:22:50,610 --> 00:22:52,230 Па може да ви само чекор напред за момент? 631 00:22:52,230 --> 00:22:55,670 Ова е моментално мојот најмалите нумерирани кандидат, и јас одам да се запамети 632 00:22:55,670 --> 00:22:57,000 дека со, како, една променлива. 633 00:22:57,000 --> 00:22:57,930 Но јас ќе одам да го задржи проверка. 634 00:22:57,930 --> 00:22:59,890 Дали има некој чиј број е помал? 635 00:22:59,890 --> 00:23:00,460 Шест, бр. 636 00:23:00,460 --> 00:23:01,390 Ох, има Нил повторно. 637 00:23:01,390 --> 00:23:04,050 >> Па јас ќе одам да ти помогнам назад вид на концептуално. 638 00:23:04,050 --> 00:23:05,120 Нил ќе дојде напред. 639 00:23:05,120 --> 00:23:08,440 И сега, променливата дека јас сум со користење на ги пратите на кој има најмалата 640 00:23:08,440 --> 00:23:11,390 број се ажурира да содржат Нил локација. 641 00:23:11,390 --> 00:23:12,110 Добро, ајде да видиме. 642 00:23:12,110 --> 00:23:13,960 Три, седум, пет. 643 00:23:13,960 --> 00:23:15,590 ОК, знам дека Нил беше најмалиот. 644 00:23:15,590 --> 00:23:18,110 Што е наједноставниот нешто за мене да направите сега? 645 00:23:18,110 --> 00:23:21,410 Јас не одам да отпад моето време од само жуборот Нил едно место налево. 646 00:23:21,410 --> 00:23:25,350 Зошто да не можам само да ги ставите Нил каде што припаѓа, што е секако каде? 647 00:23:25,350 --> 00:23:26,160 >> Сите на патот на почетокот. 648 00:23:26,160 --> 00:23:27,720 Па Нил, дојдете со мене. 649 00:23:27,720 --> 00:23:28,910 И она што беше вашето име повторно? 650 00:23:28,910 --> 00:23:29,310 >> GRACE: Грејс. 651 00:23:29,310 --> 00:23:29,710 >> Дејвид Џ MALAN: Грејс. 652 00:23:29,710 --> 00:23:29,920 OK. 653 00:23:29,920 --> 00:23:32,490 Па Грејс, за жал, вие сте вид на на патот. 654 00:23:32,490 --> 00:23:34,290 Така како ние да се реши овој проблем? 655 00:23:34,290 --> 00:23:34,490 Нели? 656 00:23:34,490 --> 00:23:37,500 Ако ова е низа, има само седум локации. 657 00:23:37,500 --> 00:23:40,830 Потсетиме дека, со Rob, ние разговаравме за прогласување возрасти, а ние само имаше 658 00:23:40,830 --> 00:23:41,740 конечен број на векови? 659 00:23:41,740 --> 00:23:42,535 Истата идеја тука. 660 00:23:42,535 --> 00:23:44,300 Ние имаме само ограничен број на ints. 661 00:23:44,300 --> 00:23:47,590 Грејс е вид на во нашата начин, па како да се поправи? 662 00:23:47,590 --> 00:23:49,555 >> Наједноставниот начин е како, Благодат, жалам. 663 00:23:49,555 --> 00:23:51,870 Ви се случува да мора да одат преку таму, па ние може да се направи простор. 664 00:23:51,870 --> 00:23:55,290 Сега, ако мислиш за ова, можеби ние само го направи проблем полошо. 665 00:23:55,290 --> 00:23:58,510 А можеби ние го сторивме, бидејќи што ако Грејс беа во право место? 666 00:23:58,510 --> 00:24:01,730 Но ние знаеме дека не е, затоа што во спротивно, таа ќе беше 667 00:24:01,730 --> 00:24:03,980 стои напред, наместо на Нил во ова време, нели? 668 00:24:03,980 --> 00:24:05,550 Ние веќе проверуваат нејзиниот број надвор. 669 00:24:05,550 --> 00:24:05,770 >> Сите во право. 670 00:24:05,770 --> 00:24:09,110 Па сега, Нил е во право место, како и Што можам да направам мала оптимизација. 671 00:24:09,110 --> 00:24:11,740 За следната минута, јас ќе одам да се игнорира Нил, сите заедно, така што нема да 672 00:24:11,740 --> 00:24:15,280 отпад своето време, или случајно разменуваат со него на погрешно место. 673 00:24:15,280 --> 00:24:17,805 Па сега, како можам да се најдат на следниот елемент тоа е најмалиот? 674 00:24:17,805 --> 00:24:18,480 Две. 675 00:24:18,480 --> 00:24:20,225 Тоа е прилично добар број, ако дека сакате да се чекор напред и 676 00:24:20,225 --> 00:24:21,100 Јас ќе ти запамети. 677 00:24:21,100 --> 00:24:21,980 Шест, не е добро. 678 00:24:21,980 --> 00:24:24,820 Четири, три, седум, пет, не е добро. 679 00:24:24,820 --> 00:24:26,800 Па да ми се движат да Вашиот вистинското место. 680 00:24:26,800 --> 00:24:28,470 А ние само што влегов среќа овој пат. 681 00:24:28,470 --> 00:24:31,350 >> Сега, јас ќе одам да ги игнорира овие две момчиња, а сега направи уште еден 682 00:24:31,350 --> 00:24:32,260 поминат низ ова. 683 00:24:32,260 --> 00:24:33,490 Шест години, тоа е прилично мал број. 684 00:24:33,490 --> 00:24:34,300 Ајде напред. 685 00:24:34,300 --> 00:24:35,220 Ох, извинете. 686 00:24:35,220 --> 00:24:37,640 Број на grace е подобро, па чекор врз напред. 687 00:24:37,640 --> 00:24:38,260 Четири. 688 00:24:38,260 --> 00:24:39,120 Жал ми е, Грејс. 689 00:24:39,120 --> 00:24:39,950 Се врати повторно. 690 00:24:39,950 --> 00:24:41,550 Број три е подобро. 691 00:24:41,550 --> 00:24:42,290 Седум. 692 00:24:42,290 --> 00:24:42,720 Пет. 693 00:24:42,720 --> 00:24:43,550 И сега што викаш повторно? 694 00:24:43,550 --> 00:24:44,000 >> ЈАСОН: Џејсон. 695 00:24:44,000 --> 00:24:44,420 >> Дејвид Џ MALAN: Џејсон. 696 00:24:44,420 --> 00:24:47,050 Така Џејсон сега е најмалиот елемент што сум избран. 697 00:24:47,050 --> 00:24:49,160 Каде што е тој ќе оди? 698 00:24:49,160 --> 00:24:50,380 Значи, каде што шест е. 699 00:24:50,380 --> 00:24:51,210 И вашето име е повторно? 700 00:24:51,210 --> 00:24:51,710 >> Gabe: Габе. 701 00:24:51,710 --> 00:24:52,340 >> Дејвид Џ MALAN: Габе. 702 00:24:52,340 --> 00:24:53,220 Габе е во тек. 703 00:24:53,220 --> 00:24:54,640 Што е најлесната работа да се направи? 704 00:24:54,640 --> 00:24:58,390 Разменуваат овие две момчиња и продолжи. 705 00:24:58,390 --> 00:24:59,020 Па сега ајде да видиме. 706 00:24:59,020 --> 00:25:00,170 Кој е најмалиот? 707 00:25:00,170 --> 00:25:01,030 Четири. 708 00:25:01,030 --> 00:25:01,990 Дозволете ми само вид на измамник. 709 00:25:01,990 --> 00:25:03,090 Пет се случува да биде најмалата. 710 00:25:03,090 --> 00:25:05,220 Сметам дека следната, ако сакате да ги интензивираат напред, она што можам да треба да направите со 711 00:25:05,220 --> 00:25:06,820 овие момци, со Габе? 712 00:25:06,820 --> 00:25:08,450 Разменуваат повторно. 713 00:25:08,450 --> 00:25:10,740 Па сега, се уште малку на ред. 714 00:25:10,740 --> 00:25:14,140 Најдов Габе да биде најмалата, па Го појави надвор, ќе се движат момци завршена. 715 00:25:14,140 --> 00:25:15,190 И направено. 716 00:25:15,190 --> 00:25:17,200 >> Значи одговорот е ист. 717 00:25:17,200 --> 00:25:18,600 Крајниот резултат е ист. 718 00:25:18,600 --> 00:25:22,730 Кој од овие два алгоритми е подобар? 719 00:25:22,730 --> 00:25:23,500 Вториот, слушнав. 720 00:25:23,500 --> 00:25:24,252 Зошто? 721 00:25:24,252 --> 00:25:25,900 >> ЗВУЧНИК 3: Тоа е n чекори [нечујни]. 722 00:25:25,900 --> 00:25:27,600 >> Дејвид Џ MALAN: Тоа е n чекори во повеќето. 723 00:25:27,600 --> 00:25:28,490 Интересна. 724 00:25:28,490 --> 00:25:30,610 Така е тоа иако? 725 00:25:30,610 --> 00:25:33,630 Па како не можам да најдам на најмалиот елемент? 726 00:25:33,630 --> 00:25:37,060 Колку чекори морав да се земе на најде најмалиот елемент? 727 00:25:37,060 --> 00:25:39,220 Имав изгледа целиот пат на крајот, нели? 728 00:25:39,220 --> 00:25:41,530 Бидејќи во тој најлош случај, она што ако Нил беа над овде? 729 00:25:41,530 --> 00:25:45,700 Па само наоѓање на најмалиот елемент зема me n чекори, или n минус 1. 730 00:25:45,700 --> 00:25:46,100 Но, ОК. 731 00:25:46,100 --> 00:25:46,980 Па поправи Нил. 732 00:25:46,980 --> 00:25:48,740 Се сеќавам дека, од една минута или така одамна. 733 00:25:48,740 --> 00:25:51,680 >> Но како не сум се најдат на следниот најмалиот елемент? 734 00:25:51,680 --> 00:25:54,830 Тоа е n минус 1, или n минус 2, навистина, од бројот на чекори. 735 00:25:54,830 --> 00:25:55,440 Па ред. 736 00:25:55,440 --> 00:25:57,390 Па јас го n минус 2. 737 00:25:57,390 --> 00:25:57,600 Сите во право. 738 00:25:57,600 --> 00:25:59,130 Така што се чувствува малку подобро. 739 00:25:59,130 --> 00:25:59,730 Сите во право. 740 00:25:59,730 --> 00:26:03,270 Колку чекори следниот пат да се најде бројот три? 741 00:26:03,270 --> 00:26:04,420 Значи n минус 4. 742 00:26:04,420 --> 00:26:07,670 Па тоа е намалување, еден помалку чекор на секоја итерација. 743 00:26:07,670 --> 00:26:08,740 Значи ова се чувствува подобро, нели? 744 00:26:08,740 --> 00:26:13,450 Ако последен пат тоа беше грубо n пати n, овој пат тоа е n минус 1, плус n минус 745 00:26:13,450 --> 00:26:16,500 2, плус n минус 3, плус n минус 4, точка, точка, точка. 746 00:26:16,500 --> 00:26:18,750 Но ако се потсетиме од вашиот средно училиште учебници, малку измамник 747 00:26:18,750 --> 00:26:24,380 лист на задната страна која има формули, ако ги додадете оваа серија на броеви, 748 00:26:24,380 --> 00:26:31,280 она што е вкупниот број на чекори ќе биде дека јас земам тука? 749 00:26:31,280 --> 00:26:36,580 >> Ова е еден од оние, како, n минус 1, пати n, поделени со 2. 750 00:26:36,580 --> 00:26:39,040 Па дозволете ми да видам дали можам да се повлече ова за само еден миг. 751 00:26:39,040 --> 00:26:42,230 И повторно, Јас сум вид на заокружување некои броеви само да го задржи нашиот живот едноставен, 752 00:26:42,230 --> 00:26:47,830 но како што се сеќавам, тоа е нешто како ако Јас се направи N минус 1 нешта, тогаш n минус 753 00:26:47,830 --> 00:26:53,570 2, тогаш n минус 3, тоа е грубо нешто како ова над 2, и ако јас 754 00:26:53,570 --> 00:26:55,510 помножиш оваа надвор, тоа е всушност n плоштад. 755 00:26:55,510 --> 00:26:58,940 Дека не се чувствува премногу добро. n минус n над 2. 756 00:26:58,940 --> 00:27:00,350 >> Но, тука е нешто. 757 00:27:00,350 --> 00:27:03,720 Во компјутерската наука, кога проблемите почне да се поинтересно е кога n 758 00:27:03,720 --> 00:27:04,700 станува навистина голем. 759 00:27:04,700 --> 00:27:08,110 И кога n станува навистина голем, што на овие вредности се случува да доминира на сите 760 00:27:08,110 --> 00:27:09,750 на другите? 761 00:27:09,750 --> 00:27:10,990 Тоа е вид на n квадрат, нели? 762 00:27:10,990 --> 00:27:13,340 Да, делење со 2 е прилично добар. 763 00:27:13,340 --> 00:27:16,740 Но ако зборуваме за милијарди парчиња на податоци, или трилиони 764 00:27:16,740 --> 00:27:18,700 делови на податоци, во ред, па ти си двапати побрзо. 765 00:27:18,700 --> 00:27:22,440 Но кој навистина се грижи ако тоа голем број, ако овој фактор е она што добива 766 00:27:22,440 --> 00:27:23,040 поголеми и поголеми. 767 00:27:23,040 --> 00:27:25,990 И сигурно, тоа го прави повеќе од разлика од овој човек. 768 00:27:25,990 --> 00:27:29,120 Па дури иако вие момци се во право, вториот алгоритам, ние ќе го наречеме 769 00:27:29,120 --> 00:27:32,970 селекција вид, е, во реалниот свет, малку побрзо потенцијално, бидејќи јас сум 770 00:27:32,970 --> 00:27:35,360 земање помалку и помалку чекори секој пат. 771 00:27:35,360 --> 00:27:37,340 >> Тоа не е навистина фундаментално побрзо. 772 00:27:37,340 --> 00:27:41,430 Затоа што ако ние всушност игра ова за големи вредности на n, на крајот на 773 00:27:41,430 --> 00:27:44,750 на денот, за доволно голема за n, тоа е уште случува да се чувствуваат прилично бавен. 774 00:27:44,750 --> 00:27:46,770 Па, дозволете ми да земе една последните помине во тоа. 775 00:27:46,770 --> 00:27:48,920 Тоа е она што јас би го нарекол селекција вид. 776 00:27:48,920 --> 00:27:51,040 Вие момци можат самите го ресетирате за последен пат? 777 00:27:51,040 --> 00:27:53,550 И во последниот случај, јас ќе одам да предложи нешто 778 00:27:53,550 --> 00:27:54,970 наречен вметнување вид. 779 00:27:54,970 --> 00:27:57,470 Вметнување вид суштество, концептуално, малку различни. 780 00:27:57,470 --> 00:28:00,980 >> Наместо да оди напред и назад и изборот на најмалиот елемент, јас сум 781 00:28:00,980 --> 00:28:05,030 само ќе се справи со секоја од овие момци како што јас ги сретнуваме, и вметнете 782 00:28:05,030 --> 00:28:06,850 нив во нивните правилната место. 783 00:28:06,850 --> 00:28:10,160 Па јас сум само ќе почнат со Grace, и гледам дека таа е број четири. 784 00:28:10,160 --> 00:28:11,720 Каде број четири припаѓаат? 785 00:28:11,720 --> 00:28:14,940 Јас не почнаа сортирање ништо, па Грејс добива да остане право таму. 786 00:28:14,940 --> 00:28:18,355 И сега ќе одам да се тврди, ако може преземе чекор на вашето право, ова 787 00:28:18,355 --> 00:28:21,650 мојата подредени листата, ова е мојот несортиран преостанати листата. 788 00:28:21,650 --> 00:28:23,260 Па сега јас ќе одам да продолжи следната, и она што е вашето име повторно? 789 00:28:23,260 --> 00:28:23,700 >> BRANSON: Бренсон. 790 00:28:23,700 --> 00:28:24,150 >> Дејвид Џ MALAN: Бренсон. 791 00:28:24,150 --> 00:28:25,375 Па Бренсон е број два. 792 00:28:25,375 --> 00:28:27,490 Па јас ќе одам да ти земе надвор за момент. 793 00:28:27,490 --> 00:28:30,940 А сега, каде ќе припаѓаат во оваа низа? 794 00:28:30,940 --> 00:28:32,360 Па на правото на Грејс. 795 00:28:32,360 --> 00:28:35,670 Па уште еднаш, ние сме вид на правење Благодат направи многу работа овде. 796 00:28:35,670 --> 00:28:37,290 Каде што ние ви го стави? 797 00:28:37,290 --> 00:28:40,120 Па ние ќе да ви слајд на лево, и вметнете Бренсон таму. 798 00:28:40,120 --> 00:28:41,680 Но сега тврдам дека вие момци се направи. 799 00:28:41,680 --> 00:28:43,240 Но известување, јас не сум користење на екстра простор. 800 00:28:43,240 --> 00:28:45,130 Тоа е уште 2 елементи тука, 5 повеќе од тука. 801 00:28:45,130 --> 00:28:47,910 Вкупно низа големина е 7, па јас сум не мамење, во ред? 802 00:28:47,910 --> 00:28:51,950 >> Така, сега имаме, со Габе тука, број шест, каде ќе припаѓаат? 803 00:28:51,950 --> 00:28:52,650 Имаш среќа повторно. 804 00:28:52,650 --> 00:28:53,820 Па ќе го добиете да остане право таму. 805 00:28:53,820 --> 00:28:57,210 Само да потрае мал чекор кон десно само да го направи јасно дека сте подредени. 806 00:28:57,210 --> 00:29:00,520 И сега имаме Нил повторно, број еден, каде и да одите? 807 00:29:00,520 --> 00:29:03,540 И сега е местото каде што ќе почнат да се види дека овој алгоритам, иако на прв 808 00:29:03,540 --> 00:29:05,950 поглед, се чувствува прилично паметни, види она што е за да се случи. 809 00:29:05,950 --> 00:29:07,370 Ако може да се чекор напред. 810 00:29:07,370 --> 00:29:09,260 >> Каде што сакаме да се стави Нил? 811 00:29:09,260 --> 00:29:11,830 Па очигледно тука, па како ние да се Нил таму? 812 00:29:11,830 --> 00:29:12,970 Ајде да го направиме овој чекор-по-чекор. 813 00:29:12,970 --> 00:29:15,620 Габе, каде ќе треба да одат? 814 00:29:15,620 --> 00:29:19,590 Да, така да еден голем чекор, или две полу-чекори за да се направи 815 00:29:19,590 --> 00:29:20,820 еден чекор таму. 816 00:29:20,820 --> 00:29:21,750 Благодат, каде и да одите? 817 00:29:21,750 --> 00:29:22,510 Добар. 818 00:29:22,510 --> 00:29:23,500 Па уште еден чекор. 819 00:29:23,500 --> 00:29:24,960 И, конечно, Бренсон? 820 00:29:24,960 --> 00:29:25,460 Уште еден чекор. 821 00:29:25,460 --> 00:29:27,190 И сега ние може да се стави Нил во место. 822 00:29:27,190 --> 00:29:28,440 >> Па сега, продолжи и оваа логика. 823 00:29:28,440 --> 00:29:32,420 Иако ние не се префрлаат Нил над, и одново, и одново, да го стави 824 00:29:32,420 --> 00:29:36,420 Каде и да оди, во најлош случај, следниот број ќе се судрите би можеле да 825 00:29:36,420 --> 00:29:42,220 биде број, да речеме, имаше голем број нула, тогаш ние ќе треба да се префрлат сите на 826 00:29:42,220 --> 00:29:42,730 овие момци. 827 00:29:42,730 --> 00:29:44,950 Да претпоставиме дека има голем број, негативен еден, тогаш треба да го пренасочиме 828 00:29:44,950 --> 00:29:46,080 сите од овие момци. 829 00:29:46,080 --> 00:29:48,500 Значи ние сме навистина само вид на нервира проблемот околу, така што ние сме 830 00:29:48,500 --> 00:29:52,620 пренос на сметка од процесот на селекција, па вметнување 831 00:29:52,620 --> 00:29:56,930 процес, како што вие момци само имаше да се движи околу n минус нешто 832 00:29:56,930 --> 00:29:57,940 број на чекори. 833 00:29:57,940 --> 00:30:01,200 И дека бројот на чекори е само ќе да се зголеми, како јас изберете повеќе броеви, 834 00:30:01,200 --> 00:30:04,730 ако јас мора да се задржи турканиците вие ​​момци назад, и назад, и назад. 835 00:30:04,730 --> 00:30:08,320 >> Па Тажната работа сега е сите овие алгоритми се n квадрат. 836 00:30:08,320 --> 00:30:10,570 Ајде да одиме напред и благодарение на овие момци, и да се визуелизира овие малку 837 00:30:10,570 --> 00:30:11,090 поинаку. 838 00:30:11,090 --> 00:30:12,312 Многу добро направено. 839 00:30:12,312 --> 00:30:14,120 >> [Аплауз] 840 00:30:14,120 --> 00:30:15,030 >> Сите во право. 841 00:30:15,030 --> 00:30:16,280 Таму да одите. 842 00:30:16,280 --> 00:30:18,390 843 00:30:18,390 --> 00:30:18,470 Ви благодариме за - 844 00:30:18,470 --> 00:30:19,190 >> BRANSON: [нечујни] задржи на броеви. 845 00:30:19,190 --> 00:30:21,990 >> Дејвид Џ MALAN: Не, вие може да задржи на броеви, како и. 846 00:30:21,990 --> 00:30:23,440 Сите во право. 847 00:30:23,440 --> 00:30:24,100 Убаво направено. 848 00:30:24,100 --> 00:30:25,300 Сите во право. 849 00:30:25,300 --> 00:30:30,510 Па ајде да видиме дали можеме сега не може да резимираме побрзо, и повеќе визуелно, 850 00:30:30,510 --> 00:30:33,410 токму она што се случи тука како што следи. 851 00:30:33,410 --> 00:30:36,510 852 00:30:36,510 --> 00:30:38,770 Одам да одите напред и повлечете го Firefox. 853 00:30:38,770 --> 00:30:41,310 Ние ќе ја поврзат оваа демонстрација на веб-страницата на курсот. 854 00:30:41,310 --> 00:30:43,870 Јава е малку досадно да се работи во некои прелистувачи овие денови. 855 00:30:43,870 --> 00:30:46,760 Па ако си играат со ова дома, сфатиш дека можеби ќе треба да го користите на Firefox 856 00:30:46,760 --> 00:30:47,990 да го добие работа. 857 00:30:47,990 --> 00:30:50,440 И она што јас ќе одам да направите со овој демонстрација е следниот. 858 00:30:50,440 --> 00:30:54,875 >> На дното, јас имам цел куп мени опции, вклучувајќи почеток и 859 00:30:54,875 --> 00:30:55,840 Сопри. 860 00:30:55,840 --> 00:30:59,450 Исто така, како настрана, се чини дека да се биде бубачка во овие програми, при што ќе ги 861 00:30:59,450 --> 00:31:03,720 не може да всушност гледаат на проектот или да престане копче, освен ако не се одржи команда или Alt 862 00:31:03,720 --> 00:31:06,560 плус и зумирате, кој љубопитно ви покажува повеќе копчиња. 863 00:31:06,560 --> 00:31:09,090 Па само Материјал цел, ако игра со ова дома. 864 00:31:09,090 --> 00:31:12,870 Сега ќе одам да кликнете на Start за само момент, по специфицирање задоцнување од, 865 00:31:12,870 --> 00:31:16,810 како, 200 милисекунди тука, само за да можеме да видиме што се случува. 866 00:31:16,810 --> 00:31:20,180 >> Така тврдам дека ова е визуелизација на првиот алгоритам 867 00:31:20,180 --> 00:31:23,730 овие момци го, меур вид, при што ние заменети луѓе пар-мудар. 868 00:31:23,730 --> 00:31:27,490 Клучот увид на оваа визуелизација е дека висината на барови 869 00:31:27,490 --> 00:31:30,510 претставува големината на број. 870 00:31:30,510 --> 00:31:32,210 Па повисоки има црти, толку поголем број. 871 00:31:32,210 --> 00:31:33,680 Пократко бар, помал број. 872 00:31:33,680 --> 00:31:38,630 И ако забележите, ние сме минува низ првиот повторување на овој алгоритам, 873 00:31:38,630 --> 00:31:42,620 Замена на големи и мали броеви, така што малиот број доаѓа прво и 874 00:31:42,620 --> 00:31:44,280 големиот број оди на десно. 875 00:31:44,280 --> 00:31:48,770 >> И штом ќе го добиеме на крајот на низа на многу повеќе броеви од седум, ние сме 876 00:31:48,770 --> 00:31:49,900 ќе се вратиме на почеток. 877 00:31:49,900 --> 00:31:51,140 И да се предвиди ова. 878 00:31:51,140 --> 00:31:54,860 На далеку лево, дека малиот човек се случува да се разменуваат на страна, и ова 879 00:31:54,860 --> 00:31:56,010 процесот се повторува. 880 00:31:56,010 --> 00:31:59,450 Сега ова визуелизација брзо добива здодевен, па дозволете ми да оди напред и да престане 881 00:31:59,450 --> 00:32:04,170 , сменете го задоцнување нешто многу побрзо само за да добие сега, чувство за 882 00:32:04,170 --> 00:32:05,060 овој алгоритам. 883 00:32:05,060 --> 00:32:07,840 >> Значи, иако сум го забрза, ова е како надградба на мојата процесор, за купување 884 00:32:07,840 --> 00:32:08,580 на нов компјутер. 885 00:32:08,580 --> 00:32:12,980 Не сум фундаментално се промени мојот алгоритам, но ти навистина може да види повеќе 886 00:32:12,980 --> 00:32:16,800 јасно отколку со луѓето, дека големите броеви се жуборот до врвот, 887 00:32:16,800 --> 00:32:20,900 и мал број се жуборот надолу кон дното. 888 00:32:20,900 --> 00:32:22,390 А сега ова нешто овде подредени. 889 00:32:22,390 --> 00:32:25,260 И како настрана, во плоштади, има само некои книговодство таму да 890 00:32:25,260 --> 00:32:28,010 помогне да брои колку споредби, или колку свопови имаат 891 00:32:28,010 --> 00:32:28,950 всушност е направено. 892 00:32:28,950 --> 00:32:30,750 >> Добро, ајде пробајте едно од другите видовме. 893 00:32:30,750 --> 00:32:37,116 Дозволете ми да кликнете на меурот вид тука, и дозволете ми да изберат, и целата оваа веб страница 894 00:32:37,116 --> 00:32:38,936 е малку кабриолет. 895 00:32:38,936 --> 00:32:41,155 Ајде да го прифати ризикот и тоа кандидира повторно. 896 00:32:41,155 --> 00:32:44,560 897 00:32:44,560 --> 00:32:45,030 Таму ќе одиме. 898 00:32:45,030 --> 00:32:47,180 Па ајде да направиме избор вид. 899 00:32:47,180 --> 00:32:49,140 Јас не знам зошто на менито се појавува таму. 900 00:32:49,140 --> 00:32:54,070 Ајде да зумирате да се утврдат дека бубачка, сменете го ова на 50. 901 00:32:54,070 --> 00:32:56,020 Ах, да всушност прават дека многу побрзо. 902 00:32:56,020 --> 00:32:59,160 Пет милисекунди или така, и да почне. 903 00:32:59,160 --> 00:33:00,470 >> Па ова е избор кој вид. 904 00:33:00,470 --> 00:33:03,070 Значи, повторно, мислам за она што ние го направив со луѓето тука горе. 905 00:33:03,070 --> 00:33:08,490 Отидовме преку низа и избрани најмалиот елемент, повторно, 906 00:33:08,490 --> 00:33:09,250 и повторно, и повторно. 907 00:33:09,250 --> 00:33:11,110 Сега тврдам дека уште беше прилично лош. 908 00:33:11,110 --> 00:33:15,010 Тоа беше уште n квадрат, дава или зема, но тоа беше, во реалниот свет, малку 909 00:33:15,010 --> 00:33:18,280 побрзо, бидејќи бев навистина преземање малку помалку чекори секој пат. 910 00:33:18,280 --> 00:33:19,800 Но ние сме само зборува што? 911 00:33:19,800 --> 00:33:21,830 Можеби 40 или така барови тука? 912 00:33:21,830 --> 00:33:23,200 Ние не зборуваме 40 милиони евра. 913 00:33:23,200 --> 00:33:27,430 Па тоа не е сосема јасно дека беше навистина значителен добивка. 914 00:33:27,430 --> 00:33:32,530 >> А сега допуштете ми се вратиш назад и промени во нашето трети алгоритам, кој беше изберете 915 00:33:32,530 --> 00:33:33,180 вметнување вид. 916 00:33:33,180 --> 00:33:36,380 А сега тоа е навистина кабриолет бидејќи мени навистина не треба да биде таму долу. 917 00:33:36,380 --> 00:33:40,840 Па сега ние ќе дојдете назад до овде и да почне овој алгоритам. 918 00:33:40,840 --> 00:33:43,270 Шиштење, почне и запре. 919 00:33:43,270 --> 00:33:47,160 Значи ова еден вид на има прилично модел на него, при што ние сме повторно 920 00:33:47,160 --> 00:33:50,240 вметнување на луѓето, или во овој случај, барови во 921 00:33:50,240 --> 00:33:52,620 нивната соодветна локација. 922 00:33:52,620 --> 00:33:55,430 И тоа е веќе направено пред Се свртев. 923 00:33:55,430 --> 00:33:58,940 Но ова, исто така, во теорија, се уште n квадрат. 924 00:33:58,940 --> 00:34:01,430 >> Да видиме ако не можеме да резимираме овие како што следи. 925 00:34:01,430 --> 00:34:04,750 Одам да одите напред и само за да даде ни вид на заеднички начин на зборување 926 00:34:04,750 --> 00:34:08,489 за овие работи, дозволете ми да се воведе само малку на нотација тука. 927 00:34:08,489 --> 00:34:12,480 Вие сте за да се види нешто што се нарекува голема О, бидејќи е буквално голем 928 00:34:12,480 --> 00:34:16,320 О И ова е начинот на кој компјутер научник или математичар дури и го користи 929 00:34:16,320 --> 00:34:19,230 за да се опише трчање време на некои алгоритам. 930 00:34:19,230 --> 00:34:21,400 Колку чекори Дали тоа всушност го земам? 931 00:34:21,400 --> 00:34:25,080 >> Сега ќе одам да си се посрамоти со мојот ракопис тука во само еден миг. 932 00:34:25,080 --> 00:34:29,020 Но дозволете ми да оди напред и да се каже дека ова ќе биде големо O овде. 933 00:34:29,020 --> 00:34:33,610 И дозволете ми да се воведе еден друг симбол, главниот град на омега. 934 00:34:33,610 --> 00:34:37,080 Омега ќе биде спротивното, во суштина, на големите О Каде големо O 935 00:34:37,080 --> 00:34:40,790 средства, во најлош случај, колку време некои алгоритам може да потрае, во 936 00:34:40,790 --> 00:34:43,480 условите од n, омега се случува да се биде колку време би можеле да го 937 00:34:43,480 --> 00:34:45,409 земе во најдобар случај. 938 00:34:45,409 --> 00:34:48,090 И ќе видиме што ние подразбираме под најдобар случај во само еден миг. 939 00:34:48,090 --> 00:34:49,940 >> Значи, да почнеме нешто едноставно. 940 00:34:49,940 --> 00:34:54,719 Дозволете ми да започнам со линеарно пребарување. 941 00:34:54,719 --> 00:34:55,679 Па не сортирање. 942 00:34:55,679 --> 00:34:58,000 Ние ќе го наречеме овој линеарно пребарување. 943 00:34:58,000 --> 00:35:01,140 И сега, се направи малку маса надвор од ова. 944 00:35:01,140 --> 00:35:06,600 И сега, во случај на линеарно пребарување, во најлош случај, колку чекори е 945 00:35:06,600 --> 00:35:11,770 тоа ќе ме однесе да Најдете број на произволен избор? 946 00:35:11,770 --> 00:35:14,540 И таму е N Вкупно врати или n вкупниот број. 947 00:35:14,540 --> 00:35:15,940 Најлош случај. 948 00:35:15,940 --> 00:35:18,800 Колку чекори сум јас ќе мора да се се земе да се најде бројот 50 во низа 949 00:35:18,800 --> 00:35:20,830 од n врати? 950 00:35:20,830 --> 00:35:21,410 И зошто? 951 00:35:21,410 --> 00:35:23,680 Бидејќи тоа би можело да биде на сите начин над кон крајот. 952 00:35:23,680 --> 00:35:27,120 Толку многу како Џенифер се среќава, на број 50 беше целиот пат над, така што во 953 00:35:27,120 --> 00:35:30,760 најлош случај линеарно пребарување е голема О од n, ќе речеме. 954 00:35:30,760 --> 00:35:33,430 >> Што е со најдобар случај, ако добиете навистина среќен? 955 00:35:33,430 --> 00:35:36,200 Тоа е само случува да се земе еден чекор, или постојан број на чекори. 956 00:35:36,200 --> 00:35:37,830 Па ние ќе се опише тој како 1. 957 00:35:37,830 --> 00:35:39,010 Значи ова е прилично добар. 958 00:35:39,010 --> 00:35:41,210 Сега што ако ние го сторивме нешто како бинарна пребарување? 959 00:35:41,210 --> 00:35:43,860 960 00:35:43,860 --> 00:35:47,846 Па бинарни пребарување, во најлош случај, зеде колку време? 961 00:35:47,846 --> 00:35:49,250 >> [INTERPOSING ГЛАСОВИ] 962 00:35:49,250 --> 00:35:51,310 >> Дејвид Џ MALAN: Па, всушност, јас Слушнав дека во неколку места. 963 00:35:51,310 --> 00:35:56,390 Па тоа е, всушност, се логирате n, дава или зема, бидејќи, како што ја делиме на листата на половина 964 00:35:56,390 --> 00:36:00,730 повторно, и повторно, и повторно, ние сме во можност да се најде, во крајна линија, вредноста, 965 00:36:00,730 --> 00:36:04,750 ако тоа е таму, но постои фати. 966 00:36:04,750 --> 00:36:08,590 Што е претпоставката дека ние треба да земе здраво за готово за бинарни пребарување? 967 00:36:08,590 --> 00:36:09,700 Тоа мора да се подредени. 968 00:36:09,700 --> 00:36:12,770 Тоа не е сортирани, можете да се подели на работа во половина повторно и повторно, и вие 969 00:36:12,770 --> 00:36:15,490 може да оди лево, а вие може да одат право, и можете да одите лево и десно, но ти си 970 00:36:15,490 --> 00:36:18,070 нема да се најде елемент, ако листата не е сортирана, бидејќи 971 00:36:18,070 --> 00:36:18,790 може да го пропуштите. 972 00:36:18,790 --> 00:36:22,120 Бидејќи вашиот хеуристичка, за одење левата или десно се случува да биде недостатоци, ако тоа е 973 00:36:22,120 --> 00:36:23,420 навистина не подредени. 974 00:36:23,420 --> 00:36:26,110 Па таму е еден вид на скриени трошоци да се користи нешто како ова. 975 00:36:26,110 --> 00:36:29,250 >> Сега, ајде да одиме во нашиот сортирање алгоритми не бараат - 976 00:36:29,250 --> 00:36:31,140 ох, всушност, ајде да одиме во овој празно. 977 00:36:31,140 --> 00:36:33,190 Бинарни барај во најдобар случај? 978 00:36:33,190 --> 00:36:36,290 Тоа е, исто така, 1 ако тоа само се случува да биде во многу средината на низата, или 979 00:36:36,290 --> 00:36:37,810 средината на телефонот книга. 980 00:36:37,810 --> 00:36:39,710 Сега ајде да направиме меур вид. 981 00:36:39,710 --> 00:36:42,570 Па уште еднаш, сега ние сме влегуваат во видови не, пребарувања. 982 00:36:42,570 --> 00:36:47,220 >> Во најлош случај, колку чекори не можеме тврдат меур вид се случува да се земе? 983 00:36:47,220 --> 00:36:48,410 n квадрат. 984 00:36:48,410 --> 00:36:49,200 Па ќе одам да се подготви тоа. 985 00:36:49,200 --> 00:36:51,710 Ooh, мојата ракопис изгледа дури и полошо кога тоа е проектиран дека голема. 986 00:36:51,710 --> 00:36:52,510 Сите во право. 987 00:36:52,510 --> 00:36:53,570 Така што за N квадрат. 988 00:36:53,570 --> 00:36:59,460 И во најдобар случај на меурот вид, колку чекори е тоа ќе потрае? 989 00:36:59,460 --> 00:37:00,980 1, слушнав. 990 00:37:00,980 --> 00:37:01,760 >> ЗВУЧНИК 1: n. 991 00:37:01,760 --> 00:37:03,286 >> Дејвид Џ MALAN: N, слушнав. 992 00:37:03,286 --> 00:37:04,200 >> ЗВУЧНИК 1: 2. 993 00:37:04,200 --> 00:37:05,010 >> Дејвид Џ MALAN: 2, слушнав. 994 00:37:05,010 --> 00:37:06,670 Слушам 3? 995 00:37:06,670 --> 00:37:07,080 Сите во право. 996 00:37:07,080 --> 00:37:11,390 Па јас сум слушнал 1, n, 2, но ајде да ги собереш за разлика барем во првите од оние 997 00:37:11,390 --> 00:37:12,330 предлози, 1. 998 00:37:12,330 --> 00:37:15,370 Тоа не е лоша инстинкт, бидејќи тоа вид на следниов шаблон овде. 999 00:37:15,370 --> 00:37:19,670 Но, ако тоа трае само 1 чекор, како во свет, јас може да се тврди дека листата 1000 00:37:19,670 --> 00:37:22,900 е сортирана, бидејќи ако јас сум дозволено само да се земе 1 чекор, колку елементи 1001 00:37:22,900 --> 00:37:25,230 може јас всушност проверете, за да бидеме сигурни? 1002 00:37:25,230 --> 00:37:28,270 Па, само 1, што значи дека n минус 1 елементи кои би можеле да бидат надвор од 1003 00:37:28,270 --> 00:37:31,310 ред, а јас сум само ќе се заснова на верата по во потрага на 1 елемент кој на 1004 00:37:31,310 --> 00:37:31,850 нешто се подредени. 1005 00:37:31,850 --> 00:37:33,930 Толку 1 не е точно тука. 1006 00:37:33,930 --> 00:37:35,710 Така минимално, колку морам да се погледне? 1007 00:37:35,710 --> 00:37:36,680 >> [INTERPOSING ГЛАСОВИ] 1008 00:37:36,680 --> 00:37:40,160 >> Дејвид Џ MALAN: N минус 1, или навистина, n, затоа што треба да се погледне во секој 1009 00:37:40,160 --> 00:37:42,190 елемент да бидете сигурни дека тоа не е на ред. 1010 00:37:42,190 --> 00:37:44,750 Но, повторно, ние ќе средиме од бран нашата рацете на помал број и 1011 00:37:44,750 --> 00:37:47,100 се претпостави дека, како n добива големи, тие се неинтересен во секој случај. 1012 00:37:47,100 --> 00:37:48,380 Па тоа е балон вид. 1013 00:37:48,380 --> 00:37:49,830 И сега, ајде да направиме овие последните две. 1014 00:37:49,830 --> 00:37:53,520 Селекција вид, а потоа ние ќе направи вметнување вид. 1015 00:37:53,520 --> 00:37:57,160 А потоа ние ќе удар вашиот умови со нешто многу 1016 00:37:57,160 --> 00:37:58,926 подобро од сите овие. 1017 00:37:58,926 --> 00:38:00,410 Сите во право. 1018 00:38:00,410 --> 00:38:04,700 >> Што е најлошото работи времето на селекција кој вид? 1019 00:38:04,700 --> 00:38:05,680 >> ЗВУЧНИК 4: N квадрат. 1020 00:38:05,680 --> 00:38:06,710 >> Дејвид Џ MALAN: N плоштад, ја слушам. 1021 00:38:06,710 --> 00:38:09,790 Но, зошто n квадрат, интуитивно? 1022 00:38:09,790 --> 00:38:11,170 >> ЗВУЧНИК 4: Бидејќи ние само го направив тоа. 1023 00:38:11,170 --> 00:38:12,260 >> Дејвид Џ MALAN: Бидејќи ние само го направив тоа. 1024 00:38:12,260 --> 00:38:12,550 OK. 1025 00:38:12,550 --> 00:38:13,380 Добар одговор. 1026 00:38:13,380 --> 00:38:16,660 Но интуитивно, зошто е избор вид n квадрат? 1027 00:38:16,660 --> 00:38:18,980 Она што не ни треба да направите повторно и повторно? 1028 00:38:18,980 --> 00:38:22,570 Ние моравме да ги задржи скенирање преку, се ви најмалиот, ти ли си 1029 00:38:22,570 --> 00:38:24,020 најмалиот, да не сте најмалите. 1030 00:38:24,020 --> 00:38:27,480 И готово, бевме во можност да се земе n чекори, тогаш n минус 1, тогаш n минус 2. 1031 00:38:27,480 --> 00:38:30,700 Но ако вид на додадете оние сè, или ја преземат верба дека јас додадов 1032 00:38:30,700 --> 00:38:34,810 за нив однапред, ние се добие приближно n квадрат минус некои помали броеви. 1033 00:38:34,810 --> 00:38:36,730 Па ќе одам да се јавите оваа n квадрат. 1034 00:38:36,730 --> 00:38:39,530 Но со селекција вид во најдобар случај, колку чекори е тоа 1035 00:38:39,530 --> 00:38:40,632 ќе ме земе? 1036 00:38:40,632 --> 00:38:41,840 >> ЗВУЧНИК 5: [нечујни] 1037 00:38:41,840 --> 00:38:44,350 >> Дејвид Џ MALAN: Тоа е за жал уште n квадрат, нели? 1038 00:38:44,350 --> 00:38:49,590 Бидејќи ако јас сум изборот на најмалите елемент, и имавме седум луѓе тука, 1039 00:38:49,590 --> 00:38:53,280 Знам само, еднаш бев се дојде до многу крајот, дека сум го нашол на најмалите 1040 00:38:53,280 --> 00:38:55,670 број, каде што тој или таа може да биде. 1041 00:38:55,670 --> 00:38:58,820 Но како можам да се најдат на следниот Најмал број? 1042 00:38:58,820 --> 00:39:00,160 Јас треба да направите друга помине. 1043 00:39:00,160 --> 00:39:04,810 Значи во најдобар случај, она што е внесување на селекција кој вид? 1044 00:39:04,810 --> 00:39:07,830 Тоа е веќе вид листа, број еден, број два, број три, број четири. 1045 00:39:07,830 --> 00:39:08,600 Но, јас сум на компјутер. 1046 00:39:08,600 --> 00:39:10,190 Можам само да се погледне во едно работа во исто време. 1047 00:39:10,190 --> 00:39:12,465 Јас не може да се најде на направиме чекор назад како човечки и да каже, 1048 00:39:12,465 --> 00:39:14,030 ooh, ова изгледа точни. 1049 00:39:14,030 --> 00:39:17,580 >> Можам само да судат точноста во селекција вид со избирање на 1050 00:39:17,580 --> 00:39:18,370 Најмал број. 1051 00:39:18,370 --> 00:39:21,390 Но, дури и ако најдам број еден, прво, ако не знам ништо во врска со 1052 00:39:21,390 --> 00:39:24,460 другите броеви, кои јас не се направи, сè што можам знам дека сум бил предаден низа 1053 00:39:24,460 --> 00:39:27,930 или приврзок на вратите зад кои се броеви, единствениот начин знам дека еден 1054 00:39:27,930 --> 00:39:28,680 беше најмалиот? 1055 00:39:28,680 --> 00:39:32,440 Ако јас се добие целиот пат тука и се реализира, проклето, еден беше навистина најмалите. 1056 00:39:32,440 --> 00:39:34,870 >> Но, како можам потоа да одреди дека две е следниот најмалиот? 1057 00:39:34,870 --> 00:39:38,350 Со тоа исто неефикасноста повторно и повторно. 1058 00:39:38,350 --> 00:39:42,210 Значи, конечно, со вметнување вид, како, во најлош случај, 1059 00:39:42,210 --> 00:39:44,990 Дали ние велиме врши? 1060 00:39:44,990 --> 00:39:49,100 Тоа не е премногу е n квадрат. 1061 00:39:49,100 --> 00:39:53,020 И како за со најдобар случај? 1062 00:39:53,020 --> 00:39:56,282 Ќе им го оставиме тоа како cliffhanger. 1063 00:39:56,282 --> 00:40:00,090 Ние ќе се пополни во таа празна следниот пат, но прво нека ми предложи дека ние 1064 00:40:00,090 --> 00:40:02,620 фундаментално го направи подобро од сите овие, во ред? 1065 00:40:02,620 --> 00:40:05,220 >> Така што мислам за себе она што вметнување вид се случува да биде. 1066 00:40:05,220 --> 00:40:06,910 Па, тоа не беше многу драматичен, затоа што јас сум единствениот 1067 00:40:06,910 --> 00:40:08,970 што ја видоа промени. 1068 00:40:08,970 --> 00:40:09,620 Wow. 1069 00:40:09,620 --> 00:40:10,420 OK. 1070 00:40:10,420 --> 00:40:12,615 Значи тука имаме малку различни демонстрации. 1071 00:40:12,615 --> 00:40:16,580 Ако јас зумирате тука, ќе видите дека на на левата страна имаме меур вид, во 1072 00:40:16,580 --> 00:40:20,740 средината имаме избор вид, како и на на екстремната десница, имаме нешто што ние 1073 00:40:20,740 --> 00:40:23,380 не погледна уште наречен спојат вид. 1074 00:40:23,380 --> 00:40:26,080 Но, сметаат дека она што сте биле правиш тука досега денес. 1075 00:40:26,080 --> 00:40:29,200 Кога Џенифер прв дојде на сцената, отидовме преку низа на броеви 1076 00:40:29,200 --> 00:40:33,750 повторно, и повторно, со линеарен пребарување, и добивме линеарна трчање време, големо O 1077 00:40:33,750 --> 00:40:35,100 на n, така да се каже. 1078 00:40:35,100 --> 00:40:41,000 >> Кога ние сега сметаат дека во првата недела од класа, кога имавме поделба и освојување, 1079 00:40:41,000 --> 00:40:43,740 и имавме книгата на телефонот кинење, и Џенифер, и ние колективно 1080 00:40:43,740 --> 00:40:47,500 балон дека клучните увид, кој требаше да повторете си повторно и повторно 1081 00:40:47,500 --> 00:40:50,930 некако фрлаат далеку, фрлаат далеку, фрлање далеку, половина од проблемот, или 1082 00:40:50,930 --> 00:40:55,320 генерално, делење на проблемот на половина, и потоа лекувањето на помал дел од 1083 00:40:55,320 --> 00:40:59,630 проблемот што е концептуално еквивалентни на другите, ние некако не 1084 00:40:59,630 --> 00:41:00,910 фундаментално подобро. 1085 00:41:00,910 --> 00:41:04,720 Но со балон вид, со избор вид, со вметнување вид, ние сме може 1086 00:41:04,720 --> 00:41:06,560 нема такви сознанија дека Џенифер не. 1087 00:41:06,560 --> 00:41:10,220 Ние доста само си се врати и издаде целиот куп на пати, а ние 1088 00:41:10,220 --> 00:41:12,650 tweaked работите малку, Замена Во овој редослед, можеби 1089 00:41:12,650 --> 00:41:13,730 вметнување или избирање. 1090 00:41:13,730 --> 00:41:16,950 Но на крајот на денот, јас навистина многу на непријатно одење напред и назад. 1091 00:41:16,950 --> 00:41:21,160 Ние не сме навистина потпора нешто паметни како Џенифер му се допадна делење 1092 00:41:21,160 --> 00:41:22,040 и освојување. 1093 00:41:22,040 --> 00:41:25,620 >> Па се спојат вид, пак, кои ние нема да видиме до следната недела, тоа се случува 1094 00:41:25,620 --> 00:41:29,540 да потпора дека клучната идеја со делење влезот, а потоа преполовување, а потоа 1095 00:41:29,540 --> 00:41:30,580 преполовување, а потоа преполовување. 1096 00:41:30,580 --> 00:41:34,590 И на секоја итерација на таа јамка, сортирање на левата половина, и правото 1097 00:41:34,590 --> 00:41:38,200 половина, а потоа на левата половина од левата половина, и десната половина на левата страна, а потоа 1098 00:41:38,200 --> 00:41:40,990 на левата половина на десната половина, и на десната половина на десната половина. 1099 00:41:40,990 --> 00:41:42,840 И повторување повторно и повторно. 1100 00:41:42,840 --> 00:41:46,170 >> Па ќе видите ова визуелно, но ова е она што не чека следната недела. 1101 00:41:46,170 --> 00:41:49,760 И воопшто, кога мислиме малку малку потешко на кој било таков проблем. 1102 00:41:49,760 --> 00:41:52,435 1103 00:41:52,435 --> 00:41:57,970 Имаме n квадрат на левата страна, н квадрат во средината, и n 1104 00:41:57,970 --> 00:41:59,400 логирате n десно. 1105 00:41:59,400 --> 00:42:00,590 Така што вашиот вистински cliffhanger. 1106 00:42:00,590 --> 00:42:02,040 Ќе се видиме во понеделник. 1107 00:42:02,040 --> 00:42:05,163 >> [Аплауз]