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