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