1 00:00:00,000 --> 00:00:11,100 >> [За възпроизвеждане на музика] 2 00:00:11,100 --> 00:00:11,490 >> DAVID J. 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 И това е съвсем нормално, ако сте все още се борят с проблема Set 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,?] може би дори пляскане, и 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 >> ДЖЕНИФЪР: [недоловим] 36 00:01:44,850 --> 00:01:45,170 >> DAVID J. Malan: Моля? 37 00:01:45,170 --> 00:01:45,860 >> ДЖЕНИФЪР: Дженифър. 38 00:01:45,860 --> 00:01:46,390 >> DAVID J. 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 >> [APPLAUSE] 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 >> ДЖЕНИФЪР: Хм, мислех, че може би, ако - 60 00:02:27,222 --> 00:02:27,714 [Недоловим] 61 00:02:27,714 --> 00:02:28,206 >> DAVID J. Malan: Oh. 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 >> ДЖЕНИФЪР: Така че аз просто започне в започваме да виждаме това, което първият брой 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 >> DAVID J. 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 >> Дженифър: О, боже. 73 00:02:51,712 --> 00:02:53,128 >> DAVID J. Malan: Ah. 74 00:02:53,128 --> 00:02:54,280 >> ДЖЕНИФЪР: Така че аз просто имам късмет. 75 00:02:54,280 --> 00:02:55,270 >> DAVID J. 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 >> ДЖЕНИФЪР: Така че, ако те са били подредени, I че може би най-малката до най-голямата. 83 00:03:11,715 --> 00:03:11,970 >> DAVID J. Malan: OK. 84 00:03:11,970 --> 00:03:15,260 >> ДЖЕНИФЪР: Или, ако това в крайна сметка е наистина голям, а след това най-голямата до най-малката. 85 00:03:15,260 --> 00:03:15,540 >> DAVID J. 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 >> ДЖЕНИФЪР: Всички от тях. 91 00:03:29,860 --> 00:03:30,420 >> DAVID J. Malan: Всички от тях. 92 00:03:30,420 --> 00:03:31,740 Така че нека да обобщим, че като п. 93 00:03:31,740 --> 00:03:34,790 Там се случва да бъде 7, но нека по- обикновено казват има п врати на 94 00:03:34,790 --> 00:03:35,650 екрана тук. 95 00:03:35,650 --> 00:03:40,110 Така че в най-лошия случай, ще трябва да погледнем зад седем врати, или п врати. 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 >> ДЖЕНИФЪР: Да. 100 00:03:47,500 --> 00:03:50,000 >> DAVID J. 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 >> ДЖЕНИФЪР: OK. 106 00:03:59,930 --> 00:04:02,290 >> DAVID J. Malan: - по-рано? 107 00:04:02,290 --> 00:04:03,180 >> ДЖЕНИФЪР: Нека да започнем с първия. 108 00:04:03,180 --> 00:04:03,540 >> DAVID J. 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 >> ДЖЕНИФЪР: 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 >> DAVID J. Malan: OK. 116 00:04:13,670 --> 00:04:15,990 Нека да видим, което мислиш? 117 00:04:15,990 --> 00:04:19,050 >> ДЖЕНИФЪР: Опитайте последният. 118 00:04:19,050 --> 00:04:19,500 Ница. 119 00:04:19,500 --> 00:04:20,880 >> DAVID J. Malan: Много добре направено. 120 00:04:20,880 --> 00:04:21,860 Добре. 121 00:04:21,860 --> 00:04:23,010 >> [APPLAUSE] 122 00:04:23,010 --> 00:04:24,310 >> DAVID J. 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 >> ДЖЕНИФЪР: OK. 128 00:04:34,560 --> 00:04:35,980 >> DAVID J. 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 >> ДЖЕНИФЪР: Върни се в началото. 135 00:04:47,680 --> 00:04:48,320 >> DAVID J. 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 >> ДЖЕНИФЪР: ако не знаят, че подредени. 141 00:04:56,720 --> 00:04:57,005 >> DAVID J. Malan: Правилно. 142 00:04:57,005 --> 00:04:58,490 Е, ако знаех са сортирани - 143 00:04:58,490 --> 00:04:58,700 >> Дженифър: О, знаех, да. 144 00:04:58,700 --> 00:05:00,910 >> DAVID J. Malan: - Но ти не Знам къде 50 беше още? 145 00:05:00,910 --> 00:05:01,785 >> ДЖЕНИФЪР: Просто продължавай. 146 00:05:01,785 --> 00:05:02,130 >> DAVID J. 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 OK, за да мога да работя. 150 00:05:05,270 --> 00:05:05,610 >> ДЖЕНИФЪР: OK. 151 00:05:05,610 --> 00:05:07,210 >> DAVID J. Malan: Сега, ако ти си просто Ще продължа, какво е вашето 152 00:05:07,210 --> 00:05:09,680 алгоритъм възложени подкрепени в. 153 00:05:09,680 --> 00:05:10,740 >> ДЖЕНИФЪР: Линейната -. 154 00:05:10,740 --> 00:05:11,820 >> DAVID J. 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 >> ДЖЕНИФЪР: Започнете от средата. 161 00:05:26,450 --> 00:05:26,690 >> DAVID J. 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 >> ДЖЕНИФЪР: Отиди в това полувреме. 169 00:05:39,400 --> 00:05:41,700 >> DAVID J. Malan: И защо в дясно? 170 00:05:41,700 --> 00:05:43,900 >> ДЖЕНИФЪР: Ако те бяха нещо като най-малката до най-големия, след това 50 трябва да бъде 171 00:05:43,900 --> 00:05:44,720 в тази насока. 172 00:05:44,720 --> 00:05:44,920 >> DAVID J. 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 със седем врати, но наистина само с три. 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 >> ДЖЕНИФЪР: So 16 все още е доста малък, в сравнение с 50, така че може би ще се опитам, 182 00:06:05,870 --> 00:06:06,700 подобни, тази. 183 00:06:06,700 --> 00:06:07,890 >> DAVID J. 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 >> ДЖЕНИФЪР: Мога да изхвърлите това и след това просто - 187 00:06:12,100 --> 00:06:12,360 >> DAVID J. Malan: OK. 188 00:06:12,360 --> 00:06:14,212 Добър, можете да изхвърлите лявата половина има. 189 00:06:14,212 --> 00:06:14,890 >> ДЖЕНИФЪР: - вземете тази. 190 00:06:14,890 --> 00:06:15,530 >> DAVID J. Malan: И отдясно. 191 00:06:15,530 --> 00:06:15,760 >> ДЖЕНИФЪР: Да. 192 00:06:15,760 --> 00:06:17,820 >> DAVID J. 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 >> ДЖЕНИФЪР: това трябва да, като, може би намаляване наполовина на времето, или дори повече, да. 212 00:07:06,460 --> 00:07:07,320 >> DAVID J. Malan: OK, може би дори повече. 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 >> SPEAKER 1: [недоловим] 227 00:07:41,230 --> 00:07:43,970 >> DAVID J. Malan: Така регистър база 2 на 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 >> ДЖЕНИФЪР: Уау. 238 00:08:03,420 --> 00:08:04,410 >> DAVID J. Malan: Добре, тук. 239 00:08:04,410 --> 00:08:06,545 Благодаря ви за нанасянето на стреса тук. 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 екрана, след което ще Jennifer трябваше да изглежда, потенциално, 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 Проблемът на, да речем, на оста х и размера на времето, необходимо за 251 00:08:39,059 --> 00:08:40,440 решаване на у. 252 00:08:40,440 --> 00:08:43,330 Но картината I загатваше рано е тази зелена линия. 253 00:08:43,330 --> 00:08:45,970 Green умишлено, защото тя просто се чувствам по-добре. 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 отново, и отново, нещо в примка мода. 280 00:10:03,350 --> 00:10:06,370 Защото няма да има лукс, като Дженифър направи в началото, за да 281 00:10:06,370 --> 00:10:10,460 Просто трябва един куп ИС и да кажа, Хм, ако този първи брой е четири, 282 00:10:10,460 --> 00:10:11,800 нека да скачат по целия път до края. 283 00:10:11,800 --> 00:10:14,180 О, ако този брой е твърде голям, нека да се движат произволно назад 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 Къде е линейна графика което ние наричаме п? 292 00:10:35,330 --> 00:10:37,580 Е, това е нещо към дъното на тази снимка, нали? 293 00:10:37,580 --> 00:10:40,500 Така че всичко, което направихме, ние сме нещо като приближение на х-ос и 294 00:10:40,500 --> 00:10:44,780 ордината да се опита да се получи усещане за това, което други видове криви изглеждат. 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 Наистина, нарязани на кубчета п изглежда доста зле. 299 00:10:55,410 --> 00:10:58,400 2 до п изглежда доста зле. N квадрат изглежда доста зле. 300 00:10:58,400 --> 00:11:01,630 И ще видим какво някои от тези може да бъде в действителност днес. 301 00:11:01,630 --> 00:11:05,430 И влезте п не се чувства толкова зле, но по-добре от п е регистър на основата 2 п. 302 00:11:05,430 --> 00:11:08,080 Но знаете ли, това щеше да бъде още по-невероятно, ако Дженифър, или ако ние, 303 00:11:08,080 --> 00:11:12,910 че първата седмица, е дошъл с нещо, което е регистър на дневника на п. 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 Така п куб изглежда доста зле в момента. 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 п, наистина, стане по-голям много по-бързо. 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 Дори и в първата версия на Facebook, тъй като броят на приятели, и 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 И вида проблеми места като Facebook и 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 Така че успех на Дженифър в тази секунда алгоритъм, честно казано, тя направи невероятно 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 милиона врати. 340 00:12:51,450 --> 00:12:54,080 Вход на п определено ще да изпълнява много, много 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 тук, но предполагам, че Jennifer Трябваше да го направя сама? 345 00:13:05,160 --> 00:13:10,120 Да предположим, че вратите въпросните представени данни в база данни или 346 00:13:10,120 --> 00:13:14,260 приятели, регистрирани за Facebook, или всички уеб страници в интернет, които 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 Jennifer да направя, че сортирането? 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 като в случай на Дженифър, ако повече от претоварени размера на общото време 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 на, OK. 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 >> [Вмъкване VOICES] 379 00:14:26,530 --> 00:14:28,160 >> DAVID J. Malan: Oop, съжалявам. 380 00:14:28,160 --> 00:14:30,210 Bug. 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 >> SPEAKER 2: Просто ще се получи -. 388 00:14:41,210 --> 00:14:41,900 >> DAVID J. 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 >> [APPLAUSE] 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 House. 405 00:15:14,190 --> 00:15:14,620 >> Брансън: Hi. 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: Hi. 410 00:15:20,230 --> 00:15:21,040 Аз съм Гейб. 411 00:15:21,040 --> 00:15:22,300 Аз съм младши в Cabot. 412 00:15:22,300 --> 00:15:24,826 413 00:15:24,826 --> 00:15:25,980 >> Нийл: Аз съм Нийл. 414 00:15:25,980 --> 00:15:29,090 Аз съм първокурсник в Matthews. 415 00:15:29,090 --> 00:15:29,550 >> JASON: Аз съм Джейсън. 416 00:15:29,550 --> 00:15:32,816 Аз съм първокурсник в Greenough. 417 00:15:32,816 --> 00:15:33,700 >> MIKE: Аз съм Майк. 418 00:15:33,700 --> 00:15:37,360 Аз съм първокурсник в Grays. 419 00:15:37,360 --> 00:15:37,990 >> ДЖЕС: Аз съм Джес. 420 00:15:37,990 --> 00:15:40,313 Аз съм второкурсник в Leverett. 421 00:15:40,313 --> 00:15:41,300 >> DAVID J. 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 Go. 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 >> SPEAKER 1: поне най-голямо. 438 00:16:14,900 --> 00:16:15,000 >> DAVID J. 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 >> SPEAKER 1: [недоловим] 444 00:16:24,083 --> 00:16:26,010 445 00:16:26,010 --> 00:16:26,280 >> DAVID J. Malan: OK. 446 00:16:26,280 --> 00:16:28,920 Така че, ако видите човек по-малък от си номер, след това преминете към 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 Така че е вероятно някои видове примка случва в съзнанието им. 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 Сега аз ще се отмести тук и да кажа, 5: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 >> DAVID J. 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 >> ДЖЕС: [недоловим] 479 00:17:16,150 --> 00:17:17,089 >> DAVID J. Malan: OK, суап. 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 >> SPEAKER 1: Същото нещо. 493 00:17:39,220 --> 00:17:39,940 >> DAVID J. 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 OK, не. 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 Един CPU, ако щете. 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 >> SPEAKER 1: Не. 530 00:18:40,670 --> 00:18:41,050 >> DAVID J. 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 след I стигна до тук, и започна на 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 OK, твърде много, в крайна сметка е ще бъде отговорът. 558 00:19:51,420 --> 00:19:54,960 Но дори и тогава, на определен брой не е толкова интересно. 559 00:19:54,960 --> 00:19:56,670 Нека обобщим това като п. 560 00:19:56,670 --> 00:20:00,520 Така че, ако бях п хората тук, и те бяха, нещо, в произволен ред в 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 това е седем, шест -, така че това е п минус един стъпки за първи път. 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 Само ще кажа, добре, друга п минус 1. 568 00:20:22,300 --> 00:20:25,240 Така че п минус 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 Всъщност е п квадрат, нали? 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 >> MIKE: Mike. 587 00:21:03,360 --> 00:21:03,640 >> DAVID J. Malan: Майк? 588 00:21:03,640 --> 00:21:08,100 OK, Майк, можеш просто да се присъедините към мен през тук само за една секунда? 589 00:21:08,100 --> 00:21:08,880 Всъщност, не. 590 00:21:08,880 --> 00:21:10,150 Съжаляваме Mike, назад нека. 591 00:21:10,150 --> 00:21:10,910 Какъв ти е името? 592 00:21:10,910 --> 00:21:11,180 >> НИЙЛ: Нийл. 593 00:21:11,180 --> 00:21:11,640 >> DAVID J. Malan: Нийл. 594 00:21:11,640 --> 00:21:13,750 OK, Нийл, ти идваш с мен, ако нямате нищо против. 595 00:21:13,750 --> 00:21:17,150 Така че аз ще да предложи, само за простота, че Neil сега е в неговата 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 Но помислете сега, колко по-далеч Neil се наложи да отидете? 602 00:21:31,630 --> 00:21:32,690 Това е грубо п. 603 00:21:32,690 --> 00:21:33,570 Знаеш ли, това всъщност не е п. 604 00:21:33,570 --> 00:21:36,040 Това е като, п минус 1, но аз съм се раздразнен следене на малката 605 00:21:36,040 --> 00:21:37,550 номер, така че нека просто го наречем п. 606 00:21:37,550 --> 00:21:42,860 >> Така че, ако Neil премества една стъпка максимално всеки време, и да се движат Neil една стъпка, 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 че много стъпки, за да получите Neil всички Между другото там, където му е мястото. 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 общо като п квадрат. 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 правилните инстинкти на просто вид на смяна по двойки. 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 начин, защо да не го направя в най-наивен начин е възможно и да видим дали I 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 О, номер две е още по-добре. 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 Six, не. 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 Neil ще излезе. 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 Нямам намерение да си губя времето, като просто бълбука Neil едно място наляво. 646 00:23:21,410 --> 00:23:25,350 Защо да не съм сложил Neil където той принадлежи, което, разбира се, къде? 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: Grace. 651 00:23:29,310 --> 00:23:29,710 >> DAVID J. Malan: Grace. 652 00:23:29,710 --> 00:23:29,920 OK. 653 00:23:29,920 --> 00:23:32,490 Така Grace, за съжаление, ти си вид на пътя. 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 Спомнете си, че с Роб, ние говорихме за обявяване възрасти, и имахме само един 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 Ние имаме само краен брой цели числа. 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 И може би сме направили, защото това, което, ако Grace са на мястото си? 666 00:23:58,510 --> 00:24:01,730 Но ние знаем, че не е, защото В противен случай тя би била 667 00:24:01,730 --> 00:24:03,980 права напред, вместо да Neil по това време, нали? 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 За следващата минута, аз отивам да се игнорира Neil всички заедно, така че да не 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 Two. 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 Six, че доста малко на брой. 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 Броя на Грейс е по-добре, така стъпка по напред. 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 Seven. 692 00:24:42,290 --> 00:24:42,720 Five. 693 00:24:42,720 --> 00:24:43,550 И сега това, което ти беше името? 694 00:24:43,550 --> 00:24:44,000 >> JASON: Jason. 695 00:24:44,000 --> 00:24:44,420 >> DAVID J. Malan: Jason. 696 00:24:44,420 --> 00:24:47,050 Така че Джейсън вече е най-малката елемент съм избран. 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 >> DAVID J. 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 Five ще бъде най-малкият. 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 >> SPEAKER 3: това е п стъпки [недоловим]. 722 00:25:25,900 --> 00:25:27,600 >> DAVID J. Malan: Това е н стъпките на най-много. 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 Поради това, че най-лошия случай, това, което Neil ако бяха тук? 729 00:25:41,530 --> 00:25:45,700 Така че просто намери най-малкият елемент ми отнема N стъпки, или п минус 1. 730 00:25:45,700 --> 00:25:46,100 Но, OK. 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 Това е п минус 1, или п минус 2 наистина, от броя на стъпките. 735 00:25:54,830 --> 00:25:55,440 Така OK. 736 00:25:55,440 --> 00:25:57,390 Така че аз съм п минус 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 Така п минус 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, този път е п минус 1, плюс п минус 745 00:26:13,450 --> 00:26:16,500 2, както и п минус 3, плюс п минус четири, точка, точка, точка. 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, п пъти, разделена на две. 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 но доколкото си спомням, това е нещо като, ако Правя п минус едно неща, тогава п минус 753 00:26:47,830 --> 00:26:53,570 2, след N минус 3, това е грубо нещо като това над 2, и ако 754 00:26:53,570 --> 00:26:55,510 умножете това, че е всъщност н квадрат. 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 В компютърните науки, когато проблемите започват да се интересно е, когато п 758 00:27:03,720 --> 00:27:04,700 стане наистина голям. 759 00:27:04,700 --> 00:27:08,110 И когато п стане наистина голям, което на тези стойности ще доминират всички 760 00:27:08,110 --> 00:27:09,750 на другите? 761 00:27:09,750 --> 00:27:10,990 Това е вид на п квадрат, нали? 762 00:27:10,990 --> 00:27:13,340 Да, се дели на две е доста добър. 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 Insertion вид е, концептуално, малко по-различно. 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 Така че аз съм просто ще започнем с Грейс, и виждам, че тя е номер четири. 784 00:28:10,160 --> 00:28:11,720 Къде номер четири принадлежат? 785 00:28:11,720 --> 00:28:14,940 Аз не са започнали сортиране нищо, така Grace получава да останем там. 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 >> Брансън: Брансън. 790 00:28:23,700 --> 00:28:24,150 >> DAVID J. 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 Така че отново, ние сме вид вземане Grace направи много работа тук. 796 00:28:35,670 --> 00:28:37,290 Къде ще ви постави? 797 00:28:37,290 --> 00:28:40,120 Така че ние ще ви се плъзга към наляво, и го поставете Branson там. 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 Тя все още е два елемента Оттук 5 тук. 801 00:28:45,130 --> 00:28:47,910 Общ размер на масива е 7, така че аз съм не изневерява, нали? 802 00:28:47,910 --> 00:28:51,950 >> Така че сега ние имаме, с Gabe тук, на номер шест, къде ти е мястото? 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 Така че очевидно тук, така че как ще стигнем Neil там? 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 И накрая, Branson? 820 00:29:24,960 --> 00:29:25,460 Друга стъпка. 821 00:29:25,460 --> 00:29:27,190 И сега можем да сложим Neil на място. 822 00:29:27,190 --> 00:29:28,440 >> Така че сега, да продължи тази логика. 823 00:29:28,440 --> 00:29:32,420 Макар и да не се изместват Neil над, и отново, и отново, за да го сложи 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 >> Така че тъжно нещо сега е всички тези алгоритми са п квадрат. 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 >> [APPLAUSE] 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 >> Брансън: [недоловим] запазите номера. 845 00:30:19,190 --> 00:30:21,990 >> DAVID J. 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 Java е малко досадно да се работи На някои браузъри тези дни. 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 действителност не може да съвпадне с началото или да спре Ако не държите бутона Command или Alt 862 00:31:03,720 --> 00:31:06,560 плюс и увеличавате, които любопитно ви показва повече бутони. 863 00:31:06,560 --> 00:31:09,090 Така че просто FYI ако играете с това у дома. 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 Shorter бара, по-малки номера. 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 Тя е все още п квадрат, или да се даде, но това беше, в реалния свят, малко 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 Whoop, пускане и спиране. 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 Но това също на теория, все още п квадрат. 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 O. И това е начин, че един компютър учен или математик дори използва 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. като има предвид големия 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 И има п общо врати или п общия брой. 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 врати, п? 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 Толкова много, като Jennifer срещат, на номер 50 е целия път, така че в 953 00:35:27,120 --> 00:35:30,760 най-лошия случай линейно търсене е голяма O М, ще кажем. 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 Така че ние ще опишем, че като един. 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 >> [Вмъкване VOICES] 962 00:35:49,250 --> 00:35:51,310 >> DAVID J. 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 Binary търсене в най-добрия случай? 978 00:36:33,190 --> 00:36:36,290 Това е също един, ако тя просто се случва да бъде в самия центъра на масива, или 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 О, моят почерк изглежда още по-зле когато се очаква, че голяма. 986 00:36:51,710 --> 00:36:52,510 Добре. 987 00:36:52,510 --> 00:36:53,570 Така че това е п квадрат. 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 >> SPEAKER 1: п. 991 00:37:01,760 --> 00:37:03,286 >> DAVID J. Malan: N, чух. 992 00:37:03,286 --> 00:37:04,200 >> SPEAKER 1: 2. 993 00:37:04,200 --> 00:37:05,010 >> DAVID J. 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, п, 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 Но ако тя отнема само една стъпка, как в светът може ли да претендирам, че списъкът 1000 00:37:19,670 --> 00:37:22,900 се сортира, защото ако аз съм само право да вземе една стъпка, колко елементи 1001 00:37:22,900 --> 00:37:25,230 бих могъл да се провери действително да бъде сигурен? 1002 00:37:25,230 --> 00:37:28,270 Е, само един, което означава, че има п минус 1 елементи, които биха могли да бъдат изложени на 1003 00:37:28,270 --> 00:37:31,310 ред, а аз съм просто ще на вярата след погледнете в един елемент, че 1004 00:37:31,310 --> 00:37:31,850 нещо, което се сортира. 1005 00:37:31,850 --> 00:37:33,930 Така че едно е да не коригира тук. 1006 00:37:33,930 --> 00:37:35,710 Така минимално, колко трябва ли да гледам? 1007 00:37:35,710 --> 00:37:36,680 >> [Вмъкване VOICES] 1008 00:37:36,680 --> 00:37:40,160 >> DAVID J. Malan: N минус 1, или наистина, п, защото аз трябва да разгледаме всеки 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 приемем, че, като п получава голяма, те са безинтересно или иначе. 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 >> SPEAKER 4: N квадрат. 1020 00:38:05,680 --> 00:38:06,710 >> DAVID J. Malan: N квадрат, което чувам. 1021 00:38:06,710 --> 00:38:09,790 Но защо п квадрат, интуитивно? 1022 00:38:09,790 --> 00:38:11,170 >> SPEAKER 4: Защото ние просто го направих. 1023 00:38:11,170 --> 00:38:12,260 >> DAVID J. 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 минус 1, а след това N минус 2. 1031 00:38:27,480 --> 00:38:30,700 Но ако нещо добавите онези, всичко, или да го вземат на вярата, че сте добавили 1032 00:38:30,700 --> 00:38:34,810 тях в аванс, получаваме около п квадрат минус някои по-малки номера. 1033 00:38:34,810 --> 00:38:36,730 Така че аз ще се обадя на този п квадрат. 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 >> SPEAKER 5: [недоловим] 1037 00:38:41,840 --> 00:38:44,350 >> DAVID J. Malan: Това е за съжаление още п квадрат, нали? 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 ох, това изглежда правилно. 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 Тя също е М квадрат. 1061 00:39:49,100 --> 00:39:53,020 А какво ще кажеш с най-добрия случай? 1062 00:39:53,020 --> 00:39:56,282 Ще оставим това за Катерачът. 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 М, така да се каже. 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 променени нещата малко по малко, смяна в този ред, може би 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 Ние п квадрат в ляво, п квадрат в средата, и п 1104 00:41:57,970 --> 00:41:59,400 влезте п отдясно. 1105 00:41:59,400 --> 00:42:00,590 Така че там е истинското ти Катерачът. 1106 00:42:00,590 --> 00:42:02,040 Ще се видим в понеделник. 1107 00:42:02,040 --> 00:42:05,163 >> [APPLAUSE]