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