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 >> Дејвид Џ 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 овој петок, и тука и во Кембриџ, и во Њу Хевн, 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 Естрада: Алан Естрада. 47 00:01:55,570 --> 00:01:56,778 Дејвид Џ MALAN: Алан Естрада. 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 Дејвид Џ 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 >> Дејвид Џ MALAN: Така би можело да одите напред и да се најде за нас Мајк Смит, 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 Естрада: Хм. 59 00:02:15,130 --> 00:02:17,380 Дејвид Џ MALAN: Буквално кинење на проблемот на половина. 60 00:02:17,380 --> 00:02:20,210 61 00:02:20,210 --> 00:02:22,083 >> ALAN Естрада: О. 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 >> Дејвид Џ MALAN: Во ред. 65 00:02:23,700 --> 00:02:24,200 Добро. 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 >> Дејвид Џ 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 >> Дејвид Џ MALAN: Што секција сме? 76 00:02:37,594 --> 00:02:39,150 ALAN Естрада: ауспуси, така. 77 00:02:39,150 --> 00:02:39,941 >> Дејвид Џ MALAN: Во ред. 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 Дејвид Џ MALAN: Мајк Смит. 84 00:02:52,049 --> 00:02:53,090 ALAN Естрада: Мајк Смит. 85 00:02:53,090 --> 00:02:54,760 Дејвид Џ MALAN: Сега, ние сме во хируршки. 86 00:02:54,760 --> 00:02:57,840 Сега, лекарите. 87 00:02:57,840 --> 00:02:58,340 Now-- 88 00:02:58,340 --> 00:02:59,856 >> ALAN Естрада: Let's- ајде да одиме со вистински. 89 00:02:59,856 --> 00:03:00,370 Реално. 90 00:03:00,370 --> 00:03:00,970 >> Дејвид Џ MALAN: Реал. 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 >> Дејвид Џ MALAN: На кој начин? 96 00:03:07,333 --> 00:03:08,240 ALAN Естрада: Чекај. 97 00:03:08,240 --> 00:03:08,790 М is-- нели? 98 00:03:08,790 --> 00:03:09,110 Почнавме with-- 99 00:03:09,110 --> 00:03:10,090 >> Дејвид Џ 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 >> Дејвид Џ 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 Дејвид Џ MALAN: Ова ќе учат можете да се фрлиш од столот. 110 00:03:21,610 --> 00:03:22,318 >> ALAN Естрада: О. 111 00:03:22,318 --> 00:03:22,890 Ох. 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 Ох. 115 00:03:25,170 --> 00:03:25,669 Ох. 116 00:03:25,669 --> 00:03:26,812 Оваа is-- Добро, јас го добив. 117 00:03:26,812 --> 00:03:27,520 Смит тука? 118 00:03:27,520 --> 00:03:28,894 >> Дејвид Џ MALAN: Смит, ви благодарам. 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 >> Дејвид Џ MALAN: Ох, ќе морате Смит. 125 00:03:32,580 --> 00:03:33,415 ВО РЕД. 126 00:03:33,415 --> 00:03:34,040 >> ALAN Естрада: Да, јас Смит доби токму тука. 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 >> Дејвид Џ 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 Дејвид Џ 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 Смит. 137 00:03:45,830 --> 00:03:46,310 >> ALAN Естрада: Смит. 138 00:03:46,310 --> 00:03:46,750 >> Дејвид Џ MALAN: Смит. 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 Ох. 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 Дејвид Џ 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 >> Дејвид Џ MALAN: Ница. 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 >> Дејвид Џ 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 Дејвид Џ 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 Дејвид Џ MALAN: Во ред. 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 >> Дејвид Џ 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 И така, ако телефонот книга имаше можеби и 1.000 страници, 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 Дејвид Џ 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 се подредени од А до Z, и по азбучен ред помеѓу. 187 00:05:11,230 --> 00:05:13,100 Но, денес, ние сега се бара На прашањето, добро, 188 00:05:13,100 --> 00:05:16,170 како го направи Веризон или на телефон компанијата да го во ваква состојба? 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 колку тоа го правеше на трошоците Веризон или некој друг 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 Тоа не е важно ако угледување Мајк Смит 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 >> И ако Јордан всушност би можеле да ни се придружат до тука на сцена. 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 Дејвид Џ MALAN: Каролина, ајде до. 208 00:05:58,691 --> 00:06:02,070 И ќе се приклучи од страна на мене и Јордан тука. 209 00:06:02,070 --> 00:06:03,800 Каролина, ви благодарам. 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 дека ФАС користи за администрирање одредени завршните испити. 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, Д, Ј, Б, по целиот пат од A до 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 С е почетокот. 222 00:06:35,050 --> 00:06:42,410 Б. Ј пред Л Б, П. 223 00:06:42,410 --> 00:06:45,140 >> Дејвид Џ 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 Р. 228 00:06:57,299 --> 00:06:58,090 Дејвид Џ MALAN: Во ред. 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 >> Дејвид Џ MALAN: Во ред. 232 00:07:02,564 --> 00:07:03,064 >> CAROLINE: О. 233 00:07:03,064 --> 00:07:04,120 Дејвид Џ MALAN: О, добро. 234 00:07:04,120 --> 00:07:04,970 >> CAROLINE: Е. 235 00:07:04,970 --> 00:07:06,730 >> Дејвид Џ MALAN: Е, Ф Да. 236 00:07:06,730 --> 00:07:07,620 >> CAROLINE: Т, U, В. 237 00:07:07,620 --> 00:07:10,689 >> Дејвид Џ MALAN: 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 Добро. 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: К. 246 00:07:22,270 --> 00:07:22,980 Дејвид Џ MALAN: Во ред. 247 00:07:22,980 --> 00:07:25,070 К. Па ти си вид на изборот нив еден по друг, 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 >> Дејвид Џ MALAN: Во ред. 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: Г. 255 00:07:32,409 --> 00:07:33,700 Дејвид Џ MALAN: G е одеше лево. 256 00:07:33,700 --> 00:07:36,017 S ќе десно. 257 00:07:36,017 --> 00:07:37,642 Добро, А се оди на целиот пат замина. 258 00:07:37,642 --> 00:07:38,790 >> CAROLINE: A, B, C, D. 259 00:07:38,790 --> 00:07:39,873 >> Дејвид Џ MALAN: Сега, добро. 260 00:07:39,873 --> 00:07:43,260 Имаме А, Б, В В случува таму долу. 261 00:07:43,260 --> 00:07:45,566 Добро, Т. 262 00:07:45,566 --> 00:07:46,611 >> CAROLINE: H, I, Џ 263 00:07:46,611 --> 00:07:47,860 Дејвид Џ MALAN: H, I, Ј Добро. 264 00:07:47,860 --> 00:07:49,160 CAROLINE: Во центарот, јас сум gonna-- 265 00:07:49,160 --> 00:07:50,000 Дејвид Џ MALAN: Во ред. 266 00:07:50,000 --> 00:07:52,375 Па сега, ние ќе треба да се вид на спојување на овие различни купови. 267 00:07:52,375 --> 00:08:00,730 Па A до C, а потоа ќе видам D, и Е, и F и G, и H, и I. Ница. 268 00:08:00,730 --> 00:08:05,540 Ј, К И тогаш, овој куп е наопаку, но тоа е во ред. 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 >> Дејвид Џ MALAN: Одлично. 275 00:08:11,880 --> 00:08:14,122 Така голема благодарност до Каролин за сортирање овие. 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 Па сега ајде да се разгледа за момент Каролин како помина правејќи дека, 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 И штом таа се најде некои проксимална писма, оние 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 Брзо волонтер. 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 >> Дејвид Џ 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 Добро. 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: Може ли unclick врата? 335 00:10:41,020 --> 00:10:42,620 Дејвид Џ MALAN: Не, вие не може да unclick. 336 00:10:42,620 --> 00:10:43,119 TREVOR: Во ред. 337 00:10:43,119 --> 00:10:43,974 Оваа. 338 00:10:43,974 --> 00:10:45,640 Дејвид Џ 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 >> Дејвид Џ MALAN: Не 342 00:10:48,042 --> 00:10:48,450 >> TREVOR: Во ред. 343 00:10:48,450 --> 00:10:48,735 Оваа. 344 00:10:48,735 --> 00:10:49,020 >> Дејвид Џ 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 Дејвид Џ MALAN: Во ред. 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: Во ред. 365 00:11:36,090 --> 00:11:37,670 >> Дејвид Џ 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 Дејвид Џ 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 со Џеј, кои дојдоа, многу како Тревор тука, доброволно, 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 репродукција] 405 00:13:03,806 --> 00:13:05,430 Дејвид Џ MALAN: Така што помина многу добро. 406 00:13:05,430 --> 00:13:06,796 Тоа беа несортиран врати. 407 00:13:06,796 --> 00:13:08,670 И Џеј, се разбира, сето тоа се наоѓаат премногу брзо. 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 Се разбира, потоа дадовме Џеј втора шанса, 411 00:13:17,950 --> 00:13:20,320 при што се подредени на вратите, исто како што направивме за Тревор, 412 00:13:20,320 --> 00:13:22,300 и Тревор направив супер и овој пат. 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 >> -OH! 422 00:13:38,860 --> 00:13:40,800 >> - [Беззвучен] Во ред. 423 00:13:40,800 --> 00:13:46,236 Па јас ќе одам да се провери на крајот прво да се утврди дали there's-- О. 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 репродукција] 427 00:13:55,729 --> 00:13:56,520 Дејвид Џ MALAN: Во ред. 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 И така Џеј доби среќен двата пати. 431 00:14:03,270 --> 00:14:06,685 И тој, исто така, доби среќен со тоа што последната година, јас нареди некои Blu-ray дисковите 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 беше оспорена со точна Истиот проблем, иако во С.Д. 437 00:14:17,780 --> 00:14:19,360 како што наскоро ќе видиме, во тоа време. 438 00:14:19,360 --> 00:14:22,622 И ќе најдете дека не само што тој да потрае малку подолго од Џеј, 439 00:14:22,622 --> 00:14:25,580 малку подолго од Тревор, тоа беше всушност оваа прекрасна можност 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 Најди-ни бројот седум, ве молам. 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 Еден. 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 Три. 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 Седум. 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 репродукција] 487 00:16:30,360 --> 00:16:31,840 >> Дејвид Џ 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 крајна линија може да ја применувате овие идеи 1.000 влеза, еден милион влезови, 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 Две. 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 Три. 509 00:17:24,420 --> 00:17:25,400 Четири. 510 00:17:25,400 --> 00:17:27,247 Нека me-- ред, пет. 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 >> Дејвид Џ 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 >> Џозеф: Јосиф. 528 00:17:47,140 --> 00:17:49,190 >> Дејвид Џ MALAN: Јосиф, вие сте број два. 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 CYNTHIA: Синтија. 532 00:17:54,430 --> 00:17:57,548 Дејвид Џ MALAN: Синтија, број пет. 533 00:17:57,548 --> 00:17:58,452 [Беззвучен] 534 00:17:58,452 --> 00:17:59,618 Дејвид Џ MALAN: [Беззвучен]. 535 00:17:59,618 --> 00:18:00,391 Давид, број шест. 536 00:18:00,391 --> 00:18:00,890 Мет: Мат. 537 00:18:00,890 --> 00:18:02,160 Дејвид Џ 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 >> Дејвид Џ MALAN: Waverly, број осум. 541 00:18:04,470 --> 00:18:04,970 Во ред. 542 00:18:04,970 --> 00:18:06,510 Ако could-- whoops. 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 А потоа ние, главно, се piecing работите заедно. 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-- ако се потсетиме од Стандардното издание на Проблем Постави Еден, 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 Шест и осум години, во ред. 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 Еден збор пред осум години, и така што ние треба да направам? 586 00:19:36,990 --> 00:19:38,090 Ајде да се разменуваат со овие две. 587 00:19:38,090 --> 00:19:39,316 Една и осум. 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 >> Добро, јасно не. 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 Шест и еден, на ред. 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 Па две и четири се уште се во ред. 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 >> Добро. 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 Добро. 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 Еден, 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 Дејвид Џ MALAN: Жал ми е? 659 00:21:36,120 --> 00:21:37,070 ПУБЛИКАТА: Нема промени. 660 00:21:37,070 --> 00:21:38,653 Дејвид Џ 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 Можеби тоа беше голема буква, како А, или низок букви 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 Шест, не сум заинтересирана. 695 00:22:56,460 --> 00:22:57,810 Осум, не сум заинтересиран. 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 Седум, не се заинтересирани. 700 00:23:03,450 --> 00:23:04,530 Пет, не се заинтересирани. 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 >> Дејвид Џ 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 >> Дејвид Џ 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 Дејвид Џ MALAN: Во ред. 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 >> Дејвид Џ 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 >> Џозеф: Јосиф. 757 00:24:49,760 --> 00:24:50,085 >> Дејвид Џ MALAN: Јосиф? 758 00:24:50,085 --> 00:24:52,000 Ние ќе треба да ја напушти Јосиф во место. 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 Сега четири е моменталниот најмалите. 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 Дејвид Џ MALAN: Серена, ако може имате своја број и swap with-- 769 00:25:10,620 --> 00:25:11,550 KALSANG: Kalsang. 770 00:25:11,550 --> 00:25:12,940 Дејвид Џ 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, Dun, Dun, 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, Dun, Dun, 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, Dun, Dun, Dun. 782 00:25:33,631 --> 00:25:34,880 Шест е најмалиот. 783 00:25:34,880 --> 00:25:35,520 Добро. 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 >> Значи она што ние сме само направено од страна iteratively избирање на еден елемент по друг 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 Без истурам од buzzwords или вид на одговори кои се веќе познати, 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 Дејвид Џ 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 >> Џозеф: Јосиф. 830 00:27:25,090 --> 00:27:26,030 >> Дејвид Џ MALAN: Јосиф, ако може да се чекор назад 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 Совршен. 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 >> Дејвид Џ 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 Па тоа е како n 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 треба да ги преземат сите n 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 И така математички, ако n е бројот на елементите или броеви 926 00:31:06,900 --> 00:31:11,990 што почнавме со тоа, може да се замисли дека ова е иста како и n минус 1, 927 00:31:11,990 --> 00:31:14,250 плус n минус 2 чекори, n плус минус 3 чекори, 928 00:31:14,250 --> 00:31:16,780 плус n минус 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 е само n квадрат минус n поделено со 2. 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 Тоа е n квадрат поделен со 2 минус n / 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, минус n / 2. 947 00:32:02,910 --> 00:32:05,080 >> Но, генерално, ако n е ќе биде голема вредност, 948 00:32:05,080 --> 00:32:08,740 Одам да се тврди дека n квадрат ќе биде доминантен фактор. 949 00:32:08,740 --> 00:32:10,490 Тоа е само ќе да биде поголем придонес 950 00:32:10,490 --> 00:32:12,877 на бројот на чекори од n / 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 Јас би го приклучиш на милиони евра, така што можам да добијам милион квадрат поделен со 2, 960 00:32:34,120 --> 00:32:35,990 минус еден милион поделено со 2. 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.000.000.000, 999 милиони евра, 965 00:32:54,370 --> 00:33:01,210 500.000 против нашата оригинална вредност, 500 милијарди долари, што е толку проклето блиску. 966 00:33:01,210 --> 00:33:06,850 Нели? n квадрат поделен со 2 дава us-- или подобро кажано, n квадрат поделен со 2 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 n квадрат, навистина не е голема работа. 971 00:33:20,010 --> 00:33:22,490 На n квадрат прави овие броеви расте навистина брзо. 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 На крајот од денот, оваа формула е од редот на n квадрат. 977 00:33:37,810 --> 00:33:39,350 >> Да, ние сме делење со 2 во таму. 978 00:33:39,350 --> 00:33:41,360 Да, ние сме одземање исклучена n минус 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 Како и фактот дека јас сум со користење на овој о е намерно. 987 00:34:04,550 --> 00:34:06,680 Кога велам од редот на, јас сум конкретно 988 00:34:06,680 --> 00:34:09,560 кои се однесуваат на нешто наречен голем О. И големи О 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 >> Па ако може да се каже дека еден алгоритам е во голема О од n квадрат, 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 што е потребно за да од n квадрат чекори. 995 00:34:30,090 --> 00:34:31,420 Можеби и повеќе, можеби и помалку. 996 00:34:31,420 --> 00:34:33,435 Но, тоа е од редот на n квадрат. 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 Тоа нема да биде n коцки, или 2 на n, или нешто многу поголемо. 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 се извршува на тој вид на селекција време е од редот на n квадрат. 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 пред, тоа е од редот на n квадрат 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 чекори, нели? 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-- whoops. 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 Три. 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 придонесува за денешните цели да по наредба на n квадрат. 1074 00:37:52,610 --> 00:37:57,640 >> Па дозволете ми да пропише дека премногу меур вид е, исто така, во n квадрат. 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 Грубо n чекори. 1079 00:38:07,960 --> 00:38:12,650 Но колку пати би можел треба да поминат низ оваа листа? 1080 00:38:12,650 --> 00:38:13,920 >> Па, грубо n време. 1081 00:38:13,920 --> 00:38:15,680 Можеби n минус 1, но грубо n пати. 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 Одам низ листата, и број некој припаѓа на целиот пат таму. 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 Земајќи приближно n чекори на Давид. 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 >> Тој мора да се движат како, n простори на овој начин. 1095 00:38:51,840 --> 00:38:57,960 Па само да се направи за сортирање на листата, Морам да одиме напред и назад n пати. 1096 00:38:57,960 --> 00:39:01,540 И секој пат, јас сум гледање на n елементи. 1097 00:39:01,540 --> 00:39:05,410 Затоа направете n работите n пати на редоследот на 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 Што е алгоритам веќе видовме кој што се од редот на n чекори? 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 алгоритми, кои се во голема О на n. 1115 00:39:46,810 --> 00:39:50,680 >> Бидејќи да се најде Мајк Смит во телефонот книга на n-страници, во најлош случај, 1116 00:39:50,680 --> 00:39:52,422 може да ме n чекори земе. 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 Биг О на n, затоа што во теорија, треба да се истакне сите присутни во просторијата. 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 Компјутерски научник би реализира, почекајте една минута, 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 и ние сме само ќе фрлаат подели со 2, 1129 00:40:19,140 --> 00:40:21,830 и само велат, големи О на n за тоа алгоритам, како и. 1130 00:40:21,830 --> 00:40:22,760 >> Она што за оваа? 1131 00:40:22,760 --> 00:40:26,170 Ние ќе ги прескокне некои од овие, но она што беше алгоритам кој беше дневникот на n? 1132 00:40:26,170 --> 00:40:29,900 Кои се околу логирате n чекори? 1133 00:40:29,900 --> 00:40:30,870 На поделба и освојување. 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 ги поедноставува како голема О од 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 Временска константа. 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 Здраво светот. 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 Што е n мерење во тој случај? 1158 00:41:30,550 --> 00:41:32,251 >> ПУБЛИКАТА: [Беззвучен]. 1159 00:41:32,251 --> 00:41:33,250 Дејвид Џ 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 Со оглед на големите О значи што е, на горна граница на вашето време на работа? 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. на пример, што е еден алгоритам кој што се секогаш n квадрат чекори? 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 >> Колку време е потребно за да вид n елементи во најдобар 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 Омега на n. 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 барем со хром и некои други. 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 ќе видите дека тоа е навистина уште е во голема О од n квадрат. 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 Сите од овие алгоритми досега кои работат во големите О од n квадрат 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 А подели, па владеј стратегија на десната страна. 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 Меур вид vs избор вид vs спојат вид. 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 >> [Beeping] 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 >> [Наснован beeping] 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 Исто така проверете heapsort на веб-страницата на овој човек е. 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 >> [Whooshing И МУЗИКА] 1279 00:47:48,334 --> 00:50:24,839