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