1 00:00:00,000 --> 00:00:00,990 2 00:00:00,990 --> 00:00:02,970 >> [За възпроизвеждане на музика] 3 00:00:02,970 --> 00:00:10,400 4 00:00:10,400 --> 00:00:12,550 >> DAVID J. Malan: Това е CS50. 5 00:00:12,550 --> 00:00:14,612 И това е началото на три седмица. 6 00:00:14,612 --> 00:00:16,820 Така че ние имаме много вълнуващо неща, които да обхващат днес. 7 00:00:16,820 --> 00:00:20,160 Много възможности за доброволци на сцената. 8 00:00:20,160 --> 00:00:22,780 И накрая, днес е не става въпрос за код на всички. 9 00:00:22,780 --> 00:00:24,820 Но това е за идеи, и това е за алгоритми, 10 00:00:24,820 --> 00:00:28,420 и действително връщането обратно някои от поуките от нула седмица, 11 00:00:28,420 --> 00:00:31,910 където изземване, ние въведено това чудовище. 12 00:00:31,910 --> 00:00:33,880 И заеми вдъхновение от това, за да започне 13 00:00:33,880 --> 00:00:36,879 за решаване на все по-сложни проблеми алгоритмично. 14 00:00:36,879 --> 00:00:38,420 Но първо, няколко съобщения. 15 00:00:38,420 --> 00:00:42,020 Така един, ако искате да се присъедините Персонал и съученици CS50 е на обяд 16 00:00:42,020 --> 00:00:44,670 този петък, тук и в Cambridge, и в Ню Haven, 17 00:00:44,670 --> 00:00:48,060 моля, посетете на курса сайт, където може да се намери на URL. 18 00:00:48,060 --> 00:00:50,390 Лекция тази сряда ще Не е тук Сандърс. 19 00:00:50,390 --> 00:00:53,610 Тя ще бъде само онлайн, така че мелодия на интернет страницата на CS50, 20 00:00:53,610 --> 00:00:55,850 дали тук, в Кеймбридж или Ню Хейвън, както добре. 21 00:00:55,850 --> 00:00:58,110 >> И тогава проблем зададете два вече е в ръцете ви. 22 00:00:58,110 --> 00:01:03,067 Ако не сте се хвърли в още, позволете ми да предложи на остро внушението 23 00:01:03,067 --> 00:01:05,150 че особено сега, когато проблема определя предварително, 24 00:01:05,150 --> 00:01:08,669 Наистина ли искате да започне още сега, ако не бъркам малко през уикенда или преди 25 00:01:08,669 --> 00:01:10,710 когато за първи път излизат на Петък, защото ще 26 00:01:10,710 --> 00:01:14,380 откриете, че те не са непременно получаване на по-дълъг или по-голямо предизвикателство за 27 00:01:14,380 --> 00:01:14,950 себе си. 28 00:01:14,950 --> 00:01:17,575 Мисля, че ще се намери, че в Като цяло, те са склонни да вземат приблизително 29 00:01:17,575 --> 00:01:18,892 около един и същ период от време. 30 00:01:18,892 --> 00:01:20,850 Но това със сигурност зависи на студента, и то 31 00:01:20,850 --> 00:01:22,880 зависи от нагласата с която го подход. 32 00:01:22,880 --> 00:01:24,910 Но неизменно, ти започваш да тичам нагоре срещу някои стена, 33 00:01:24,910 --> 00:01:26,350 и ти започваш да се удари някои бъгове, и ти си просто 34 00:01:26,350 --> 00:01:27,950 няма да бъде в състояние да го преодолееш в някакъв момент. 35 00:01:27,950 --> 00:01:31,380 И това е изключително ценно, за да може да се излезе, да се върне на следващия ден, 36 00:01:31,380 --> 00:01:35,286 отидете в работно време, пост на CS50 Обсъдете или други подобни, за да се получи в действителност разблокиране. 37 00:01:35,286 --> 00:01:36,160 Така че имайте това предвид. 38 00:01:36,160 --> 00:01:40,830 Като се започне най-ранната е възможно е най-доброто нещо което можете да направите. 39 00:01:40,830 --> 00:01:44,160 Така че тук е мястото, където ние започнахме класа, над нулата в седмицата. 40 00:01:44,160 --> 00:01:47,441 И можем да получим доброволец тук, за да ми помогне да намерите микрофони? 41 00:01:47,441 --> 00:01:47,940 ДОБРЕ. 42 00:01:47,940 --> 00:01:48,900 Отстояване вече. 43 00:01:48,900 --> 00:01:50,080 Хайде нагоре. 44 00:01:50,080 --> 00:01:53,707 Предполагам, че това е начина, по който ще се работи. 45 00:01:53,707 --> 00:01:54,415 Как се казваш? 46 00:01:54,415 --> 00:01:55,570 ALAN Естрада: Alan Estrada. 47 00:01:55,570 --> 00:01:56,778 DAVID J. Malan: Alan Estrada. 48 00:01:56,778 --> 00:01:57,910 Хайде нагоре. 49 00:01:57,910 --> 00:01:58,619 Приятно ми е. 50 00:01:58,619 --> 00:01:59,910 ALAN Естрада: Приятно ми е да се запознаем. 51 00:01:59,910 --> 00:02:02,772 DAVID J. Malan: И ти беше тук с нас в нула седмица, разбира се. 52 00:02:02,772 --> 00:02:03,028 ALAN Естрада: Бях. 53 00:02:03,028 --> 00:02:03,160 Аз бях. 54 00:02:03,160 --> 00:02:05,868 >> DAVID J. Malan: Така че може да отидеш напред и да се намери за нас Mike Smith, 55 00:02:05,868 --> 00:02:08,639 колкото може по-бързо? 56 00:02:08,639 --> 00:02:10,639 Колкото може по-бързо. 57 00:02:10,639 --> 00:02:13,756 Буквално разкъсване на проблема на половина, колкото е необходимо, за да. 58 00:02:13,756 --> 00:02:15,130 >> ALAN Естрада: Um. 59 00:02:15,130 --> 00:02:17,380 DAVID J. Malan: Буквално разкъсване на проблема на половина. 60 00:02:17,380 --> 00:02:20,210 61 00:02:20,210 --> 00:02:22,083 >> ALAN Естрада: Oh. 62 00:02:22,083 --> 00:02:22,583 Мм. 63 00:02:22,583 --> 00:02:23,300 Много добре. 64 00:02:23,300 --> 00:02:23,700 >> DAVID J. Malan: OK. 65 00:02:23,700 --> 00:02:24,200 Good. 66 00:02:24,200 --> 00:02:24,701 Благодаря. 67 00:02:24,701 --> 00:02:25,700 ALAN Естрада: Много добре. 68 00:02:25,700 --> 00:02:26,210 ДОБРЕ. 69 00:02:26,210 --> 00:02:27,610 >> DAVID J. Malan: И така, сега, сте го сведено 70 00:02:27,610 --> 00:02:29,320 на половината от размера на проблема. 71 00:02:29,320 --> 00:02:31,267 Сега, ние сме до една четвърт. 72 00:02:31,267 --> 00:02:33,475 Възможно ли е да се обръща внимание на чия страна сме поддържаш? 73 00:02:33,475 --> 00:02:34,405 >> [Сайта] 74 00:02:34,405 --> 00:02:35,970 >> ALAN Естрада: Да, аз think-- 75 00:02:35,970 --> 00:02:37,594 >> DAVID J. Malan: Какво точка ние сме в? 76 00:02:37,594 --> 00:02:39,150 ALAN Естрада: ауспуси, така. 77 00:02:39,150 --> 00:02:39,941 >> DAVID J. Malan: OK. 78 00:02:39,941 --> 00:02:42,810 Но Майк Смит се случва да бъде след ауспуси. 79 00:02:42,810 --> 00:02:44,130 So-- 80 00:02:44,130 --> 00:02:48,180 >> [Сайта] 81 00:02:48,180 --> 00:02:48,742 >> Всичко е наред. 82 00:02:48,742 --> 00:02:50,200 ALAN Естрада: Когато търсим? 83 00:02:50,200 --> 00:02:52,049 DAVID J. Malan: Майк Смит. 84 00:02:52,049 --> 00:02:53,090 ALAN Естрада: Майк Смит. 85 00:02:53,090 --> 00:02:54,760 DAVID J. Malan: Сега, ние сме в хирургично. 86 00:02:54,760 --> 00:02:57,840 Сега, лекарите. 87 00:02:57,840 --> 00:02:58,340 Сега-- 88 00:02:58,340 --> 00:02:59,856 >> ALAN Естрада: Let's- да вървим с реални. 89 00:02:59,856 --> 00:03:00,370 Real. 90 00:03:00,370 --> 00:03:00,970 >> DAVID J. Malan: Real. 91 00:03:00,970 --> 00:03:01,470 ДОБРЕ. 92 00:03:01,470 --> 00:03:03,700 Ако имате нужда от Реал. 93 00:03:03,700 --> 00:03:05,250 Сега, по какъв начин е Майк Смит? 94 00:03:05,250 --> 00:03:06,250 >> ALAN Естрада: Този начин. 95 00:03:06,250 --> 00:03:07,333 >> DAVID J. Malan: Накъде? 96 00:03:07,333 --> 00:03:08,240 ALAN Естрада: Изчакайте. 97 00:03:08,240 --> 00:03:08,790 M is-- нали? 98 00:03:08,790 --> 00:03:09,110 Започнахме with-- 99 00:03:09,110 --> 00:03:10,090 >> DAVID J. Malan: Да. 100 00:03:10,090 --> 00:03:10,650 Те са напуснали. 101 00:03:10,650 --> 00:03:11,430 Прав си. 102 00:03:11,430 --> 00:03:11,710 >> ALAN Естрада: Да. 103 00:03:11,710 --> 00:03:13,126 >> DAVID J. Malan: Така Майк тук. 104 00:03:13,126 --> 00:03:13,990 ALAN Естрада: Какво? 105 00:03:13,990 --> 00:03:14,665 >> [Сайта] 106 00:03:14,665 --> 00:03:17,365 107 00:03:17,365 --> 00:03:18,330 >> Лош пример, момчета. 108 00:03:18,330 --> 00:03:18,830 Извинете. 109 00:03:18,830 --> 00:03:21,610 DAVID J. Malan: Това ще научи можете да скочи от стола си. 110 00:03:21,610 --> 00:03:22,318 >> ALAN Естрада: Oh. 111 00:03:22,318 --> 00:03:22,890 Oh. 112 00:03:22,890 --> 00:03:23,390 Хванах те. 113 00:03:23,390 --> 00:03:24,670 Хванах те. 114 00:03:24,670 --> 00:03:25,170 Oh. 115 00:03:25,170 --> 00:03:25,669 Oh. 116 00:03:25,669 --> 00:03:26,812 Това is-- OK, имам теб. 117 00:03:26,812 --> 00:03:27,520 Smith точно тук? 118 00:03:27,520 --> 00:03:28,894 >> DAVID J. Malan: Smith, благодаря ви. 119 00:03:28,894 --> 00:03:30,535 Така че аз ще продължавам да гледам Смит? 120 00:03:30,535 --> 00:03:30,790 >> ALAN Естрада: О, да. 121 00:03:30,790 --> 00:03:31,340 Не не не. 122 00:03:31,340 --> 00:03:31,600 О, не. 123 00:03:31,600 --> 00:03:31,940 Това е мое. 124 00:03:31,940 --> 00:03:32,580 >> DAVID J. Malan: О, имаш Smith. 125 00:03:32,580 --> 00:03:33,415 ДОБРЕ. 126 00:03:33,415 --> 00:03:34,040 >> ALAN Естрада: Да, имам Smith точно тук. 127 00:03:34,040 --> 00:03:34,700 Съжаляваме, момчета. 128 00:03:34,700 --> 00:03:35,860 Мислех, че сме Michael-- търсеха Майкъл. 129 00:03:35,860 --> 00:03:36,550 Извинете. 130 00:03:36,550 --> 00:03:37,550 >> DAVID J. Malan: Всичко е наред. 131 00:03:37,550 --> 00:03:39,950 Добре, сега сме в Paccini и синове. 132 00:03:39,950 --> 00:03:41,242 >> ALAN Естрада: Paccini и синовете. 133 00:03:41,242 --> 00:03:43,158 DAVID J. Malan: Само ти и аз сме в по този въпрос. 134 00:03:43,158 --> 00:03:44,050 ДОБРЕ. 135 00:03:44,050 --> 00:03:45,130 Намерете ни Майк Смит. 136 00:03:45,130 --> 00:03:45,830 Smith. 137 00:03:45,830 --> 00:03:46,310 >> ALAN Естрада: Smith. 138 00:03:46,310 --> 00:03:46,750 >> DAVID J. Malan: Smith. 139 00:03:46,750 --> 00:03:47,728 Ние сме в R за боклук. 140 00:03:47,728 --> 00:03:48,644 ALAN Естрада: За боклука. 141 00:03:48,644 --> 00:03:50,096 Oh. 142 00:03:50,096 --> 00:03:52,480 Това ще отнеме известно време. 143 00:03:52,480 --> 00:03:54,340 >> [Сайта] 144 00:03:54,340 --> 00:03:55,804 145 00:03:55,804 --> 00:03:56,720 DAVID J. Malan: обувки. 146 00:03:56,720 --> 00:03:58,080 Ние сме в обувките. 147 00:03:58,080 --> 00:04:00,210 >> ALAN Естрада: Сега ние сме gonna-- 148 00:04:00,210 --> 00:04:01,105 >> DAVID J. Malan: Nice. 149 00:04:01,105 --> 00:04:01,980 ALAN Естрада: Which-- 150 00:04:01,980 --> 00:04:03,620 [Сайта] 151 00:04:03,620 --> 00:04:05,440 О, това е страхотно. 152 00:04:05,440 --> 00:04:06,910 [Сайта] 153 00:04:06,910 --> 00:04:08,380 154 00:04:08,380 --> 00:04:09,390 >> DAVID J. Malan: Всичко е наред. 155 00:04:09,390 --> 00:04:11,365 >> ALAN Естрада: О, това е добре. 156 00:04:11,365 --> 00:04:14,425 Не мисля, че аз отивам да Трябва PSAT приятели след това. 157 00:04:14,425 --> 00:04:15,300 DAVID J. Malan: Добро. 158 00:04:15,300 --> 00:04:16,078 Спортинг. 159 00:04:16,078 --> 00:04:17,036 ALAN Естрада: Спортинг. 160 00:04:17,036 --> 00:04:18,668 Хм, L, M, N, O, P. 161 00:04:18,668 --> 00:04:19,459 DAVID J. Malan: OK. 162 00:04:19,459 --> 00:04:21,600 Така че нека да разкъсат тази наполовина. 163 00:04:21,600 --> 00:04:22,270 ОК е. 164 00:04:22,270 --> 00:04:25,606 Това завършва зле, така или иначе, защото Майк Смит не ще бъде в жълтите страници. 165 00:04:25,606 --> 00:04:26,430 >> ALAN Естрада: Aw. 166 00:04:26,430 --> 00:04:27,140 >> DAVID J. Malan: Не, това е ОК. 167 00:04:27,140 --> 00:04:28,930 Но нека да се преструвам, като той е на тази страница. 168 00:04:28,930 --> 00:04:33,260 Така че сега, че сте сведено проблема надолу до една страница, и ние открихме, Майк Смит. 169 00:04:33,260 --> 00:04:35,180 >> [Аплодисменти] 170 00:04:35,180 --> 00:04:35,757 171 00:04:35,757 --> 00:04:36,340 Добре благодаря. 172 00:04:36,340 --> 00:04:40,700 173 00:04:40,700 --> 00:04:41,200 ДОБРЕ. 174 00:04:41,200 --> 00:04:43,646 Това беше изключително. 175 00:04:43,646 --> 00:04:45,954 Но все пак това е по-бързо отколкото линейно търсене, 176 00:04:45,954 --> 00:04:47,870 където можем да започне в началото на книгата, 177 00:04:47,870 --> 00:04:51,210 и ние преминаваме от ляво на дясно, в крайна сметка търси Майк Смит. 178 00:04:51,210 --> 00:04:53,540 И така, ако телефонния указател имаше може би хиляда страници, 179 00:04:53,540 --> 00:04:56,300 може би това щеше да отнеме ни 10 или така сълзи страница. 180 00:04:56,300 --> 00:04:59,380 >> Но може би сте ливъридж докосна предположение 181 00:04:59,380 --> 00:05:03,602 по време на всичко това, което ще рече че в телефонния указател предварително е какво? 182 00:05:03,602 --> 00:05:04,310 АУДИТОРИЯ: Сортирани. 183 00:05:04,310 --> 00:05:05,000 DAVID J. Malan: Тя е сортирани. 184 00:05:05,000 --> 00:05:05,160 Нали така? 185 00:05:05,160 --> 00:05:07,909 Това подредени по азбучен ред, така че че всички тези имена и номера 186 00:05:07,909 --> 00:05:11,230 са подредени от A към Z, а по азбучен ред по средата. 187 00:05:11,230 --> 00:05:13,100 Но днес, ние сега питам въпросът, добре, 188 00:05:13,100 --> 00:05:16,170 как направих Verizon или телефона фирма го получите в това състояние? 189 00:05:16,170 --> 00:05:19,560 >> Защото това е едно нещо, за да се наберат това предположение, и следователно, 190 00:05:19,560 --> 00:05:22,570 решаване на проблема с алгоритъм по-ефективно. 191 00:05:22,570 --> 00:05:24,900 Но ние никога не попита нула седмица, добре, 192 00:05:24,900 --> 00:05:27,790 колко много го е направил разходи Verizon или някой друг 193 00:05:27,790 --> 00:05:29,620 за да получите този телефон книга в сортиран ред? 194 00:05:29,620 --> 00:05:29,780 >> Нали така? 195 00:05:29,780 --> 00:05:31,529 Това няма значение, ако погледна Mike Smith 196 00:05:31,529 --> 00:05:35,190 е супер бързо, ако това ви отнема година, за да се справи страниците първоначално. 197 00:05:35,190 --> 00:05:35,690 Нали така? 198 00:05:35,690 --> 00:05:38,620 Вие може и просто да се пресее чрез рандомизирани телефонен указател, 199 00:05:38,620 --> 00:05:40,690 ако то се случва да бъде супер скъпо да го оправи. 200 00:05:40,690 --> 00:05:42,350 Така че, ако можем да имаме друг доброволец. 201 00:05:42,350 --> 00:05:46,350 Нека да потърсим тук как можем might-- хайде up-- как 202 00:05:46,350 --> 00:05:48,100 бихме могли да отидем за сортиране тях. 203 00:05:48,100 --> 00:05:51,990 >> И ако в действителност може да Jordan Присъединете се към нас тук на сцената. 204 00:05:51,990 --> 00:05:55,100 Хайде нагоре само за миг. 205 00:05:55,100 --> 00:05:56,359 Как се казваш? 206 00:05:56,359 --> 00:05:57,150 CAROLINE: Каролин. 207 00:05:57,150 --> 00:05:58,691 DAVID J. Malan: Caroline, хайде нагоре. 208 00:05:58,691 --> 00:06:02,070 И вие ще се присъедини от мен и Йордания тук. 209 00:06:02,070 --> 00:06:03,800 Caroline, благодаря ви. 210 00:06:03,800 --> 00:06:04,300 Всичко е наред. 211 00:06:04,300 --> 00:06:08,330 Така че това, което имаме тук за Каролин е 26 сини книги 212 00:06:08,330 --> 00:06:10,747 че FAS използва за администриране определени изпити. 213 00:06:10,747 --> 00:06:13,330 Те стават трудно да се намери, но това, което ние сме направили предварително 214 00:06:13,330 --> 00:06:15,800 е, че ние сме поставени нечие име на лицевата страна на всяка от тях, 215 00:06:15,800 --> 00:06:18,133 но ние продължаваме да се прости с него След гасенето пълните имена. 216 00:06:18,133 --> 00:06:22,720 Така че ние ще постави на лицето с името L, D, J, B, по целия път от А до Z, 217 00:06:22,720 --> 00:06:24,090 но те са в произволен ред. 218 00:06:24,090 --> 00:06:26,890 И така, ако щете, да говорим си път през проблема, колкото 219 00:06:26,890 --> 00:06:31,620 го, може ли да отида напред и сортирате те за нас, от А до Я. 220 00:06:31,620 --> 00:06:34,070 >> АУДИТОРИЯ: ОК, така че L е като, по средата. 221 00:06:34,070 --> 00:06:35,050 C започва. 222 00:06:35,050 --> 00:06:42,410 B. J преди L. B, Q. 223 00:06:42,410 --> 00:06:45,140 >> DAVID J. Malan: Задръжте че помислих за една секунда. 224 00:06:45,140 --> 00:06:48,910 Защото в противен случай това е само интересна за вас, мен и Йордания. 225 00:06:48,910 --> 00:06:49,724 Ето. 226 00:06:49,724 --> 00:06:50,640 АУДИТОРИЯ: [недоловим]. 227 00:06:50,640 --> 00:06:57,299 R. 228 00:06:57,299 --> 00:06:58,090 DAVID J. Malan: OK. 229 00:06:58,090 --> 00:06:59,310 Какво правиш? 230 00:06:59,310 --> 00:07:01,730 >> CAROLINE: M идва след О. 231 00:07:01,730 --> 00:07:02,564 >> DAVID J. Malan: OK. 232 00:07:02,564 --> 00:07:03,064 >> CAROLINE: O. 233 00:07:03,064 --> 00:07:04,120 DAVID J. Malan: O, Good. 234 00:07:04,120 --> 00:07:04,970 >> CAROLINE: E. 235 00:07:04,970 --> 00:07:06,730 >> DAVID J. Malan: E, F. Да. 236 00:07:06,730 --> 00:07:07,620 >> CAROLINE: T, U, V. 237 00:07:07,620 --> 00:07:10,689 >> DAVID J. Malan: V, T, U, V. Така че Изглежда сте making-- продължавай. 238 00:07:10,689 --> 00:07:12,730 Тя изглежда като вие правите голяма купчина тук, 239 00:07:12,730 --> 00:07:13,910 и вид на голяма купчина там. 240 00:07:13,910 --> 00:07:16,230 Така че през първата половина на азбуката, втората половина на азбуката. 241 00:07:16,230 --> 00:07:16,460 ДОБРЕ. 242 00:07:16,460 --> 00:07:16,960 Good. 243 00:07:16,960 --> 00:07:19,680 Вид на разделянето на проблема на две. 244 00:07:19,680 --> 00:07:21,771 M, N, X. Да. 245 00:07:21,771 --> 00:07:22,270 CAROLINE: K. 246 00:07:22,270 --> 00:07:22,980 DAVID J. Malan: OK. 247 00:07:22,980 --> 00:07:25,070 K. Значи вид избиране ги един след друг, 248 00:07:25,070 --> 00:07:27,620 поставяйки я вляво или вдясно, или Z, става на пода. 249 00:07:27,620 --> 00:07:28,012 ДОБРЕ. 250 00:07:28,012 --> 00:07:29,190 >> CAROLINE: Z става на пода. 251 00:07:29,190 --> 00:07:29,360 >> DAVID J. Malan: OK. 252 00:07:29,360 --> 00:07:30,920 Y се случва на пода. 253 00:07:30,920 --> 00:07:31,735 Сега можем да сложим X. 254 00:07:31,735 --> 00:07:32,409 >> CAROLINE: G. 255 00:07:32,409 --> 00:07:33,700 DAVID J. Malan: G ще напусна. 256 00:07:33,700 --> 00:07:36,017 S ще полето. 257 00:07:36,017 --> 00:07:37,642 Добре, A ще целия път наляво. 258 00:07:37,642 --> 00:07:38,790 >> CAROLINE: A, B, C, D. 259 00:07:38,790 --> 00:07:39,873 >> DAVID J. Malan: Сега добро. 260 00:07:39,873 --> 00:07:43,260 Имаме A, B, C. W, става там долу. 261 00:07:43,260 --> 00:07:45,566 Добре, T. 262 00:07:45,566 --> 00:07:46,611 >> CAROLINE: H, I, J. 263 00:07:46,611 --> 00:07:47,860 DAVID J. Malan: H, I, J. Good. 264 00:07:47,860 --> 00:07:49,160 CAROLINE: В центъра, аз съм gonna-- 265 00:07:49,160 --> 00:07:50,000 DAVID J. Malan: OK. 266 00:07:50,000 --> 00:07:52,375 Така че сега, ние ще натура на сливането на тези различни пилоти. 267 00:07:52,375 --> 00:08:00,730 Така A през C, тогава виждам D, и E, и F, и G, H и и I. Ница. 268 00:08:00,730 --> 00:08:05,540 J, К. И тогава, това е купчина с главата надолу, но това е ОК. 269 00:08:05,540 --> 00:08:06,040 Разбира се. 270 00:08:06,040 --> 00:08:07,240 Ние може да намали някои ъгли. 271 00:08:07,240 --> 00:08:07,950 ДОБРЕ. 272 00:08:07,950 --> 00:08:10,530 И тогава ние трябва W, X, Y, Z. 273 00:08:10,530 --> 00:08:11,250 >> CAROLINE: Да. 274 00:08:11,250 --> 00:08:11,880 >> DAVID J. Malan: отлично. 275 00:08:11,880 --> 00:08:14,122 Така че по-голямо благодаря на Caroline за сортиране тях. 276 00:08:14,122 --> 00:08:15,030 >> [Аплодисменти] 277 00:08:15,030 --> 00:08:17,287 >> Благодаря. 278 00:08:17,287 --> 00:08:18,120 Благодаря ти много. 279 00:08:18,120 --> 00:08:22,910 Така че сега нека да разгледаме за момент как Caroline обикаляше да прави, че, 280 00:08:22,910 --> 00:08:26,040 и какво точно сме успяхме to-- как можем 281 00:08:26,040 --> 00:08:28,409 са били в състояние да реши, че проблем, когато бяхме просто 282 00:08:28,409 --> 00:08:29,950 дал цял куп случайни входове. 283 00:08:29,950 --> 00:08:31,610 >> Е, изглежда, че има беше малко на система там? 284 00:08:31,610 --> 00:08:32,110 Право. 285 00:08:32,110 --> 00:08:34,495 Така че по-ранните писма в азбуката, тя 286 00:08:34,495 --> 00:08:37,120 беше удар от ляво, и късните букви в азбуката, 287 00:08:37,120 --> 00:08:38,270 тя е въвеждането в правото. 288 00:08:38,270 --> 00:08:40,500 И веднага след като тя намери някои близки букви, Ones 289 00:08:40,500 --> 00:08:43,124 които отиват в непосредствена близост един до друг, тя ще постави тези в ред. 290 00:08:43,124 --> 00:08:46,750 И така, ние вид имаше тези малки купища сортирани подаване на данни. 291 00:08:46,750 --> 00:08:50,540 >> И така, това е съвсем като това, което повечето от нас, хората ще направят. 292 00:08:50,540 --> 00:08:53,530 Бихме нещо пресее през него, и ние бихме вид има механизъм. 293 00:08:53,530 --> 00:08:56,930 Но това може да бъде трудно да се напише тя установени в една формула, само по себе си. 294 00:08:56,930 --> 00:08:59,010 Той се почувства малко по-органично от това. 295 00:08:59,010 --> 00:09:02,560 Така че нека да видим дали можем сега да свързания Проблемът с малко входове. 296 00:09:02,560 --> 00:09:05,170 >> Вместо 26, нека направи нещо много по-малко 297 00:09:05,170 --> 00:09:09,890 с просто кажем, седем, зад тези врати, така да се каже. 298 00:09:09,890 --> 00:09:11,300 Има само седем числа? 299 00:09:11,300 --> 00:09:15,240 И ако целта сега в ръка е да се намери стойност, 300 00:09:15,240 --> 00:09:17,850 нека да видим как ефективно ние можем да го направим. 301 00:09:17,850 --> 00:09:22,460 И нека да видим дали можем сега започват да се прилагат някои цифри, 302 00:09:22,460 --> 00:09:26,310 или някои формули, с които да се опише ефективността на нашия телефонен указател 303 00:09:26,310 --> 00:09:31,060 алгоритъм, нашия изпит книга алгоритъм, и по-общо, намиране на информация. 304 00:09:31,060 --> 00:09:34,770 >> Така че за това, нека да вървим напред, и на сензорния екран тук, 305 00:09:34,770 --> 00:09:41,100 поставя на уеб браузър, който има точно тези седем врати. 306 00:09:41,100 --> 00:09:46,670 И ако можем да се получи един друг доброволно да дойде върху тук, 307 00:09:46,670 --> 00:09:48,480 Вложил съм същите тези врати тук. 308 00:09:48,480 --> 00:09:49,170 Quick доброволец. 309 00:09:49,170 --> 00:09:51,130 >> Този one-- демонстрации вървят до по-бързо и по-бързо сега. 310 00:09:51,130 --> 00:09:51,600 Хайде надолу. 311 00:09:51,600 --> 00:09:52,308 Как се казваш? 312 00:09:52,308 --> 00:09:53,040 TREVOR: Тревър. 313 00:09:53,040 --> 00:09:53,998 >> DAVID J. Malan: Тревър? 314 00:09:53,998 --> 00:09:55,770 Добре, Тревър, хайде надолу. 315 00:09:55,770 --> 00:09:59,212 Така че Тревър е доброволно тук, за да направя подобен проблем, но този, който е 316 00:09:59,212 --> 00:10:02,170 тесен обхват, както и че ще ходи за да ни позволи да се опита да се формализира сега 317 00:10:02,170 --> 00:10:03,970 процеса на сортиране тези номера. 318 00:10:03,970 --> 00:10:05,500 >> Така че Тревър, хубаво е да се запознаем. 319 00:10:05,500 --> 00:10:08,720 Така че тук е масив, така че да говори, списък на седем врати. 320 00:10:08,720 --> 00:10:10,327 Давай напред и да ни намерите на броя 50. 321 00:10:10,327 --> 00:10:12,410 И тогава след факта, да ни кажете как сте го намерили. 322 00:10:12,410 --> 00:10:19,124 323 00:10:19,124 --> 00:10:20,040 Трябва be-- оправи. 324 00:10:20,040 --> 00:10:21,945 Да, това е този тук? 325 00:10:21,945 --> 00:10:24,680 Охо. 326 00:10:24,680 --> 00:10:25,560 ДОБРЕ. 327 00:10:25,560 --> 00:10:26,680 Можете кликнали, че един. 328 00:10:26,680 --> 00:10:28,690 Good. 329 00:10:28,690 --> 00:10:29,780 >> И добре. 330 00:10:29,780 --> 00:10:30,970 Сега вие сте кликнали, че един. 331 00:10:30,970 --> 00:10:34,060 И нека да ви дам микрофона, така че да можете да го имат в един момент. 332 00:10:34,060 --> 00:10:37,000 Давай напред и да щракнете на в съседство, който възнамерявате. 333 00:10:37,000 --> 00:10:39,812 Да добре. 334 00:10:39,812 --> 00:10:41,020 TREVOR: Мога ли да махнете отметката врата? 335 00:10:41,020 --> 00:10:42,620 DAVID J. Malan: Не, вие не можете да махнете отметката. 336 00:10:42,620 --> 00:10:43,119 TREVOR: OK. 337 00:10:43,119 --> 00:10:43,974 Този. 338 00:10:43,974 --> 00:10:45,640 DAVID J. Malan: Къде искате да отидете? 339 00:10:45,640 --> 00:10:46,410 Кое? 340 00:10:46,410 --> 00:10:47,230 >> TREVOR: Това един. 341 00:10:47,230 --> 00:10:48,042 >> DAVID J. Malan: No. 342 00:10:48,042 --> 00:10:48,450 >> TREVOR: OK. 343 00:10:48,450 --> 00:10:48,735 Този. 344 00:10:48,735 --> 00:10:49,020 >> DAVID J. Malan: Да. 345 00:10:49,020 --> 00:10:49,700 Това беше добре. 346 00:10:49,700 --> 00:10:50,380 Всичко е наред. 347 00:10:50,380 --> 00:10:53,900 И така, какво е алгоритъм си или Процедура за този начин, Тревър? 348 00:10:53,900 --> 00:10:56,149 >> TREVOR: Току-що премина през врати, докато не намерили 50. 349 00:10:56,149 --> 00:10:56,940 DAVID J. Malan: OK. 350 00:10:56,940 --> 00:10:58,150 Отлично алгоритъм. 351 00:10:58,150 --> 00:10:59,540 Така че това е добре. 352 00:10:59,540 --> 00:11:03,120 Защото в действителност, ако разкрие какво е зад тези две други врати, това, което 353 00:11:03,120 --> 00:11:06,954 ние ще намерим тук е, че имаме само случаен вход. 354 00:11:06,954 --> 00:11:08,870 Така че това е всъщност като добър, колкото бихте могли да получите. 355 00:11:08,870 --> 00:11:12,509 И всъщност, имаш по-добър от изчерпателно търсене в целия масив, 356 00:11:12,509 --> 00:11:15,300 защото това би било наистина Нещастната ако е ударил броя 357 00:11:15,300 --> 00:11:16,604 50 в последната врата. 358 00:11:16,604 --> 00:11:18,520 Но какво, ако ние, вместо ти даде предположение. 359 00:11:18,520 --> 00:11:20,630 Да предположим, че подреди всички тези врати, около 360 00:11:20,630 --> 00:11:23,500 така че да имат номера сортирани този път, 361 00:11:23,500 --> 00:11:29,730 но този път това е всъщност а different-- този път, 362 00:11:29,730 --> 00:11:32,640 това е всъщност подредени за вас. 363 00:11:32,640 --> 00:11:35,380 И сега целта на една ръка разстояние е да се удари в брой 50. 364 00:11:35,380 --> 00:11:36,090 >> TREVOR: OK. 365 00:11:36,090 --> 00:11:37,670 >> DAVID J. Malan: Какво е алгоритъм ви ще бъде? 366 00:11:37,670 --> 00:11:39,628 >> TREVOR: Е, ако това е подредени, това е или ще 367 00:11:39,628 --> 00:11:42,710 да be--, ако най-голямата до най-големия, низходящ, това ще бъде първата, 368 00:11:42,710 --> 00:11:44,751 или, ако това е точно обратното, това ще бъде последният. 369 00:11:44,751 --> 00:11:48,897 Така че аз просто ще се включи тази врата, и след това просто докоснете последната врата. 370 00:11:48,897 --> 00:11:49,980 DAVID J. Malan: отлично. 371 00:11:49,980 --> 00:11:50,270 Всичко е наред. 372 00:11:50,270 --> 00:11:51,150 Така че ние открихме броя 50. 373 00:11:51,150 --> 00:11:52,970 Така че веднага щом се знаеше те са подредени, ние 374 00:11:52,970 --> 00:11:55,040 са били в състояние да се наберат това предположение. 375 00:11:55,040 --> 00:11:57,040 Така че те са твърде много като примера на телефонния указател. 376 00:11:57,040 --> 00:11:59,540 Веднага след като имате, дори и с един малък проблем, подобен на този, 377 00:11:59,540 --> 00:12:02,380 Вашите входове предварително подредени, можем всъщност се намери стойността спорно 378 00:12:02,380 --> 00:12:03,130 по-ефективно. 379 00:12:03,130 --> 00:12:05,800 >> И аз не ви кажа, ако това е сортирани малки до големи, или големи до малки, 380 00:12:05,800 --> 00:12:08,080 и така че е много разумно да започне в единия край или другата 381 00:12:08,080 --> 00:12:09,750 действително да откриете, че целевата стойност. 382 00:12:09,750 --> 00:12:11,400 Така че благодаря на Тревър, както добре. 383 00:12:11,400 --> 00:12:13,260 И аз ще propose-- добре направено. 384 00:12:13,260 --> 00:12:16,960 Имаме малка скоба, всъщност, че е сред любимите ни моменти в CS50, 385 00:12:16,960 --> 00:12:19,700 при което понякога тези демонстрации не съвсем отиде по план. 386 00:12:19,700 --> 00:12:22,050 И наистина точно сега, аз придърпа грешен интерфейс 387 00:12:22,050 --> 00:12:23,508 с които да се използват сензорния екран. 388 00:12:23,508 --> 00:12:24,660 Така че това беше по моя вина там. 389 00:12:24,660 --> 00:12:26,600 >> Така че това ще допринесе за за следващата година, както клип 390 00:12:26,600 --> 00:12:28,570 защо аз бях като кликнете върху собствения си екран. 391 00:12:28,570 --> 00:12:31,390 Но нека хвърлим един бърз поглед какво се случи миналата година 392 00:12:31,390 --> 00:12:34,770 с Jay, който дойде, много по- като Тревър тук, доброволно, 393 00:12:34,770 --> 00:12:39,380 и в този кратък клип, ще видите как същата тази демонстрация не е съвсем 394 00:12:39,380 --> 00:12:41,074 разкрие същите поуките. 395 00:12:41,074 --> 00:12:41,740 [Възпроизвеждане на видео] 396 00:12:41,740 --> 00:12:45,360 -Всички Искам да направя сега е да се намери за мен, и за нас, 397 00:12:45,360 --> 00:12:51,674 Наистина, броят 50 стъпка по стъпка. 398 00:12:51,674 --> 00:12:52,450 >> -В Номер 50? 399 00:12:52,450 --> 00:12:53,190 >> -В Номер 50. 400 00:12:53,190 --> 00:12:55,356 И вие може да разкрие какво е зад всяка от тези врати 401 00:12:55,356 --> 00:12:58,540 просто като го докоснете с пръст. 402 00:12:58,540 --> 00:13:00,910 Мамка му. 403 00:13:00,910 --> 00:13:02,870 >> [Сайта] 404 00:13:02,870 --> 00:13:03,806 >> [END PLAYBACK] 405 00:13:03,806 --> 00:13:05,430 DAVID J. Malan: Така, че мина много добре. 406 00:13:05,430 --> 00:13:06,796 Това бяха несортиран вратите. 407 00:13:06,796 --> 00:13:08,670 И Jay, разбира се, всичко намерено твърде бързо. 408 00:13:08,670 --> 00:13:12,910 Тревър е направил много по-добра работа от гледна точка на поучаеми момент, 409 00:13:12,910 --> 00:13:15,850 така да се каже, тази година в отнема повече време, за да го намерите. 410 00:13:15,850 --> 00:13:17,950 Разбира се, след това дадохме Jay втори шанс, 411 00:13:17,950 --> 00:13:20,320 чрез което сортирани вратите, точно както направихме за Trevor, 412 00:13:20,320 --> 00:13:22,300 и Trevor направих супер добре този път. 413 00:13:22,300 --> 00:13:26,124 Но Джей го направи два пъти по-бързо. 414 00:13:26,124 --> 00:13:26,790 [Възпроизвеждане на видео] 415 00:13:26,790 --> 00:13:29,650 -В Цел сега е да се ни намерите номера 50, 416 00:13:29,650 --> 00:13:33,030 но го направи алгоритмично, и да ни кажете как започваш за това. 417 00:13:33,030 --> 00:13:33,660 >> -ДОБРЕ. 418 00:13:33,660 --> 00:13:35,604 >> -И Ако го намери, да поддържате филма. 419 00:13:35,604 --> 00:13:37,228 Ако не го намерите, можете да го върне. 420 00:13:37,228 --> 00:13:38,044 >> -Man. 421 00:13:38,044 --> 00:13:38,860 >> -О! 422 00:13:38,860 --> 00:13:40,800 >> - [Недоловим] OK. 423 00:13:40,800 --> 00:13:46,236 Така че аз отивам да проверите краищата първо да се определи дали there's-- Oh. 424 00:13:46,236 --> 00:13:48,646 >> [Аплодисменти] 425 00:13:48,646 --> 00:13:53,948 426 00:13:53,948 --> 00:13:55,729 >> [END PLAYBACK] 427 00:13:55,729 --> 00:13:56,520 DAVID J. Malan: OK. 428 00:13:56,520 --> 00:13:59,760 Така сортиране врати ясно води до по-голяма ефективност. 429 00:13:59,760 --> 00:14:01,680 И така, два пъти по-бързо това имах предвид там. 430 00:14:01,680 --> 00:14:03,270 И така Jay извади късмет и двата пъти. 431 00:14:03,270 --> 00:14:06,685 И той също извади късмет с това, че последната години, си поръчах някои блу-рей дискове 432 00:14:06,685 --> 00:14:07,560 действително да дават. 433 00:14:07,560 --> 00:14:09,768 Съжалявам за тази година, ние не са имали една и съща, Тревър. 434 00:14:09,768 --> 00:14:11,540 Но все пак по-добре е за няколко години назад. 435 00:14:11,540 --> 00:14:14,820 И някои от вас може би знаят това колега, Шон, който, когато е бил в CS50, 436 00:14:14,820 --> 00:14:17,780 е обжалван с точната същия проблем, макар и в SD, 437 00:14:17,780 --> 00:14:19,360 както вие скоро ще видите, през деня. 438 00:14:19,360 --> 00:14:22,622 И вие ще откриете, че не само е направил Той отнеме малко повече време, отколкото Jay, 439 00:14:22,622 --> 00:14:25,580 малко по-дълго, отколкото Trevor, че е Всъщност тази чудесна възможност 440 00:14:25,580 --> 00:14:29,820 да се ангажира почти всички в тълпа а ла цената е правилна, насърчаване 441 00:14:29,820 --> 00:14:31,889 него да се намери броя бяхме търси. 442 00:14:31,889 --> 00:14:32,930 Нека. хвърлим един бърз поглед. 443 00:14:32,930 --> 00:14:33,320 >> [Възпроизвеждане на видео] 444 00:14:33,320 --> 00:14:33,820 >> -ДОБРЕ. 445 00:14:33,820 --> 00:14:36,680 Така че вашата задача тук, Шон, е следното. 446 00:14:36,680 --> 00:14:40,860 Имам скрити зад тях врати числото седем. 447 00:14:40,860 --> 00:14:45,120 Но закътано в някои от тези врати както и други отрицателни числа. 448 00:14:45,120 --> 00:14:47,500 И целта ви е да се мисли, на този най-горния ред на номерата 449 00:14:47,500 --> 00:14:50,390 като само масив, или просто поредица от парчета хартия 450 00:14:50,390 --> 00:14:51,510 с числа, които стоят зад тях. 451 00:14:51,510 --> 00:14:55,540 И целта ви е, само с помощта на върха масив тук, ме намери числото седем. 452 00:14:55,540 --> 00:14:58,570 И ние тогава ще критикуваме как да отидете за да го прави. 453 00:14:58,570 --> 00:14:59,070 -Всичко е наред. 454 00:14:59,070 --> 00:15:00,850 -Find Ни числото седем, моля. 455 00:15:00,850 --> 00:15:10,500 456 00:15:10,500 --> 00:15:11,000 Не. 457 00:15:11,000 --> 00:15:15,050 458 00:15:15,050 --> 00:15:18,550 Пет, 19, 13. 459 00:15:18,550 --> 00:15:22,240 460 00:15:22,240 --> 00:15:24,770 >> [Сайта] 461 00:15:24,770 --> 00:15:25,910 >> Това не е подвеждащ въпрос. 462 00:15:25,910 --> 00:15:29,410 463 00:15:29,410 --> 00:15:29,910 One. 464 00:15:29,910 --> 00:15:33,218 465 00:15:33,218 --> 00:15:34,695 >> [Сайта] 466 00:15:34,695 --> 00:15:37,861 В този момент, резултатът ви не е много добро, така че може и да продължи да функционира. 467 00:15:37,861 --> 00:15:40,610 468 00:15:40,610 --> 00:15:41,110 Three. 469 00:15:41,110 --> 00:15:43,890 470 00:15:43,890 --> 00:15:45,378 >> [Сайта] 471 00:15:45,378 --> 00:15:46,370 472 00:15:46,370 --> 00:15:47,774 >> Продължи. 473 00:15:47,774 --> 00:15:50,690 Честно казано, аз не мога да помогна, но се чудя това, което дори и да мисля за, so-- 474 00:15:50,690 --> 00:15:51,959 >> [Сайта] 475 00:15:51,959 --> 00:15:53,229 476 00:15:53,229 --> 00:15:55,020 Само най-горния ред, така че имаш три лявата. 477 00:15:55,020 --> 00:15:56,200 Така ме намерят седем. 478 00:15:56,200 --> 00:15:59,700 479 00:15:59,700 --> 00:16:02,167 >> [Сайта] 480 00:16:02,167 --> 00:16:14,870 481 00:16:14,870 --> 00:16:15,370 17. 482 00:16:15,370 --> 00:16:25,675 483 00:16:25,675 --> 00:16:26,946 Seven. 484 00:16:26,946 --> 00:16:28,780 >> [Аплодисменти] 485 00:16:28,780 --> 00:16:29,426 >> Всичко е наред. 486 00:16:29,426 --> 00:16:30,360 >> [END PLAYBACK] 487 00:16:30,360 --> 00:16:31,840 >> DAVID J. Malan: Така можехме гледате тези през целия ден. 488 00:16:31,840 --> 00:16:34,090 И разбира се, някои от тазгодишните демонстрации може би 489 00:16:34,090 --> 00:16:36,330 сега ще се окажете в следващия Тазгодишният видео, както добре. 490 00:16:36,330 --> 00:16:39,040 Така че сега е нека действително съсредоточи върху алгоритмите 491 00:16:39,040 --> 00:16:42,140 тук, и да видим дали не можем Сега започнете да се формализира 492 00:16:42,140 --> 00:16:46,650 как можем да отида за получаване нашия данни в това състояние, че това е сортирана, 493 00:16:46,650 --> 00:16:50,054 така че в крайна сметка, ние можем действително го търси по-ефективно. 494 00:16:50,054 --> 00:16:52,470 И въпреки, че отиваме да се използва сравнително малки групи от данни, 495 00:16:52,470 --> 00:16:54,511 Както вече на осем числа имаме тук на дъската, 496 00:16:54,511 --> 00:16:58,230 в крайна сметка успя да достигне същите тези идеи 1000 входа, един милион входове, 497 00:16:58,230 --> 00:17:02,100 4 милиарда входове, тъй като алгоритмите ще бъде коренно същото. 498 00:17:02,100 --> 00:17:05,359 >> И така, това е нашата последна възможност за доброволци и днес, 499 00:17:05,359 --> 00:17:09,790 но може би най-въпрос за един, за които ние се нуждаем от осем доброволци 500 00:17:09,790 --> 00:17:12,960 да се качи и да ходи с нас чрез Веднага след процес на сортиране какво ще 501 00:17:12,960 --> 00:17:15,212 да бъде на тях музика стои тук. 502 00:17:15,212 --> 00:17:16,170 Позволете ми да започна отново тук. 503 00:17:16,170 --> 00:17:19,692 >> Така че един в turquoise-- зелено е това? 504 00:17:19,692 --> 00:17:21,130 Възможно ли е да извърши? 505 00:17:21,130 --> 00:17:21,630 Two. 506 00:17:21,630 --> 00:17:23,069 Хайде надолу. 507 00:17:23,069 --> 00:17:23,569 ДОБРЕ. 508 00:17:23,569 --> 00:17:24,420 Three. 509 00:17:24,420 --> 00:17:25,400 Four. 510 00:17:25,400 --> 00:17:27,247 Нека me-- OK, пет. 511 00:17:27,247 --> 00:17:28,830 Вие сте били номинирани от приятеля си. 512 00:17:28,830 --> 00:17:31,340 Шест, седем, а осем. 513 00:17:31,340 --> 00:17:32,130 Хайде нагоре. 514 00:17:32,130 --> 00:17:32,630 Всичко е наред. 515 00:17:32,630 --> 00:17:33,190 Благодаря ти много. 516 00:17:33,190 --> 00:17:33,689 Хайде нагоре. 517 00:17:33,689 --> 00:17:34,790 Хайде нагоре. 518 00:17:34,790 --> 00:17:35,330 >> Всичко е наред. 519 00:17:35,330 --> 00:17:38,890 Така че това, което имаме и това here-- е сред по-неудобни тези, 520 00:17:38,890 --> 00:17:42,390 тъй като това ще изисква от вас хумор ми за по малко от време. 521 00:17:42,390 --> 00:17:43,442 Ти ще бъдеш номер едно. 522 00:17:43,442 --> 00:17:44,150 Как се казваш? 523 00:17:44,150 --> 00:17:44,610 >> Анан: Анан. 524 00:17:44,610 --> 00:17:45,526 >> DAVID J. Malan: Анан. 525 00:17:45,526 --> 00:17:46,092 Дейвид. 526 00:17:46,092 --> 00:17:46,800 Как се казваш? 527 00:17:46,800 --> 00:17:47,140 >> JOSEPH: Joseph. 528 00:17:47,140 --> 00:17:49,190 >> DAVID J. Malan: Joseph, Ако сте номер две. 529 00:17:49,190 --> 00:17:52,260 >> СЕРЕНА: Серина, номер три. 530 00:17:52,260 --> 00:17:53,722 Стефан, номер четири. 531 00:17:53,722 --> 00:17:54,430 Синтия: Синтия. 532 00:17:54,430 --> 00:17:57,548 DAVID J. Malan: Синтия, номер пет. 533 00:17:57,548 --> 00:17:58,452 [Недоловим] 534 00:17:58,452 --> 00:17:59,618 DAVID J. Malan: [недоловим]. 535 00:17:59,618 --> 00:18:00,391 Дейвид, номер шест. 536 00:18:00,391 --> 00:18:00,890 MATT: Мат. 537 00:18:00,890 --> 00:18:02,160 DAVID J. Malan: брой на Мат седем. 538 00:18:02,160 --> 00:18:02,850 И? 539 00:18:02,850 --> 00:18:03,210 >> Waverly: Waverly. 540 00:18:03,210 --> 00:18:04,470 >> DAVID J. Malan: Waverly, номер осем. 541 00:18:04,470 --> 00:18:04,970 Всичко е наред. 542 00:18:04,970 --> 00:18:06,510 Ако could-- Опа. 543 00:18:06,510 --> 00:18:08,820 Ако всичко, което, както си първо влизане, има 544 00:18:08,820 --> 00:18:10,820 Осем са музикални щандове тук с лице към публиката. 545 00:18:10,820 --> 00:18:14,200 Ако можеше да сложиш номера на тези музика стои по такъв начин, 546 00:18:14,200 --> 00:18:16,560 че те е изравнена с същите номера на дъската. 547 00:18:16,560 --> 00:18:19,560 Така че да се правите, че да изглежда като от поставите номера на тези музика 548 00:18:19,560 --> 00:18:21,960 стои тук. 549 00:18:21,960 --> 00:18:25,980 Отлично досега. 550 00:18:25,980 --> 00:18:26,600 >> Отлично. 551 00:18:26,600 --> 00:18:26,890 ДОБРЕ. 552 00:18:26,890 --> 00:18:29,556 Така че сега, ние ще зададем въпрос по няколко различни начина. 553 00:18:29,556 --> 00:18:31,610 Как можем да отидем за сортиране тези хора тук? 554 00:18:31,610 --> 00:18:34,500 Тъй като имахме няколко подходи по-рано, при което бяхме 555 00:18:34,500 --> 00:18:36,360 вид вземане на две различни кофи. 556 00:18:36,360 --> 00:18:38,842 И тогава ние бяхме като цяло реди неща заедно. 557 00:18:38,842 --> 00:18:41,050 Веднага след като видяхме две числа че бе заедно, 558 00:18:41,050 --> 00:18:41,975 ние ги съберете заедно. 559 00:18:41,975 --> 00:18:43,350 Две писма, които вървят заедно. 560 00:18:43,350 --> 00:18:45,058 >> Но нека да видим дали можем не може да се формализира това, 561 00:18:45,058 --> 00:18:48,044 така че да можем в крайна сметка да има някои псевдо-код щете, 562 00:18:48,044 --> 00:18:49,710 с която можете да реши тези проблеми. 563 00:18:49,710 --> 00:18:51,870 Така че сега, аз съм гледам навън при тези номера тук. 564 00:18:51,870 --> 00:18:55,030 И виждам цял куп грешки. 565 00:18:55,030 --> 00:18:57,750 В крайна сметка, аз искам един на наляво и осем от дясно. 566 00:18:57,750 --> 00:19:00,650 >> И така, аз разглеждам тези две, четири и две. 567 00:19:00,650 --> 00:19:02,930 И какъв е проблемът, очевидно? 568 00:19:02,930 --> 00:19:04,261 Да. 569 00:19:04,261 --> 00:19:04,760 So. 570 00:19:04,760 --> 00:19:07,160 Две очевидно идва преди четири, така че знам какво? 571 00:19:07,160 --> 00:19:10,210 Позволете ми първо да алчни подход, ако щете, който много прилича на проблеми 572 00:19:10,210 --> 00:19:13,790 зададете one--, ако си спомняте от Standard Edition на Проблем Set One, 573 00:19:13,790 --> 00:19:16,820 когато аз просто локално реши проблема това е точно тук пред мен 574 00:19:16,820 --> 00:19:17,690 и да видим къде той ме води. 575 00:19:17,690 --> 00:19:17,870 >> ДОБРЕ. 576 00:19:17,870 --> 00:19:20,161 Така че две и четири, да ме пусне напред и просто да ви суап две. 577 00:19:20,161 --> 00:19:22,400 Ако физически можете да се движите себе си и вашата хартия, 578 00:19:22,400 --> 00:19:25,040 Изглежда съм намерила изброят в по-добро състояние. 579 00:19:25,040 --> 00:19:26,330 >> Сега, те са добри. 580 00:19:26,330 --> 00:19:28,480 Отивам да се премине, четири и шест, изглежда добре. 581 00:19:28,480 --> 00:19:29,110 Не е проблем. 582 00:19:29,110 --> 00:19:30,440 Six и осем, OK. 583 00:19:30,440 --> 00:19:31,860 Осем и един, друг проблем. 584 00:19:31,860 --> 00:19:34,750 Защото това, което е вярно, около осем и един? 585 00:19:34,750 --> 00:19:36,990 One идва преди осем, и така, какво да правим? 586 00:19:36,990 --> 00:19:38,090 Нека да сменяте тези две. 587 00:19:38,090 --> 00:19:39,316 One и осем. 588 00:19:39,316 --> 00:19:40,690 И сега, аз отивам да продължи да функционира. 589 00:19:40,690 --> 00:19:42,030 Отивам да продължим да търсим напред. 590 00:19:42,030 --> 00:19:42,840 И нека да видим какво ще стане. 591 00:19:42,840 --> 00:19:44,680 Осем и три, на Разбира се, в ред. 592 00:19:44,680 --> 00:19:45,815 Нека суап. 593 00:19:45,815 --> 00:19:46,940 Осем и седем, разбира се. 594 00:19:46,940 --> 00:19:47,481 Няма ред. 595 00:19:47,481 --> 00:19:48,280 Нека суап. 596 00:19:48,280 --> 00:19:49,940 Осем и пет, разбира се, нека да суап. 597 00:19:49,940 --> 00:19:50,560 Всичко е наред. 598 00:19:50,560 --> 00:19:51,880 Списък се сортира. 599 00:19:51,880 --> 00:19:53,060 нали? 600 00:19:53,060 --> 00:19:54,280 >> OK, явно не. 601 00:19:54,280 --> 00:19:55,860 Но това е малко по-добре, нали? 602 00:19:55,860 --> 00:19:57,270 Защото известие, което се случи. 603 00:19:57,270 --> 00:20:01,749 Всеки път, когато се извършва замяна, по-малък Номер вид прецедени по този начин, 604 00:20:01,749 --> 00:20:03,790 и по-голям брой прецедени този начин, или ще 605 00:20:03,790 --> 00:20:06,880 започнете поговорка разпенва до наляво или надясно пропуска. 606 00:20:06,880 --> 00:20:10,080 >> Сега, това не е достатъчно, тъй като в най-добрия редица мощ 607 00:20:10,080 --> 00:20:11,990 са се преместили на едно място напред, или в най-лошия, 608 00:20:11,990 --> 00:20:13,880 редица може да има премества едно място по-нататък. 609 00:20:13,880 --> 00:20:16,369 Така ли какво, този вид от работил доста добре досега. 610 00:20:16,369 --> 00:20:17,410 Нека просто го опитайте отново. 611 00:20:17,410 --> 00:20:18,880 Две и четири, те са ОК. 612 00:20:18,880 --> 00:20:20,180 Четири и шест, те са ОК. 613 00:20:20,180 --> 00:20:21,790 Six и един, в ред. 614 00:20:21,790 --> 00:20:23,007 Така че нека да ви две суап. 615 00:20:23,007 --> 00:20:25,840 И сега, забележите проблем те години започва да става малко по-добре отново. 616 00:20:25,840 --> 00:20:27,006 Шест и три, в ред. 617 00:20:27,006 --> 00:20:28,100 Нека вие двамата разменят. 618 00:20:28,100 --> 00:20:29,730 Шест и седем, вие сте добре. 619 00:20:29,730 --> 00:20:32,230 Седем и пет, разбира се, в ред. 620 00:20:32,230 --> 00:20:33,920 Седем и осем, в ред. 621 00:20:33,920 --> 00:20:36,470 И сега, може да се наложи да направите това още няколко пъти. 622 00:20:36,470 --> 00:20:39,830 И всъщност, мисля за себе си може би колко пъти максимално 623 00:20:39,830 --> 00:20:41,330 може ли да ходи напред-назад? 624 00:20:41,330 --> 00:20:42,390 >> Ще се върна към това. 625 00:20:42,390 --> 00:20:43,700 Така че две и четири са все още OK. 626 00:20:43,700 --> 00:20:44,940 Четири и един, Не. 627 00:20:44,940 --> 00:20:45,747 Така че, нека суап. 628 00:20:45,747 --> 00:20:47,830 И пак забележите визуално един е вид бълбука 629 00:20:47,830 --> 00:20:49,163 наляво, където трябва да бъде. 630 00:20:49,163 --> 00:20:50,010 Четири и три суап. 631 00:20:50,010 --> 00:20:51,330 Четири и шест. 632 00:20:51,330 --> 00:20:53,100 Шест и пет суап. 633 00:20:53,100 --> 00:20:53,959 Шест и седем. 634 00:20:53,959 --> 00:20:55,000 Седем и осем са добри. 635 00:20:55,000 --> 00:20:55,500 >> Good. 636 00:20:55,500 --> 00:20:58,460 Ние получаваме още по-добре. 637 00:20:58,460 --> 00:20:59,130 Така че нека да видим. 638 00:20:59,130 --> 00:21:00,940 Сега, ние имаме две и една. 639 00:21:00,940 --> 00:21:02,520 Разбира се, сменяте. 640 00:21:02,520 --> 00:21:07,520 Две и три, три и четири, четири и пет, шест и седем, седем и осем. 641 00:21:07,520 --> 00:21:08,020 Good. 642 00:21:08,020 --> 00:21:08,730 И знаеш ли какво? 643 00:21:08,730 --> 00:21:11,190 Защото аз направих една промяна там, позволете ми да направя една проверка здрав разум. 644 00:21:11,190 --> 00:21:13,023 Нека да отидем по целия път обратно в началото. 645 00:21:13,023 --> 00:21:13,680 ДОБРЕ. 646 00:21:13,680 --> 00:21:14,750 One, two-- Мда, виждаш ли? 647 00:21:14,750 --> 00:21:15,870 Нещо не беше наред. 648 00:21:15,870 --> 00:21:18,420 Три, четири, пет, шест, седем, осем. 649 00:21:18,420 --> 00:21:21,920 И в този последен пас, са можете удобно с моя сега 650 00:21:21,920 --> 00:21:23,830 твърдейки, че е сортирани? 651 00:21:23,830 --> 00:21:24,330 ДОБРЕ. 652 00:21:24,330 --> 00:21:25,880 Визуално, това е абсолютно вярно. 653 00:21:25,880 --> 00:21:28,410 Но функционално, което е също така просто да се случи 654 00:21:28,410 --> 00:21:31,870 с това, че последната атака, която ви позволява да потвърдя, че този списък е наистина 655 00:21:31,870 --> 00:21:32,660 сортирани? 656 00:21:32,660 --> 00:21:34,477 >> Какво съм направил или не направи това миналата пас? 657 00:21:34,477 --> 00:21:35,810 АУДИТОРИЯ: Няма промяна. 658 00:21:35,810 --> 00:21:36,120 DAVID J. Malan: Съжаляваме? 659 00:21:36,120 --> 00:21:37,070 АУДИТОРИЯ: Няма промени. 660 00:21:37,070 --> 00:21:38,653 DAVID J. Malan: Няма промяна. 661 00:21:38,653 --> 00:21:41,947 Така че би било глупаво от моя страна да направя същата алгоритъм отново 662 00:21:41,947 --> 00:21:43,780 ако не е допуснал променя първи път. 663 00:21:43,780 --> 00:21:45,160 И държавата не се е променило. 664 00:21:45,160 --> 00:21:47,576 Разбира се, аз няма да се направи Всички промени, за втори път. 665 00:21:47,576 --> 00:21:49,820 И така, това е безопасно сега да се каже, списък е сортиран. 666 00:21:49,820 --> 00:21:52,069 >> И наистина, това е сега нещо, което ние ще принцип 667 00:21:52,069 --> 00:21:56,900 повикване балон сортиране, при което по двойки, можете поправяне на грешки отново, 668 00:21:56,900 --> 00:22:00,210 и отново, и отново, и вие продължавай напред и назад, 669 00:22:00,210 --> 00:22:03,370 и назад и напред, докато не да няма такива суапове, като в този момент 670 00:22:03,370 --> 00:22:07,089 можете да сте сигурни, да, аз завърши определяне на всички грешки. 671 00:22:07,089 --> 00:22:08,630 Нека да изчисти и да се опита друг подход. 672 00:22:08,630 --> 00:22:11,590 Ако вие може да се върне в реда, в който са били преди малко, 673 00:22:11,590 --> 00:22:13,780 която изглеждаше така. 674 00:22:13,780 --> 00:22:17,640 Сега, нека да подход на Малко по-скоро като на изпит книгата, 675 00:22:17,640 --> 00:22:21,122 с което бяхме постоянно избор на буква от азбуката 676 00:22:21,122 --> 00:22:22,830 че ние вид исках да се справят с по-нататък. 677 00:22:22,830 --> 00:22:26,420 Може би това е високо писмо, като A, или нисък писмо Z. 678 00:22:26,420 --> 00:22:28,170 >> Така че всеки се е върнала в този ред. 679 00:22:28,170 --> 00:22:29,800 А сега нека да направим това. 680 00:22:29,800 --> 00:22:34,880 Нека да видим Знам, че имам осем номера тук. 681 00:22:34,880 --> 00:22:37,410 Отивам да вървим напред и да просто избират съзнателно 682 00:22:37,410 --> 00:22:38,520 най-малките елементи. 683 00:22:38,520 --> 00:22:38,760 Нали така? 684 00:22:38,760 --> 00:22:39,801 Това изглежда твърде интуитивен. 685 00:22:39,801 --> 00:22:42,560 Защо не мога да намеря най-малките елемент, сложи я там, където принадлежи, 686 00:22:42,560 --> 00:22:45,280 след това получи следващата по-малка елемент, сложи то там, където принадлежи, и просто се повтаря. 687 00:22:45,280 --> 00:22:46,820 >> Защото интуитивно, че трябва да работи също. 688 00:22:46,820 --> 00:22:48,441 Така четири, че е доста малък брой. 689 00:22:48,441 --> 00:22:49,940 Отивам да си спомни къде е това. 690 00:22:49,940 --> 00:22:50,523 Чакай малко. 691 00:22:50,523 --> 00:22:51,577 Две е по-малък. 692 00:22:51,577 --> 00:22:53,910 Нека сега да си спомня къде двама е, и да забравите за четири. 693 00:22:53,910 --> 00:22:55,050 Ние ще се справим с това по-късно. 694 00:22:55,050 --> 00:22:56,460 Six, не ме интересува. 695 00:22:56,460 --> 00:22:57,810 Eight, аз не съм интересуват. 696 00:22:57,810 --> 00:22:59,780 Един от тях е новата ми малко на брой. 697 00:22:59,780 --> 00:23:01,470 Така че аз отивам да си спомни къде е една. 698 00:23:01,470 --> 00:23:02,534 Три, не се интересувам. 699 00:23:02,534 --> 00:23:03,450 Seven, не се интересувам. 700 00:23:03,450 --> 00:23:04,530 Five, не се интересувам. 701 00:23:04,530 --> 00:23:07,390 >> Така че, без да пада на сцената тази година, 702 00:23:07,390 --> 00:23:09,890 Отивам да вземете номер one-- и какво е вашето име отново? 703 00:23:09,890 --> 00:23:10,150 >> Анан: Анан. 704 00:23:10,150 --> 00:23:11,220 >> DAVID J. Malan: Анан. 705 00:23:11,220 --> 00:23:13,540 И ако можете да се присъедините към мен в началото на списъка 706 00:23:13,540 --> 00:23:14,870 нека да си сложиш където ти е мястото. 707 00:23:14,870 --> 00:23:16,080 Unfortunately-- какво е вашето име? 708 00:23:16,080 --> 00:23:16,650 >> СТЕФАН: Стефан. 709 00:23:16,650 --> 00:23:18,191 >> DAVID J. Malan: Стефан е в пътя. 710 00:23:18,191 --> 00:23:23,490 Така че, преди Стефан решава този проблем, какво да правим? 711 00:23:23,490 --> 00:23:25,412 Какво да правим със Стефан? 712 00:23:25,412 --> 00:23:27,269 >> АУДИТОРИЯ: [недоловим]. 713 00:23:27,269 --> 00:23:28,060 DAVID J. Malan: OK. 714 00:23:28,060 --> 00:23:28,850 Така че бихме могли да направим това. 715 00:23:28,850 --> 00:23:31,730 Бихме могли да вземат нещо като Стефан и неговият четири, а просто да го постави в променлива 716 00:23:31,730 --> 00:23:33,530 и държа на него за някаква сума от време, 717 00:23:33,530 --> 00:23:35,220 като по този начин място за номер едно. 718 00:23:35,220 --> 00:23:36,280 И това не е лошо. 719 00:23:36,280 --> 00:23:39,270 Мога да предложа, защо да не направим ние просто сложи Стефан тук? 720 00:23:39,270 --> 00:23:41,610 Защо може да наруши този един от идеите, ние започнахме 721 00:23:41,610 --> 00:23:44,830 Говорим за последен път, миналата седмица? 722 00:23:44,830 --> 00:23:45,330 Да? 723 00:23:45,330 --> 00:23:45,740 >> АУДИТОРИЯ: [недоловим]. 724 00:23:45,740 --> 00:23:46,860 >> DAVID J. Malan: Няма по индекса за него. 725 00:23:46,860 --> 00:23:49,735 Ако мислите, че на този, наистина, като масив, това е като отрицателен, 726 00:23:49,735 --> 00:23:52,900 така че няма памет всъщност тук, ако това наистина е масив, 727 00:23:52,900 --> 00:23:55,090 като ние обявена миналата седмица в лекция. 728 00:23:55,090 --> 00:23:56,250 Така че ние не трябва да направите това. 729 00:23:56,250 --> 00:23:57,340 Бихме могли да го съхранява в променлива. 730 00:23:57,340 --> 00:23:57,820 >> Или знаеш ли какво? 731 00:23:57,820 --> 00:23:59,153 Чух някой друг да го предложи. 732 00:23:59,153 --> 00:24:01,020 Какво друго можем да направим със Стефан? 733 00:24:01,020 --> 00:24:03,770 Защо не можем просто да го изгони и го постави върху това къде номер едно беше. 734 00:24:03,770 --> 00:24:05,170 Така че, ако искате да отидете там. 735 00:24:05,170 --> 00:24:07,300 И наистина, това е доста добро решение. 736 00:24:07,300 --> 00:24:10,480 Сега, от една страна, аз съм вид на прави проблема по-лошо. 737 00:24:10,480 --> 00:24:13,650 Сега е по-далеч Четири от мястото, където трябва да бъде. 738 00:24:13,650 --> 00:24:14,900 Тя трябва да бъде към тази половина. 739 00:24:14,900 --> 00:24:16,100 >> Но знаете ли какво? 740 00:24:16,100 --> 00:24:17,630 Това можеше да е лош късмет. 741 00:24:17,630 --> 00:24:18,822 Може би номер осем е бил тук. 742 00:24:18,822 --> 00:24:20,530 И така, може би бихме са придобили късмет, 743 00:24:20,530 --> 00:24:22,460 и бутна осем по-близо до края. 744 00:24:22,460 --> 00:24:24,710 Така че в края на деня, то вид на всички средни място. 745 00:24:24,710 --> 00:24:26,085 Ние не трябва да се грижи за четири. 746 00:24:26,085 --> 00:24:29,400 Всичко, което ме интересува в момента е избиране на най-малкия елемент. 747 00:24:29,400 --> 00:24:32,030 >> И сега, това, което аз отивам да направите, е да забравите за номер едно 748 00:24:32,030 --> 00:24:35,160 постоянно, защото знам, че на списък зад мен сега се сортира. 749 00:24:35,160 --> 00:24:36,720 Така че моят списък беше преди осем размер. 750 00:24:36,720 --> 00:24:37,720 Сега, това е с размер на седем. 751 00:24:37,720 --> 00:24:40,340 Така че моят проблем е все малки, макар и линейно. 752 00:24:40,340 --> 00:24:43,022 Така че сега, аз отивам да изберете ток-малкият елемент, две. 753 00:24:43,022 --> 00:24:46,520 Шест, осем, четири, три, седем, пет. 754 00:24:46,520 --> 00:24:47,770 Това е най-малкия елемент. 755 00:24:47,770 --> 00:24:49,416 Така че това, което съм аз ще направя with-- какво е вашето име отново? 756 00:24:49,416 --> 00:24:49,760 >> JOSEPH: Joseph. 757 00:24:49,760 --> 00:24:50,085 >> DAVID J. Malan: Йосиф? 758 00:24:50,085 --> 00:24:52,000 Отиваме да напусне Joseph на място. 759 00:24:52,000 --> 00:24:54,842 Сега, аз отивам да се преструвам че тези момчета are-- добре, 760 00:24:54,842 --> 00:24:56,550 Знам, че тези две вече са подредени. 761 00:24:56,550 --> 00:24:58,424 Нека сега се съсредоточи върху остатък от списъка. 762 00:24:58,424 --> 00:25:00,080 Шест е текущата малката. 763 00:25:00,080 --> 00:25:01,190 Осем е по-голям. 764 00:25:01,190 --> 00:25:02,970 Сега Four е текущата малката. 765 00:25:02,970 --> 00:25:04,762 Три сега е текущата малката. 766 00:25:04,762 --> 00:25:07,720 И така, сега, аз отивам да изберете три, които is-- какво се казваше? 767 00:25:07,720 --> 00:25:08,190 СЕРЕНА: Серена. 768 00:25:08,190 --> 00:25:10,620 DAVID J. Malan: Серина, ако можех вземете своя номер и суап with-- 769 00:25:10,620 --> 00:25:11,550 KALSANG: Kalsang. 770 00:25:11,550 --> 00:25:12,940 DAVID J. Malan: Kalsang. 771 00:25:12,940 --> 00:25:15,220 Хайде обратно, и ние сме Ще сменяте тези две. 772 00:25:15,220 --> 00:25:17,360 И сега, нека да поставим този на автопилот. 773 00:25:17,360 --> 00:25:21,589 Отивам да отида и да я оставите да вие, момчета, за да изберете следващите най-малките елементи. 774 00:25:21,589 --> 00:25:22,380 Dun, сивокафяв, сивокафяв, сивокафяв. 775 00:25:22,380 --> 00:25:24,560 Номер четири, какво трябва да направя? 776 00:25:24,560 --> 00:25:26,261 Отлично. 777 00:25:26,261 --> 00:25:27,760 Сега, аз отивам да се направи още един пропуск. 778 00:25:27,760 --> 00:25:28,590 Dun, сивокафяв, сивокафяв, сивокафяв. 779 00:25:28,590 --> 00:25:31,465 Виждам пет е следващата по-малка. 780 00:25:31,465 --> 00:25:32,840 Сега, аз ще взема още един пас. 781 00:25:32,840 --> 00:25:33,631 Dun, сивокафяв, сивокафяв, сивокафяв. 782 00:25:33,631 --> 00:25:34,880 Six е най-малката. 783 00:25:34,880 --> 00:25:35,520 Good. 784 00:25:35,520 --> 00:25:36,585 Седем е най-малката. 785 00:25:36,585 --> 00:25:37,085 Няма промяна. 786 00:25:37,085 --> 00:25:38,630 Осем е най-малката. 787 00:25:38,630 --> 00:25:39,170 Съставено. 788 00:25:39,170 --> 00:25:43,900 >> Така че това, което току-що направено чрез итеративно избиране на един елемент след друга 789 00:25:43,900 --> 00:25:47,230 се приложи нещо, което сме ще официализира като избор на сортиране. 790 00:25:47,230 --> 00:25:49,120 И това е може би дори по-лесно да се обясни, 791 00:25:49,120 --> 00:25:51,310 в които буквално всичко, което искате да направите, е просто да 792 00:25:51,310 --> 00:25:54,700 Ще назад и напред през списъка избиране, следващата по-малка елемент, 793 00:25:54,700 --> 00:25:55,720 докато сте готови. 794 00:25:55,720 --> 00:25:58,650 >> Така че това е още по-лесно, може би интуитивно, в сравнение с миналата. 795 00:25:58,650 --> 00:26:00,020 Нека се опитаме за последен една. 796 00:26:00,020 --> 00:26:03,060 Ако вие може да себе си нулират в следните позиции 797 00:26:03,060 --> 00:26:08,600 за последен път, нека да видим дали не можем Сега се формализира един друг подход. 798 00:26:08,600 --> 00:26:12,857 В действителност, би някой там искал да предложа 799 00:26:12,857 --> 00:26:14,440 как иначе бихме могли да го направим? 800 00:26:14,440 --> 00:26:17,439 Без да хвърлят вън модерни думички или сортиране на отговорите, които вече са известни, 801 00:26:17,439 --> 00:26:19,689 просто интуитивно, какво можем да направим? 802 00:26:19,689 --> 00:26:21,635 >> АУДИТОРИЯ: [недоловим]. 803 00:26:21,635 --> 00:26:22,510 DAVID J. Malan: Да. 804 00:26:22,510 --> 00:26:24,620 Така че има някои много интуиция там. 805 00:26:24,620 --> 00:26:28,020 Хубавите неща се случват по този начин досега по компютърни науки, когато ние разделяме 806 00:26:28,020 --> 00:26:30,832 и завладяване на проблема за разделяне го на половина и половина и половина. 807 00:26:30,832 --> 00:26:32,540 И така наистина, ние може да започне да се направи това. 808 00:26:32,540 --> 00:26:35,754 И в действителност, че ще бъде, ще виж, един от най-добрите ни решения, все още. 809 00:26:35,754 --> 00:26:37,420 Но нека се върна към това след дълго. 810 00:26:37,420 --> 00:26:40,500 В действителност, ние ще направим че малко по-късно тази седмица. 811 00:26:40,500 --> 00:26:42,180 Какво друго може да направим, за да се реши този? 812 00:26:42,180 --> 00:26:44,647 Така че всеки тук е в привидно случаен ред. 813 00:26:44,647 --> 00:26:45,230 Знаеш ли какво? 814 00:26:45,230 --> 00:26:48,320 Вместо да отида напред и назад, назад и напред, назад и напред 815 00:26:48,320 --> 00:26:50,624 всеки път, това се чувства като Правя много разходки. 816 00:26:50,624 --> 00:26:52,790 Защо не мога просто да започне в началото на списъка 817 00:26:52,790 --> 00:26:54,960 и просто сложи четири където му е мястото? 818 00:26:54,960 --> 00:26:59,680 Така че нека да приемем за момент, че моя списък е само този първи елемент. 819 00:26:59,680 --> 00:27:04,937 Е четири подредени в този момент във времето, ако всичко, което ме интересува е всичко тук? 820 00:27:04,937 --> 00:27:06,520 Това е нещо тривиално вярно, нали? 821 00:27:06,520 --> 00:27:10,000 Подобно на списъка, съдържащ един номер, и че номер четири е очевидно сортирани. 822 00:27:10,000 --> 00:27:13,070 >> Така че нека просто да предвидят че този списък е сортиран. 823 00:27:13,070 --> 00:27:15,090 Но сега имам останалата част на този списък. 824 00:27:15,090 --> 00:27:17,240 Така че сега, аз се сблъскват две. 825 00:27:17,240 --> 00:27:21,690 Къде два очевидно принадлежат по отношение на четири? 826 00:27:21,690 --> 00:27:22,580 Преди четири. 827 00:27:22,580 --> 00:27:23,862 Така че това, което мога да направя тук? 828 00:27:23,862 --> 00:27:24,820 Какво е вашето име отново? 829 00:27:24,820 --> 00:27:25,090 >> JOSEPH: Joseph. 830 00:27:25,090 --> 00:27:26,030 >> DAVID J. Malan: Joseph, ако бихте могли да се върнем назад 831 00:27:26,030 --> 00:27:27,790 само за миг с вашия номер. 832 00:27:27,790 --> 00:27:31,130 И сега какво трябва да направя Стефан тук? 833 00:27:31,130 --> 00:27:33,720 Нека да смени Стефан тук. 834 00:27:33,720 --> 00:27:35,520 И сега, нека Йосиф дойде тук. 835 00:27:35,520 --> 00:27:39,660 И сега, нека да се твърди, че тук всичко се сортира. 836 00:27:39,660 --> 00:27:42,474 Така че, подобен резултат, но по- коренно различен подход. 837 00:27:42,474 --> 00:27:44,140 Аз дори не погледнах какво има там долу. 838 00:27:44,140 --> 00:27:46,310 Аз просто продължавате да приемате елементите като те са предадени за мен, 839 00:27:46,310 --> 00:27:47,240 и да се справят с тях. 840 00:27:47,240 --> 00:27:48,330 >> Така че сега, виждам, номер шест. 841 00:27:48,330 --> 00:27:51,110 Къде номер шест принадлежат? 842 00:27:51,110 --> 00:27:53,250 Имаме две, четири, шест. 843 00:27:53,250 --> 00:27:54,800 Точно къде е тя в момента. 844 00:27:54,800 --> 00:27:57,750 Така че нека да оставим това сам, а сега твърдят, че тази част от списъка 845 00:27:57,750 --> 00:27:58,772 сега сортирани. 846 00:27:58,772 --> 00:28:01,230 И така, това се чувства фундаментално различна с това, че аз съм просто 847 00:28:01,230 --> 00:28:05,230 движещи се през списъка тук линейно, а аз никога не съм удвояване обратно. 848 00:28:05,230 --> 00:28:05,730 Да. 849 00:28:05,730 --> 00:28:06,230 Всичко е наред. 850 00:28:06,230 --> 00:28:08,190 Така осем, къде ти е мястото? 851 00:28:08,190 --> 00:28:08,730 Точно тук. 852 00:28:08,730 --> 00:28:09,310 Perfect. 853 00:28:09,310 --> 00:28:10,210 Така че сега, една. 854 00:28:10,210 --> 00:28:10,900 Охо. 855 00:28:10,900 --> 00:28:13,010 Това се чувства като това е ще бъде скъпо. 856 00:28:13,010 --> 00:28:15,690 Сега в предишния алгоритъм, Аз просто замениха хората. 857 00:28:15,690 --> 00:28:18,648 Така че аз може да го постави по целия път към началото, но след това се премества Йосиф. 858 00:28:18,648 --> 00:28:21,450 Но ако се преместя Йосиф, сега каква ще е наред? 859 00:28:21,450 --> 00:28:24,250 >> Сега, аз съм нещо като undone-- съм една стъпка напред и след това 860 00:28:24,250 --> 00:28:26,300 една крачка назад, защото сега Йосиф ще бъде извън строя. 861 00:28:26,300 --> 00:28:26,830 Така че нека да направим това. 862 00:28:26,830 --> 00:28:29,150 Ако можеше да вземе номер едно и стъпка назад само за миг. 863 00:28:29,150 --> 00:28:30,490 Как можем да put-- какво е името ви отново? 864 00:28:30,490 --> 00:28:31,130 >> Анан: Анан. 865 00:28:31,130 --> 00:28:32,610 >> DAVID J. Malan: Анан на място? 866 00:28:32,610 --> 00:28:36,091 Какво трябва да се случи по отношение до две, четири, шест, а осем? 867 00:28:36,091 --> 00:28:37,570 Всички те ще трябва да се смени. 868 00:28:37,570 --> 00:28:42,590 Така че, ако осем биха искали да се смени Първо, след шест, след четири, след това два. 869 00:28:42,590 --> 00:28:45,380 И тогава Анан, ако искате искал да дойде тук, добре. 870 00:28:45,380 --> 00:28:47,760 Но тук, ние сме просто вид платена цена 871 00:28:47,760 --> 00:28:49,510 на различен етап в алгоритъма. 872 00:28:49,510 --> 00:28:52,550 Като има предвид, за последен път с избор сортиране, и дори балон сортиране, 873 00:28:52,550 --> 00:28:54,700 Вървя назад и напред, назад и напред, 874 00:28:54,700 --> 00:28:58,360 който е със сигурност добавяне време-мъдър, и буквално поетапно. 875 00:28:58,360 --> 00:29:00,660 >> Въвежда се подреди, на първо поглед, изглежда, че е 876 00:29:00,660 --> 00:29:05,150 супер-умни, по който аз съм просто вземане на бавен, постепенен прогрес, 877 00:29:05,150 --> 00:29:07,120 но аз няма да ходя тази назад и напред. 878 00:29:07,120 --> 00:29:09,410 Но ако някой е наистина в ред, известие 879 00:29:09,410 --> 00:29:10,840 цялата работа аз просто трябваше да се направи. 880 00:29:10,840 --> 00:29:14,750 Аз трябваше да се движат половината от списъка само за да направи място за номер едно. 881 00:29:14,750 --> 00:29:16,790 Така че това е една и съща сума на работата до този момент тя 882 00:29:16,790 --> 00:29:18,690 чувства, просто различен вид работа. 883 00:29:18,690 --> 00:29:19,370 >> Да продължим. 884 00:29:19,370 --> 00:29:22,657 Така че сега ние знаем, че всеки, от едно до осем са подредени. 885 00:29:22,657 --> 00:29:23,740 Ето, имам номер три. 886 00:29:23,740 --> 00:29:25,864 Ако искате да вземете номер три, една крачка назад. 887 00:29:25,864 --> 00:29:28,260 И какво вие трябва да направите? 888 00:29:28,260 --> 00:29:28,760 Да. 889 00:29:28,760 --> 00:29:33,070 Така че това е още един, два, три стъпки. 890 00:29:33,070 --> 00:29:36,010 Три единици за време, което просто струват мен, така че сега може да се побере три. 891 00:29:36,010 --> 00:29:37,460 И накрая, седем. 892 00:29:37,460 --> 00:29:39,730 >> Да вървим напред и да имат можете да се върнем назад. 893 00:29:39,730 --> 00:29:42,780 Това само ще ни струва една единица време, но това е ОК. 894 00:29:42,780 --> 00:29:44,170 И сега, пет ще да е малко по-скъпо. 895 00:29:44,170 --> 00:29:45,340 Ако искате да се върнем назад. 896 00:29:45,340 --> 00:29:48,380 Ние трябва да се движат осем, и седем, а шест. 897 00:29:48,380 --> 00:29:50,749 И тогава всеки е сега сортирани. 898 00:29:50,749 --> 00:29:52,290 Така че голяма ръка на нашите доброволци тук. 899 00:29:52,290 --> 00:29:53,554 Благодаря ти много. 900 00:29:53,554 --> 00:29:56,220 >> [Аплодисменти] 901 00:29:56,220 --> 00:29:56,860 >> Благодаря на всички. 902 00:29:56,860 --> 00:29:57,520 Благодаря на всички. 903 00:29:57,520 --> 00:30:02,940 Така че нека да видим сега колко скъпо всичко това е. 904 00:30:02,940 --> 00:30:06,210 Нека разгледаме може би най- простият от тях, метод на мехурчето. 905 00:30:06,210 --> 00:30:09,950 И аз казвам простата, само защото можете да го решим лакомо, като просто 906 00:30:09,950 --> 00:30:11,660 фиксира двойки Проблемът тук. 907 00:30:11,660 --> 00:30:13,720 Фиксирайте двойки проблема тук, отново и отново 908 00:30:13,720 --> 00:30:17,680 и отново, повтаряйки, тъй като много пъти, колкото всъщност трябва да. 909 00:30:17,680 --> 00:30:21,050 >> Така се оказва, че с балон сортиране, добре, 910 00:30:21,050 --> 00:30:25,820 колко стъпки трябва ли да се вземат на първото преминаване на този алгоритъм? 911 00:30:25,820 --> 00:30:30,850 Аз може take-- нека see-- една, две, три, четири, пет, шест, седем. 912 00:30:30,850 --> 00:30:32,190 А има и осем елементи тук. 913 00:30:32,190 --> 00:30:35,280 Така че това е като п минус 1 стъпки за получите от началото на списъка 914 00:30:35,280 --> 00:30:36,380 на края на списъка. 915 00:30:36,380 --> 00:30:41,350 >> Но с избор на сортиране, припомни, че аз съм избор на елементи отново и отново 916 00:30:41,350 --> 00:30:44,590 и отново, че това е най-малкото, Аз съм го поставя на мястото, 917 00:30:44,590 --> 00:30:46,616 но след това аз не съм търси зад мен отново. 918 00:30:46,616 --> 00:30:49,490 Така че аз мисля, че е малко по-ясно, след това, че за първи път, бих могъл 919 00:30:49,490 --> 00:30:52,680 Трябва да се вземат всички п минус 1 етапи да се намери най-малкия елемент. 920 00:30:52,680 --> 00:30:55,920 След това ги сложи на място, и аз изгони всеки, който е бил тук преди това. 921 00:30:55,920 --> 00:30:57,500 >> Но тогава не е нужно да продължи да гледаш този елемент, 922 00:30:57,500 --> 00:30:59,040 защото знам, че това е вече най-малките. 923 00:30:59,040 --> 00:31:01,581 Така че сега, не мога да гледам само седем елементи, след шест елемента, 924 00:31:01,581 --> 00:31:03,290 След пет елемента, след четири елемента. 925 00:31:03,290 --> 00:31:06,900 И така, математически, ако п е броя на елементите или номера 926 00:31:06,900 --> 00:31:11,990 че ние започнахме с, можете да си представите че това е същото като N минус 1, 927 00:31:11,990 --> 00:31:14,250 плюс п минус 2 стъпки, плюс п минус 3 стъпки, 928 00:31:14,250 --> 00:31:16,780 плюс п минус 4 стъпки, през цялото път до само една крачка. 929 00:31:16,780 --> 00:31:18,160 И аз съм на последната ми човек. 930 00:31:18,160 --> 00:31:20,650 >> И ако си спомняте, че много на статистики книги или книги по математика 931 00:31:20,650 --> 00:31:24,730 имат тези формули на Твърда назад или пред тях, 932 00:31:24,730 --> 00:31:27,690 се оказва, че тази серия може да се изрази по-просто 933 00:31:27,690 --> 00:31:28,857 като N пъти N минус 1 над 2. 934 00:31:28,857 --> 00:31:31,273 И това е добре, ако това не е в челните редици на вашия ум. 935 00:31:31,273 --> 00:31:32,420 Но това наистина е вярно. 936 00:31:32,420 --> 00:31:34,449 Това е просто по-прост начин да го пишете. 937 00:31:34,449 --> 00:31:36,240 И след това, ако смятате обратно към началното училище, 938 00:31:36,240 --> 00:31:38,698 когато просто започнете да се умножи неща, това, разбира се, 939 00:31:38,698 --> 00:31:41,820 е просто п квадрат минус п разделена на две. 940 00:31:41,820 --> 00:31:44,772 Всичко, което съм направил, е разширяване изразите там. 941 00:31:44,772 --> 00:31:46,730 И така, нека да пренапише този малко по-различно. 942 00:31:46,730 --> 00:31:49,780 Това е п карирани, разделено на две минус п / 2. 943 00:31:49,780 --> 00:31:53,270 >> Така че отново, аз съм просто вид на прилагането някои аритметика правила там. 944 00:31:53,270 --> 00:31:57,140 Но забележете, че сега най-големият план в този израз, така да се каже, 945 00:31:57,140 --> 00:31:58,540 е, че N квадрат. 946 00:31:58,540 --> 00:32:02,910 Така че, да, това е п квадрат разделена на две, минус N / 2. 947 00:32:02,910 --> 00:32:05,080 >> Но обикновено, ако п е Ще бъде голяма стойност, 948 00:32:05,080 --> 00:32:08,740 Отивам да се твърди, че п квадрат ще бъде доминиращ фактор. 949 00:32:08,740 --> 00:32:10,490 Това е просто щеше да бъде по-голям принос 950 00:32:10,490 --> 00:32:12,877 на броя на стъпки от п / 2. 951 00:32:12,877 --> 00:32:13,960 Така че това, което мога да кажа от това? 952 00:32:13,960 --> 00:32:16,795 Нека се опитаме един прост пример, дори макар и по математика получава малко голям. 953 00:32:16,795 --> 00:32:20,210 >> Така че предполагам, че имахме 1 милион души на сцената, или 1 милион неща 954 00:32:20,210 --> 00:32:21,320 че искаме да сортирате. 955 00:32:21,320 --> 00:32:23,730 Нека да включите милиона в точно тази формула 956 00:32:23,730 --> 00:32:27,230 да видим колко стъпки е необходимо общо да сортирате милион елементи, използвайки речем, 957 00:32:27,230 --> 00:32:28,560 Избор на вид. 958 00:32:28,560 --> 00:32:30,760 >> Така че ние ще трябва по същата формула, както преди. 959 00:32:30,760 --> 00:32:34,120 Бих включите милиона, така че мога да получа един милион карирани, разделено на две, 960 00:32:34,120 --> 00:32:35,990 минус милион разделена на две. 961 00:32:35,990 --> 00:32:40,180 Ако го направя, че математиката в аванс Оттук имаме 500 милиарда 962 00:32:40,180 --> 00:32:47,460 минус 500 000, които ни дава 499 999 500 000, 963 00:32:47,460 --> 00:32:49,270 което е дяволски много голям. 964 00:32:49,270 --> 00:32:54,370 >> В действителност, ако се сравни с предприятието 499 милиарда, 999 милиона, 965 00:32:54,370 --> 00:33:01,210 500 000 срещу нашата първоначална стойност, 500 милиарда, това е така, по дяволите близо. 966 00:33:01,210 --> 00:33:06,850 Нали така? п карирани, разделено на 2 дава us-- или по-скоро, п карирани, разделено на две 967 00:33:06,850 --> 00:33:08,370 ни даде 500 милиарда. 968 00:33:08,370 --> 00:33:13,510 Това е дяволски много близки до 499 999 500 000, 969 00:33:13,510 --> 00:33:17,970 което означава изваждане на разстояние 500 000, или по-общо, изваждане на разстояние 970 00:33:17,970 --> 00:33:20,010 п издялан, наистина е голяма работа. 971 00:33:20,010 --> 00:33:22,490 The п квадрат прави тези числа растат много по-бързо. 972 00:33:22,490 --> 00:33:25,790 >> Сега, това е важно само доколкото както ние, като компютърни специалисти, 973 00:33:25,790 --> 00:33:29,350 По принцип не се случва да се грижи толкова много около нюансите на тези формули 974 00:33:29,350 --> 00:33:31,400 и точно това, което точни отговори са. 975 00:33:31,400 --> 00:33:33,390 Ние само, че се полагат грижи, знаеш ли какво? 976 00:33:33,390 --> 00:33:37,810 В края на деня, тази формула е от порядъка на п квадрат. 977 00:33:37,810 --> 00:33:39,350 >> Да, ние сме се дели на две в там. 978 00:33:39,350 --> 00:33:41,360 Да, ние сме се извади извън п минус 2. 979 00:33:41,360 --> 00:33:46,860 Но в края на деня, терминът че наистина ни боли и да ни струва 980 00:33:46,860 --> 00:33:48,995 много стъпки е, че квадратен план. 981 00:33:48,995 --> 00:33:51,370 И така, какво компютърен учен ще обикновено правя 982 00:33:51,370 --> 00:33:54,160 се игнорира всички тези, по-малки поръчки, термини 983 00:33:54,160 --> 00:33:56,900 и просто да погледнете този, който допринася най-много за цената. 984 00:33:56,900 --> 00:34:00,530 >> И това е хубаво, защото можем Сега се говори в много по-голяма универсалност 985 00:34:00,530 --> 00:34:02,470 за алгоритми, както и да ги сравните. 986 00:34:02,470 --> 00:34:04,550 А фактът, че аз съм използването на тази O е умишлено. 987 00:34:04,550 --> 00:34:06,680 Когато казвам на реда на, аз съм по-специално 988 00:34:06,680 --> 00:34:09,560 отнасящи се до нещо нарича голяма О. И голяма O 989 00:34:09,560 --> 00:34:14,090 е нотация че компютър учен използва, за да опише 990 00:34:14,090 --> 00:34:16,710 горна граница на нещо. 991 00:34:16,710 --> 00:34:21,150 >> Така че, ако се каже, че един алгоритъм е в голяма О п квадрат, 992 00:34:21,150 --> 00:34:23,380 както аз предложих просто Преди миг, че средства 993 00:34:23,380 --> 00:34:27,710 че от гледна точка на неговото движение време или на нейната ефективност, 994 00:34:27,710 --> 00:34:30,090 отнема от порядъка п квадрат стъпки. 995 00:34:30,090 --> 00:34:31,420 Може би повече, може би по-малко. 996 00:34:31,420 --> 00:34:33,435 Но това е от порядъка на п квадрат. 997 00:34:33,435 --> 00:34:34,560 И това е горната граница. 998 00:34:34,560 --> 00:34:36,530 Това няма да бъде по-болезнено от това. 999 00:34:36,530 --> 00:34:40,800 Това няма да е п кубчета, или 2 до п, или нещо много по-голямо. 1000 00:34:40,800 --> 00:34:43,800 Това е горна граница на каквото и да е цена. 1001 00:34:43,800 --> 00:34:46,150 Така че има предвид, че, нека разгледа само няколко примера. 1002 00:34:46,150 --> 00:34:49,820 И това е само ограничен списък на много чести, работещи пъти 1003 00:34:49,820 --> 00:34:52,870 за алгоритми, които е писано да бъде илюстративни за някои неща, с които сме се 1004 00:34:52,870 --> 00:34:53,600 Вече видяхме. 1005 00:34:53,600 --> 00:34:58,060 >> Така например, в случай на Избор на вид, това, което аз твърдя тук 1006 00:34:58,060 --> 00:35:02,250 е бягане, че изборът на сортиране време е от порядъка на п квадрат. 1007 00:35:02,250 --> 00:35:06,260 В най-лошия случай, аз отивам да има цял куп случайни числа тук. 1008 00:35:06,260 --> 00:35:08,600 И както видяхме математически, ако аз държа ходене 1009 00:35:08,600 --> 00:35:11,310 в списъка, през списък, избора на следващия най-малкият 1010 00:35:11,310 --> 00:35:14,410 елемент, отново и отново, ако съм всъщност запиша всички стъпки 1011 00:35:14,410 --> 00:35:18,750 Аз съм като, както аз предложих formulaically преди, това е от порядъка на п квадрат 1012 00:35:18,750 --> 00:35:20,370 стъпки, които аз съм като. 1013 00:35:20,370 --> 00:35:24,520 >> И се оказва, че балон сортиране и сортиране чрез вмъкване 1014 00:35:24,520 --> 00:35:27,370 са също толкова бавно в най-лошия случай. 1015 00:35:27,370 --> 00:35:32,040 Помислете, например, сортиране чрез вмъкване, последния алгоритъм ние разгледани, 1016 00:35:32,040 --> 00:35:35,500 които трябваше да разгледаме елемента, и след това го поставете там, където принадлежи. 1017 00:35:35,500 --> 00:35:38,720 И тогава ще погледна следващия елемент, и я поставили там, където принадлежи. 1018 00:35:38,720 --> 00:35:40,990 >> Така че, помисли за най-добрия възможен сценарий. 1019 00:35:40,990 --> 00:35:45,590 Да предположим, че бях ми доброволци се наредят буквално като този, от едно до осем, 1020 00:35:45,590 --> 00:35:47,440 вече сортирани. 1021 00:35:47,440 --> 00:35:51,300 Колко стъпки е вмъкване на сортиране ще отнеме, за да сортирате осем души, 1022 00:35:51,300 --> 00:35:55,640 ако те пристигнат на сцената търси по този начин? 1023 00:35:55,640 --> 00:35:57,410 >> Осем души вече са подредени. 1024 00:35:57,410 --> 00:35:58,760 И аз използвам сортиране чрез вмъкване. 1025 00:35:58,760 --> 00:36:02,180 Това последното на алгоритмите. 1026 00:36:02,180 --> 00:36:03,640 Ами, нека да установят отново доста бързо. 1027 00:36:03,640 --> 00:36:05,504 Така че ако започна тук, виждам една. 1028 00:36:05,504 --> 00:36:06,420 Когато човек принадлежи? 1029 00:36:06,420 --> 00:36:07,730 Той принадлежи точно тук. 1030 00:36:07,730 --> 00:36:08,330 Виждам две. 1031 00:36:08,330 --> 00:36:09,660 Откъде идва два принадлежат? 1032 00:36:09,660 --> 00:36:10,260 Точно тук. 1033 00:36:10,260 --> 00:36:10,900 Виждам три. 1034 00:36:10,900 --> 00:36:11,920 Откъде идва три принадлежат? 1035 00:36:11,920 --> 00:36:12,480 Точно тук. 1036 00:36:12,480 --> 00:36:13,100 >> Виждам четири. 1037 00:36:13,100 --> 00:36:13,600 Точно тук. 1038 00:36:13,600 --> 00:36:15,660 Пет, шест, седем, осем. 1039 00:36:15,660 --> 00:36:17,320 Няма причина да се повтарям. 1040 00:36:17,320 --> 00:36:21,260 И така, как много стъпки е, че по отношение на N? 1041 00:36:21,260 --> 00:36:23,870 Това е от порядъка на п стъпки, нали? N минус 1. 1042 00:36:23,870 --> 00:36:27,567 Но аз взех един линеен номер от стъпки, и сега съм свършен. 1043 00:36:27,567 --> 00:36:28,900 Така че това е най-добрия случай, все пак. 1044 00:36:28,900 --> 00:36:29,983 Какво ще кажете за най-лошия случай? 1045 00:36:29,983 --> 00:36:32,730 Какво осем са били там, а седем са били там, 1046 00:36:32,730 --> 00:36:35,840 и едно и две са тук, така че че списъкът беше наистина обърнати? 1047 00:36:35,840 --> 00:36:38,300 >> Е, какво ще се случи в действителност ако това е номерът? 1048 00:36:38,300 --> 00:36:41,300 И ние ще направим само няколко примера. 1049 00:36:41,300 --> 00:36:49,300 Какво става, ако наистина, броят осем е тук, а number-- Опа. 1050 00:36:49,300 --> 00:36:52,660 1051 00:36:52,660 --> 00:36:56,430 И какво, ако наистина броя осем е чак тук, 1052 00:36:56,430 --> 00:36:57,790 и аз съм с вкарване подреди? 1053 00:36:57,790 --> 00:36:58,290 >> ДОБРЕ. 1054 00:36:58,290 --> 00:37:00,280 Аз твърдя, в момента тя е на мястото си. 1055 00:37:00,280 --> 00:37:03,152 Но сега, когато се seven-- седем отидете? 1056 00:37:03,152 --> 00:37:04,360 Разбира се, тя отива тук. 1057 00:37:04,360 --> 00:37:06,760 Така че аз трябва да се движат и осем над едно място. 1058 00:37:06,760 --> 00:37:08,554 Сега шест, къде отиде? 1059 00:37:08,554 --> 00:37:09,220 Е, добре. 1060 00:37:09,220 --> 00:37:13,150 Сега, аз трябва да се движат и осем над място, а седем над място, 1061 00:37:13,150 --> 00:37:14,440 и тогава аз цоп установени шест. 1062 00:37:14,440 --> 00:37:16,870 >> Така за първи път, то разходите ми една стъпка да оправя нещата, 1063 00:37:16,870 --> 00:37:18,570 След това ми струва две стъпки, за да оправи нещата. 1064 00:37:18,570 --> 00:37:20,370 Колко стъпки е ще предприеме, за да се определи 1065 00:37:20,370 --> 00:37:22,720 неща, които да поставят пет на правилното място? 1066 00:37:22,720 --> 00:37:23,340 Three. 1067 00:37:23,340 --> 00:37:29,520 Защото сега ще трябва да изместват една, две, три. 1068 00:37:29,520 --> 00:37:32,430 Колко стъпки е то ще отнеме да сложи четири на правилното място? 1069 00:37:32,430 --> 00:37:36,040 4 плюс 5 плюс 6, плюс 7. 1070 00:37:36,040 --> 00:37:40,260 >> И така, това е математически идентичен това, което ние, описан за избор на вид. 1071 00:37:40,260 --> 00:37:42,130 Ние имаме тази серия това е просто увеличаване. 1072 00:37:42,130 --> 00:37:45,650 1 плюс 2 плюс 3 плюс 4, или обратното, 7 плюс 6 1073 00:37:45,650 --> 00:37:52,610 плюс 5 плюс 4 добавя за днешния цели на по нареждане на п квадрат. 1074 00:37:52,610 --> 00:37:57,640 >> Така че нека да предвижда също, че метод на мехурчето е и в п квадрат. 1075 00:37:57,640 --> 00:38:01,340 Защото с балон сортиране, всеки път, когато отида в списъка, 1076 00:38:01,340 --> 00:38:03,100 Аз съм като приблизително, колко стъпки? 1077 00:38:03,100 --> 00:38:06,260 Всеки път, когато буквално ходи от там до там? 1078 00:38:06,260 --> 00:38:07,960 Около н стъпки. 1079 00:38:07,960 --> 00:38:12,650 Но колко пъти мощ I трябва да преминете през списъка? 1080 00:38:12,650 --> 00:38:13,920 >> Е, грубо п време. 1081 00:38:13,920 --> 00:38:15,680 Може би п минус 1, но около п пъти. 1082 00:38:15,680 --> 00:38:16,430 Е, защо е това? 1083 00:38:16,430 --> 00:38:19,560 Е, с балон сортиране, ако ние започваме с балон сортиране, 1084 00:38:19,560 --> 00:38:23,570 със списъка в най-лошия възможен ситуация, която отново е напълно 1085 00:38:23,570 --> 00:38:25,550 назад, какво ще се случи? 1086 00:38:25,550 --> 00:38:28,830 I проверете списъка, и номер една принадлежи целия път там. 1087 00:38:28,830 --> 00:38:33,280 >> Но с балон сортиране, колко далеч прави една преминем първата ми атака през списъка? 1088 00:38:33,280 --> 00:38:36,620 Колко петна прави той получи по-близо до правилното място? 1089 00:38:36,620 --> 00:38:37,240 Само един. 1090 00:38:37,240 --> 00:38:40,281 Така че, ако нещо през тази причина, всеки път, чрез този алгоритъм, 1091 00:38:40,281 --> 00:38:41,880 Приемащи около п стъпки на Дейвид. 1092 00:38:41,880 --> 00:38:44,940 Но колко пасове в списъка е 1093 00:38:44,940 --> 00:38:49,060 ще вземе за един да се балон наляво където принадлежи? 1094 00:38:49,060 --> 00:38:51,840 >> Той трябва да се движат като, п пространства по този начин. 1095 00:38:51,840 --> 00:38:57,960 Така че просто да се направи сортиране на списъка, Имам да ходи напред-назад н пъти. 1096 00:38:57,960 --> 00:39:01,540 И всеки път, аз съм погледнете в наш елементи. 1097 00:39:01,540 --> 00:39:05,410 Така правят неща н н пъти по реда на N квадрат. 1098 00:39:05,410 --> 00:39:07,220 >> Сега, ние ще видим в някои на шортите, че 1099 00:39:07,220 --> 00:39:10,440 са вградени в следващия проблем е CS50 зададете, друг подход към тях, 1100 00:39:10,440 --> 00:39:13,490 но за сега, нека просто да разгледа някои други, работещи пъти, 1101 00:39:13,490 --> 00:39:16,840 особено ако тези вземат сортиране малко време, за да потънат инча 1102 00:39:16,840 --> 00:39:21,790 Какво е един алгоритъм, които вече сме виждали който взема от порядъка на п стъпки? 1103 00:39:21,790 --> 00:39:27,560 >> Какво трябва да се вземат линеен номер на стъпки, които сме виждали до този момент? 1104 00:39:27,560 --> 00:39:29,350 Какво е това? 1105 00:39:29,350 --> 00:39:30,480 Търсене на телефонния указател. 1106 00:39:30,480 --> 00:39:31,390 Първият алгоритъм. 1107 00:39:31,390 --> 00:39:31,560 Нали така? 1108 00:39:31,560 --> 00:39:33,650 Къде сме линейно търсите Майк Смит? 1109 00:39:33,650 --> 00:39:34,150 Наистина. 1110 00:39:34,150 --> 00:39:37,180 От нула седмица, когато започнах превръщайки една страница в даден момент, 1111 00:39:37,180 --> 00:39:40,095 и дори заяви, че е вид алгоритъм линеен чувство, 1112 00:39:40,095 --> 00:39:42,720 и ние имахме, че картината на дъска с директен червен линия 1113 00:39:42,720 --> 00:39:44,678 и правата жълтото линия, тези, които наистина са били 1114 00:39:44,678 --> 00:39:46,810 алгоритми, които са в голяма О п. 1115 00:39:46,810 --> 00:39:50,680 >> Защото, за да намерите Mike Smith в телефонен Книга от п страници, в най-лошия случай, 1116 00:39:50,680 --> 00:39:52,422 може да ме п стъпки предприема. 1117 00:39:52,422 --> 00:39:53,630 Ами като посещаемостта? 1118 00:39:53,630 --> 00:39:55,790 Едно две три четири пет шест. 1119 00:39:55,790 --> 00:39:59,420 Какво е времето за работа на този алгоритъм за вземане на посещаемостта? 1120 00:39:59,420 --> 00:40:03,070 Голям О М, защото на теория I Трябва да отбележим всички в залата. 1121 00:40:03,070 --> 00:40:05,861 >> Сега като настрана, какво да кажем за друга оптимизация от нула седмица? 1122 00:40:05,861 --> 00:40:08,117 Две, четири, шест, осем, 10, 12. 1123 00:40:08,117 --> 00:40:10,200 A компютърен специалист би осъзнават, чакай малко, 1124 00:40:10,200 --> 00:40:12,320 това е от порядъка на N, разделено на два етапа. 1125 00:40:12,320 --> 00:40:12,820 Нали така? 1126 00:40:12,820 --> 00:40:14,444 Защото аз съм това двама души в даден момент. 1127 00:40:14,444 --> 00:40:17,015 Но ние ще пренебрегнем тези по-ниски условия за поръчки, 1128 00:40:17,015 --> 00:40:19,140 и ние просто ще изхвърлите разделете на две, 1129 00:40:19,140 --> 00:40:21,830 и само да кажа, голяма O на п че за алгоритъм, както добре. 1130 00:40:21,830 --> 00:40:22,760 >> Какво ще кажете за това? 1131 00:40:22,760 --> 00:40:26,170 Ще прескочим някои от тях, но това, което е алгоритъм, който е дневник на п? 1132 00:40:26,170 --> 00:40:29,900 Това отне около влезте н стъпки? 1133 00:40:29,900 --> 00:40:30,870 The разделяй и владей. 1134 00:40:30,870 --> 00:40:31,369 Точно. 1135 00:40:31,369 --> 00:40:33,900 Като пример на телефонен указател в нула-рано днес седмица и, 1136 00:40:33,900 --> 00:40:36,191 където сме разделени на проблема отново и отново и отново. 1137 00:40:36,191 --> 00:40:39,070 Ние го привлече на дъската в седмицата нула като извита зелена линия, 1138 00:40:39,070 --> 00:40:41,460 и ние, каза онзи ден, че е логаритмична алгоритъм. 1139 00:40:41,460 --> 00:40:44,970 >> И наистина, номера му стъпки необходимо, за да извършите разделяй и владей, 1140 00:40:44,970 --> 00:40:48,610 или двоично търсене, тъй като ние ще започнем наричайки го, като в телефонния указател, 1141 00:40:48,610 --> 00:40:50,680 е от порядъка на дневника и стъпки. 1142 00:40:50,680 --> 00:40:52,470 И това е малко странно един. 1143 00:40:52,470 --> 00:40:54,910 >> Какво става с една стъпка, или по-специално 1144 00:40:54,910 --> 00:40:56,240 постоянна редица стъпки? 1145 00:40:56,240 --> 00:40:58,865 Може би това е две, може би това е три, но компютърен учен просто 1146 00:40:58,865 --> 00:41:01,423 той опростява толкова голям O на 1, някои постоянен брой стъпки. 1147 00:41:01,423 --> 00:41:04,256 Каква е нещо, което може да направи това отнема постоянен брой стъпки? 1148 00:41:04,256 --> 00:41:08,030 1149 00:41:08,030 --> 00:41:10,930 >> Какво е времето за работа на пляскайки? 1150 00:41:10,930 --> 00:41:11,920 Constant време. 1151 00:41:11,920 --> 00:41:12,420 Нали така? 1152 00:41:12,420 --> 00:41:15,490 Подобно на това, което е времето за работа на прави нищо, че отнема само един 1153 00:41:15,490 --> 00:41:18,570 операция, като отпечатате F Hello World. 1154 00:41:18,570 --> 00:41:24,110 Това може да се каже, че константно време, освен ако не е по-малко от ъглов случай с щампа F, 1155 00:41:24,110 --> 00:41:28,260 това, което биха могли времето за изпълнение от печат F действително да бъде? 1156 00:41:28,260 --> 00:41:28,790 И защо? 1157 00:41:28,790 --> 00:41:30,550 Какво е п измервателна в този случай? 1158 00:41:30,550 --> 00:41:32,251 >> АУДИТОРИЯ: [недоловим]. 1159 00:41:32,251 --> 00:41:33,250 DAVID J. Malan: Точно така. 1160 00:41:33,250 --> 00:41:34,900 Броят на символите ние искаме да отпечатате. 1161 00:41:34,900 --> 00:41:36,191 Така че това е много в зависимост от контекста. 1162 00:41:36,191 --> 00:41:39,910 Днес, ние сме били с акцент върху много букви и цифри, тук на дъската. 1163 00:41:39,910 --> 00:41:43,540 Но това може да бъде и герои в действително низ. 1164 00:41:43,540 --> 00:41:46,420 Така се оказва, че има друг мярка, която ще започне да се грижат за, 1165 00:41:46,420 --> 00:41:48,530 и това е точно обратното на големия О, така да се каже. 1166 00:41:48,530 --> 00:41:50,120 >> Това е омега нотация. 1167 00:41:50,120 --> 00:41:53,380 Като има предвид големия O означава това, което е, на горна граница на времето си на работа? 1168 00:41:53,380 --> 00:41:55,580 Максимално, колко време може да отнеме нещо? 1169 00:41:55,580 --> 00:41:59,250 Omega-- съжалявам това продължава да идва up-- е обратното на това, 1170 00:41:59,250 --> 00:42:02,960 при което тя е по-ниска граница на период от време може да отнеме нещо. 1171 00:42:02,960 --> 00:42:10,480 >> So. Например, какво е алгоритъм който взема винаги п квадрат стъпки? 1172 00:42:10,480 --> 00:42:15,600 Е, един от алгоритмите, които сме виждали Днес, в действителност, може да бъде и това. 1173 00:42:15,600 --> 00:42:16,720 Избор на сортиране. 1174 00:42:16,720 --> 00:42:18,270 Избор на сортиране е доста глупаво. 1175 00:42:18,270 --> 00:42:21,760 Дори ако algorithm-- съжалявам, дори и ако масивът е вече подредени, 1176 00:42:21,760 --> 00:42:24,150 Избор на вид ще запази разхождах из списъка 1177 00:42:24,150 --> 00:42:28,907 да се уверите, че има най-малките елемент отново и отново и отново. 1178 00:42:28,907 --> 00:42:31,740 И въпреки че на хора при аудитория знаете, че, чакай малко, 1179 00:42:31,740 --> 00:42:33,948 вие вече премина малкия елемент, компютърът 1180 00:42:33,948 --> 00:42:37,300 не знае, че докато тя изглежда през целия път списъка. 1181 00:42:37,300 --> 00:42:40,240 По същия начин, долна граница, която може също така да се вземе предвид 1182 00:42:40,240 --> 00:42:42,000 може да бъде линейно време. 1183 00:42:42,000 --> 00:42:48,260 >> Колко време отнема да се подреди наш елементи в най-добрия 1184 00:42:48,260 --> 00:42:52,420 При използване на нещо като балон подреди? 1185 00:42:52,420 --> 00:42:54,280 Да предположим, че вашия списък вече е сортиран. 1186 00:42:54,280 --> 00:42:56,696 Казахме балон подреди поема реда на N квадрат стъпки. 1187 00:42:56,696 --> 00:42:59,640 Но какво, ако той вече е сортирано? 1188 00:42:59,640 --> 00:43:02,310 Ами ако ти осъзнаваш, след едно преминаване през масива 1189 00:43:02,310 --> 00:43:03,540 че сте прави не суапове? 1190 00:43:03,540 --> 00:43:05,970 Имате ли нужда да продължат да правят повече преминавания? 1191 00:43:05,970 --> 00:43:06,470 >> Не. 1192 00:43:06,470 --> 00:43:10,340 Така че по-ниска граница на метод на мехурчето Може да се каже, за да бъде линейна. 1193 00:43:10,340 --> 00:43:11,830 Омега на п. 1194 00:43:11,830 --> 00:43:14,450 И ние можем да погледнем други от тях, както добре. 1195 00:43:14,450 --> 00:43:17,990 Така че нека да хвърлим един бърз поглед най-просто визуализация тук 1196 00:43:17,990 --> 00:43:20,790 да се види как те се отличат. 1197 00:43:20,790 --> 00:43:24,592 Отивам да сляза тук в тази страница, която е на разположение на интернет страницата на C50, 1198 00:43:24,592 --> 00:43:27,550 но то ще бъде болка, за да получите работи, тъй като тя използва технология, наречена 1199 00:43:27,550 --> 00:43:30,560 Java аплети, което е до голяма степен не се поддържа тези дни, 1200 00:43:30,560 --> 00:43:32,730 най-малко от Chrome и някои други. 1201 00:43:32,730 --> 00:43:37,070 >> И нека да вървим напред и да се ускори този и обясни какво се случва. 1202 00:43:37,070 --> 00:43:40,840 Това е демонстрация на балон сортиране, първият алгоритъм ще погледна. 1203 00:43:40,840 --> 00:43:43,950 И това е визуализация това, че всеки на тези пръти представлява номер. 1204 00:43:43,950 --> 00:43:45,710 Колкото по-голям бар, толкова по-големи номера. 1205 00:43:45,710 --> 00:43:47,520 Колкото по-малка бара, по-малък номер. 1206 00:43:47,520 --> 00:43:50,353 И това, което можете да видите визуално, дори въпреки че това се случва супер бързо, 1207 00:43:50,353 --> 00:43:53,699 е, че червената лента е като мен, ходене напред и назад за определяне на проблеми. 1208 00:43:53,699 --> 00:43:56,740 Можете да видите, че по-големите елементи са наистина ври до правото, 1209 00:43:56,740 --> 00:43:59,650 и по-малки елементи се надига в ляво. 1210 00:43:59,650 --> 00:44:01,870 И тук, ако ние всъщност изглежда по-тясно сътрудничество, 1211 00:44:01,870 --> 00:44:04,330 всъщност можем да преброим брой сравнения и суапове 1212 00:44:04,330 --> 00:44:05,350 които са били направени. 1213 00:44:05,350 --> 00:44:07,360 >> Но вместо това, нека да погледнем при втория алгоритъм 1214 00:44:07,360 --> 00:44:11,240 разгледахме по-рано с нашите доброволци, селекция за сортиране. 1215 00:44:11,240 --> 00:44:13,500 Визуално, тя има много по-различен ефект. 1216 00:44:13,500 --> 00:44:16,820 Но това е, отново, много интуитивен, в да пазим избора на следващия най-малкият 1217 00:44:16,820 --> 00:44:18,660 елемент, и имаме малко късмет. 1218 00:44:18,660 --> 00:44:20,110 Това почувствах фундаментално по-бързо. 1219 00:44:20,110 --> 00:44:22,840 Но ако ние се завтече това отново и отново и отново с много входове, 1220 00:44:22,840 --> 00:44:26,680 ще видим, че това е наистина все още в голяма O на п квадрат. 1221 00:44:26,680 --> 00:44:29,920 >> Нека да направим едно последно една тук, сортиране чрез вмъкване, 1222 00:44:29,920 --> 00:44:33,180 което е третият алгоритъм ще погледна, и изземване 1223 00:44:33,180 --> 00:44:36,700 че това се занимава с елементи, тъй като им се сблъсква, 1224 00:44:36,700 --> 00:44:39,290 Но след това може би смени нещата да се правят по стаите, 1225 00:44:39,290 --> 00:44:41,660 вмъкване на елементи, където им е мястото. 1226 00:44:41,660 --> 00:44:45,330 >> И това също завършва давайки краен резултат. Сега всички три от тези, 1227 00:44:45,330 --> 00:44:46,490 усети доста бързо. 1228 00:44:46,490 --> 00:44:48,740 И наистина, аз ги прокара в един доста добър клип. 1229 00:44:48,740 --> 00:44:52,510 Но в основата си, всички те са доста ужасно, за да бъдем честни. 1230 00:44:52,510 --> 00:44:56,960 Всички тези алгоритми досега които работят в големия O на п квадрат 1231 00:44:56,960 --> 00:44:59,270 отнеме доста малко време, за да работи в края. 1232 00:44:59,270 --> 00:45:01,920 >> И наистина, ние можем да видим и се чувствам по този накрая 1233 00:45:01,920 --> 00:45:04,090 ако аз спра тази третата и последна демонстрация. 1234 00:45:04,090 --> 00:45:05,840 Това е друга визуализация, което се случва 1235 00:45:05,840 --> 00:45:08,500 за да се покаже балонче подредени в ляво, подбор подреди по средата, 1236 00:45:08,500 --> 00:45:13,410 и нещо, като един от нашите ръката повдига по-рано предложи, 1237 00:45:13,410 --> 00:45:15,020 сортиране чрез сливане в дясно. 1238 00:45:15,020 --> 00:45:16,937 A разделяй и владей стратегия в дясно. 1239 00:45:16,937 --> 00:45:19,520 И това е, в действителност, това, което сме ще разгледаме в сряда. 1240 00:45:19,520 --> 00:45:21,990 Но нека си време те да вървят паралелно. 1241 00:45:21,990 --> 00:45:26,765 Това е приблизително същия брой елементи, всички работещи едновременно. 1242 00:45:26,765 --> 00:45:30,940 1243 00:45:30,940 --> 00:45:34,440 Bubble подреди срещу селекция подреди срещу сливането на сортиране. 1244 00:45:34,440 --> 00:45:36,760 >> Сега, всички те са течаща на теория в същото време. 1245 00:45:36,760 --> 00:45:39,830 Процесорът работи по най- със същата скорост, но вие 1246 00:45:39,830 --> 00:45:44,014 може да се почувства как скучно това е много бързо ще стане, 1247 00:45:44,014 --> 00:45:45,930 и колко бързо, когато ние се инжектира малко на седмица 1248 00:45:45,930 --> 00:45:49,330 алгоритми нула може да ние ускори нещата. 1249 00:45:49,330 --> 00:45:51,760 >> А сега нека да сравни те в един последен форма. 1250 00:45:51,760 --> 00:45:55,710 Отивам да се продължи напред към страницата на CS50, където 1251 00:45:55,710 --> 00:45:59,020 имаме този последен линк за днес, където някой в ​​интернет 1252 00:45:59,020 --> 00:46:03,960 Любезно се сглоби видеоклип, който улавя какво различно сортиране 1253 00:46:03,960 --> 00:46:07,510 алгоритми звучи като. 1254 00:46:07,510 --> 00:46:09,577 Това е сортиране чрез вмъкване. 1255 00:46:09,577 --> 00:46:12,072 >> [Сигнализиращ] 1256 00:46:12,072 --> 00:46:13,070 1257 00:46:13,070 --> 00:46:16,850 >> Чрез която можете да започнете прилагането на честота въз основа на височината на лентата с бар. 1258 00:46:16,850 --> 00:46:19,826 Това е метод на мехурчето. 1259 00:46:19,826 --> 00:46:21,822 >> [Ненормален сигнализиращ] 1260 00:46:21,822 --> 00:46:33,299 1261 00:46:33,299 --> 00:46:45,774 >> Очаквайте следващата is-- пришествие до следващия is-- селекция сортиране, 1262 00:46:45,774 --> 00:46:48,820 където отново ни е да изберем следващата по-малка елемент, 1263 00:46:48,820 --> 00:46:51,820 и ние можем да видим, че нарастващото от ляво на дясно. 1264 00:46:51,820 --> 00:47:01,120 1265 00:47:01,120 --> 00:47:04,000 >> Обединяване на сортиране, като по този начин нашият победител далеч днес. 1266 00:47:04,000 --> 00:47:09,659 1267 00:47:09,659 --> 00:47:12,450 Забележете как се раздели неща в [недоловим] половина и квартали. 1268 00:47:12,450 --> 00:47:17,510 1269 00:47:17,510 --> 00:47:21,660 Gnome сортиране, която нямаме говори, и създава визуално 1270 00:47:21,660 --> 00:47:24,450 и audally малко на различна форма и звук. 1271 00:47:24,450 --> 00:47:27,060 1272 00:47:27,060 --> 00:47:30,160 Връщайки се назад и напред, почистване на нещата. 1273 00:47:30,160 --> 00:47:32,230 Също така проверете пирамидално сортиране на интернет страницата на този човек. 1274 00:47:32,230 --> 00:47:36,100 1275 00:47:36,100 --> 00:47:36,810 >> И това е. 1276 00:47:36,810 --> 00:47:38,210 Ние ще ви видим следващия път. 1277 00:47:38,210 --> 00:47:42,647 1278 00:47:42,647 --> 00:47:48,334 >> [Свистящ И MUSIC] 1279 00:47:48,334 --> 00:50:24,839