1 00:00:00,000 --> 00:00:11,270 2 00:00:11,270 --> 00:00:14,910 >> ПРЕДСЕДНИК: Добро, ово је ЦС50. 3 00:00:14,910 --> 00:00:19,020 То је крај недеље три, а ако нисте узели већ предност, 4 00:00:19,020 --> 00:00:21,790 знају да ће бити ручак овог петка као и обично, где 5 00:00:21,790 --> 00:00:25,430 можете уживати добар разговор и храна на Фире анд Ице 6 00:00:25,430 --> 00:00:27,980 са неким од ЦС50 је особља и школских другова. 7 00:00:27,980 --> 00:00:30,170 Главе до УРЛ овде. 8 00:00:30,170 --> 00:00:33,420 >> Сада можете да се сећате, или сте могу ускоро бити упознати са, 9 00:00:33,420 --> 00:00:35,970 ове ствари овде, што су дати се на крају 10 00:00:35,970 --> 00:00:37,850 семестра за многе класе. 11 00:00:37,850 --> 00:00:40,870 Такозвани испит блуе књига, у којој пишете своје одговоре на испите. 12 00:00:40,870 --> 00:00:44,240 Сада сам овде 26 су плаве књиге, на сваком од њих 13 00:00:44,240 --> 00:00:47,580 је написано име, од А до Ж заиста имена су тако једноставно, 14 00:00:47,580 --> 00:00:50,490 кроз З. и један од Циљеви при руци данас 15 00:00:50,490 --> 00:00:53,910 ће бити да наставе са оним смо почели у понедељак, што није 16 00:00:53,910 --> 00:00:57,830 толико гледа кода, али стварно гледајући идеје и решавање проблема. 17 00:00:57,830 --> 00:01:00,170 Један од циљева и обећања овог курса 18 00:01:00,170 --> 00:01:02,985 је да вас научи да размишљају више Пажљиво, више методично, 19 00:01:02,985 --> 00:01:05,400 и да ефикасније решава проблеме. 20 00:01:05,400 --> 00:01:09,526 И заиста, можемо то да урадимо стварно чак и без додиривања линију кода. 21 00:01:09,526 --> 00:01:12,150 Тако да имам пар слонова овде данас, наранџаста и плава, 22 00:01:12,150 --> 00:01:15,780 Ако бисмо могли да једног волонтера, можда из даље уназад него обично. 23 00:01:15,780 --> 00:01:18,070 Како би било тамо, хајде доле. 24 00:01:18,070 --> 00:01:24,180 Чији је циљ ће бити да помогне Плус управља овај испит овде. 25 00:01:24,180 --> 00:01:24,935 Како се зовеш? 26 00:01:24,935 --> 00:01:25,768 >> Публика: Мари Бетх. 27 00:01:25,768 --> 00:01:27,560 ПРЕДСЕДНИК: Мари Бетх, хајде горе. 28 00:01:27,560 --> 00:01:29,560 Пусти ме да је микрофон за тебе. 29 00:01:29,560 --> 00:01:32,172 30 00:01:32,172 --> 00:01:32,880 Драго ми је да вас упознам. 31 00:01:32,880 --> 00:01:34,005 >> ПУБЛИКА: Драго ми је. 32 00:01:34,005 --> 00:01:36,790 ПРЕДСЕДНИК: Добро, тако да имам Овде Плава књига до З, 33 00:01:36,790 --> 00:01:41,680 а ја ћу се претварати да Имам једног од ученика, 34 00:01:41,680 --> 00:01:45,770 и они долазе у нешто насумично на крају три сата испита блока, 35 00:01:45,770 --> 00:01:49,400 па они завршавају у неким Полу-Рандом Ордер овако. 36 00:01:49,400 --> 00:01:54,510 Сада је ваш посао у само тренутак иде да бити-- ово је у ствари, како су се 37 00:01:54,510 --> 00:01:56,820 окренуо у крајем класе, највероватније. 38 00:01:56,820 --> 00:02:01,120 Ваш посао сада ће бити, сасвим једноставно, да реши ове плаве књиге за нас 39 00:02:01,120 --> 00:02:05,220 од А до З. 40 00:02:05,220 --> 00:02:08,400 >> Публика: Ох, ово је ће трајати заувек. 41 00:02:08,400 --> 00:02:13,747 >> ПРЕДСЕДНИК: И ми ћемо гледати као што сте то урадили, без притиска. 42 00:02:13,747 --> 00:02:15,330 ПУБЛИКА: Не, нема притиска или ништа. 43 00:02:15,330 --> 00:02:19,230 44 00:02:19,230 --> 00:02:23,570 >> ПРЕДСЕДНИК: А за забаву, хајде да стави до тајмер. 45 00:02:23,570 --> 00:02:26,680 46 00:02:26,680 --> 00:02:28,700 >> ПУБЛИКА: толико забавно, толико забавно. 47 00:02:28,700 --> 00:02:36,741 48 00:02:36,741 --> 00:02:38,574 >> ПРЕДСЕДНИК: Могу држати микрофон за вас. 49 00:02:38,574 --> 00:02:40,240 У реду, управо смо удвостручили нашу брзину. 50 00:02:40,240 --> 00:02:44,190 51 00:02:44,190 --> 00:02:49,060 Дакле, у међувремену, дозволите ми да представљају оно што је ће бити питање за Мари Бетх 52 00:02:49,060 --> 00:02:51,540 је оно што је она ради, како је она иде о решавању ово? 53 00:02:51,540 --> 00:02:54,040 И, у ствари, можда нећете имати икада размишљали о нечему 54 00:02:54,040 --> 00:02:57,440 тако једноставно као када сте изабрали до 26 књига као што је ова, 55 00:02:57,440 --> 00:02:59,350 који немају природни наредио њима. 56 00:02:59,350 --> 00:03:01,335 Шта је процес да сте заправо коришћење? 57 00:03:01,335 --> 00:03:03,770 Да ли је то прилично насумично само брање прву што видите 58 00:03:03,770 --> 00:03:05,250 и стављајући га на свом месту? 59 00:03:05,250 --> 00:03:09,680 Да ли први корак руке око у потрази за онда тражите Б? 60 00:03:09,680 --> 00:03:11,722 Да ли да погледате пар њих раме уз раме 61 00:03:11,722 --> 00:03:14,680 и само да кажем, чекај мало, ово није у реду, а онда замените налог? 62 00:03:14,680 --> 00:03:16,960 Већ смо видели у понедељак да постоји неколико начина 63 00:03:16,960 --> 00:03:22,140 у којем можемо да урадимо ово, а заиста као што смо близу краја овде 64 00:03:22,140 --> 00:03:26,360 Ја бих да обратите пажњу, можда од чега Мари Бетх ради. 65 00:03:26,360 --> 00:03:30,040 Имамо неколико гомиле чини се, већи један, три мање. 66 00:03:30,040 --> 00:03:33,790 67 00:03:33,790 --> 00:03:36,415 >> ПУБЛИКА: Ја их наручивање кад нађем два писма 68 00:03:36,415 --> 00:03:39,540 да ја знам су заједно у низу, Ставио сам их заједно, тако да ја не 69 00:03:39,540 --> 00:03:42,915 морају да брину о одржавању Трацк читавог реда књига. 70 00:03:42,915 --> 00:03:45,706 То је само, ох, је први, Имам тај стек овде. 71 00:03:45,706 --> 00:03:47,580 ГОВОРИ: Дакле, скоро као слагалица комада да 72 00:03:47,580 --> 00:03:49,860 имају право на облик поклапају једни са другима. 73 00:03:49,860 --> 00:03:51,026 Публика: Прилично, да. 74 00:03:51,026 --> 00:03:55,320 ГОВОРИ: У реду, одлично. 75 00:03:55,320 --> 00:03:59,850 А сада сваки од њих гомиле је вероватно сортирано? 76 00:03:59,850 --> 00:04:00,990 >> Публика: Да. 77 00:04:00,990 --> 00:04:09,900 >> ПРЕДСЕДНИК: Добро, кроз З. Алл десно, честитам, успео си. 78 00:04:09,900 --> 00:04:11,461 Имате свој избор. 79 00:04:11,461 --> 00:04:11,960 Плава? 80 00:04:11,960 --> 00:04:13,530 У реду, хвала вам на томе. 81 00:04:13,530 --> 00:04:16,679 Тако Мари Бетх ли предложити оно што је њен приступ је био, 82 00:04:16,679 --> 00:04:19,720 али оно што је још један приступ како сте Можда иде о сортирање те ствари? 83 00:04:19,720 --> 00:04:21,130 Шта би ти урадио? 84 00:04:21,130 --> 00:04:24,060 Рекорд да победи било би један минут и 50 секунди или тако, 85 00:04:24,060 --> 00:04:26,039 плус оне Заборавио сам да бројим. 86 00:04:26,039 --> 00:04:27,080 Шта би ти урадио? 87 00:04:27,080 --> 00:04:27,579 Да? 88 00:04:27,579 --> 00:04:28,735 ПУБЛИКА: Узми стек. 89 00:04:28,735 --> 00:04:29,776 Почети од почетка. 90 00:04:29,776 --> 00:04:32,284 Проверите своје папире. 91 00:04:32,284 --> 00:04:36,586 А ако је неко виши врх него, можда, они су, 92 00:04:36,586 --> 00:04:38,980 дно један је већа, а затим их пребаците. 93 00:04:38,980 --> 00:04:41,300 >> ГОВОРИ: ОК, почевши на врху и дну, 94 00:04:41,300 --> 00:04:43,716 и онда радити свој пут унутра тако их замене? 95 00:04:43,716 --> 00:04:46,580 У реду, тако да мало сличан у духу са буббле врсте, 96 00:04:46,580 --> 00:04:49,160 али избор екстреме нису суседне парове. 97 00:04:49,160 --> 00:04:52,080 Али мање од тога је да постоји сигурно гомила различитих начина 98 00:04:52,080 --> 00:04:54,210 можемо да урадимо ово, а Искрено, мислим да би некако 99 00:04:54,210 --> 00:04:55,700 усвојила неколико приступа, зар не? 100 00:04:55,700 --> 00:05:00,567 Сте направили неку од четири разврстаних шипова, и затим их ефикасно уједине. 101 00:05:00,567 --> 00:05:02,650 И то је, претпостављам, још један техника укупно. 102 00:05:02,650 --> 00:05:06,950 Ниси га третира као једна велика гомила, ви подељен проблем на четири четворки, 103 00:05:06,950 --> 00:05:09,820 ако хоћете, а онда некако спојио их у крају. 104 00:05:09,820 --> 00:05:13,410 >> Па хајде да размотри, на крају, Како другачије бисмо могли урадити. 105 00:05:13,410 --> 00:05:15,860 Формализована смо појам на Буббле методу прошли пут, 106 00:05:15,860 --> 00:05:18,780 и Буббле Сорт опозива је алгоритам да визуелно 107 00:05:18,780 --> 00:05:22,640 са осам својих другова овде, наизглед насумице поредани на први поглед. 108 00:05:22,640 --> 00:05:26,110 И ми смо онда одлучили паровима, ако два елемента су ван реда, 109 00:05:26,110 --> 00:05:26,950 једноставно их замене. 110 00:05:26,950 --> 00:05:28,930 Па четири и два су очигледно не ради, 111 00:05:28,930 --> 00:05:31,080 тако да они два класесбиедру заменио позицију. 112 00:05:31,080 --> 00:05:35,390 А онда смо поновили са четири и шест, затим шест и осам, на сваке итерације, 113 00:05:35,390 --> 00:05:36,980 креће на десно. 114 00:05:36,980 --> 00:05:42,590 >> Па с обзиром осам особа, колико попарно Поређења сам урадио док ходате из 115 00:05:42,590 --> 00:05:45,220 лева на десно у једном таквом итерацији? 116 00:05:45,220 --> 00:05:48,410 Колико Поређења? 117 00:05:48,410 --> 00:05:49,197 Седам, зар не? 118 00:05:49,197 --> 00:05:51,405 Јер ако постоји осам људи, али имате пар 119 00:05:51,405 --> 00:05:53,880 их и ви се креће један хоп са десне стране, 120 00:05:53,880 --> 00:05:56,060 нећеш имати осам поређења, јер не можете да упоредите 121 00:05:56,060 --> 00:05:59,226 елемент против себе, или би само бесмислено, тако да имате седам. 122 00:05:59,226 --> 00:06:01,290 Или уопште, ако је имамо н људи, ми смо 123 00:06:01,290 --> 00:06:04,300 урадите н минус 1 поређења са балон врсте. 124 00:06:04,300 --> 00:06:08,150 >> Дакле, хајде да сада размотрити колико је добар или лоша Буббле Сорт заправо, и покушајте 125 00:06:08,150 --> 00:06:13,570 да себи дам речник са што да критикује алгоритмима као што је овај, 126 00:06:13,570 --> 00:06:14,430 и ускоро наше. 127 00:06:14,430 --> 00:06:16,970 Тако да у првом пролазу кроз Буббле Сорт, први пут 128 00:06:16,970 --> 00:06:20,909 Ишао сам с лева на десно преко фаза, узео ме н минус 1 поређења. 129 00:06:20,909 --> 00:06:22,950 Као и да ће бити мој јединица мере, зар не? 130 00:06:22,950 --> 00:06:26,170 Ја сам некако говорио и шетњу, донекле брзо, спори, 131 00:06:26,170 --> 00:06:29,300 па бројање мој број секунди није посебно говори, 132 00:06:29,300 --> 00:06:32,260 али бројање броја операције да сам у понедељак, 133 00:06:32,260 --> 00:06:35,900 упоређујући двоје људи, то се осећа као леп јединици мере. 134 00:06:35,900 --> 00:06:40,980 >> Па н минус 1 кораке први пут, Али шта се онда десило после тога? 135 00:06:40,980 --> 00:06:46,610 Шта је један наопако од једном пролазу кроз иначе обичан списак? 136 00:06:46,610 --> 00:06:49,840 Шта можете да ми кажете о елементу који је био скроз тамо? 137 00:06:49,840 --> 00:06:51,300 Да? 138 00:06:51,300 --> 00:06:52,870 То је био највећи елемент, зар не? 139 00:06:52,870 --> 00:06:55,710 Број осам, иако је почео овде, сваки пут кад 140 00:06:55,710 --> 00:06:57,860 у односу је против комшија, она је стално 141 00:06:57,860 --> 00:07:00,480 бистрим до десно ханд сиде листе. 142 00:07:00,480 --> 00:07:02,710 И заиста, то је тамо где алгоритам добија своје име. 143 00:07:02,710 --> 00:07:07,630 >> Сада по тој логици, колико поређења Треба ми да се други пут 144 00:07:07,630 --> 00:07:09,800 Правим који пролазе са лева на десно? 145 00:07:09,800 --> 00:07:10,730 н минус 2, зар не? 146 00:07:10,730 --> 00:07:14,297 Управо ће то бити губим време ако ја држати упоређујући осам против некога 147 00:07:14,297 --> 00:07:16,630 друго, јер већ знамо она је била на правом месту. 148 00:07:16,630 --> 00:07:19,760 Тако да је то мало оптимизација, тако да следећи пролаз 149 00:07:19,760 --> 00:07:23,899 ће бити плус Н минус два корака, где је н број људи. 150 00:07:23,899 --> 00:07:26,940 Сада можете да некако екстраполира, чак и ако нисте рачунар научник, 151 00:07:26,940 --> 00:07:27,680 како се то завршава. 152 00:07:27,680 --> 00:07:31,259 На крају овог алгоритма, вероватно имаш само један поређење отишао. 153 00:07:31,259 --> 00:07:33,800 Морате да некако поправити почетак листе у случају да два 154 00:07:33,800 --> 00:07:36,540 и један су од реда и треба да буде један и два, 155 00:07:36,540 --> 00:07:40,330 Дакле, ово се до дна у Плус 1 коначна поређење. 156 00:07:40,330 --> 00:07:44,500 >> Сада тачка, тачка, тачка врста таласа је руке на неке од сочније детаље, 157 00:07:44,500 --> 00:07:46,452 али хајде да само напред и поједноставити. 158 00:07:46,452 --> 00:07:48,660 Ако се сећате из високог Сцхоол, искрено, многи од вас 159 00:07:48,660 --> 00:07:50,340 имали математичке књиге које су имале мало Цхеат схеет 160 00:07:50,340 --> 00:07:52,550 на насловној или Поклопац са задње стране који вам је показао 161 00:07:52,550 --> 00:07:56,400 шта сериес сумирања попут Овај на крају додао до. 162 00:07:56,400 --> 00:07:59,600 У општем случају, ако имате променљива попут н, и заиста ова, 163 00:07:59,600 --> 00:08:01,634 Ако сте гледали на вашем Олд Сцхоол матх боок, 164 00:08:01,634 --> 00:08:04,050 видели бисте да је ово у ствари додаје до ове суме овде 165 00:08:04,050 --> 00:08:07,970 н пута н минус 1 све подељено са 2. 166 00:08:07,970 --> 00:08:11,172 Дакле, за сада само да утврђују То је истина, тако на Леап оф Фаитх, 167 00:08:11,172 --> 00:08:12,880 то је оно што овај сумира до, и ми смо могли 168 00:08:12,880 --> 00:08:14,341 докаже да је у више општем случају. 169 00:08:14,341 --> 00:08:15,590 Али сада хајде да се прошири ово. 170 00:08:15,590 --> 00:08:19,920 Дакле, хајде да се умножавају ово, тако да је н квадрат, минус н, све подељено са 2. 171 00:08:19,920 --> 00:08:23,200 То је стварно н квадрат, подељено са 2, минус н више од 2, 172 00:08:23,200 --> 00:08:25,010 тако да је све лепо и занимљиво. 173 00:08:25,010 --> 00:08:27,060 Али шта се дешава ако сада плуг-ин вредности? 174 00:08:27,060 --> 00:08:29,724 Претпостављам да нисам имао осам људи, али кажу милион. 175 00:08:29,724 --> 00:08:31,890 И милион само зато то је прилично велики број, 176 00:08:31,890 --> 00:08:34,039 хајде да у плуг и види шта се дешава. 177 00:08:34,039 --> 00:08:39,039 Дакле, ако сам утикач милион у ту формулу Идем да милион квадрат, 178 00:08:39,039 --> 00:08:42,868 подељено са 2, минус милиона, подељено са 2. 179 00:08:42,868 --> 00:08:44,159 Сада шта то иде до изједначења? 180 00:08:44,159 --> 00:08:47,354 Тако 500 милијарди, минус 500.000. 181 00:08:47,354 --> 00:08:49,270 И ако ја заправо радим да се математика, то значи 182 00:08:49,270 --> 00:08:53,920 који сортирање милион људи са балон врсте 183 00:08:53,920 --> 00:09:01,800 Можда ме се 499.999.500.000 кораци или поређења на крају, 184 00:09:01,800 --> 00:09:02,900 само смо екстраполацијом. 185 00:09:02,900 --> 00:09:06,860 >> То се осећа прилично споро, али, искрено мерење један посебан улаз 186 00:09:06,860 --> 00:09:09,160 овако, није све то рекли. 187 00:09:09,160 --> 00:09:14,050 Али заиста то не сугерише да је н добија све веће и веће, овај алгоритам 188 00:09:14,050 --> 00:09:16,280 врста осећа лошије и горе, или стварно 189 00:09:16,280 --> 00:09:20,450 почети да осећају бол који степеновање, да је н на квадрат, 190 00:09:20,450 --> 00:09:21,770 која сабира прилично брзо. 191 00:09:21,770 --> 00:09:25,340 А овај детаљ није изгубила на људе, у ствари 192 00:09:25,340 --> 00:09:29,640 Пре неколико година неки сенатор који је био кампање, сео за интервју 193 00:09:29,640 --> 00:09:32,180 са Гоогле Ериц Шмит, извршни директор у то време, 194 00:09:32,180 --> 00:09:36,380 и био је оспорио са питањем личи ми истражујемо данас. 195 00:09:36,380 --> 00:09:38,468 Хајде да погледамо. 196 00:09:38,468 --> 00:09:45,280 >> [ВИДЕО РЕПРОДУКЦИЈА] 197 00:09:45,280 --> 00:09:48,560 >> Сенаторе, ти си овде на Гоогле, и волим 198 00:09:48,560 --> 00:09:53,382 да мислим о председништва као интервју за посао. 199 00:09:53,382 --> 00:09:56,434 Сада је тешко добити посао као председник, 200 00:09:56,434 --> 00:09:58,100 и идете кроз суровости сада. 201 00:09:58,100 --> 00:10:01,860 Такође је тешко добити посао у Гоогле-у. 202 00:10:01,860 --> 00:10:05,490 Имамо питања, а ми питајте наших кандидата питања, 203 00:10:05,490 --> 00:10:09,770 а ово је од Ларри Швимер. 204 00:10:09,770 --> 00:10:14,760 Љта-- ви мислите да сам шалим се, то је овде. 205 00:10:14,760 --> 00:10:17,930 Који је најефикаснији начин да се сортирање милион 32-битне целе бројеве? 206 00:10:17,930 --> 00:10:21,800 207 00:10:21,800 --> 00:10:24,350 >> -Велл-- 208 00:10:24,350 --> 00:10:25,200 >> Жао ми је, маибе-- 209 00:10:25,200 --> 00:10:27,400 >> Не, не, не. 210 00:10:27,400 --> 00:10:30,700 Мислим да је балон врсту би био погрешан пут којим треба ићи. 211 00:10:30,700 --> 00:10:34,165 212 00:10:34,165 --> 00:10:38,180 >> Хајде, ко му је то рекао? 213 00:10:38,180 --> 00:10:40,590 Нисам видела рачунар Наука у позадини. 214 00:10:40,590 --> 00:10:42,130 >> -Имамо Наше шпијуне тамо. 215 00:10:42,130 --> 00:10:44,930 216 00:10:44,930 --> 00:10:48,444 >> ОК, хајде да питамо другачији Интервју питање. 217 00:10:48,444 --> 00:10:49,300 >> [ЕНД ВИДЕО РЕПРОДУКЦИЈА] 218 00:10:49,300 --> 00:10:52,290 >> ПРЕДСЕДНИК: Тако говори о Конкретни бројеви ипак, 219 00:10:52,290 --> 00:10:53,890 неће бити све то корисно. 220 00:10:53,890 --> 00:10:56,810 То није живот лекција коју балон Сорт, дао милион улаза, 221 00:10:56,810 --> 00:10:58,590 може потрајати чак 500 милијарди корака. 222 00:10:58,590 --> 00:11:01,120 Ви стварно не могу генерализовати такође ефикасно од тога 223 00:11:01,120 --> 00:11:03,560 и доносе добре одлуке дизајна приликом писања програма. 224 00:11:03,560 --> 00:11:07,070 Дакле, хајде да, иако се фокусира на то како можемо да поједноставимо овај резултат. 225 00:11:07,070 --> 00:11:11,780 >> Па сам нагласио у жуто овде резултат н квадрат подељен са 2, 226 00:11:11,780 --> 00:11:14,330 па милион квадрата подељена са 2, а затим 227 00:11:14,330 --> 00:11:16,710 Ја сам нагласио шта крајњи одговор 228 00:11:16,710 --> 00:11:20,180 Када смо одузима Офф н подељен са 2. 229 00:11:20,180 --> 00:11:24,850 А тврдња ћу да сада, који је дођавола брига ако одузмете Офф 230 00:11:24,850 --> 00:11:30,060 мали стари Н преко 2, када први део ове формуле је толико много већи? 231 00:11:30,060 --> 00:11:33,910 Доминира друга израз, н квадрат подељен 2 232 00:11:33,910 --> 00:11:37,510 је много већи, јасно, јер н добија велика као милион, 233 00:11:37,510 --> 00:11:41,450 да постоји заиста велика разлика у крај дана од 500 милијарди 234 00:11:41,450 --> 00:11:45,730 и 499.999.500.000? 235 00:11:45,730 --> 00:11:46,349 Не баш. 236 00:11:46,349 --> 00:11:48,640 Па шта ћемо да уради како компјутерски научници се 237 00:11:48,640 --> 00:11:53,270 игнорисати те ниже услове реда и узети нешто овако и стварно 238 00:11:53,270 --> 00:11:56,050 само поједноставити да израз који ће битно. 239 00:11:56,050 --> 00:12:00,315 Већи Наши скупови података се, већи нашим базама података добију, више веб странице 240 00:12:00,315 --> 00:12:02,690 морамо да тражи, више пријатељи имате на Фацебоок. 241 00:12:02,690 --> 00:12:07,340 >> Као н добија већи, ми стварно ће да брине о величини 242 00:12:07,340 --> 00:12:11,560 термин у сваком таквом анализи наш алгоритми перформансе. 243 00:12:11,560 --> 00:12:16,230 И ја ћу да кажем, знаш шта, Буббле Сортирај је по налогу Биг О, 244 00:12:16,230 --> 00:12:18,060 по налогу Н на квадрат. 245 00:12:18,060 --> 00:12:20,090 То није баш н квадрат као што смо видели, 246 00:12:20,090 --> 00:12:22,060 али који није брига о тим мањим условима, 247 00:12:22,060 --> 00:12:24,390 и искрено, који заиста брига ако поделимо са 2? 248 00:12:24,390 --> 00:12:25,870 То је само стални фактор. 249 00:12:25,870 --> 00:12:29,480 И 500 милијарди долара у односу на 250 милијарди стварно тако велика ствар? 250 00:12:29,480 --> 00:12:32,190 Ја само могу да чекам годину дана, нека мој лаптоп буквално 251 00:12:32,190 --> 00:12:34,810 добити дупло брже у хардверу, и такве разлике 252 00:12:34,810 --> 00:12:36,650 Само одлази природно током времена. 253 00:12:36,650 --> 00:12:39,300 >> Оно што ми је стало је израз, део 254 00:12:39,300 --> 00:12:42,489 израза који ће да варира као наш улаз постаје све већа и већа. 255 00:12:42,489 --> 00:12:45,280 И заиста, у стварном свету, то је оно што све више дешава 256 00:12:45,280 --> 00:12:48,330 то су улази на наше проблеме и алгоритми су све већи. 257 00:12:48,330 --> 00:12:53,470 Па Биг О ће бити нотација, асимптотско нотација, које смо управо 258 00:12:53,470 --> 00:12:57,160 користити као компјутерски научници за описивање перформансе, или трчање време, 259 00:12:57,160 --> 00:12:58,130 алгоритма. 260 00:12:58,130 --> 00:13:00,800 Тако да можемо да упоредимо алгоритме на различитим рачунарима писаним 261 00:13:00,800 --> 00:13:04,170 од стране различитих људи, користећи неки суштински слично метрички 262 00:13:04,170 --> 00:13:07,557 као број поређења си одлука, или можда број свопови 263 00:13:07,557 --> 00:13:08,140 правите. 264 00:13:08,140 --> 00:13:11,910 >> Оно што ми не идемо у Број је количина времена 265 00:13:11,910 --> 00:13:13,981 који пролази на сату на зиду типично. 266 00:13:13,981 --> 00:13:16,230 Оно што нећемо да брине о томе колико је меморије 267 00:13:16,230 --> 00:13:17,820 користите данас у најмању руку, иако је то 268 00:13:17,820 --> 00:13:19,370 Још један ресурс можемо мерити. 269 00:13:19,370 --> 00:13:23,610 Ми ћемо покушати да заснивамо наше анализе на само основне операције, они, 270 00:13:23,610 --> 00:13:25,930 искрено, да можете највише визуелно види. 271 00:13:25,930 --> 00:13:30,700 Дакле, са нечим као Биг О од н квадрат, ја тврдим да је О н квадрат 272 00:13:30,700 --> 00:13:35,820 је горња граница тзв руннинг време балон врсте. 273 00:13:35,820 --> 00:13:38,820 Другим речима, ако је желео да тврде да постоји 274 00:13:38,820 --> 00:13:41,370 Ова горња граница колико кораци алгоритам може потрајати, 275 00:13:41,370 --> 00:13:46,240 то ће бити у великој Ø Н квадрат у овом случају, горњу границу. 276 00:13:46,240 --> 00:13:49,710 >> Шта ако сам уместо тога променити прича да се не ради о буббле врсте, 277 00:13:49,710 --> 00:13:50,910 али о томе горња граница. 278 00:13:50,910 --> 00:13:54,030 Можете ли се сетити алгоритма које смо гледали већ 279 00:13:54,030 --> 00:13:59,530 чији горњу границу, максимална мерење времена, или операција, 280 00:13:59,530 --> 00:14:04,300 би се рећи да је ограничен Н, линеарна функција, 281 00:14:04,300 --> 00:14:07,260 Не квадратни која је закривљена? 282 00:14:07,260 --> 00:14:10,780 Шта је алгоритам који Увек не траје дуже 283 00:14:10,780 --> 00:14:12,860 него као н корака, или 2н кораци, или 3Н кораци? 284 00:14:12,860 --> 00:14:13,360 Да? 285 00:14:13,360 --> 00:14:15,030 >> ПУБЛИКА: Проналажење највећи број на листи? 286 00:14:15,030 --> 00:14:16,930 >> ГОВОРИ: Перфецт, проналажење највећи број на листи. 287 00:14:16,930 --> 00:14:18,940 Ако сам дао листу људи за пример, 288 00:14:18,940 --> 00:14:21,440 сваки који држи број, који је максималан број 289 00:14:21,440 --> 00:14:23,770 корака треба ме, разумно паметан човек, 290 00:14:23,770 --> 00:14:27,530 да пронађе највећи особу на том списку? 291 00:14:27,530 --> 00:14:28,100 Н, зар не? 292 00:14:28,100 --> 00:14:31,320 Јер, у најгорем случају, где је Можда највећа вредност бити? 293 00:14:31,320 --> 00:14:32,700 Добро, све на крају. 294 00:14:32,700 --> 00:14:34,575 Дакле, у најгорем случају горња граница, могао бих 295 00:14:34,575 --> 00:14:36,450 морамо да идемо до краја овде и бити као, 296 00:14:36,450 --> 00:14:39,170 Ох, ево је број осам, или шта год да је вредност. 297 00:14:39,170 --> 00:14:41,330 Сада само би било глупо ако ја стално идем, зар не? 298 00:14:41,330 --> 00:14:43,840 У потрази за више и више елемената Ако последњи од њих је тамо? 299 00:14:43,840 --> 00:14:45,340 Тако да сигурно, н је горњу границу. 300 00:14:45,340 --> 00:14:47,420 Не треба да предузму више корака од тога. 301 00:14:47,420 --> 00:14:51,580 >> Па шта ако уместо тога сам предложио да постоје алгоритми на овом свету који 302 00:14:51,580 --> 00:14:57,750 имају време рада који је омеђена Биг О дневника Н, лог н? 303 00:14:57,750 --> 00:15:00,390 Где смо видели раније? 304 00:15:00,390 --> 00:15:00,890 Да? 305 00:15:00,890 --> 00:15:03,309 >> ПУБЛИКА: У проблему у телефонском именику? 306 00:15:03,309 --> 00:15:04,850 ПРЕДСЕДНИК: Као проблем у именику. 307 00:15:04,850 --> 00:15:07,754 Каква је била мера како много времена или колико сузе ИТ 308 00:15:07,754 --> 00:15:10,170 Требало ми је да нађем неког попут Мике Смитх у именику? 309 00:15:10,170 --> 00:15:13,212 Тврдио смо да је лог н, и чак и ако нису упознати или да је 310 00:15:13,212 --> 00:15:15,170 мало магловито шта логаритхм или експонент је, 311 00:15:15,170 --> 00:15:17,650 Само запамтите да лог н генерално се односи на процес, 312 00:15:17,650 --> 00:15:20,790 у овом случају, поделе нешто на пола опет, и опет, 313 00:15:20,790 --> 00:15:25,790 и опет, и опет, такав да добија све више мали као ти то. 314 00:15:25,790 --> 00:15:28,470 >> Па лог н односи, наравно, у телефонски именик пример, 315 00:15:28,470 --> 00:15:32,662 у бинарни потрази у теорији, када смо имао виртуелна врата на табли, 316 00:15:32,662 --> 00:15:34,370 или када је Сеан у потрази за нечим. 317 00:15:34,370 --> 00:15:37,374 Да је користио бинарну претрагу, лог н би горња граница колико 318 00:15:37,374 --> 00:15:38,040 време које узима. 319 00:15:38,040 --> 00:15:44,027 Али ти алгоритми који се извршавао на лог Н Претпоставља Који кључ детаље? 320 00:15:44,027 --> 00:15:45,360 То је листа сортирана, зар не? 321 00:15:45,360 --> 00:15:47,789 Ваш алгоритам је лоше ако Ваш улаз се не сортира, 322 00:15:47,789 --> 00:15:49,830 а ипак користите нешто као бинарног претраживања 323 00:15:49,830 --> 00:15:51,704 јер би могао скочити право над елементом 324 00:15:51,704 --> 00:15:53,600 без схватајући да је заиста тамо. 325 00:15:53,600 --> 00:15:55,600 >> Сад шта би то значило, Биг О једног? 326 00:15:55,600 --> 00:15:59,117 То не значи да је ваш алгоритам траје један и само један корак, 327 00:15:59,117 --> 00:16:01,200 то само значи да треба исти број корака. 328 00:16:01,200 --> 00:16:04,060 Можда је то 1, можда је 10, можда је 1.000, 329 00:16:04,060 --> 00:16:07,750 али је независна од величина проблема. 330 00:16:07,750 --> 00:16:10,850 Без обзира на то колико је велико н, Цонстант време алгоритам 331 00:16:10,850 --> 00:16:12,747 увек узима исти број корака. 332 00:16:12,747 --> 00:16:15,080 Дакле, шта може бити алгоритам смо говорили о томе или једноставно 333 00:16:15,080 --> 00:16:20,418 интуитивно који долази да ти да Увек ради у такозваном сталном време? 334 00:16:20,418 --> 00:16:20,918 Да? 335 00:16:20,918 --> 00:16:22,001 >> ПУБЛИКА: Додајте два броја. 336 00:16:22,001 --> 00:16:25,320 ПРЕДСЕДНИК: Додајте два броја, 2 плус 2 једнако 4, урађено. 337 00:16:25,320 --> 00:16:27,227 Тако да може да ради, шта друго? 338 00:16:27,227 --> 00:16:28,560 Како би било још стварном свету, зар не? 339 00:16:28,560 --> 00:16:30,686 >> ПУБЛИКА: Проналажење Прва ствар на листи. 340 00:16:30,686 --> 00:16:32,810 ПРЕДСЕДНИК: Проналажење први елемент у листи, сигурно. 341 00:16:32,810 --> 00:16:34,540 Ми смо заправо причали већ око низова, 342 00:16:34,540 --> 00:16:36,540 како добити на први елемент у низу, 343 00:16:36,540 --> 00:16:40,465 Без обзира на то колико дуго низ је у Ц код? 344 00:16:40,465 --> 00:16:43,090 Само користите као носач Зеро нотација, бам, си тамо. 345 00:16:43,090 --> 00:16:46,120 И заиста, као низови страну, нешто Суппорт опште позната 346 00:16:46,120 --> 00:16:49,240 као случајним приступом, са директним приступом Меморија, јер буквално можете 347 00:16:49,240 --> 00:16:50,284 скочи на било ком месту. 348 00:16:50,284 --> 00:16:52,700 Можемо да урадимо ово још више једноставно можемо уназад до недеље нула 349 00:16:52,700 --> 00:16:53,900 када смо нуле. 350 00:16:53,900 --> 00:16:59,707 Колико је времена било потребно за кажу блок у нуле да изврши? 351 00:16:59,707 --> 00:17:00,790 Само Цонстант време, зар не? 352 00:17:00,790 --> 00:17:03,960 Да кажем нешто, кажу нешто, није битно 353 00:17:03,960 --> 00:17:07,359 Колико је велика Огреботине свет, то је увек Биће потребно исту количину времена 354 00:17:07,359 --> 00:17:08,490 да једноставно кажем нешто. 355 00:17:08,490 --> 00:17:11,089 >> Дакле, то је константа време, али оно што је друга страна? 356 00:17:11,089 --> 00:17:13,030 Ако је то горња границе, шта ако желимо 357 00:17:13,030 --> 00:17:17,089 да опише ниже границе наших алгоритама времена рада? 358 00:17:17,089 --> 00:17:19,852 Готово најбољем случају потенцијално, ако хоћете, 359 00:17:19,852 --> 00:17:23,060 мада ови услови може да се примени на најбољи начин сандуци, најгорим случајевима, просек предмета више 360 00:17:23,060 --> 00:17:26,359 генерално, али хајде да се фокусирамо на нижим границе уопште. 361 00:17:26,359 --> 00:17:31,920 Шта је алгоритам који има доње границе н корака, 362 00:17:31,920 --> 00:17:33,350 или 2н корака, или 3Н кораци? 363 00:17:33,350 --> 00:17:36,241 Неки фактор н корака, То је његова доња граница. 364 00:17:36,241 --> 00:17:36,740 Да? 365 00:17:36,740 --> 00:17:37,910 >> ПУБЛИКА: Буббле сорт? 366 00:17:37,910 --> 00:17:41,610 >> ПРЕДСЕДНИК: Буббле сорт узима ви минимално Н кораци, зашто? 367 00:17:41,610 --> 00:17:42,279 Зашто је то тако? 368 00:17:42,279 --> 00:17:45,320 Зашто би то почетак да дођем к вама интуитивно, чак и ако то не само 369 00:17:45,320 --> 00:17:46,530 још? 370 00:17:46,530 --> 00:17:47,030 Да? 371 00:17:47,030 --> 00:17:47,990 >> ПУБЛИКА: [неразумљиво]. 372 00:17:47,990 --> 00:17:51,652 373 00:17:51,652 --> 00:17:52,360 ГОВОРИ: Тачно. 374 00:17:52,360 --> 00:17:55,810 У најбољем могућем сценарију Буббле Сорт, а доста алгоритама, 375 00:17:55,810 --> 00:17:58,769 ако ти предати осам људи који су већ сортирају, 376 00:17:58,769 --> 00:18:00,560 било би глупо за вас, алгоритам, 377 00:18:00,560 --> 00:18:02,202 да иде напред и назад више него једном, зар не? 378 00:18:02,202 --> 00:18:04,285 Јер чим ти хода кроз листу једном, 379 00:18:04,285 --> 00:18:08,090 ви треба да схвате, ох, направио сам не свапс, ова листа је сортирана, излаз. 380 00:18:08,090 --> 00:18:09,700 Али то ће вас н кораке предузети. 381 00:18:09,700 --> 00:18:12,033 >> И обрнуто, што је још једна начин размишљања о томе? 382 00:18:12,033 --> 00:18:15,240 Буббле врста је Омега, да тако кажем, Н, 383 00:18:15,240 --> 00:18:19,050 јер ако погледате мање од н елемената, што 384 00:18:19,050 --> 00:18:23,009 постоји фундаментално питање? 385 00:18:23,009 --> 00:18:24,550 Не знам да ли је то сортирају, десно. 386 00:18:24,550 --> 00:18:26,800 Ми људи Можда поглед на осам људи и бити као, Ох, то је сортирано, 387 00:18:26,800 --> 00:18:28,430 да ме није н кораке предузети, али јесте. 388 00:18:28,430 --> 00:18:30,810 Очи, чак и ако сте љубазни из имају велики видно поље, 389 00:18:30,810 --> 00:18:33,184 погледао осам елемената, погледао осам људи, 390 00:18:33,184 --> 00:18:34,610 То је ефикасно осам корака. 391 00:18:34,610 --> 00:18:38,612 И само ако ходам кроз цео Списак ја схватају, да, сортирано. 392 00:18:38,612 --> 00:18:41,320 Ако престанем да размишљам пола, све Добро, то је прилично поредани сада, 393 00:18:41,320 --> 00:18:42,520 какве су шансе да није сортиране? 394 00:18:42,520 --> 00:18:44,186 То алгоритми неће бити тачан. 395 00:18:44,186 --> 00:18:46,250 Можда буду брже, али нетачно. 396 00:18:46,250 --> 00:18:48,500 >> Тако да сада имамо начин описује ниже границе, 397 00:18:48,500 --> 00:18:49,710 А шта је са сталном времену? 398 00:18:49,710 --> 00:18:54,565 Шта је алгоритам који има мањи везани на свом Потребно време једног? 399 00:18:54,565 --> 00:18:58,350 1 корак, 2 корака, 10 корака, али константна, независно од н, 400 00:18:58,350 --> 00:18:59,310 величина улаза? 401 00:18:59,310 --> 00:19:03,930 402 00:19:03,930 --> 00:19:04,600 Да, позади. 403 00:19:04,600 --> 00:19:05,309 >> ПУБЛИКА: принтф? 404 00:19:05,309 --> 00:19:06,183 ПРЕДСЕДНИК: Шта је то? 405 00:19:06,183 --> 00:19:07,184 ПУБЛИКА: принтф? 406 00:19:07,184 --> 00:19:07,850 ПРЕДСЕДНИК: принтф. 407 00:19:07,850 --> 00:19:08,400 У реду, наравно. 408 00:19:08,400 --> 00:19:10,720 Тако да је потребно фиксни број корака. 409 00:19:10,720 --> 00:19:13,170 И ја би требало сада да Сад-- Говоримо о Ц коду 410 00:19:13,170 --> 00:19:16,040 а не Сцратцх, нешто попут рецимо, са принтф, 411 00:19:16,040 --> 00:19:17,710 требало би да почне да се опрезан. 412 00:19:17,710 --> 00:19:21,090 Јер принтф узима улаз, то је ниска, 413 00:19:21,090 --> 00:19:23,220 и гудаче да технички има дужину. 414 00:19:23,220 --> 00:19:25,530 Дакле, ако ми сада желимо да изаберете на вас, ако не смета, 415 00:19:25,530 --> 00:19:29,430 Технички смо могли тврдити да је принтф узима променљиве улаз дужине, 416 00:19:29,430 --> 00:19:32,270 и сигурно то може потрајати више Време је да одштампате стринг тако дуго, 417 00:19:32,270 --> 00:19:33,560 него овако дуго. 418 00:19:33,560 --> 00:19:36,570 >> Па шта ако смо у обзир сортирање и претраживање примере? 419 00:19:36,570 --> 00:19:40,450 Шта је са Мике Смитх на телефону књига, или бинарна претрага уопште? 420 00:19:40,450 --> 00:19:42,220 У најбољем случају, шта би могло да се деси? 421 00:19:42,220 --> 00:19:45,577 Ја отворим телефонског именика и, бам, ту је Мике Смитх је број. 422 00:19:45,577 --> 00:19:46,660 Могу да га позовем одмах. 423 00:19:46,660 --> 00:19:49,390 >> Је један корак, можда два корака, али константан број корака 424 00:19:49,390 --> 00:19:50,230 ако имам среће. 425 00:19:50,230 --> 00:19:52,570 И искрено, видели смо на Мондаи Иоур цлассмате 426 00:19:52,570 --> 00:19:54,710 добити прилично среће два пута узастопно. 427 00:19:54,710 --> 00:19:57,050 И то је било заиста константан пут у нижим границама 428 00:19:57,050 --> 00:20:01,280 на алгоритму у питању за проналажење број 50 стоји иза оних затворена 429 00:20:01,280 --> 00:20:01,830 врата. 430 00:20:01,830 --> 00:20:06,400 >> Сада, као на страну, ако откријете да су Биг О, горња граница, 431 00:20:06,400 --> 00:20:09,310 и Омега, доња граница, су једно у исти, да 432 00:20:09,310 --> 00:20:11,830 је иста формула у заграде, можете такође 433 00:20:11,830 --> 00:20:15,170 кажу, само да буде фенси, да је нешто у тета 434 00:20:15,170 --> 00:20:18,270 Н или тета неког другог вредности. 435 00:20:18,270 --> 00:20:20,661 То само значи да када велики О и омега су исти. 436 00:20:20,661 --> 00:20:21,910 Шта о избору врсти сада? 437 00:20:21,910 --> 00:20:23,400 Хајде да користимо овај нови вокабулар. 438 00:20:23,400 --> 00:20:27,407 У избору врсте, шта смо раде опет, и опет, и опет? 439 00:20:27,407 --> 00:20:29,990 Хтео сам напред и назад кроз листа, у потрази за кога? 440 00:20:29,990 --> 00:20:33,260 441 00:20:33,260 --> 00:20:34,730 Најмањи број. 442 00:20:34,730 --> 00:20:37,560 >> Па колико корака, како многи Поређења зар не 443 00:20:37,560 --> 00:20:43,250 морати да како да схватим ко најмањи елемент у листи био? 444 00:20:43,250 --> 00:20:44,437 н минус 1, зар не? 445 00:20:44,437 --> 00:20:47,770 Јер ако сам почети с једним сам дао и ја почнем њега или њу у односу, 446 00:20:47,770 --> 00:20:49,519 онда њему или њој, он или она, он или она, 447 00:20:49,519 --> 00:20:52,010 могу само да упарите елементе заједно н минус 1 пута. 448 00:20:52,010 --> 00:20:55,630 Тако да избор сорт Слично узима н минус 1 кораке први пут. 449 00:20:55,630 --> 00:20:59,540 >> Колико корака то ме води у наћи други најмањи елемент? 450 00:20:59,540 --> 00:21:02,920 н минус 2, јер сам био глуп ако Стално гледајући истих људи 451 00:21:02,920 --> 00:21:06,280 опет, ако сам већ га је изабрао или ње и да их стави на своје место. 452 00:21:06,280 --> 00:21:09,270 И трећи корак, н минус 3, затим н минус 4. 453 00:21:09,270 --> 00:21:11,020 Видели смо овај образац пре, и заиста 454 00:21:11,020 --> 00:21:13,460 Избор сорт Слично има горњу границу 455 00:21:13,460 --> 00:21:16,210 за Н на квадрат, ако урадимо ону сумирање. 456 00:21:16,210 --> 00:21:19,790 Оно што је његова доња граница, избор врста? 457 00:21:19,790 --> 00:21:25,350 Минимално, колико времена селекција мора Сорт узети, као што смо то дефинисано у понедељак? 458 00:21:25,350 --> 00:21:29,370 459 00:21:29,370 --> 00:21:30,490 Предложити две опције. 460 00:21:30,490 --> 00:21:32,360 Можда је н, као и раније. 461 00:21:32,360 --> 00:21:35,040 Можда је то н квадрат, као што је је сада као горњу границу. 462 00:21:35,040 --> 00:21:35,874 >> Публика: н квадрат. 463 00:21:35,874 --> 00:21:36,664 ПРЕДСЕДНИК: н квадрат. 464 00:21:36,664 --> 00:21:37,368 Зашто? 465 00:21:37,368 --> 00:21:40,060 >> ПУБЛИКА: Зато што имаш дефинисати [неразумљиво]. 466 00:21:40,060 --> 00:21:41,510 >> ГОВОРИ: Тачно. 467 00:21:41,510 --> 00:21:45,077 Барем како сам је дефинисано селекције врсту било је прилично наивно, настави, 468 00:21:45,077 --> 00:21:46,160 наћи најмањи елемент. 469 00:21:46,160 --> 00:21:47,770 Иди опет наћи најмањи елемент. 470 00:21:47,770 --> 00:21:49,490 Иди опет наћи најмањи елемент. 471 00:21:49,490 --> 00:21:51,700 Нема врста оптимизација тамо да 472 00:21:51,700 --> 00:21:54,350 Можда дозволите ми прекинути после само н или тако корака. 473 00:21:54,350 --> 00:21:57,080 Дакле заиста, селекција врста, омега Н на квадрат. 474 00:21:57,080 --> 00:22:00,667 >> Шта је са уметања врсти, где сам узео који сам добио, а онда сам га гурнуо 475 00:22:00,667 --> 00:22:01,750 или је на правом месту? 476 00:22:01,750 --> 00:22:04,958 Онда сам наставио да другом лицу, гурнуо га је на правом месту. 477 00:22:04,958 --> 00:22:07,910 Затим следећа особа, гурнуо њега или ње на правом месту. 478 00:22:07,910 --> 00:22:10,537 Обратите пажњу да је ово веома Линеар, да тако кажем. 479 00:22:10,537 --> 00:22:12,620 Ја сам права линија, ја сам не иде напред и назад, 480 00:22:12,620 --> 00:22:16,080 Никада нисам гледајући уназад стварно, али шта се дешава кад сам га убаците 481 00:22:16,080 --> 00:22:20,302 или она у почетку списак као што смо урадили у понедељак? 482 00:22:20,302 --> 00:22:21,010 Шта се дешава? 483 00:22:21,010 --> 00:22:21,510 Да? 484 00:22:21,510 --> 00:22:23,122 ПУБЛИКА: [неразумљиво]. 485 00:22:23,122 --> 00:22:24,830 ГОВОРИ: Да, то био улов, зар не? 486 00:22:24,830 --> 00:22:26,746 Можда се сећате из својим друговима, ако 487 00:22:26,746 --> 00:22:29,670 су правили било какве покрет са ногама, то је операција. 488 00:22:29,670 --> 00:22:33,610 Дакле, ако је било троје људи овде и нова особа припадало пут тамо, 489 00:22:33,610 --> 00:22:37,360 на дугом сцени као што је овај, наравно, он је или она само да оде до самог краја. 490 00:22:37,360 --> 00:22:40,074 Али, ако размишљамо о рачунара и низ меморије, 491 00:22:40,074 --> 00:22:41,990 ови људи иду морати дволичност преко 492 00:22:41,990 --> 00:22:43,260 како би направили места за ту особу. 493 00:22:43,260 --> 00:22:46,930 И тако да је н минус 1 схуффлингс, н минус 2 схуффлингс, н 494 00:22:46,930 --> 00:22:50,660 минус 3 схуффлингс је само врста дешава иза мене, не испред мене 495 00:22:50,660 --> 00:22:52,710 као и раније, у неком смислу. 499 00:22:52,557 --> 00:22:54,640 Сада као страну, и као можда сте видели на мрежи 500 00:22:54,640 --> 00:22:57,699 ако почнете убадањем негде око врсте, има толико различитих оне 501 00:22:57,699 --> 00:22:59,490 тамо, неки од њих боље од других. 502 00:22:59,490 --> 00:23:02,200 Заиста, богосорт је један То је врста забаве да се угледају. 503 00:23:02,200 --> 00:23:06,650 Богосорт узима сет бројеви или кажу шпил карата, 504 00:23:06,650 --> 00:23:09,870 случајно их схуффлес, и проверава да ли они сортирају. 505 00:23:09,870 --> 00:23:12,130 А ако не, то понови. 506 00:23:12,130 --> 00:23:14,140 А ако не, то понови. 507 00:23:14,140 --> 00:23:15,440 Ако не, не опет. 508 00:23:15,440 --> 00:23:17,060 Невероватно глупа. 509 00:23:17,060 --> 00:23:19,520 >> И заиста, ако сте прочитали као Википедиа артицле, 510 00:23:19,520 --> 00:23:21,200 његов надимак је глупо Сорт. 511 00:23:21,200 --> 00:23:25,180 То ће на крају радити, надамо се, дати довољно времена, 512 00:23:25,180 --> 00:23:28,240 али да количина времена могао да доста времена. 513 00:23:28,240 --> 00:23:31,650 Дакле, ако бих могао, хајде да убрзамо ствари се из Мари Бетх примеру раније, 514 00:23:31,650 --> 00:23:35,150 тако што још неколико елемената, али још два процесора. 515 00:23:35,150 --> 00:23:37,100 Двоје људи, вама ако Не би ми сметало ме придруживања. 516 00:23:37,100 --> 00:23:40,972 Како око 1 овде, и хајде да иде-- нико тамо? 517 00:23:40,972 --> 00:23:41,722 Нико тамо? 518 00:23:41,722 --> 00:23:42,221 У реду. 519 00:23:42,221 --> 00:23:44,190 Ви са црном мајица, да, хајде доле. 520 00:23:44,190 --> 00:23:45,000 У реду, како се зовеш? 521 00:23:45,000 --> 00:23:45,720 >> Публика: Питер. 522 00:23:45,720 --> 00:23:46,100 >> ПРЕДСЕДНИК: Шта је то? 523 00:23:46,100 --> 00:23:46,766 >> Публика: Питер. 524 00:23:46,766 --> 00:23:49,450 ГОВОРИ: Питер, Дејвид, драго ми је да смо се упознали. 525 00:23:49,450 --> 00:23:53,670 У реду, имамо Питер овде, ако желе да дођу на сто овде. 526 00:23:53,670 --> 00:23:54,550 А како се ти зовеш? 527 00:23:54,550 --> 00:23:55,216 >> Публика: Елена. 528 00:23:55,216 --> 00:23:55,970 ГОВОРИ: Елена. 529 00:23:55,970 --> 00:23:57,030 У реду, драго ми је да смо се упознали. 530 00:23:57,030 --> 00:23:58,060 Елена сусрет Петер. 531 00:23:58,060 --> 00:23:59,170 Питер, Елена. 532 00:23:59,170 --> 00:24:02,290 И ми ћемо морати Андрев овде као добро, молим те. 533 00:24:02,290 --> 00:24:06,107 И ваш изазов иде бити да сортирате шпил карата. 534 00:24:06,107 --> 00:24:08,190 А ако непознатим, Децк картица треба на крају 535 00:24:08,190 --> 00:24:11,064 бити сортирани нешто попут Ово где ћемо урадити клубове, а затим 536 00:24:11,064 --> 00:24:13,660 су спадес, онда срца и Дијаманти, од кеца као један, 537 00:24:13,660 --> 00:24:15,570 све до краља. 538 00:24:15,570 --> 00:24:20,890 >> Картице ћу ти дати ће бити 52 у количини. 539 00:24:20,890 --> 00:24:23,160 Идемо на сличан начин пут када, на тренутак. 540 00:24:23,160 --> 00:24:26,410 Идемо бацити Андрев појави на екрану овде, 541 00:24:26,410 --> 00:24:28,170 тако да гледају како се ово. 542 00:24:28,170 --> 00:24:31,070 И тако да је све ово је све видљивији, 543 00:24:31,070 --> 00:24:33,490 то су картице које сам добио на Амазон. 544 00:24:33,490 --> 00:24:42,861 Тако да већ насумично сортирају, а ми ћемо вас време. 545 00:24:42,861 --> 00:24:44,610 И ми ћемо Кееп Ит Реал овај пут, 546 00:24:44,610 --> 00:24:47,820 па ћемо покушати да вас притисак јер би у супротном то ће добити досадно 547 00:24:47,820 --> 00:24:48,460 брзо. 548 00:24:48,460 --> 00:24:53,860 Ако би могао да настави да сортирате 52 елементи заједно преко неки начин, сада. 549 00:24:53,860 --> 00:25:04,710 550 00:25:04,710 --> 00:25:07,180 >> И опет, као што гледамо ове момци шта ради, на крају 551 00:25:07,180 --> 00:25:10,200 ће производити очигледно Резултат, размислите о стварно 552 00:25:10,200 --> 00:25:12,962 како они то раде једни, како можете да га описати. 553 00:25:12,962 --> 00:25:15,045 Јер опет, су сви процеси, алгоритми 554 00:25:15,045 --> 00:25:17,090 да узимамо здраво за готово као човек. 555 00:25:17,090 --> 00:25:22,349 Али ви сте вероватно дуго интуиција, дуго пре него што чак и 556 00:25:22,349 --> 00:25:24,390 размишљала је о узимању Класа цомпутер сциенце вас 557 00:25:24,390 --> 00:25:27,223 можда имао интуицију са што за решавање проблема као што је овај. 558 00:25:27,223 --> 00:25:29,560 Али када препознајете обрасци и почну 559 00:25:29,560 --> 00:25:32,407 да формализују кораке са којима сте решавање ових проблема, 560 00:25:32,407 --> 00:25:35,490 ћете наћи да можете решити много занимљивији и много сложеније 561 00:25:35,490 --> 00:25:39,190 Проблеми брзо. 562 00:25:39,190 --> 00:25:42,351 Тако да неко из публике, што је најмање један елемент алгоритма 563 00:25:42,351 --> 00:25:43,350 да они користе овде? 564 00:25:43,350 --> 00:25:44,275 >> ПУБЛИКА: [неразумљиво] 565 00:25:44,275 --> 00:25:45,150 ПРЕДСЕДНИК: Шта је то? 566 00:25:45,150 --> 00:25:47,062 Публика: Би одело. 567 00:25:47,062 --> 00:25:47,770 ПРЕДСЕДНИК: По оделу. 568 00:25:47,770 --> 00:25:50,630 Дакле, прво су груписањем све дијаманата заједно 569 00:25:50,630 --> 00:25:52,560 чини, сви срца заједно Чини се, 570 00:25:52,560 --> 00:25:56,520 и тако даље, без поштовања за бројеве на картицама. 571 00:25:56,520 --> 00:26:00,900 А сада се појављују, на пример, да да их сортирате по броју. 572 00:26:00,900 --> 00:26:06,870 573 00:26:06,870 --> 00:26:08,910 Врло добро. 574 00:26:08,910 --> 00:26:12,370 >> У реду, па шта ће бити последњи корак онда овде? 575 00:26:12,370 --> 00:26:16,950 Једном када имамо четири разврстане одела, шта морамо да урадимо за четири гомиле 576 00:26:16,950 --> 00:26:20,059 у циљу постизања један поредани палуби, једноставно? 577 00:26:20,059 --> 00:26:21,350 Тако да морамо да их поново споји. 578 00:26:21,350 --> 00:26:25,160 >> Тако да је занимљива идеја која Опет, претпостављам, је веома интуитиван и 579 00:26:25,160 --> 00:26:28,140 ако никада можда ошамарио та врста етикете на њему. 580 00:26:28,140 --> 00:26:31,900 Овај фундаментални појам поделе Проблем није у пола овом тренутку, 581 00:26:31,900 --> 00:26:33,410 али најмање у четири комада. 582 00:26:33,410 --> 00:26:36,810 Решавање прилично суштински идентичне проблеме 583 00:26:36,810 --> 00:26:40,480 у изолацији сваке друге, и затим спајање резултате. 584 00:26:40,480 --> 00:26:46,940 585 00:26:46,940 --> 00:26:50,140 И, одлично, урађено. 586 00:26:50,140 --> 00:26:52,140 У реду, велики округли аплауз, ако бисмо могли. 587 00:26:52,140 --> 00:26:56,480 >> [АППЛАУСЕ] 588 00:26:56,480 --> 00:26:59,740 >> ПРЕДСЕДНИК: Немам појма шта ћете везе са овим, али ево ти. 589 00:26:59,740 --> 00:27:01,690 Хвала вам пуно. 590 00:27:01,690 --> 00:27:04,660 Па хајде да видимо, два минута и осам секунди, 591 00:27:04,660 --> 00:27:07,490 Ако желите да оспори своје пријатеље. 592 00:27:07,490 --> 00:27:12,160 Шта је онда ће бити одузети од овога 593 00:27:12,160 --> 00:27:13,830 да можемо искористити уопште? 594 00:27:13,830 --> 00:27:16,080 Па, мислим назад на Овај низ бројева, 595 00:27:16,080 --> 00:27:19,060 и мислим се сада на неке од Псеудокод смо написано у прошлости, 596 00:27:19,060 --> 00:27:22,080 и то је за Псеудокод решавање проблема у именику. 597 00:27:22,080 --> 00:27:25,150 При чему у Псеудокод И набројао више методички начин 598 00:27:25,150 --> 00:27:28,400 о описујући како сам урадио веома интуитиван људски алгоритам поделе телефон 599 00:27:28,400 --> 00:27:31,650 књига у пола, поновите, понављам, понављам, док не нађем неког попут Мике Смитх, 600 00:27:31,650 --> 00:27:33,790 Ако је он доиста у именику. 601 00:27:33,790 --> 00:27:37,610 >> Али сам некако користио шта ћу назвати веома итеративан приступ овде, 602 00:27:37,610 --> 00:27:42,160 посебно обавештењу линија 8 и линија 11. 603 00:27:42,160 --> 00:27:46,750 Они су доказ итеративни приступ, Лоопинг приступ, 604 00:27:46,750 --> 00:27:49,040 јер је то управо понашање које изазивају. 605 00:27:49,040 --> 00:27:52,910 Те линије оба кажу иди на Линија три, а можете некако 606 00:27:52,910 --> 00:27:55,140 мислим да је у вашем Еие ума као петља. 607 00:27:55,140 --> 00:27:59,080 Те је говорио да се вратите до корак три и понављам, опет, и опет, 608 00:27:59,080 --> 00:28:00,010 и поново. 609 00:28:00,010 --> 00:28:04,410 >> Али шта ако искористе кључну идеју овде да ми није последњи пут, 610 00:28:04,410 --> 00:28:10,280 и поједноставити линија 8 и линија 11 и њихови суседи 611 00:28:10,280 --> 00:28:12,840 јер управо то, у жуто. 612 00:28:12,840 --> 00:28:16,480 Није суштински скраћење Псеудокод веома много, 613 00:28:16,480 --> 00:28:20,530 али је у основи мења природа мог алгоритма. 614 00:28:20,530 --> 00:28:24,220 Оно што сада говорим у кораку 7, у кораку 10, 615 00:28:24,220 --> 00:28:29,140 је да се тражи за Мике на потпуно исти начин, 616 00:28:29,140 --> 00:28:31,580 али само у левој пола или десна половина. 617 00:28:31,580 --> 00:28:33,420 >> Другим речима, ако је Почнем од корака један, 618 00:28:33,420 --> 00:28:36,150 покупи телефонског именика, отворен до средине из именика, погледај имена, 619 00:28:36,150 --> 00:28:39,010 ако је Смит је међу име је, позовите Мајк, друго 620 00:28:39,010 --> 00:28:44,340 ако је Смит је раније у књизи, Седми корак сеарцх фор Мике ин левој половини књиге. 621 00:28:44,340 --> 00:28:47,130 Али та врста осећа као то ме оставља виси, зар не? 622 00:28:47,130 --> 00:28:49,240 У жутом, јесте упутство, али како радим 623 00:28:49,240 --> 00:28:51,870 сеарцх фор Мике у левој половина именика? 624 00:28:51,870 --> 00:28:54,210 Где имам алгоритам са којима сам 625 00:28:54,210 --> 00:28:57,100 да тражите некога као Мике Смитх? 626 00:28:57,100 --> 00:28:58,980 Па, то је нас буљи у лице. 627 00:28:58,980 --> 00:29:03,090 Ја могу да буквално користите исти Програм ефикасно иде до врха 628 00:29:03,090 --> 00:29:06,490 Поново и поново Трчање исти линија кода. 629 00:29:06,490 --> 00:29:10,610 >> Тако да, иако то треба да се осећа као мало у цикличне дефиниције 630 00:29:10,610 --> 00:29:13,480 где си одговарате неко Питање које некако питам 631 00:29:13,480 --> 00:29:15,990 Опет исто питање, као и зашто, зашто, зашто? 632 00:29:15,990 --> 00:29:21,580 Реалност је, јер смо напорно смо кодирана пар специјалних линија, корак 4, 633 00:29:21,580 --> 00:29:25,320 што је ако, и корак 12, који је ефективно друге гране, 634 00:29:25,320 --> 00:29:30,120 јер ми имамо те изрицање привремених мера, Овај алгоритам ће прекинути ако се 635 00:29:30,120 --> 00:29:32,050 наћи Мике, или ако то не урадимо. 636 00:29:32,050 --> 00:29:36,810 Али у кораку 7 и 10 Сада, имамо оно што ћемо назвати рекурзивни алгоритам. 637 00:29:36,810 --> 00:29:40,420 А Рекурзија је заиста моћан идеја то је мало ум савијање на први поглед, 638 00:29:40,420 --> 00:29:42,500 сада можемо применити на следећи начин. 639 00:29:42,500 --> 00:29:46,600 >> Мерге сорт ће бити последњи врста која гледамо, барем у класи формално. 640 00:29:46,600 --> 00:29:50,040 И то је суштински другачије од оне последње три, а сигурно 641 00:29:50,040 --> 00:29:52,140 последња четири ако се укључити богосорт. 642 00:29:52,140 --> 00:29:54,810 Ево Псеудокод за стапања врсте. 643 00:29:54,810 --> 00:30:00,170 Када је на улазу н елемената, тако да с обзиром низ величине н, ако је н мање од 2, 644 00:30:00,170 --> 00:30:01,040 вратити. 645 00:30:01,040 --> 00:30:03,610 Па зашто морам да Санити прво проверите? 646 00:30:03,610 --> 00:30:09,477 Шта је импликација ако те предати низ чија је дужина је н мање од 2? 647 00:30:09,477 --> 00:30:11,060 То је већ сортирају, очигледно, зар не? 648 00:30:11,060 --> 00:30:13,640 Јер листа или има један елемент, који је тривијално 649 00:30:13,640 --> 00:30:15,180 поредани зато што је једина ствар тамо. 650 00:30:15,180 --> 00:30:18,138 Или, то је од величине нула, што значи нема ништа за сортирање, тако по природи 651 00:30:18,138 --> 00:30:18,720 је сортирана. 652 00:30:18,720 --> 00:30:20,410 Нема баш ништа не ваља. 653 00:30:20,410 --> 00:30:22,310 Тако да је наш такозвани основни случај. 654 00:30:22,310 --> 00:30:24,440 >> То је слично у духу на оно што смо урадили са Мајком. 655 00:30:24,440 --> 00:30:26,023 Ако је Мајк је у телефонском именику, зови га. 656 00:30:26,023 --> 00:30:27,740 Ако он није тамо, одустати. 657 00:30:27,740 --> 00:30:31,240 То је такозвани основни случај, да се уверите Овај алгоритам на крају дана 658 00:30:31,240 --> 00:30:33,540 ће престати да у одређеним околностима. 659 00:30:33,540 --> 00:30:37,890 >> Али овде је Леап оф Фаитх сада, друго, сортирање левој половини елемената, 660 00:30:37,890 --> 00:30:39,740 затим сортирате право половина од елемената, 661 00:30:39,740 --> 00:30:41,189 а затим се стапа сортирани половине. 662 00:30:41,189 --> 00:30:43,230 А овде где се осећа да смо копирала напоље. 663 00:30:43,230 --> 00:30:46,900 Ја сам вас питао да сортирате н елемената, а ја сам 664 00:30:46,900 --> 00:30:50,712 говорећи, ОК, разумем сортирање по лево и сортирање право. 665 00:30:50,712 --> 00:30:52,420 Али ја кажем једну друга ствар, и ово 666 00:30:52,420 --> 00:30:55,530 је Кључна тема изгледа у интуицији до сада, 667 00:30:55,530 --> 00:30:57,380 ту је овај трећи корак спајања. 668 00:30:57,380 --> 00:31:00,430 Који чак иако њега изгледа тако глуп у духу, 669 00:31:00,430 --> 00:31:02,320 Као само спојити ствари заједно, чини 670 00:31:02,320 --> 00:31:05,380 бити кључни корак ка склапање два проблема који 671 00:31:05,380 --> 00:31:07,330 су на крају подељене на пола. 672 00:31:07,330 --> 00:31:12,090 >> Тако спајају врсте, хајде да урадимо ово, ако ћете хумор ми, са још једним демонстрацијама, 673 00:31:12,090 --> 00:31:14,730 само да имамо неке Бројеви за рад. 674 00:31:14,730 --> 00:31:19,470 Да ли могу да размењују осам стрес Лопте за осам људи? 675 00:31:19,470 --> 00:31:29,320 У реду, шта је са тобом три, ви Фоур У овом делу, пет, шест, и да 676 00:31:29,320 --> 00:31:30,720 Не 7, 8, хајде горе. 677 00:31:30,720 --> 00:31:35,120 678 00:31:35,120 --> 00:31:36,520 ОК, да у реду. 679 00:31:36,520 --> 00:31:38,640 Минус 8, тамо идемо, плус 1. 680 00:31:38,640 --> 00:31:39,150 Одлична. 681 00:31:39,150 --> 00:31:42,000 У реду хајде горе, хајдемо брзо вам бројеве. 682 00:31:42,000 --> 00:31:50,800 Број два, број три, број четири, број пет, шест, седам, осам и. 683 00:31:50,800 --> 00:31:52,140 Сам осам добро овај пут. 684 00:31:52,140 --> 00:31:56,390 >> У реду, тако да само напред ако можеш, и хајде да сортирају по оригиналном редоследу 685 00:31:56,390 --> 00:31:59,810 да смо имали јуче што је изгледало овако, ако не би сметало. 686 00:31:59,810 --> 00:32:03,620 И хајде да то урадимо испред стола. 687 00:32:03,620 --> 00:32:06,510 У реду, тако да споје врста. 688 00:32:06,510 --> 00:32:08,820 Ово је место где се иде да се занимљиво, 689 00:32:08,820 --> 00:32:12,800 јер изгледа да даје себе много мање информација данас. 690 00:32:12,800 --> 00:32:15,149 >> Па споји врста, пре свега на улазу од н елемената, 691 00:32:15,149 --> 00:32:18,440 и очигледно не мање од два, то је осам, тако да имам још мало посла. 692 00:32:18,440 --> 00:32:21,140 Дакле, сада смо ментално као класа су сада у другом грани, 693 00:32:21,140 --> 00:32:22,540 што значи три корака. 694 00:32:22,540 --> 00:32:25,017 Прво, морам да сортирате Лева половина елемената. 695 00:32:25,017 --> 00:32:26,350 Па како да идем о томе ово? 696 00:32:26,350 --> 00:32:28,950 Па, ја ћу некако ментално поделити листу овде, 697 00:32:28,950 --> 00:32:30,700 не морате да физички крећу, а ја сам 698 00:32:30,700 --> 00:32:33,180 ће се фокусирати само на Лева половина елемената овде. 699 00:32:33,180 --> 00:32:36,770 Па како да идем о сортирање Листа сада величине четири? 700 00:32:36,770 --> 00:32:38,730 Шта је мој алгоритам? 701 00:32:38,730 --> 00:32:42,580 Први пут сам проверити је н мање од два, не, па сам наставите на другом блоку поново. 702 00:32:42,580 --> 00:32:43,900 Сортирај левој половини елемената. 703 00:32:43,900 --> 00:32:45,608 >> Тако да сада опет, ментално, и ово је где 704 00:32:45,608 --> 00:32:49,550 морате да остварите много ментална историја, ако хоћете. 705 00:32:49,550 --> 00:32:51,940 Сада сам сортирање лево половина левој половини. 706 00:32:51,940 --> 00:32:57,000 У реду, тако да сада зовем свог исто стапање сортирање алгоритма, је н мање од два? 707 00:32:57,000 --> 00:33:00,590 Не, то је два, па морам да сортирате Лева половина, а десна половина. 708 00:33:00,590 --> 00:33:02,042 Па идемо, сортирање левој половини. 709 00:33:02,042 --> 00:33:03,750 Зашто једноставно не узети један корак напред. 710 00:33:03,750 --> 00:33:04,415 Како се зовеш? 711 00:33:04,415 --> 00:33:04,860 >> Публика: Даррен. 712 00:33:04,860 --> 00:33:05,260 >> ГОВОРИ: Дан. 713 00:33:05,260 --> 00:33:06,040 Дан је иступио. 714 00:33:06,040 --> 00:33:06,748 >> Публика: Даррен. 715 00:33:06,748 --> 00:33:09,000 ГОВОРИ: Дарен, урађено. 716 00:33:09,000 --> 00:33:10,090 Да ли сте рекли Дарен или Дан? 717 00:33:10,090 --> 00:33:10,550 >> Публика: Даррен. 718 00:33:10,550 --> 00:33:11,216 >> ГОВОРИ: Даррен. 719 00:33:11,216 --> 00:33:14,422 У реду, Даррен је изашао напред и он је сада сортирана. 720 00:33:14,422 --> 00:33:16,130 А ово је скоро Инане тврдња, зар не? 721 00:33:16,130 --> 00:33:18,862 Ја стварно не изгледа да се постизање ништа, али хајде да наставимо. 722 00:33:18,862 --> 00:33:20,820 Сад ме пусти да сортирате право половина елемената. 723 00:33:20,820 --> 00:33:21,200 Како се зовеш? 724 00:33:21,200 --> 00:33:21,690 >> Публика: Луке. 725 00:33:21,690 --> 00:33:22,273 >> ГОВОРИ: Луке. 726 00:33:22,273 --> 00:33:23,400 Хајде, иступи. 727 00:33:23,400 --> 00:33:25,640 Урађено, ја сам сортирано Луке. 728 00:33:25,640 --> 00:33:28,570 Лева половина је сада сортирају и десна половина сада сортиран, 729 00:33:28,570 --> 00:33:30,770 али опет, ту је кључни корак овде. 730 00:33:30,770 --> 00:33:32,940 Шта даље треба да урадим? 731 00:33:32,940 --> 00:33:33,941 Стопи сортирани половине. 732 00:33:33,941 --> 00:33:36,648 Сада ћемо само сви назад на овај начин, 733 00:33:36,648 --> 00:33:38,620 јер сам некако треба неки Сцратцх простора. 734 00:33:38,620 --> 00:33:40,411 То је скоро као ови момци су на столу, 735 00:33:40,411 --> 00:33:42,460 и треба ми мало места да их се креће даље. 736 00:33:42,460 --> 00:33:44,170 Па ћу да се споје момци би лоокинг 737 00:33:44,170 --> 00:33:45,960 на левој половини и десне половине. 738 00:33:45,960 --> 00:33:48,740 И који очигледно на првом месту, лева половина или десна половина? 739 00:33:48,740 --> 00:33:52,710 Дакле десна половина, па кренимо Луке над овде да првобитну позицију Даррен. 740 00:33:52,710 --> 00:33:57,640 И сада да споји своју леву половину у, Даррен ће да се креће тамо. 741 00:33:57,640 --> 00:33:59,750 >> Тако се осећа као готово ефекат балон врста, 742 00:33:59,750 --> 00:34:02,482 али мој основни алгоритам, другачије овај пут. 743 00:34:02,482 --> 00:34:04,815 Али сада је место где ствари постају мало досадна јер тебе 744 00:34:04,815 --> 00:34:06,810 морају ментално уназад где сам стали. 745 00:34:06,810 --> 00:34:09,893 Управо сам спојио разврстане половине, што значи да сам гдје у мом алгоритму? 746 00:34:09,893 --> 00:34:12,229 747 00:34:12,229 --> 00:34:13,770 Морам да сортирате десној половини, зар не? 748 00:34:13,770 --> 00:34:15,910 >> Ако се уназад, буквално на видео, ти ћеш 749 00:34:15,910 --> 00:34:18,339 видимо да смо на ово тачка Луке и Даррен 750 00:34:18,339 --> 00:34:21,370 сортирање улево за половина левој половини. 751 00:34:21,370 --> 00:34:23,430 Онда смо спојили оне сортирана половине, које 752 00:34:23,430 --> 00:34:27,941 значи следећи корак је врста десна половина леве половине. 753 00:34:27,941 --> 00:34:29,649 У реду, хајде да ово брже. 754 00:34:29,649 --> 00:34:33,282 У реду, шест, ја ћу тврде сада су поредани, хајде напред. 755 00:34:33,282 --> 00:34:33,990 Како се зовеш? 756 00:34:33,990 --> 00:34:34,589 >> Публика: Адриано. 757 00:34:34,589 --> 00:34:35,200 >> ГОВОРИ: Адриано. 758 00:34:35,200 --> 00:34:36,010 Адриано је сада сортирана. 759 00:34:36,010 --> 00:34:36,450 А како се ти зовеш? 760 00:34:36,450 --> 00:34:37,080 >> Публика: Алекс. 761 00:34:37,080 --> 00:34:38,379 >> ПРЕДСЕДНИК: Алекс је сада сортирана. 762 00:34:38,379 --> 00:34:40,750 Лева половина, десна половина, шта је финални корак? 763 00:34:40,750 --> 00:34:41,250 Мерге. 764 00:34:41,250 --> 00:34:44,310 Прилично тривијално, па сам ће да се споји у шест, 765 00:34:44,310 --> 00:34:46,930 узети корак уназад, осам, корак уназад. 766 00:34:46,930 --> 00:34:49,530 И сада приметити да је ово користан Такеаваи, шта 767 00:34:49,530 --> 00:34:53,930 је сада истина о левој половини листу, без обзира на то како смо почели? 768 00:34:53,930 --> 00:34:55,090 Се разврстава га. 769 00:34:55,090 --> 00:34:57,750 >> Сада то није разврстани у Велики шеми ствари, 770 00:34:57,750 --> 00:35:00,250 али је сортирана самостално на другу половину. 771 00:35:00,250 --> 00:35:04,100 Шта сад сам на корак ако наставим премотавање како се прича почела? 772 00:35:04,100 --> 00:35:05,680 Сада морам да сортирате десној половини. 773 00:35:05,680 --> 00:35:07,630 Дакле, сада смо пут назад на почетак приче, 774 00:35:07,630 --> 00:35:08,921 и хајде да урадимо то брже. 775 00:35:08,921 --> 00:35:11,320 Па ћу да сортирате десна половина целе листе. 776 00:35:11,320 --> 00:35:13,060 Шта је следећи корак? 777 00:35:13,060 --> 00:35:15,840 Сортирајте левој половини десној половини. 778 00:35:15,840 --> 00:35:18,715 Сортирајте левој половини Лева половина десној половини. 779 00:35:18,715 --> 00:35:19,590 А како се ти зовеш? 780 00:35:19,590 --> 00:35:20,230 >> Публика: Омар. 781 00:35:20,230 --> 00:35:21,970 >> ГОВОРИ: Омар, корак напред, урађено. 782 00:35:21,970 --> 00:35:22,860 Лева половина је сортиран. 783 00:35:22,860 --> 00:35:23,330 А како се ти зовеш? 784 00:35:23,330 --> 00:35:23,820 >> Публика: Крис. 785 00:35:23,820 --> 00:35:25,620 >> ГОВОРИ: Крис, узети корак напред, ви сте сада сортирају. 786 00:35:25,620 --> 00:35:27,010 Шта је кључни корак сада? 787 00:35:27,010 --> 00:35:27,510 Мерге. 788 00:35:27,510 --> 00:35:30,509 Дакле, један ће спојити своје место овде, ако би могао узети корак уназад, 789 00:35:30,509 --> 00:35:32,930 а три ће се узети корак уназад, спојити. 790 00:35:32,930 --> 00:35:38,080 Па левој половини десна половина, сада сортирана. 791 00:35:38,080 --> 00:35:41,747 Искрено, ово алгоритам изгледа као да се троши много више времена него раније, 792 00:35:41,747 --> 00:35:44,830 Али, ако то урадили у реалном времену, ми ћемо види шта Такеаваис ће бити. 793 00:35:44,830 --> 00:35:47,970 Сада сам овде, зар не половина десној половини, 794 00:35:47,970 --> 00:35:50,170 пусти ме само напред и сортирање левој половини. 795 00:35:50,170 --> 00:35:51,482 Корак напред, како се зовеш? 796 00:35:51,482 --> 00:35:52,190 Публика: Рамсеи. 797 00:35:52,190 --> 00:35:53,210 ПРЕДСЕДНИК: Рамсеи је сада сортирана. 798 00:35:53,210 --> 00:35:53,570 Како се зовеш? 799 00:35:53,570 --> 00:35:54,200 >> Публика: Марина. 800 00:35:54,200 --> 00:35:57,033 >> ПРЕДСЕДНИК: Марина је сада сортирано као Па, ако се узме један корак напред. 801 00:35:57,033 --> 00:36:00,690 Кључни корак овде сада споје, ја сам ће да уберу од мојих две листе, 802 00:36:00,690 --> 00:36:01,720 лево и десно. 803 00:36:01,720 --> 00:36:05,150 Пет ће прво доћи, и седам ће доћи следећи. 804 00:36:05,150 --> 00:36:06,410 И опет, ово је намерно. 805 00:36:06,410 --> 00:36:08,535 Чињеница да они узимање кораци напред и назад 806 00:36:08,535 --> 00:36:12,997 треба да представља да ми не можемо урадите алгоритам на месту лако 807 00:36:12,997 --> 00:36:15,830 као балон врсте и избор врсте, и убацивање Сорт где смо управо 808 00:36:15,830 --> 00:36:16,960 задржао замене људе. 809 00:36:16,960 --> 00:36:19,940 Буквално треба некакву допуном папира у којима 810 00:36:19,940 --> 00:36:21,827 да ове људе док ја радим спајање, 811 00:36:21,827 --> 00:36:23,410 а онда да их врати на место. 812 00:36:23,410 --> 00:36:27,260 И то је кључ, јер ја користим Нови ресурс, простор, не само време. 813 00:36:27,260 --> 00:36:28,270 >> ОК, ово је невероватно. 814 00:36:28,270 --> 00:36:32,050 Лева половина је сортиран, десна половина је сортирају, сада када кључни корак спајање. 815 00:36:32,050 --> 00:36:33,450 Како ћу да се споји ова? 816 00:36:33,450 --> 00:36:35,470 Дакле, ако ћете следити мој лева рука и десна рука, 817 00:36:35,470 --> 00:36:38,930 Идем да истакнем своју леву руку на левој половини, моја десна рука 818 00:36:38,930 --> 00:36:42,680 на десној половини, а сада морам да одлучује корак по корак које се спојили у. 819 00:36:42,680 --> 00:36:44,650 Који очигледно прво долази? 820 00:36:44,650 --> 00:36:45,150 Број један. 821 00:36:45,150 --> 00:36:47,327 Па хајде овамо, Овде је наш Сцратцх Пад. 822 00:36:47,327 --> 00:36:49,910 Тако да сада број један, и обавештење шта ћу да урадим са моје десне стране, 823 00:36:49,910 --> 00:36:54,152 Ја ћу да померим десну једну руку корак више до тачке број три, 824 00:36:54,152 --> 00:36:55,860 а сада морам да се Истом одлуком. 825 00:36:55,860 --> 00:36:58,387 И заправо стоје право у фронт Луке одавде ако би могао, 826 00:36:58,387 --> 00:36:59,720 јер ово је наш Сцратцх Пад. 827 00:36:59,720 --> 00:37:00,610 Дакле, ко следи? 828 00:37:00,610 --> 00:37:05,000 Имамо Луке са бројем два или Крис са бројем три. 829 00:37:05,000 --> 00:37:07,460 Очигледно је Луке, број два, па дођи овамо. 830 00:37:07,460 --> 00:37:11,270 >> Али моја лева рука сада ће се се додавати да се укаже на Даррен, 831 00:37:11,270 --> 00:37:15,160 а овде је кључ однесе са спајања, ја ћу да радим ово, 832 00:37:15,160 --> 00:37:17,340 Очигледно, ако вас љубазни о прати логику. 833 00:37:17,340 --> 00:37:19,670 Али руке су ми никада ићи уназад, 834 00:37:19,670 --> 00:37:23,861 што значи да само икада Селим се отишао са мојим процесом спајања, 835 00:37:23,861 --> 00:37:26,360 и то ће бити кључ за Наша анализа у само тренутак. 836 00:37:26,360 --> 00:37:27,859 >> Дакле, сада да завршимо ово брзо. 837 00:37:27,859 --> 00:37:31,650 Дакле, три следи, од четири следи, 838 00:37:31,650 --> 00:37:38,750 а сада Пет следи, онда шест, и седам, а на крају осам. 839 00:37:38,750 --> 00:37:42,960 Осећа као најспорији алгоритма још, али не ако ми заправо 840 00:37:42,960 --> 00:37:45,510 покрените га на исте врсте брзине такта, тако да 841 00:37:45,510 --> 00:37:48,106 говоре, са истим откуцава сат као и раније. 842 00:37:48,106 --> 00:37:48,605 Зашто? 843 00:37:48,605 --> 00:37:51,100 Па, узмимо погледати на крајњи резултат. 844 00:37:51,100 --> 00:37:56,990 >> Хајде да се вратимо овамо, пусти ме повуците демонстрацију визуелно 845 00:37:56,990 --> 00:37:59,030 шта смо урадили. 846 00:37:59,030 --> 00:38:06,110 Зумирање овде, на овом Страница овде, говорећи Фирефок 847 00:38:06,110 --> 00:38:08,200 да желимо да куеуе у овом пољу, хајдемо 848 00:38:08,200 --> 00:38:11,260 кажу балон врсте, са којим сада смо добро упознати, 849 00:38:11,260 --> 00:38:14,130 Избор врста, што је још један прилично једноставан један, 850 00:38:14,130 --> 00:38:18,250 а сада данашња стапања Сорт, која ће бити наш крај врхунца. 851 00:38:18,250 --> 00:38:21,530 Разлог тако трајало много дуже овде са људима и ја вербално је, 852 00:38:21,530 --> 00:38:23,480 Очигледно, ја објашњавам сваки корак. 853 00:38:23,480 --> 00:38:26,920 Али, ако једноставно извршите ову, много као што смо урадили балон врста и селекција 854 00:38:26,920 --> 00:38:30,890 Сортирај не само визуелно, Ватцх колико много ефикасније 855 00:38:30,890 --> 00:38:33,330 Ова задуживање од подела и освајања 856 00:38:33,330 --> 00:38:39,150 може бити када се примењује на скуп података који ни величине осам, али је чак и много, 857 00:38:39,150 --> 00:38:39,970 много већи. 858 00:38:39,970 --> 00:38:44,585 Дајем ти Сорт стопити, једни поред страна са овим другим алгоритама. 859 00:38:44,585 --> 00:38:56,364 860 00:38:56,364 --> 00:38:58,530 Ово ће добити болно брзо, и крај 861 00:38:58,530 --> 00:39:00,890 није посебно врхунца, они само завршити сортирају. 862 00:39:00,890 --> 00:39:05,280 Али кључ је да одузме Погледај колико брже спојити сорт 863 00:39:05,280 --> 00:39:08,110 је, осим ако ти мислиш да сам некако зезам са тобом. 864 00:39:08,110 --> 00:39:13,100 Ако то урадимо једном последњи пут, нека је Релоад тхис, хајде да се вратимо 865 00:39:13,100 --> 00:39:14,960 и изаберите балон врсте, а за сваки случај, 866 00:39:14,960 --> 00:39:17,330 Бирајмо уметање Сорт, само за добру меру. 867 00:39:17,330 --> 00:39:20,020 И овај пут опет, хајдемо бирају стапања врсте, па да 868 00:39:20,020 --> 00:39:21,595 заправо води ове раме уз раме. 869 00:39:21,595 --> 00:39:24,140 870 00:39:24,140 --> 00:39:26,930 >> И то није, у ствари, случајност. 871 00:39:26,930 --> 00:39:31,140 Оно што сам успешно урадио је да сам подељена мој улаз на пола, опет, 872 00:39:31,140 --> 00:39:32,240 и опет, и опет. 873 00:39:32,240 --> 00:39:35,590 И само толико пута можете да поделите унос у пола, лево 874 00:39:35,590 --> 00:39:36,240 и десно. 875 00:39:36,240 --> 00:39:39,425 Шта је формула која се виђати који описује поделу на пола 876 00:39:39,425 --> 00:39:41,050 опет, и опет, и опет, и опет? 877 00:39:41,050 --> 00:39:41,890 >> Публика: Лог Н. 878 00:39:41,890 --> 00:39:42,760 >> ПРЕДСЕДНИК: Лог Н. 879 00:39:42,760 --> 00:39:46,300 Али онда постоји један кључни корак, Овај алгоритам није лог н корака. 880 00:39:46,300 --> 00:39:48,992 Ако је само да се пријавите н кораци, бисмо били у истом проблему 881 00:39:48,992 --> 00:39:51,200 као и раније, где не можемо да будемо Сигуран је све сортирају. 882 00:39:51,200 --> 00:39:54,480 Морате да минимално погледамо н елемената како би били сигурни н елементи су поредани, 883 00:39:54,480 --> 00:39:55,950 иначе то је скок вере. 884 00:39:55,950 --> 00:39:59,810 >> Тако да је минимално дневник н корака, али је Шта је са овом кључном кораку спајању 885 00:39:59,810 --> 00:40:04,370 где сам спојио моје леве и десне половине пола и ходао по бини? 886 00:40:04,370 --> 00:40:06,980 Колико корака је то да се споје? 887 00:40:06,980 --> 00:40:10,150 То је н, али нисам само спајају крајње време. 888 00:40:10,150 --> 00:40:15,089 На сваком од тих угнежђених позива, на сваки тих угнежђених стапања, још увек сортирају. 889 00:40:15,089 --> 00:40:18,380 Ја спојио ова два типа, онда ова два момци, онда ова два момка и тако даље. 890 00:40:18,380 --> 00:40:19,955 >> Тако сам и урадио спајање опет, и опет. 891 00:40:19,955 --> 00:40:20,580 Колико пута? 892 00:40:20,580 --> 00:40:23,510 Тако да сваки пут кад подељено списак на пола, ја сам стапање. 893 00:40:23,510 --> 00:40:25,460 Поделити листу на пола, уради стапање. 894 00:40:25,460 --> 00:40:28,570 Дакле, ако дели листу може да се уради лог н пута, 895 00:40:28,570 --> 00:40:33,880 и спајање на крају узима Н кораци, оно што је можда сада горња 896 00:40:33,880 --> 00:40:37,000 везан на трчању време нашег алгоритма? 897 00:40:37,000 --> 00:40:37,980 н лог н. 898 00:40:37,980 --> 00:40:40,560 >> И заиста, то је оно смо овде постигли. 899 00:40:40,560 --> 00:40:44,650 Тако осећате да визуелно кад видиш Те три ствари води раме уз раме 900 00:40:44,650 --> 00:40:47,930 је н скуаред против Н квадрат против н лог н. 901 00:40:47,930 --> 00:40:51,010 Што суштински ћемо видети, не само данас, већ у будућности, 902 00:40:51,010 --> 00:40:52,760 је много, много брже. 903 00:40:52,760 --> 00:40:56,010 Аплауз за ове момке, Ја ћу их наградити са стреса лопти. 904 00:40:56,010 --> 00:41:00,260 Хајде да прекинемо са радом данас, и видимо се у понедељак. 905 00:41:00,260 --> 00:41:02,255