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