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