1 00:00:00,000 --> 00:00:03,332 >> [За възпроизвеждане на музика] 2 00:00:03,332 --> 00:00:06,490 >> АНДИ Пенг: Добре дошли в 3-та седмица на раздел. 3 00:00:06,490 --> 00:00:09,550 Благодаря, момчета, за всичко идва към настоящия момент по-рано старт днес. 4 00:00:09,550 --> 00:00:11,466 Имаме хубава, малко днес интимна група. 5 00:00:11,466 --> 00:00:14,570 Така че да се надяваме, че ще стигнем до удар, може би, по-рано, 6 00:00:14,570 --> 00:00:15,780 малко по малко рано днес. 7 00:00:15,780 --> 00:00:22,057 Така бързо, само някои Съобщения за днес в дневния ред. 8 00:00:22,057 --> 00:00:23,890 Преди да започнем, ние сме просто ще отидем 9 00:00:23,890 --> 00:00:28,910 няколко кратки логистични проблеми, pset въпроси, разпиташ, такива неща. 10 00:00:28,910 --> 00:00:30,250 И тогава ние ще се потопите полето инча 11 00:00:30,250 --> 00:00:34,710 Ще използваме дебъгер нарича GDB да започнем развенчаването нашия код, който David 12 00:00:34,710 --> 00:00:36,550 обяснено в лекция на другия ден. 13 00:00:36,550 --> 00:00:39,420 Ще отидем през четирите видове сортове. 14 00:00:39,420 --> 00:00:42,310 Ще отидем над тях доста бързо тъй като те са доста интензивно. 15 00:00:42,310 --> 00:00:45,710 Но знам, че всички слайдове и изходния код са винаги на линия. 16 00:00:45,710 --> 00:00:50,810 Така че не се колебайте, при вашия прочит, за да да се върнете и да погледнем на това. 17 00:00:50,810 --> 00:00:53,930 >> Ще проверете асимптотичната нотация, която 18 00:00:53,930 --> 00:00:55,944 е само един луксозен начин да казва "Времето на автономна работа," 19 00:00:55,944 --> 00:00:58,360 където имаме голямото О, които Дейвид обясни в лекция. 20 00:00:58,360 --> 00:01:01,550 И ние също имаме Omega, които е по-ниска, обвързана време на работа. 21 00:01:01,550 --> 00:01:06,450 И ние ще говорим малко по- по-задълбочено по отношение на това как те работят. 22 00:01:06,450 --> 00:01:10,160 И накрая, ние ще отидем двоично търсене, защото много от вас, които вече имат 23 00:01:10,160 --> 00:01:15,190 Погледна към вашите psets вероятно знаете, че това е въпрос, който е във вашия pset. 24 00:01:15,190 --> 00:01:17,470 Така че всички ще се радваме които ние покриваме това днес. 25 00:01:17,470 --> 00:01:20,610 >> И на последно място, на вашия обратна точка, аз всъщност 26 00:01:20,610 --> 00:01:23,000 наляво около 15 минути при края просто да отидем 27 00:01:23,000 --> 00:01:27,730 логистика на pset3, на всички въпроси, може би малко на насоки, ако щете, 28 00:01:27,730 --> 00:01:28,990 преди да започнем програмиране. 29 00:01:28,990 --> 00:01:30,890 Така че нека да се опитаме да се измъкне сам материала доста бързо. 30 00:01:30,890 --> 00:01:33,880 И тогава можем да прекарат известно време приемате повече въпроси за pset. 31 00:01:33,880 --> 00:01:35,230 ДОБРЕ. 32 00:01:35,230 --> 00:01:39,570 >> Бързо, така че само няколко съобщения, преди да започнем днес. 33 00:01:39,570 --> 00:01:45,410 Първо, добре дошли да направи то през две от вашите psets. 34 00:01:45,410 --> 00:01:49,432 Взех погледнете your-- да, нека получи аплодисменти за това. 35 00:01:49,432 --> 00:01:51,140 Всъщност, бях наистина, наистина впечатлен. 36 00:01:51,140 --> 00:01:55,800 I степен първата pset за вас, момчета миналата седмица и вие, момчета направиха невероятни. 37 00:01:55,800 --> 00:01:58,290 >> Style е на точка освен няколко коментара. 38 00:01:58,290 --> 00:02:00,660 Уверете се, че сте винаги коментирайки кода си. 39 00:02:00,660 --> 00:02:03,040 Но вашите psets бяха на точка. 40 00:02:03,040 --> 00:02:05,549 И да я поддържа. 41 00:02:05,549 --> 00:02:08,090 И това е добре за грейдер да виждам, че вие, момчета са пускането 42 00:02:08,090 --> 00:02:10,704 в толкова усилия в твоя стил и вашия проект в кода 43 00:02:10,704 --> 00:02:12,120 че ние бихме искали да видиш. 44 00:02:12,120 --> 00:02:16,450 Така че аз съм минаваща покрай своята благодарност за останалата част от TAS. 45 00:02:16,450 --> 00:02:19,210 >> Въпреки това има Няколко разпиташ въпроси 46 00:02:19,210 --> 00:02:22,010 Аз просто искам да разясни, че ще направи и двете ми живот 47 00:02:22,010 --> 00:02:24,900 и много от друга СНС "живее малко по-лесно. 48 00:02:24,900 --> 00:02:28,220 Първо, аз съм забелязал това покрай week-- колко от вас 49 00:02:28,220 --> 00:02:32,301 са течаща check50 на Код си, преди да подадете? 50 00:02:32,301 --> 00:02:32,800 ДОБРЕ. 51 00:02:32,800 --> 00:02:36,690 Така че всеки трябва да се прави check50, because-- на secret-- ние всъщност 52 00:02:36,690 --> 00:02:41,540 тичам check50 като част от нашата коректност скриптове за тестване на кода си. 53 00:02:41,540 --> 00:02:45,480 Така че, ако си код е неуспешен check50, по всяка вероятност, 54 00:02:45,480 --> 00:02:47,570 Това е може би щеше да провалят нашата проверка, както добре. 55 00:02:47,570 --> 00:02:49,320 Понякога вие, момчета, имаме правилните отговори. 56 00:02:49,320 --> 00:02:52,200 Подобно, в алчни, някои от имате правилните числа, 57 00:02:52,200 --> 00:02:53,960 просто разпечатате някои допълнителни неща. 58 00:02:53,960 --> 00:02:55,940 И това допълнителни неща всъщност не успее проверката, 59 00:02:55,940 --> 00:02:58,440 защото компютърът не наистина знаят какво търси. 60 00:02:58,440 --> 00:03:00,981 И така, той просто ще преминава през, се види, че вашата продукция не 61 00:03:00,981 --> 00:03:03,810 съвпада какво очакваме отговора да, и отбележете, че е погрешно. 62 00:03:03,810 --> 00:03:06,560 >> И знам, че се е случило в някои от вашите случаи тази седмица. 63 00:03:06,560 --> 00:03:09,870 Така че аз се върнах и ръчно преокачествило код на всеки. 64 00:03:09,870 --> 00:03:12,780 В бъдеще обаче, моля, моля, уверете се, 65 00:03:12,780 --> 00:03:14,570 че сте стартирали провери 50 на вашия код. 66 00:03:14,570 --> 00:03:17,970 Защото това е вид болка за ТП да се наложи да се върнете назад и ръчно преокачествяване 67 00:03:17,970 --> 00:03:21,197 всеки един pset за всеки единично, малко изпусна инстанция. 68 00:03:21,197 --> 00:03:22,530 Така че аз не се свали и да било пунктове. 69 00:03:22,530 --> 00:03:25,210 Мисля, че може би е излетял един или два за дизайн. 70 00:03:25,210 --> 00:03:27,710 В бъдеще обаче, ако което при липса на check50, 71 00:03:27,710 --> 00:03:31,330 Ще бъдат взети точки разстояние за коректност. 72 00:03:31,330 --> 00:03:35,020 >> Освен това са psets поради петък по обяд. 73 00:03:35,020 --> 00:03:38,990 Мисля, че има седем минути края на гратисен период, който ние ви даваме. 74 00:03:38,990 --> 00:03:42,434 Per Harvard време, те ти е позволено да е седем минути края на всичко. 75 00:03:42,434 --> 00:03:44,350 Така че тук в Йейл, ние ще се придържат към това, както добре. 76 00:03:44,350 --> 00:03:47,910 Но до голяма степен, в 12:07 часа, ако вашият pset не е в, 77 00:03:47,910 --> 00:03:49,720 то се случва да бъдат маркирани като късно. 78 00:03:49,720 --> 00:03:53,160 И така, докато той е маркиран най-късно, на TA-- съм 79 00:03:53,160 --> 00:03:54,870 все още продължава да бъде класификация на вашите psets. 80 00:03:54,870 --> 00:03:56,760 Така че все пак ще виждате оценка се появи. 81 00:03:56,760 --> 00:03:58,820 Въпреки това, знаем, че най- В края на семестъра, 82 00:03:58,820 --> 00:04:02,270 всички закъснели psets просто ще бъдат автоматично нулира от компютъра. 83 00:04:02,270 --> 00:04:04,490 >> Ние правим това по две причини. 84 00:04:04,490 --> 00:04:09,220 One, понякога получаваме извини, като извинения на Дийн, 85 00:04:09,220 --> 00:04:10,762 по-късно, че аз не знам все още наоколо. 86 00:04:10,762 --> 00:04:13,761 Така че сме искали да се уверете, че ние сме класификация всичко за всеки случай, като, аз съм 87 00:04:13,761 --> 00:04:15,080 липсва извинение на Дийн. 88 00:04:15,080 --> 00:04:17,000 И на второ място, имайте ум, все още можете да 89 00:04:17,000 --> 00:04:19,370 пуснете една pset че има пълния обхват точки. 90 00:04:19,370 --> 00:04:21,430 И така, ние искал да клас всички ваши psets просто 91 00:04:21,430 --> 00:04:24,730 за да се уверите, че вашият обхват на там и можете да започнете да ги изпробвате. 92 00:04:24,730 --> 00:04:29,150 Така че дори и да е късно, пак ще получите кредит за обхват точки, мисля. 93 00:04:29,150 --> 00:04:33,730 >> Така че моралната от историята е, уверете че вашите psets са в по-време. 94 00:04:33,730 --> 00:04:38,350 И ако те не са в по-време, знаем, че това не е голяма. 95 00:04:38,350 --> 00:04:41,678 Да, преди да се премине, не всеки има всички въпроси по отношение на обратна връзка pset? 96 00:04:41,678 --> 00:04:42,178 Да. 97 00:04:42,178 --> 00:04:43,630 >> АУДИТОРИЯ: Знаете ли, ние казваме може да пуснете един от psets? 98 00:04:43,630 --> 00:04:44,296 >> АНДИ Пенг: Да. 99 00:04:44,296 --> 00:04:47,050 Така че има девет psets цялостната в течение на семестъра. 100 00:04:47,050 --> 00:04:50,610 И ако имате обхват points-- така обхват е само, 101 00:04:50,610 --> 00:04:53,567 доста много, да не се опитва на проблем, са ви прати във времето, 102 00:04:53,567 --> 00:04:56,150 са ви показва, че сте демонстрирано сте чели спец. 103 00:04:56,150 --> 00:04:57,191 Това е доста повече свобода на действие. 104 00:04:57,191 --> 00:04:59,370 И ако се изпълнява обхват точки, ние 105 00:04:59,370 --> 00:05:03,360 може да падне най-ниската един на пълен обхват. 106 00:05:03,360 --> 00:05:06,790 Така че това е в своя полза, за да завърши и се опитват всеки pset. 107 00:05:06,790 --> 00:05:10,320 >> Дори upload-- ако никой от тях работят, ги качите. 108 00:05:10,320 --> 00:05:13,711 И тогава ние ще се надяваме да бъде в състояние да ви дам някои от тези точки назад. 109 00:05:13,711 --> 00:05:14,210 Готино. 110 00:05:14,210 --> 00:05:16,780 Всякакви други въпроси? 111 00:05:16,780 --> 00:05:17,840 Страхотен. 112 00:05:17,840 --> 00:05:21,960 >> На второ място, офис hours-- малцина бързи бележки за работното време. 113 00:05:21,960 --> 00:05:24,300 Така че на първо място, дойде по-рано през седмицата. 114 00:05:24,300 --> 00:05:26,909 Никой не е някога в работно време в понеделник. 115 00:05:26,909 --> 00:05:28,700 Кристабел дойде офис часа снощи. 116 00:05:28,700 --> 00:05:29,691 Да, Кристабел. 117 00:05:29,691 --> 00:05:32,190 И какво имаме в офиса часа снощи, Кристабел? 118 00:05:32,190 --> 00:05:33,020 >> АУДИТОРИЯ: Имахме сладолед. 119 00:05:33,020 --> 00:05:36,160 >> АНДИ Пенг: Така че това е правилно, имахме сладолед в офис часа снощи. 120 00:05:36,160 --> 00:05:39,390 Макар че аз не мога да ви обещая, че ще имаме сладолед в работно време 121 00:05:39,390 --> 00:05:43,230 всяка седмица, това, което мога да ви обещая е, че ще има значително 122 00:05:43,230 --> 00:05:45,380 по-добро съотношение ученик TA да. 123 00:05:45,380 --> 00:05:47,650 Подобно на легитимни, това е като 12:57. 124 00:05:47,650 --> 00:05:50,350 Като има предвид, че с контрастни Четвъртък, имаш около 150 125 00:05:50,350 --> 00:05:52,830 наистина подчерта деца и не сладолед. 126 00:05:52,830 --> 00:05:55,360 И това просто не е продуктивно за никого. 127 00:05:55,360 --> 00:05:58,730 Така Поука се, дойде по-рано до работното време и добри неща 128 00:05:58,730 --> 00:06:00,310 ще се случи. 129 00:06:00,310 --> 00:06:02,110 >> Също така, са подготвени да задават въпроси. 130 00:06:02,110 --> 00:06:03,200 Ти знаеш? 131 00:06:03,200 --> 00:06:05,420 Независимо от това, СНС, I мисля, са казва, 132 00:06:05,420 --> 00:06:10,710 ние сме били получаване на няколко студенти които идват в четвъртък при подобно, 10:50 133 00:06:10,710 --> 00:06:15,100 Не след като прочетох спец е като да ми помогне, да ми помогне. 134 00:06:15,100 --> 00:06:18,200 За съжаление в този момент, има Не можем да направим много, за да ви помогне. 135 00:06:18,200 --> 00:06:19,590 Така че заповядайте в началото на седмицата. 136 00:06:19,590 --> 00:06:22,040 Хайде рано да работно време. 137 00:06:22,040 --> 00:06:23,350 Хайде готови да задават въпроси. 138 00:06:23,350 --> 00:06:25,310 Уверете се, че вие, като студент, където са 139 00:06:25,310 --> 00:06:27,620 което трябва да бъде така, че СНС може да ви води напред, 140 00:06:27,620 --> 00:06:32,850 което е това работно време трябва да бъдат разпределени за. 141 00:06:32,850 --> 00:06:37,380 >> На второ място, така че знам професори искали да ни изненада с тестове. 142 00:06:37,380 --> 00:06:39,439 Имах един професор тези, харесват, йо, между другото, 143 00:06:39,439 --> 00:06:41,230 не забравяйте, че средносрочната имате следващия понеделник. 144 00:06:41,230 --> 00:06:42,855 Да, аз не знаех за това междинен. 145 00:06:42,855 --> 00:06:45,630 Така че аз отивам да се окаже, че TA което ви напомня, че всички викторина 146 00:06:45,630 --> 00:06:47,270 0--, защото, знаете, че сме CS. 147 00:06:47,270 --> 00:06:50,730 Сега, след като сме направили масиви, можете да получите защо е викторина 0, а не тест 1, а? 148 00:06:50,730 --> 00:06:51,320 ДОБРЕ. 149 00:06:51,320 --> 00:06:52,490 О, аз имам някои подсмихва за това. 150 00:06:52,490 --> 00:06:53,120 ДОБРЕ. 151 00:06:53,120 --> 00:06:59,710 >> Така викторина 0 ще бъде 14 октомври, ако вие сте в секцията понеделник-сряда 152 00:06:59,710 --> 00:07:02,920 и 15 октомври, ако сте в раздела вторник-четвъртък. 153 00:07:02,920 --> 00:07:05,630 Това не се отнася за тези от вас, в Харвард 154 00:07:05,630 --> 00:07:10,350 who-- Мисля, че всичко ще бъде като вашите викторини на 14-ти. 155 00:07:10,350 --> 00:07:13,560 >> Така че да, следващата седмица, ако Дейвид, в лекция, отива, 156 00:07:13,560 --> 00:07:15,747 Да, така, че за викторина следващата седмица, вие всички 157 00:07:15,747 --> 00:07:17,580 няма да бъде шокиран, защото ти дойде на вписванията 158 00:07:17,580 --> 00:07:19,664 и вие знаете, че вашето викторина 0 е след две седмици. 159 00:07:19,664 --> 00:07:21,580 И ще имаме мнение сесии и всичко. 160 00:07:21,580 --> 00:07:26,360 Така че не се притеснява за се уплаши за това. 161 00:07:26,360 --> 00:07:29,890 Всякакви въпроси before-- всякакви въпроси на всички по отношение на логистични проблеми, 162 00:07:29,890 --> 00:07:32,591 класифициране, работно време, раздели? 163 00:07:32,591 --> 00:07:33,090 Да. 164 00:07:33,090 --> 00:07:35,100 >> АУДИТОРИЯ: Така викторината е ще бъде по време на лекцията? 165 00:07:35,100 --> 00:07:35,766 >> АНДИ Пенг: Да. 166 00:07:35,766 --> 00:07:39,460 Така че теста, според мен, е 60 разпределени в това време слот минути 167 00:07:39,460 --> 00:07:42,240 че ще вземе само в лекционната зала. 168 00:07:42,240 --> 00:07:44,810 Така че не е нужно да дойде в на, като, случаен 19:00. 169 00:07:44,810 --> 00:07:46,140 Всичко е наред. 170 00:07:46,140 --> 00:07:47,100 Да. 171 00:07:47,100 --> 00:07:50,060 Готино. 172 00:07:50,060 --> 00:07:50,840 >> Всичко е наред. 173 00:07:50,840 --> 00:07:54,330 Така че ние ще въвеждане на концепцията за вас 174 00:07:54,330 --> 00:08:00,760 тази седмица, че Дейвид има вече вид на засегна в лекция през изминалата седмица. 175 00:08:00,760 --> 00:08:02,010 Тя се нарича GDB. 176 00:08:02,010 --> 00:08:05,570 И колко от вас, докато в хода на написването на вашите psets, 177 00:08:05,570 --> 00:08:09,981 са забелязали голям бутон, който казва, "Debug" в горната част на вашия IDE? 178 00:08:09,981 --> 00:08:10,480 ДОБРЕ. 179 00:08:10,480 --> 00:08:13,770 Така че сега ние всъщност ще получите да изкопае тайната на това, което бутон, който всъщност 180 00:08:13,770 --> 00:08:14,270 прави. 181 00:08:14,270 --> 00:08:16,790 И аз ви гарантирам, че е красиво, красиво нещо. 182 00:08:16,790 --> 00:08:20,740 >> Така че до сега, мисля, е имало две неща 183 00:08:20,740 --> 00:08:23,320 учениците са били типично прави и при дебъгването psets. 184 00:08:23,320 --> 00:08:27,635 One, те или се добавят в ФОРМАТ () - така че на всеки няколко линии, 185 00:08:27,635 --> 00:08:29,760 те добавят в ФОРМАТ () - О, каква е тази променлива? 186 00:08:29,760 --> 00:08:32,551 О, каква е тази променлива now-- и ти вид виж прогресията 187 00:08:32,551 --> 00:08:33,940 на кода си, тъй като работи. 188 00:08:33,940 --> 00:08:37,030 Или втория метод деца направя е че те просто напишете цялата работа 189 00:08:37,030 --> 00:08:38,610 и след това да отидете като тази в края. 190 00:08:38,610 --> 00:08:39,970 Надяваме се, че работи. 191 00:08:39,970 --> 00:08:44,851 Гарантирам ви, GDB е по-добре от двете от тези методи. 192 00:08:44,851 --> 00:08:45,350 Да. 193 00:08:45,350 --> 00:08:46,980 Така че това ще бъде вашият нов най-добър приятел. 194 00:08:46,980 --> 00:08:51,780 Защото е красиво нещо който нагледно показва и двете 195 00:08:51,780 --> 00:08:54,850 какъв е вашият код се справя в определен момент 196 00:08:54,850 --> 00:08:57,486 както и това, което всички си променливи са носещи, 197 00:08:57,486 --> 00:08:59,610 като това, което им стойности са, при тази конкретна точка. 198 00:08:59,610 --> 00:09:02,670 И по този начин, можете наистина определени точки на прекъсване в кода си. 199 00:09:02,670 --> 00:09:04,350 Можете да стартирате чрез ред по ред. 200 00:09:04,350 --> 00:09:07,324 И GDB просто ще трябва за ти, показва за вас, 201 00:09:07,324 --> 00:09:09,490 това, което всички ваши променливи са, какво правят те, 202 00:09:09,490 --> 00:09:10,656 какво се случва в кода. 203 00:09:10,656 --> 00:09:13,240 И по такъв начин, че е много по-лесно да се види 204 00:09:13,240 --> 00:09:17,120 какво се случва вместо ФОРМАТ-ING или записвам си отчети. 205 00:09:17,120 --> 00:09:19,160 >> Така че ние ще направим един пример за това по-късно. 206 00:09:19,160 --> 00:09:20,660 Така че това изглежда малко абстрактно. 207 00:09:20,660 --> 00:09:23,490 Не се тревожете, ще направя примери. 208 00:09:23,490 --> 00:09:29,170 И така, по същество, трите най-големи, Най-използвани функции ще трябва в GDB 209 00:09:29,170 --> 00:09:32,500 са следващите, Етап свърши, Стъпка в и бутони. 210 00:09:32,500 --> 00:09:34,860 Отивам да се над главата там, всъщност, точно сега. 211 00:09:34,860 --> 00:09:40,930 >> Така че може да ви види, че всички момчета или трябва да я увеличите малко? 212 00:09:40,930 --> 00:09:43,220 213 00:09:43,220 --> 00:09:44,470 В гърба, може ли това? 214 00:09:44,470 --> 00:09:45,730 Трябва ли да я увеличите? 215 00:09:45,730 --> 00:09:46,480 Само мъничко? 216 00:09:46,480 --> 00:09:49,390 ОК готино. 217 00:09:49,390 --> 00:09:50,280 Ето. 218 00:09:50,280 --> 00:09:50,960 ДОБРЕ. 219 00:09:50,960 --> 00:09:57,000 >> Така че аз имам, тук, ми изпълнение за алчни. 220 00:09:57,000 --> 00:10:01,430 И докато много от вас, момчета, е написал алчни в линия, докато form-- че 221 00:10:01,430 --> 00:10:04,890 е напълно приемлив начин да се направи it-- друг начин да го направите е просто да 222 00:10:04,890 --> 00:10:06,280 разделят в по модул. 223 00:10:06,280 --> 00:10:09,290 Защото тогава може да има вашия стойност и след това да си остатък. 224 00:10:09,290 --> 00:10:11,150 И тогава можете просто всичко това се добавят заедно. 225 00:10:11,150 --> 00:10:13,390 Дали логиката на това, което правя тук има смисъл за всички, 226 00:10:13,390 --> 00:10:14,117 преди да започнем? 227 00:10:14,117 --> 00:10:16,760 228 00:10:16,760 --> 00:10:17,980 Един вид? 229 00:10:17,980 --> 00:10:18,710 Готино. 230 00:10:18,710 --> 00:10:19,210 Страхотен. 231 00:10:19,210 --> 00:10:21,290 Това е доста секси парче на код, бих казал. 232 00:10:21,290 --> 00:10:23,502 Както казах, Дейвид, в лекция, след известно време, 233 00:10:23,502 --> 00:10:25,960 всички вие ще започнете да виждате код като нещо, което е красиво. 234 00:10:25,960 --> 00:10:29,950 И понякога, когато видите красива код, това е толкова прекрасно чувство. 235 00:10:29,950 --> 00:10:35,410 >> Така обаче, като в същото време този код е много красива, тя не работи правилно. 236 00:10:35,410 --> 00:10:37,750 Така че нека да тичам check50 по този въпрос. 237 00:10:37,750 --> 00:10:39,440 Проверете 50 20-- ООП. 238 00:10:39,440 --> 00:10:43,221 239 00:10:43,221 --> 00:10:43,720 2? 240 00:10:43,720 --> 00:10:44,990 Е, че pset2? 241 00:10:44,990 --> 00:10:46,870 Да. 242 00:10:46,870 --> 00:10:47,520 О, pset1. 243 00:10:47,520 --> 00:10:50,970 244 00:10:50,970 --> 00:10:52,890 ДОБРЕ. 245 00:10:52,890 --> 00:10:53,900 Така че ние тече check50. 246 00:10:53,900 --> 00:11:01,550 247 00:11:01,550 --> 00:11:07,170 >> И тъй като вие може да видите тук, това е липса на няколко случаи. 248 00:11:07,170 --> 00:11:10,165 А за някои от вас, в Разбира се за правене на проблемните комплекти, 249 00:11:10,165 --> 00:11:11,110 вие сте като, ах, защо не е тя работи. 250 00:11:11,110 --> 00:11:13,318 Защо е да работиш за някои ценности, но не и за другите? 251 00:11:13,318 --> 00:11:17,760 Е, GDB ще ви помогне да фигура защо тези входове не са работили. 252 00:11:17,760 --> 00:11:18,320 >> ДОБРЕ. 253 00:11:18,320 --> 00:11:21,640 Така че нека да видим, един от проверки бях успяват в check50 254 00:11:21,640 --> 00:11:24,920 е входна стойност от 0,41. 255 00:11:24,920 --> 00:11:27,830 Така че правилният отговор, че трябва да бъдат намалени е 4. 256 00:11:27,830 --> 00:11:33,090 Но вместо това, което аз съм отпечатване е 3-N, която е неправилна. 257 00:11:33,090 --> 00:11:36,190 Така че нека просто стартирате тази ръчно, просто уверете се, че check50 работи. 258 00:11:36,190 --> 00:11:36,940 Нека да направим ./greedy. 259 00:11:36,940 --> 00:11:40,130 260 00:11:40,130 --> 00:11:43,340 Ами сега, аз трябва да се направи алчни. 261 00:11:43,340 --> 00:11:43,840 Ето. 262 00:11:43,840 --> 00:11:44,381 Сега ./greedy. 263 00:11:44,381 --> 00:11:46,950 264 00:11:46,950 --> 00:11:47,670 >> Колко се дължи? 265 00:11:47,670 --> 00:11:49,550 Нека да направим 0.41. 266 00:11:49,550 --> 00:11:52,590 И да, ние виждаме тук че това е извеждане 3 267 00:11:52,590 --> 00:11:55,160 когато правилния отговор, Всъщност трябва да бъде 4. 268 00:11:55,160 --> 00:12:01,460 Така че нека да въведете GDB и да видим как можем да отидете за определяне на този проблем. 269 00:12:01,460 --> 00:12:03,992 >> Така че първата стъпка в Винаги дебъгване на кода 270 00:12:03,992 --> 00:12:05,950 е да се създаде точка на прекъсване, или точка, при която сте 271 00:12:05,950 --> 00:12:09,079 искате компютърът или дебъгер да започнат да търсят. 272 00:12:09,079 --> 00:12:11,120 Така че, ако наистина не знам какъв ти е проблема, 273 00:12:11,120 --> 00:12:14,670 Обикновено, типичната нещо, което искаме да направите, е да се създаде нашата точка на прекъсване на основното. 274 00:12:14,670 --> 00:12:18,520 Така че, ако вие може да видите това червения бутон, точно там, 275 00:12:18,520 --> 00:12:22,860 Да, това ме определя граничните стойности за основната функция. 276 00:12:22,860 --> 00:12:24,130 Аз кликнете върху него. 277 00:12:24,130 --> 00:12:26,130 >> И тогава мога да отида до моя бутон Debug. 278 00:12:26,130 --> 00:12:27,036 Ударих този бутон. 279 00:12:27,036 --> 00:12:31,710 280 00:12:31,710 --> 00:12:36,555 Позволете ми да я увеличите обратно, ако мога. 281 00:12:36,555 --> 00:12:38,020 Ето. 282 00:12:38,020 --> 00:12:40,730 Така че ние имаме, тук, на панел в дясно. 283 00:12:40,730 --> 00:12:43,680 Съжалявам, момчета в гърба, можете наистина не може да види много добре. 284 00:12:43,680 --> 00:12:49,090 Но по същество, цялата това право панел се справя 285 00:12:49,090 --> 00:12:53,130 се следене на двете маркирания линия, която е на линията на код 286 00:12:53,130 --> 00:12:56,640 че компютърът се изпълнява в момента, както и всички ваши променливи 287 00:12:56,640 --> 00:12:57,600 тук долу. 288 00:12:57,600 --> 00:13:00,487 >> Така че имаш цента, монети, п, всички декларирани за различни неща 289 00:13:00,487 --> 00:13:01,070 в този момент. 290 00:13:01,070 --> 00:13:04,850 Не се тревожете, защото имаме всъщност не ги инициализира с всички променливи, все още. 291 00:13:04,850 --> 00:13:07,200 Така че в компютъра си, вашият компютър е просто виждам, 292 00:13:07,200 --> 00:13:14,376 о, 32 767 е последната използвана функция на това място в паметта на компютъра ми. 293 00:13:14,376 --> 00:13:16,000 И така, това е мястото, където в момента е цента. 294 00:13:16,000 --> 00:13:19,360 Но не, че след като стартирате кода, тя трябва да се превърне Initialized. 295 00:13:19,360 --> 00:13:24,110 >> Така че нека да преминем, ред по линия, какво се случва тук. 296 00:13:24,110 --> 00:13:25,350 ДОБРЕ. 297 00:13:25,350 --> 00:13:29,400 Така че тук са тримата бутони, че аз просто обяснено. 298 00:13:29,400 --> 00:13:34,090 Имате играят, или функцията Run, бутон, имате Стъпка над бутона, 299 00:13:34,090 --> 00:13:36,600 и вие също имате стъпка в бутона. 300 00:13:36,600 --> 00:13:41,260 И по същество, всичките три от тях просто проверете кода си 301 00:13:41,260 --> 00:13:42,690 и правя различни неща. 302 00:13:42,690 --> 00:13:45,680 >> Така че обикновено, когато сте отстраняване на грешки, ние не искаме просто да натиснете възпроизвеждане, 303 00:13:45,680 --> 00:13:47,930 защото Играй просто ще тече Код си до края на това. 304 00:13:47,930 --> 00:13:49,070 И тогава няма да всъщност знам какво ти е проблема 305 00:13:49,070 --> 00:13:51,432 е, освен ако не сте задали множество точки на прекъсване. 306 00:13:51,432 --> 00:13:53,890 Ако сте задали множество точки на прекъсване, тя просто ще автоматично 307 00:13:53,890 --> 00:13:56,030 тече от една точка на прекъсване, към следващата, към следващата. 308 00:13:56,030 --> 00:13:58,030 Но в този случай ние сме Просто една, защото ние 309 00:13:58,030 --> 00:13:59,970 искат да работят пътя ни от горе надолу към долната част. 310 00:13:59,970 --> 00:14:04,830 Така че отиваме да се игнорира този бутон точно сега за целите на тази програма. 311 00:14:04,830 --> 00:14:08,230 >> Така стъпка над функцията просто стъпки над всеки един ред 312 00:14:08,230 --> 00:14:11,510 и ти казва какво компютърът се прави. 313 00:14:11,510 --> 00:14:14,630 Стъпката в функция отива в реалното действие 314 00:14:14,630 --> 00:14:16,000 това е на твоя ред код. 315 00:14:16,000 --> 00:14:19,070 Така например, като ФОРМАТ (), че е функция, нали? 316 00:14:19,070 --> 00:14:21,980 Ако исках да физически стъпка в () функцията ФОРМАТ, 317 00:14:21,980 --> 00:14:25,610 Бих действително отиде в парчето код, където ФОРМАТ () е написана и виж 318 00:14:25,610 --> 00:14:26,730 какво се случва там. 319 00:14:26,730 --> 00:14:29,924 >> Но обикновено, ние предполагаме, че код, който ние ви даваме работи. 320 00:14:29,924 --> 00:14:31,340 Ние поеме ФОРМАТ () работи. 321 00:14:31,340 --> 00:14:33,170 Предполагаме, че GetInt () работи. 322 00:14:33,170 --> 00:14:35,170 Така че няма нужда да се стъпка в тези функции. 323 00:14:35,170 --> 00:14:37,170 Но ако има функции че ти пиша себе си 324 00:14:37,170 --> 00:14:39,060 че искате да проверите какво се случва, 325 00:14:39,060 --> 00:14:41,200 вие ще искате да се оттегли в тази функция. 326 00:14:41,200 --> 00:14:43,940 >> Така че сега ние просто ще да се засили през тази част от кода. 327 00:14:43,940 --> 00:14:44,485 Така че нека да видим. 328 00:14:44,485 --> 00:14:46,547 О, печат, "О Хай, как особена промяна се дължи? " 329 00:14:46,547 --> 00:14:47,130 Не ни пука. 330 00:14:47,130 --> 00:14:49,830 Ние знаем, че е работа, така че ние стъпка над него. 331 00:14:49,830 --> 00:14:53,290 >> Така че п, което е нашата плувка, че ние сме initialized-- или declared-- 332 00:14:53,290 --> 00:14:56,810 нагоре към върха, ние сме сега са равни на това да GetFloat (). 333 00:14:56,810 --> 00:14:57,810 Така че нека да прекрача това. 334 00:14:57,810 --> 00:14:59,580 И ние виждаме в дъното тук, програмата 335 00:14:59,580 --> 00:15:03,360 ме накара да въведете стойност. 336 00:15:03,360 --> 00:15:08,580 Така че нека да вход стойността искаме за тестване тук, което е 0.41. 337 00:15:08,580 --> 00:15:09,160 Страхотен. 338 00:15:09,160 --> 00:15:12,780 >> Така че сега, N- направите вие, момчета, да видят тук, в bottom-- това е 339 00:15:12,780 --> 00:15:15,140 stored-- защото ние все още не са закръглени, това е 340 00:15:15,140 --> 00:15:19,540 съхраняват в тази като гигантски плувка, че е 0.4099999996, 341 00:15:19,540 --> 00:15:22,550 която е достатъчно близо до нашата цели, точно сега, на 0.41. 342 00:15:22,550 --> 00:15:26,090 И след това ще видим по-късно, тъй като ние продължи прекрачвайки програмата, 343 00:15:26,090 --> 00:15:29,850 след тук, п е станал закръглена и цента е станал 41. 344 00:15:29,850 --> 00:15:30,350 Страхотен. 345 00:15:30,350 --> 00:15:32,230 Така че ние знаем, че нашата работна закръгляване на. 346 00:15:32,230 --> 00:15:34,700 Ние знаем, че сме в правилния брой цента, 347 00:15:34,700 --> 00:15:36,990 така че ние знаем, че това е Не наистина проблема. 348 00:15:36,990 --> 00:15:40,050 >> Така че ние продължаваме засилването на в тази програма. 349 00:15:40,050 --> 00:15:40,900 Ние отидете тук. 350 00:15:40,900 --> 00:15:46,139 И така след този ред код, ние Трябва да знаете, колко квартали имаме. 351 00:15:46,139 --> 00:15:46,680 Ние прекрача. 352 00:15:46,680 --> 00:15:52,040 И вие виждате ние, всъщност, има право на един кв защото сме изважда 25 353 00:15:52,040 --> 00:15:53,790 от нашата първоначална стойност от 41. 354 00:15:53,790 --> 00:15:55,890 И ние имаме 16 ляв за нашите цента. 355 00:15:55,890 --> 00:15:58,830 >> Всички ли се разбере как програмата е чрез засилване 356 00:15:58,830 --> 00:16:02,980 и защо цента сега стават 16 и защо, сега, монети се превърна 1? 357 00:16:02,980 --> 00:16:04,610 Всеки ли след тази логика? 358 00:16:04,610 --> 00:16:05,110 Готино. 359 00:16:05,110 --> 00:16:07,860 Така че, считано от този момент, работна програма, нали? 360 00:16:07,860 --> 00:16:09,797 Ние знаем, че прави точно това, което ние го искам. 361 00:16:09,797 --> 00:16:11,880 И ние всъщност не Трябва да разпечатате, о, това, което 362 00:16:11,880 --> 00:16:14,430 е цента в този момент, това, което е монети по тази точка. 363 00:16:14,430 --> 00:16:17,170 >> Ние продължаваме да става чрез програмата. 364 00:16:17,170 --> 00:16:18,100 Стъпка свърши. 365 00:16:18,100 --> 00:16:18,620 Готино. 366 00:16:18,620 --> 00:16:19,700 Отиваме над десетки цента. 367 00:16:19,700 --> 00:16:20,200 Страхотен. 368 00:16:20,200 --> 00:16:22,367 Ние виждаме, че това е взето разстояние 0,10 $ за една стотинка. 369 00:16:22,367 --> 00:16:23,450 И сега имаме две монети. 370 00:16:23,450 --> 00:16:25,260 Това е правилното. 371 00:16:25,260 --> 00:16:31,555 >> Ние разясни жълти стотинки и ние виждаме че ние имаме останали цента. 372 00:16:31,555 --> 00:16:32,680 Хм, това е странно. 373 00:16:32,680 --> 00:16:37,540 До тук в програмата, аз трябваше да са изважда моите пари. 374 00:16:37,540 --> 00:16:39,400 Може би аз просто не беше правене на това право на линия. 375 00:16:39,400 --> 00:16:42,190 И уви, можете да видите тук, защото знаем 376 00:16:42,190 --> 00:16:44,360 че ние сме засилването през линии 32 и 33, 377 00:16:44,360 --> 00:16:50,560 това е, когато нашата програма неправилно имаше променливи работят. 378 00:16:50,560 --> 00:16:55,136 Така че ние можем да погледнем и да видим, о, Аз съм тук, за изваждане цента, 379 00:16:55,136 --> 00:16:57,010 но аз не съм в действителност добавяне към моята монета стойност. 380 00:16:57,010 --> 00:16:57,860 Аз съм като към цента. 381 00:16:57,860 --> 00:17:00,234 И аз не искам да се добави към цента, аз искате да добавите в монети. 382 00:17:00,234 --> 00:17:05,420 Така че, ако ние променяме, че да монетите, ние имаме работна програма. 383 00:17:05,420 --> 00:17:06,730 Мога да тичам check50. 384 00:17:06,730 --> 00:17:11,063 Ти просто да излезете от GDB полето тук и след това пуснете check50 отново. 385 00:17:11,063 --> 00:17:11,938 Бих могъл да направя това. 386 00:17:11,938 --> 00:17:14,822 387 00:17:14,822 --> 00:17:18,480 Аз трябва да направя алчни. 388 00:17:18,480 --> 00:17:19,940 0.41. 389 00:17:19,940 --> 00:17:22,819 И тук, това е печат от правилния отговор. 390 00:17:22,819 --> 00:17:26,569 >> Така че, както вие може да видите, GDB е наистина мощен инструмент 391 00:17:26,569 --> 00:17:29,940 защото, когато имаме толкова много код става и толкова много променливи 392 00:17:29,940 --> 00:17:32,510 че е трудно за нас, тъй като човек, за да следите. 393 00:17:32,510 --> 00:17:35,360 Компютърът, в GDB корекция на грешки, има способността 394 00:17:35,360 --> 00:17:37,020 , за да следите всичко. 395 00:17:37,020 --> 00:17:40,480 Знам, в Visionaire, вие вероятно можеше да удари някои сегментационни грешки 396 00:17:40,480 --> 00:17:43,150 защото вие вървяхте извън границите на масива. 397 00:17:43,150 --> 00:17:46,510 В примера на Цезар, това е точно това, което съм приложени тук. 398 00:17:46,510 --> 00:17:50,060 >> Така че аз забравих да проверите за какво ще се случи, ако аз 399 00:17:50,060 --> 00:17:52,510 не са имали два аргумента на командния ред. 400 00:17:52,510 --> 00:17:53,880 Аз просто не е пускал в тази проверка. 401 00:17:53,880 --> 00:17:57,380 И така, ако аз тичам Debug-- задам моята точка на прекъсване на дясно там. 402 00:17:57,380 --> 00:17:58,055 Аз тичам Debug. 403 00:17:58,055 --> 00:18:15,880 404 00:18:15,880 --> 00:18:16,550 >> ДОБРЕ. 405 00:18:16,550 --> 00:18:17,050 Да. 406 00:18:17,050 --> 00:18:20,350 Така че всъщност, GDB е трябвало да са ми казвали, че 407 00:18:20,350 --> 00:18:22,300 Беше сегментацията на вина там. 408 00:18:22,300 --> 00:18:24,883 Аз не знам какво се случва точно там, но когато той се стартира, 409 00:18:24,883 --> 00:18:25,590 той е работил. 410 00:18:25,590 --> 00:18:29,410 Когато стартирате реда код и чрез GDB може просто изведнъж се откажат от вас, 411 00:18:29,410 --> 00:18:31,540 отиде и да погледнем какво червената Грешката е. 412 00:18:31,540 --> 00:18:33,930 Тя ще ви кажа, хей, ти имаше вина сегментация, 413 00:18:33,930 --> 00:18:38,550 което означава, че сте се опитали да достъп пространство в масив, който не съществува. 414 00:18:38,550 --> 00:18:39,050 Да. 415 00:18:39,050 --> 00:18:43,280 >> Така в следващия проблем установени през тази седмица, момчета 416 00:18:43,280 --> 00:18:45,600 Вероятно ще има много променливи витае. 417 00:18:45,600 --> 00:18:48,560 Ти няма да бъде сигурен какво всички те имат предвид в определен момент. 418 00:18:48,560 --> 00:18:53,560 Така GDB наистина ще ви помогне в фигуриращ какво те всички са равни на 419 00:18:53,560 --> 00:18:55,940 и е в състояние да се види, че визуално. 420 00:18:55,940 --> 00:19:01,995 Има ли някой объркан за това как всеки от които е работил? 421 00:19:01,995 --> 00:19:02,495 Готино. 422 00:19:02,495 --> 00:19:10,121 423 00:19:10,121 --> 00:19:10,620 Всичко е наред. 424 00:19:10,620 --> 00:19:14,260 Така че след това, ние сме Ще се потопите полето 425 00:19:14,260 --> 00:19:17,562 в четири различни видове сортове за тази седмица. 426 00:19:17,562 --> 00:19:19,520 Колко от вас, първо от всички, преди да започнем, 427 00:19:19,520 --> 00:19:23,020 Прочетох цялата спец за pset3? 428 00:19:23,020 --> 00:19:23,824 ДОБРЕ. 429 00:19:23,824 --> 00:19:24,740 Гордея се с вас, момчета. 430 00:19:24,740 --> 00:19:29,110 Това е все едно половината от този клас, които е значително повече от миналия път. 431 00:19:29,110 --> 00:19:33,950 >> Така че това е страхотно, защото, когато говорим за съдържанието 432 00:19:33,950 --> 00:19:36,170 в lecture-- или съжалявам, в section-- ми харесва 433 00:19:36,170 --> 00:19:38,210 да се отнасят много, че обратно на това, което е pset 434 00:19:38,210 --> 00:19:40,210 и как искате да приложат, че във вашата pset. 435 00:19:40,210 --> 00:19:42,400 Така че, ако идват като Прочети спец, тя ще 436 00:19:42,400 --> 00:19:45,510 да бъде много по-лесно да се разбере това, което аз говоря за когато казвам, 437 00:19:45,510 --> 00:19:48,720 О, хей, това може да е наистина добро място за прилагане на този вид. 438 00:19:48,720 --> 00:19:52,870 Така че тези от вас, които са чели спец знам, че като част от вашия pset, 439 00:19:52,870 --> 00:19:54,900 започваш да се наложи да напиши тип сортиране. 440 00:19:54,900 --> 00:19:58,670 Така че това може да бъде много полезен за много от вас днес. 441 00:19:58,670 --> 00:20:01,760 >> Така че ние ще започнем с, същество, най-прост тип 442 00:20:01,760 --> 00:20:04,580 на сортиране, сортиране на подбор. 443 00:20:04,580 --> 00:20:06,800 Типичният алгоритъм за как щяхме да отида за това 444 00:20:06,800 --> 00:20:10,460 is-- Дейвид премина през всичко това в лекция, така че аз ще се движат по-бързо 445 00:20:10,460 --> 00:20:13,900 here-- е по същество, вие имаме масив от стойности. 446 00:20:13,900 --> 00:20:17,170 И след това да намерите най- най-малката стойност е сортиран 447 00:20:17,170 --> 00:20:20,200 и вие сменяте тази стойност с първата е сортиран стойност. 448 00:20:20,200 --> 00:20:22,700 И след това просто да повтаряме с останалата част от вашия списък. 449 00:20:22,700 --> 00:20:25,740 >> И тук е визуална обяснение за това как, че ще работи. 450 00:20:25,740 --> 00:20:30,460 Така например, ако бяхме да започнете с масив от пет елемента, индекс 451 00:20:30,460 --> 00:20:35,910 0 до 4, с 3, 5, 2, 6 и 4 стойности поставен в array-- така точно сега, 452 00:20:35,910 --> 00:20:38,530 ние просто ще приемем че всички те са неразделени 453 00:20:38,530 --> 00:20:41,130 защото не сме тествани по друг начин. 454 00:20:41,130 --> 00:20:44,130 >> И така, как един вид подбор ще работата е, че тя би първата 455 00:20:44,130 --> 00:20:46,800 тече през цялата на сортиран масив. 456 00:20:46,800 --> 00:20:49,120 Тя ще избирам най-малката стойност. 457 00:20:49,120 --> 00:20:51,750 В този случай, 3, нали сега, е най-малката. 458 00:20:51,750 --> 00:20:52,680 Той получава до 5. 459 00:20:52,680 --> 00:20:55,620 Не, не е по-голяма 5 than-- или съжалявам, е не по-малко than-- 3. 460 00:20:55,620 --> 00:20:57,779 Така че минималната стойност е все още 3. 461 00:20:57,779 --> 00:20:58,695 И тогава ще стигнем до 2. 462 00:20:58,695 --> 00:21:00,990 Компютърът вижда, о, 2 е по-малко от 3. 463 00:21:00,990 --> 00:21:02,750 2 сега трябва да е минималната стойност. 464 00:21:02,750 --> 00:21:06,630 И така 2 суапове с тази първа стойност. 465 00:21:06,630 --> 00:21:10,702 >> Така след един пас, ние наистина виж че на 2 и 3, се разменят. 466 00:21:10,702 --> 00:21:13,910 И ние просто ще продължа да правя това отново с останалата част от масива. 467 00:21:13,910 --> 00:21:17,660 Така че ние ще просто преминават през последните четири индекси на масива. 468 00:21:17,660 --> 00:21:20,670 Ще видите, че 3 е следващата минималната стойност. 469 00:21:20,670 --> 00:21:23,240 Така че ние ще се разменят, че с 4. 470 00:21:23,240 --> 00:21:26,900 И тогава ние просто ще се запази преминаващ през докато, в крайна сметка, вие 471 00:21:26,900 --> 00:21:33,730 стигнем до сортиран масив, в който 2, 3, 4, 5, 6 и всички са подредени. 472 00:21:33,730 --> 00:21:37,530 Всички ли разбере логиката за това как работи един вид селекция? 473 00:21:37,530 --> 00:21:39,669 >> Просто трябва някакъв вид на минимална стойност. 474 00:21:39,669 --> 00:21:41,210 Можете да започнете да следите какво е това. 475 00:21:41,210 --> 00:21:45,170 И всеки път, когато го намерите, можете да го сменяте с първата стойност в array-- 476 00:21:45,170 --> 00:21:48,740 или не първи value-- следващата стойност в масива. 477 00:21:48,740 --> 00:21:50,150 Готино. 478 00:21:50,150 --> 00:21:55,460 >> Така че, както вие вид Видях от един кратък поглед, 479 00:21:55,460 --> 00:21:58,450 ние ще Псевдокод това. 480 00:21:58,450 --> 00:22:02,510 Така че, ако вие в гърба искат да образуване на група, всички на една маса 481 00:22:02,510 --> 00:22:06,170 може да се образува малко партньор, аз ще съм да ви дам хора като три минути 482 00:22:06,170 --> 00:22:08,190 да говорим само чрез логиката, на английски език, 483 00:22:08,190 --> 00:22:14,161 за това, как може да сме в състояние да приложи Псевдокод да напише нещо като селекция. 484 00:22:14,161 --> 00:22:14,910 А има и бонбони. 485 00:22:14,910 --> 00:22:16,118 Моля, излезе и да получите бонбони. 486 00:22:16,118 --> 00:22:19,520 Ако сте в гърба и искате бонбони, мога да хвърлят бонбони на вас. 487 00:22:19,520 --> 00:22:22,850 Всъщност, направете you-- готино. 488 00:22:22,850 --> 00:22:23,552 О, съжалявам. 489 00:22:23,552 --> 00:22:26,751 490 00:22:26,751 --> 00:22:27,250 ДОБРЕ. 491 00:22:27,250 --> 00:25:23,880 492 00:25:23,880 --> 00:25:27,140 >> Така че, ако ние бихме искали да, тъй като клас, пиши Псевдокод 493 00:25:27,140 --> 00:25:30,466 за това как човек може да се обърне този проблем, просто се чувстват свободни. 494 00:25:30,466 --> 00:25:32,340 Аз просто ще обикалят и, с цел, да зададете групи 495 00:25:32,340 --> 00:25:35,065 за следващия ред на това, което ние трябва да се прави. 496 00:25:35,065 --> 00:25:37,840 Така че, ако вие искате да започнете разстояние, какво е първото нещо, 497 00:25:37,840 --> 00:25:40,600 да направя, когато се опитвате да приложат начин за решаване на тази програма 498 00:25:40,600 --> 00:25:43,480 селективно да сортирате списък? 499 00:25:43,480 --> 00:25:46,349 Нека просто да приемем, имаме масив, нали? 500 00:25:46,349 --> 00:25:49,088 >> АУДИТОРИЯ: Вие искате да се създаде някаква сортирай [недоловим], че вие ​​сте на 501 00:25:49,088 --> 00:25:50,420 преминаващ през цялата си гама. 502 00:25:50,420 --> 00:25:51,128 >> АНДИ Пенг: Точно така. 503 00:25:51,128 --> 00:25:54,100 Така че ти започваш да искаш да превъртите през всяко пространство, нали? 504 00:25:54,100 --> 00:26:05,490 Така че, страхотно. 505 00:26:05,490 --> 00:26:08,600 Ако вие искате да ми дадете Следващата line-- да, в гърба. 506 00:26:08,600 --> 00:26:11,414 507 00:26:11,414 --> 00:26:13,290 >> АУДИТОРИЯ: Проверете ги всички за най-малките. 508 00:26:13,290 --> 00:26:14,248 >> АНДИ Пенг: Ето. 509 00:26:14,248 --> 00:26:17,438 Така че ние искаме да мине през и проверете видим какво минималната стойност е, нали? 510 00:26:17,438 --> 00:26:22,110 511 00:26:22,110 --> 00:26:24,840 Отивам да се съкрати, че да "мин." 512 00:26:24,840 --> 00:26:27,658 Какво ви момчета искам да правя след намерили минималната стойност? 513 00:26:27,658 --> 00:26:28,533 >> АУДИТОРИЯ: [недоловим] 514 00:26:28,533 --> 00:26:29,942 515 00:26:29,942 --> 00:26:33,150 АНДИ Пенг: Значи ти започваш да искаш да го включите с първото от които масив, 516 00:26:33,150 --> 00:26:33,650 нали? 517 00:26:33,650 --> 00:26:45,120 518 00:26:45,120 --> 00:26:46,850 Това е началото, аз отивам да се каже. 519 00:26:46,850 --> 00:26:47,220 Всичко е наред. 520 00:26:47,220 --> 00:26:50,386 Така че сега, че сте замениха първите един, какво искаш да направя след това? 521 00:26:50,386 --> 00:26:54,840 Така че сега ние знаем, че този тук трябва да е най-малката стойност, нали? 522 00:26:54,840 --> 00:26:58,310 След това имате допълнителна почивка на масива, който е сортиран. 523 00:26:58,310 --> 00:27:01,569 Така че това, което искам да направя тук, ако сте момчета искат да ми даде следващия ред? 524 00:27:01,569 --> 00:27:04,610 АУДИТОРИЯ: Така че след това искате да превъртите през остатъка от масива. 525 00:27:04,610 --> 00:27:05,276 АНДИ Пенг: Да. 526 00:27:05,276 --> 00:27:09,857 И така, какво означава итерации през вид предполага ние вероятно ще трябва? 527 00:27:09,857 --> 00:27:10,440 Какъв тип of-- 528 00:27:10,440 --> 00:27:12,057 >> АУДИТОРИЯ: О, допълнителна променлива? 529 00:27:12,057 --> 00:27:13,890 АНДИ Пенг: Вероятно друг за цикъл, нали? 530 00:27:13,890 --> 00:27:28,914 Така че ние сме най-вероятно ще искате да превъртите through-- страхотно. 531 00:27:28,914 --> 00:27:31,830 И тогава започваш да се върна и да Вероятно провери минималната отново, 532 00:27:31,830 --> 00:27:32,100 нали? 533 00:27:32,100 --> 00:27:34,975 И ти започваш да продължават да повтарят това, защото примките просто отиваш 534 00:27:34,975 --> 00:27:36,010 да продължи да работи, нали? 535 00:27:36,010 --> 00:27:39,190 >> Така че, както вие може да видите, ние Просто има общо Псевдокод 536 00:27:39,190 --> 00:27:41,480 за това как искаме да изглежда тази програма. 537 00:27:41,480 --> 00:27:46,646 Това обхождане тук, това, което правим обикновено трябва да напишете в нашия код 538 00:27:46,646 --> 00:27:49,270 ако искаме да превъртите през масив, какъв тип структура? 539 00:27:49,270 --> 00:27:51,030 Мисля, че Кристабел Вече казах това преди. 540 00:27:51,030 --> 00:27:51,500 >> АУДИТОРИЯ: A за контур. 541 00:27:51,500 --> 00:27:52,160 >> АНДИ Пенг: A за цикъл? 542 00:27:52,160 --> 00:27:52,770 Точно. 543 00:27:52,770 --> 00:27:56,060 Така че това е може би ще бъде за контур. 544 00:27:56,060 --> 00:27:59,240 Какво е чек тук ще означава? 545 00:27:59,240 --> 00:28:02,536 Обикновено, ако искате да проверите ако нещо е нещо else-- 546 00:28:02,536 --> 00:28:03,270 >> АУДИТОРИЯ: Ако. 547 00:28:03,270 --> 00:28:06,790 >> АНДИ Пенг: An ако, нали? 548 00:28:06,790 --> 00:28:10,790 И тогава суапа тук, ние ще разясни по-късно, тъй като David 549 00:28:10,790 --> 00:28:12,770 премина през който в лекция, както добре. 550 00:28:12,770 --> 00:28:14,580 И тогава вторият ITERATE implies-- 551 00:28:14,580 --> 00:28:15,120 >> АУДИТОРИЯ: Друго за контур. 552 00:28:15,120 --> 00:28:16,745 >> АНДИ Пенг: --another за линия, точно. 553 00:28:16,745 --> 00:28:19,870 554 00:28:19,870 --> 00:28:22,000 Така че, ако ние не търсим при това правилно, ние 555 00:28:22,000 --> 00:28:24,680 да видим, че ние сме най-вероятно ще се нуждаят от вложените за контур 556 00:28:24,680 --> 00:28:28,330 с условен израз там и след това действително част от код, който е 557 00:28:28,330 --> 00:28:31,360 Ще сменяте стойностите. 558 00:28:31,360 --> 00:28:35,980 Така че аз съм просто обикновено написани код Псевдокод тук. 559 00:28:35,980 --> 00:28:38,910 И тогава ние всъщност ще физически, като клас, 560 00:28:38,910 --> 00:28:40,700 се опита да приложи това днес. 561 00:28:40,700 --> 00:28:42,486 Нека се върнем в тази IDE. 562 00:28:42,486 --> 00:28:49,243 563 00:28:49,243 --> 00:28:50,230 >> Охо. 564 00:28:50,230 --> 00:28:51,754 Защо е така not-- то е там. 565 00:28:51,754 --> 00:28:52,253 ДОБРЕ. 566 00:28:52,253 --> 00:28:55,834 567 00:28:55,834 --> 00:28:57,500 Съжаляваме, нека се опитам да я увеличите малко повече. 568 00:28:57,500 --> 00:28:59,310 Ето. 569 00:28:59,310 --> 00:29:05,060 Всичко, което правя тук, е че съм създал една програма, наречена "избор / sort.c." 570 00:29:05,060 --> 00:29:10,860 Аз създадох масив от девет стойности, 4, 8, 2, 1, 6, 9, 7, 5, 3. 571 00:29:10,860 --> 00:29:14,370 В момента, колкото можете виж, те са неподреден. 572 00:29:14,370 --> 00:29:17,880 п ще бъде броят, че ти казва размера на ценности 573 00:29:17,880 --> 00:29:18,920 имате в масив. 574 00:29:18,920 --> 00:29:20,670 В този случай, ние имаме девет стойности. 575 00:29:20,670 --> 00:29:23,760 И аз току-що получих за контур тук че отпечатва сортиран масив. 576 00:29:23,760 --> 00:29:28,370 >> И в крайна сметка, аз също имам един за линия, която просто го отпечатва отново. 577 00:29:28,370 --> 00:29:32,070 Така теоретично, ако тази програма работи правилно, в края, 578 00:29:32,070 --> 00:29:35,670 трябва да видите отпечатан за контур в който 1, 2, 3, 4, 5, 6, 7, 8, 579 00:29:35,670 --> 00:29:39,310 9 всички са правилно в ред. 580 00:29:39,310 --> 00:29:43,410 >> Така че ние имаме нашата Псевдокод тук. 581 00:29:43,410 --> 00:29:46,090 Някой иска to-- Аз съм просто щеше да отиде да поиска volunteers-- 582 00:29:46,090 --> 00:29:49,540 да ми каже точно какво да напишете, ако ние искаме да, на първо място, просто обхождане 583 00:29:49,540 --> 00:29:52,840 чрез началото на масив? 584 00:29:52,840 --> 00:29:55,204 Каква е ред на кода съм вероятно ще се нуждаят от тук? 585 00:29:55,204 --> 00:29:56,990 >> АУДИТОРИЯ: [недоловим] 586 00:29:56,990 --> 00:29:59,010 >> АНДИ Пенг: Да, чувствам безплатно to-- Съжалявам, вие 587 00:29:59,010 --> 00:30:02,318 не трябва да стоят up-- усещане свободни да повишаваш тон малко. 588 00:30:02,318 --> 00:30:08,190 >> АУДИТОРИЯ: За инт аз се равнява 0-- 589 00:30:08,190 --> 00:30:10,690 >> АНДИ Пенг: Да, добре. 590 00:30:10,690 --> 00:30:15,220 >> АУДИТОРИЯ: аз е по-малко от дължината масив. 591 00:30:15,220 --> 00:30:19,630 >> АНДИ Пенг: Така че имайте интересуваме тук, защото ние 592 00:30:19,630 --> 00:30:23,060 не разполагат с функция, която ни казва, дължината на масив, 593 00:30:23,060 --> 00:30:25,790 вече имаме стойност, която съхранява, че. 594 00:30:25,790 --> 00:30:27,920 Нали така? 595 00:30:27,920 --> 00:30:31,010 Друго нещо, което да се запази в mind-- в масив 596 00:30:31,010 --> 00:30:33,940 от девет стойности, какви са индексите? 597 00:30:33,940 --> 00:30:38,720 Нека просто кажем, този масив е 0-3. 598 00:30:38,720 --> 00:30:41,500 Вие виждате, че последният Индексът е всъщност 3. 599 00:30:41,500 --> 00:30:45,530 Това не е 4, въпреки че има четири стойности в масива. 600 00:30:45,530 --> 00:30:49,866 >> Така че тук, ние трябва да бъдем много внимателни от това, което ни състояние за дължината 601 00:30:49,866 --> 00:30:50,490 ще бъде. 602 00:30:50,490 --> 00:30:51,948 >> АУДИТОРИЯ: Няма ли да е п минус 1? 603 00:30:51,948 --> 00:30:54,440 АНДИ Пенг: Това ще п минус 1, точно. 604 00:30:54,440 --> 00:30:57,379 Това прави ли смисъл, защо това е п минус 1, всеки? 605 00:30:57,379 --> 00:30:58,920 Това е така, защото масиви са нулеви индексира. 606 00:30:58,920 --> 00:31:02,010 Те започват от 0 и тичам до п минус 1. 607 00:31:02,010 --> 00:31:03,210 Да, това е доста труден. 608 00:31:03,210 --> 00:31:03,730 ДОБРЕ. 609 00:31:03,730 --> 00:31:05,929 И тогава-- 610 00:31:05,929 --> 00:31:08,054 АУДИТОРИЯ: Isnt'1 че вече се погрижа за него все пак, 611 00:31:08,054 --> 00:31:11,400 чрез просто не казва "по-малка или равно на "и просто казвам" по-малко от? " 612 00:31:11,400 --> 00:31:13,108 >> АНДИ Пенг: Това е наистина добър въпрос. 613 00:31:13,108 --> 00:31:13,630 Така че, да. 614 00:31:13,630 --> 00:31:17,410 Но също така, начинът, по който сме прилагане на правото проверка, 615 00:31:17,410 --> 00:31:19,120 което трябва да се сравнят две стойности. 616 00:31:19,120 --> 00:31:21,009 Така че всъщност искате да напусне "да", когато е празна. 617 00:31:21,009 --> 00:31:23,050 Защото ако се сравни това, че няма 618 00:31:23,050 --> 00:31:25,530 има нещо, след като да се сравни с, нали? 619 00:31:25,530 --> 00:31:27,460 Да. 620 00:31:27,460 --> 00:31:29,297 Така че аз ++. 621 00:31:29,297 --> 00:31:30,380 Нека добавим нашите скоби инча 622 00:31:30,380 --> 00:31:30,880 Опа. 623 00:31:30,880 --> 00:31:33,950 624 00:31:33,950 --> 00:31:34,710 Страхотен. 625 00:31:34,710 --> 00:31:39,117 Така че ние имаме началото на нашия външен контур. 626 00:31:39,117 --> 00:31:41,450 Така че сега ние вероятно искате да създадете променлива за водене 627 00:31:41,450 --> 00:31:43,085 следите на най-малката стойност, нали? 628 00:31:43,085 --> 00:31:45,751 Някой иска ли да ми дадеш ред код, който би направил това? 629 00:31:45,751 --> 00:31:48,700 630 00:31:48,700 --> 00:31:53,570 Какво ни е нужно, ако отиваме да искате да съхраните нещо? 631 00:31:53,570 --> 00:31:55,047 >> Право. 632 00:31:55,047 --> 00:31:57,630 Може би по-добро име за това ще be-- "температура" напълно works-- 633 00:31:57,630 --> 00:32:00,655 Може би по-уместно наречена би било, ако искаме най-малката value-- 634 00:32:00,655 --> 00:32:01,624 >> АУДИТОРИЯ: Мин. 635 00:32:01,624 --> 00:32:02,790 АНДИ Пенг: мин, там да отидем. 636 00:32:02,790 --> 00:32:05,230 мин би било добре. 637 00:32:05,230 --> 00:32:08,340 И така тук, това, което правим искам да го инициализира да? 638 00:32:08,340 --> 00:32:09,620 Това е доста труден. 639 00:32:09,620 --> 00:32:13,580 Защото точно сега в началото на този масив, 640 00:32:13,580 --> 00:32:15,730 не сте погледна нещо, нали? 641 00:32:15,730 --> 00:32:19,200 И какво от това, автоматично, ако ние сме само на аз равна на 0, 642 00:32:19,200 --> 00:32:22,302 какво искаме да се инициализира първата ни минимална стойност да? 643 00:32:22,302 --> 00:32:22,802 АУДИТОРИЯ: аз. 644 00:32:22,802 --> 00:32:24,790 АНДИ Пенг: аз, точно. 645 00:32:24,790 --> 00:32:27,040 Кристабел, защо ние искаме да го инициализира да съм? 646 00:32:27,040 --> 00:32:28,510 >> АУДИТОРИЯ: Защото, добре, започваме с 0. 647 00:32:28,510 --> 00:32:31,660 Така че, тъй като ние нямаме нищо за сравнение да, минималните ще останат 0. 648 00:32:31,660 --> 00:32:32,451 >> АНДИ Пенг: Точно така. 649 00:32:32,451 --> 00:32:34,400 Така че тя е точно така. 650 00:32:34,400 --> 00:32:36,780 Защото ние имаме всъщност не погледна нищо все още, 651 00:32:36,780 --> 00:32:38,680 ние не знаем какво ни е минимална стойност. 652 00:32:38,680 --> 00:32:41,960 Искаме просто да го инициализира да аз, който, в момента, е точно тук. 653 00:32:41,960 --> 00:32:44,750 И докато ние продължаваме да се движат по този масив, 654 00:32:44,750 --> 00:32:48,122 ще видим, че с всяка допълнителна пас, аз инкрементира. 655 00:32:48,122 --> 00:32:49,830 И така, в този момент, аз вероятно ще 656 00:32:49,830 --> 00:32:52,329 да иска да бъде минимално, защото тя ще бъде независимо 657 00:32:52,329 --> 00:32:54,520 е началото на сортиран масив. 658 00:32:54,520 --> 00:32:55,270 Готино. 659 00:32:55,270 --> 00:32:58,720 >> Така че сега ние искаме да добавим а за цикъл тук това е 660 00:32:58,720 --> 00:33:03,225 ще превъртите през анализатора сортиран, или останалата част на този масив. 661 00:33:03,225 --> 00:33:05,808 Някой иска ли да ми дадете ред код, който би направил това? 662 00:33:05,808 --> 00:33:08,870 663 00:33:08,870 --> 00:33:11,330 Hint-- какво имаме нужда тук? 664 00:33:11,330 --> 00:33:17,320 665 00:33:17,320 --> 00:33:18,820 Какво се случва да отида в тази за цикъл? 666 00:33:18,820 --> 00:33:19,465 Да. 667 00:33:19,465 --> 00:33:21,590 АУДИТОРИЯ: Така че ние ще искате да имат различно число, 668 00:33:21,590 --> 00:33:25,080 защото сме минава през останалата на масива вместо I, така че може би 669 00:33:25,080 --> 00:33:25,760 к. 670 00:33:25,760 --> 00:33:27,301 >> АНДИ Пенг: Да, й звучи добре за мен. 671 00:33:27,301 --> 00:33:27,850 Равно на? 672 00:33:27,850 --> 00:33:33,930 >> АУДИТОРИЯ: Така ще бъде и плюс 1, защото сте се започне по време на следващата стойност. 673 00:33:33,930 --> 00:33:40,395 И тогава на end-- така отново, й е по-малко от N минус 1, и след това й ++. 674 00:33:40,395 --> 00:33:41,103 АНДИ Пенг: Great. 675 00:33:41,103 --> 00:33:48,510 676 00:33:48,510 --> 00:33:52,750 >> И тогава тук, ние ще искаме да проверите дали нашето условие е изпълнено, 677 00:33:52,750 --> 00:33:53,250 нали? 678 00:33:53,250 --> 00:33:55,740 Защото искате да промяна на минималната стойност 679 00:33:55,740 --> 00:33:58,700 ако това е действително по-малък от това, което сте го сравни с, нали? 680 00:33:58,700 --> 00:34:01,146 Така че какво ще искат тук? 681 00:34:01,146 --> 00:34:04,160 682 00:34:04,160 --> 00:34:04,897 Проверете, за да видите. 683 00:34:04,897 --> 00:34:06,730 Какъв вид на декларация ние вероятно ще 684 00:34:06,730 --> 00:34:08,389 ти искате да използвате, ако ние искам да проверя нещо? 685 00:34:08,389 --> 00:34:09,360 >> АУДИТОРИЯ: An ако изявление. 686 00:34:09,360 --> 00:34:10,485 >> АНДИ Пенг: An ако изявление. 687 00:34:10,485 --> 00:34:13,155 Така if-- и какво ще бъде при условие, че ние искаме вътре 688 00:34:13,155 --> 00:34:13,988 на нашия ако твърдение? 689 00:34:13,988 --> 00:34:18,255 690 00:34:18,255 --> 00:34:22,960 >> АУДИТОРИЯ: Ако стойността на к е по-малко от стойността на i-- 691 00:34:22,960 --> 00:34:24,600 >> АНДИ Пенг: Точно така. 692 00:34:24,600 --> 00:34:27,480 Така if-- така че този масив се нарича "масив." 693 00:34:27,480 --> 00:34:27,980 Страхотен. 694 00:34:27,980 --> 00:34:30,465 Така че, ако array-- какво беше това? 695 00:34:30,465 --> 00:34:31,090 Кажи, че отново. 696 00:34:31,090 --> 00:34:39,590 >> АУДИТОРИЯ: Ако масив-й е по-малко от масив-и, а след това ние ще се промени мин. 697 00:34:39,590 --> 00:34:41,590 Така минималната би й. 698 00:34:41,590 --> 00:34:44,590 699 00:34:44,590 --> 00:34:47,249 >> АНДИ Пенг: Това прави ли смисъл? 700 00:34:47,249 --> 00:34:48,670 ДОБРЕ. 701 00:34:48,670 --> 00:34:52,929 И сега тук, ние всъщност искат да приложат суапа, нали? 702 00:34:52,929 --> 00:34:58,285 Така че си спомняте, в лекция, че Давид, когато той се опитва да the-- какво е суап 703 00:34:58,285 --> 00:34:59,996 it-- портокалов сок и milk-- 704 00:34:59,996 --> 00:35:01,150 >> АУДИТОРИЯ: Това беше груба. 705 00:35:01,150 --> 00:35:02,816 >> АНДИ Пенг: Да, това е вид на брутния. 706 00:35:02,816 --> 00:35:05,310 Но това е един доста добър концепция демонстриране време. 707 00:35:05,310 --> 00:35:08,430 Така че мисля за вашите ценности тук. 708 00:35:08,430 --> 00:35:10,794 Имаш масив на мин, масив от I, 709 00:35:10,794 --> 00:35:12,460 или каквото и да се опитваше да сменяте тук. 710 00:35:12,460 --> 00:35:15,310 И най-вероятно няма да ги излее в помежду си по едно и също време, нали? 711 00:35:15,310 --> 00:35:17,180 Така че какво ще да се наложи да създадете тук 712 00:35:17,180 --> 00:35:19,126 за да сменяте стойностите правилно? 713 00:35:19,126 --> 00:35:19,820 >> АУДИТОРИЯ: A временна променлива. 714 00:35:19,820 --> 00:35:21,370 >> АНДИ Пенг: A временна променлива. 715 00:35:21,370 --> 00:35:22,570 Така че нека да направим инт темп. 716 00:35:22,570 --> 00:35:25,681 Виж, това ще бъде по-добре време to-- чакай, какво беше това? 717 00:35:25,681 --> 00:35:26,180 ДОБРЕ. 718 00:35:26,180 --> 00:35:29,800 Така че това би бил по-добър време, за да дадете име на променлива "темп." 719 00:35:29,800 --> 00:35:30,730 Така че нека да направим инт темп. 720 00:35:30,730 --> 00:35:32,563 Какво ще се Зададена темп, равен тук? 721 00:35:32,563 --> 00:35:34,752 722 00:35:34,752 --> 00:35:35,335 АУДИТОРИЯ: Мин? 723 00:35:35,335 --> 00:35:38,508 724 00:35:38,508 --> 00:35:39,716 АНДИ Пенг: Това е доста труден. 725 00:35:39,716 --> 00:35:43,110 726 00:35:43,110 --> 00:35:44,880 То всъщност не е от значение в крайна сметка. 727 00:35:44,880 --> 00:35:47,690 Няма значение какво За да решите да сменяте в 728 00:35:47,690 --> 00:35:50,862 толкова дълго, колкото можете да започнете като се уверите, че сте следене на това, което смяна. 729 00:35:50,862 --> 00:35:52,250 >> АУДИТОРИЯ: Тя може да бъде масив-и. 730 00:35:52,250 --> 00:35:53,666 >> АНДИ Пенг: Да, нека да направим масив-и. 731 00:35:53,666 --> 00:35:55,950 732 00:35:55,950 --> 00:35:59,305 И тогава какъв е следващия ред на код искаме да имаме тук? 733 00:35:59,305 --> 00:36:00,680 АУДИТОРИЯ: масив-и се равнява на масив-к. 734 00:36:00,680 --> 00:36:07,154 735 00:36:07,154 --> 00:36:08,070 АНДИ Пенг: И накрая? 736 00:36:08,070 --> 00:36:12,070 АУДИТОРИЯ: масив-к равнява масив-и. 737 00:36:12,070 --> 00:36:14,525 Публика: Or масив-к равни масив-temp-- или, темп. 738 00:36:14,525 --> 00:36:17,135 739 00:36:17,135 --> 00:36:19,430 >> АНДИ Пенг: OK. 740 00:36:19,430 --> 00:36:21,510 Така че нека да стартирате тази и виж ако то се случва да работи. 741 00:36:21,510 --> 00:36:37,520 742 00:36:37,520 --> 00:36:39,335 Къде е това да се случва? 743 00:36:39,335 --> 00:36:40,210 О, това е проблем. 744 00:36:40,210 --> 00:36:44,320 Виж, по линия 40, ние сме се опитва да използва масив-й? 745 00:36:44,320 --> 00:36:47,022 Но къде й съществува само в? 746 00:36:47,022 --> 00:36:48,402 >> АУДИТОРИЯ: В за контур. 747 00:36:48,402 --> 00:36:49,110 АНДИ Пенг: Точно така. 748 00:36:49,110 --> 00:36:51,730 Така че това, което ние ще трябва да направим? 749 00:36:51,730 --> 00:36:53,170 >> АУДИТОРИЯ: тя Дефинирайте извън the-- 750 00:36:53,170 --> 00:36:57,777 751 00:36:57,777 --> 00:37:00,610 АУДИТОРИЯ: Да, предполагам че имате да се използва друг, ако изявление, нали? 752 00:37:00,610 --> 00:37:05,230 Така че, както, ако minimum-- Добре, нека да помисля. 753 00:37:05,230 --> 00:37:08,170 754 00:37:08,170 --> 00:37:09,990 >> АНДИ Пенг: Момчета, опитайте да погледнете Нека 755 00:37:09,990 --> 00:37:11,270 виж, това, което е нещо, което ние можем да направим тук? 756 00:37:11,270 --> 00:37:11,811 >> АУДИТОРИЯ: OK. 757 00:37:11,811 --> 00:37:15,900 Така че, ако минималната не е равно j-- така че ако минималната е все още i-- 758 00:37:15,900 --> 00:37:17,570 тогава ние не би трябвало да сменяте. 759 00:37:17,570 --> 00:37:22,450 760 00:37:22,450 --> 00:37:24,712 >> АНДИ Пенг: Има ли, че равният аз? 761 00:37:24,712 --> 00:37:25,920 Какво искаш да кажеш тук? 762 00:37:25,920 --> 00:37:30,494 >> АУДИТОРИЯ: Или да, ако Минималната не е равно аз, да. 763 00:37:30,494 --> 00:37:39,627 764 00:37:39,627 --> 00:37:40,210 АНДИ Пенг: OK. 765 00:37:40,210 --> 00:37:42,040 Ами, която решава, вид, нашите проблеми. 766 00:37:42,040 --> 00:37:47,265 Но това все още не решава проблем от това, което се случва, ако j-- тъй к 767 00:37:47,265 --> 00:37:49,890 не съществува извън него, това, което искаш да искаме да правим с него? 768 00:37:49,890 --> 00:37:50,698 Декларирам, че навън? 769 00:37:50,698 --> 00:37:59,410 770 00:37:59,410 --> 00:38:02,730 Нека се опитаме да стартирате този. 771 00:38:02,730 --> 00:38:04,435 Охо. 772 00:38:04,435 --> 00:38:06,200 Нашият вид не работи. 773 00:38:06,200 --> 00:38:10,060 >> Както можете да видите, нашата първоначална масив имал тези ценности. 774 00:38:10,060 --> 00:38:14,800 И след това тя трябва да има е 1, 2, 3, 4, 5, 6, 7, 8, 9. 775 00:38:14,800 --> 00:38:15,530 Не работи. 776 00:38:15,530 --> 00:38:16,030 Ааа. 777 00:38:16,030 --> 00:38:17,184 И какво ще правим? 778 00:38:17,184 --> 00:38:17,850 АУДИТОРИЯ: Debug. 779 00:38:17,850 --> 00:38:21,787 780 00:38:21,787 --> 00:38:23,370 АНДИ Пенг: Добре, можем да се опитаме това. 781 00:38:23,370 --> 00:38:25,030 Ние можем да трасира. 782 00:38:25,030 --> 00:38:26,042 Намаляване малко. 783 00:38:26,042 --> 00:38:31,177 784 00:38:31,177 --> 00:38:33,656 Нека да поставим нашия точка на прекъсване. 785 00:38:33,656 --> 00:38:37,280 Нека да отидем like-- OK. 786 00:38:37,280 --> 00:38:40,444 >> Така че, защото ние вече знаем, че тези редове, 15, 22, чрез 787 00:38:40,444 --> 00:38:43,610 са working--, защото всичко, което правя е Просто итерации през и printing-- 788 00:38:43,610 --> 00:38:45,406 Мога да отида напред и да го пропуснем. 789 00:38:45,406 --> 00:38:47,280 Да започнем от линия 25. 790 00:38:47,280 --> 00:38:48,712 ООП, позволете ми да се отърва от това. 791 00:38:48,712 --> 00:38:51,598 792 00:38:51,598 --> 00:38:54,057 >> АУДИТОРИЯ: Така че точката на прекъсване на когато започва отстраняване на грешки? 793 00:38:54,057 --> 00:38:54,890 АНДИ Пенг: Or спирки. 794 00:38:54,890 --> 00:38:55,670 АУДИТОРИЯ: Or спирки. 795 00:38:55,670 --> 00:38:55,930 АНДИ Пенг: Да. 796 00:38:55,930 --> 00:38:58,640 Можете да настроите няколко точки на прекъсване и тя може просто да скочи от единия към другия. 797 00:38:58,640 --> 00:39:01,590 Но в този случай ние не знаем когато грешката се случва. 798 00:39:01,590 --> 00:39:03,780 Така че ние просто искаме да започнете от горе на долу. 799 00:39:03,780 --> 00:39:05,020 Да. 800 00:39:05,020 --> 00:39:05,550 ДОБРЕ. 801 00:39:05,550 --> 00:39:08,460 >> Така че тази линия тук, можем да стъпка инча 802 00:39:08,460 --> 00:39:11,499 Можете да видите тук долу, ние имаме масив. 803 00:39:11,499 --> 00:39:13,290 Това са ценностите които са в масива. 804 00:39:13,290 --> 00:39:16,360 Виждаш ли, че, как индекс 0, то съответства на value-- о, 805 00:39:16,360 --> 00:39:17,526 Аз ще се опитам да я увеличите инча 806 00:39:17,526 --> 00:39:20,650 Съжаляваме, това е наистина трудно да see-- в индекса масив 0, 807 00:39:20,650 --> 00:39:24,090 ние, имат стойност от 4 и След това така нататък и така нататък. 808 00:39:24,090 --> 00:39:25,670 Ние имаме нашите местни променливи. 809 00:39:25,670 --> 00:39:28,570 Точно сега аз се равнява на 0, което искаме да бъде. 810 00:39:28,570 --> 00:39:31,540 811 00:39:31,540 --> 00:39:33,690 >> И така, нека да се запази чрез засилване. 812 00:39:33,690 --> 00:39:36,850 Нашата минимум е равно на 0, които ние също искаме да бъде. 813 00:39:36,850 --> 00:39:39,470 814 00:39:39,470 --> 00:39:45,560 И тогава ние влиза втората ни за линия, ако масив-й е по-малко от масив-и, 815 00:39:45,560 --> 00:39:46,380 което не е. 816 00:39:46,380 --> 00:39:48,130 Така видя ли как че пропускани, че? 817 00:39:48,130 --> 00:39:52,430 >> АУДИТОРИЯ: Така трябва, ако минимум, всички that-- не трябва, че 818 00:39:52,430 --> 00:39:55,424 да бъде в рамките на първата за цикъл? 819 00:39:55,424 --> 00:39:57,340 АНДИ Пенг: Не, защото Все още ли искате да тествате. 820 00:39:57,340 --> 00:40:00,329 Искаш ли да правим съпоставка всеки време, дори и след като премине през него. 821 00:40:00,329 --> 00:40:02,620 Вие не просто искам да го направя на първия пропускателен. 822 00:40:02,620 --> 00:40:05,240 Искаш ли да го направя с отново всеки допълнителен пропуск. 823 00:40:05,240 --> 00:40:07,198 Значи вие искате да проверите за Вашето състояние вътре. 824 00:40:07,198 --> 00:40:11,610 825 00:40:11,610 --> 00:40:13,746 Така че ние просто ще продължи да работи през тук. 826 00:40:13,746 --> 00:40:17,337 827 00:40:17,337 --> 00:40:18,420 Аз ще ви дам момчета намек. 828 00:40:18,420 --> 00:40:23,910 Това е свързано с факта, че когато вие сте си проверявате условно, 829 00:40:23,910 --> 00:40:26,600 не сте проверка за правилното индекс. 830 00:40:26,600 --> 00:40:32,510 Така че сега можете да започнете проверка за масив индекс на й е по-малко от масив 831 00:40:32,510 --> 00:40:33,970 индекс на аз. 832 00:40:33,970 --> 00:40:36,580 Но това, което правиш най началото на за цикъл? 833 00:40:36,580 --> 00:40:38,260 Не те ли е създаването й, равна аз? 834 00:40:38,260 --> 00:40:41,260 835 00:40:41,260 --> 00:40:45,415 >> Да, така можем действително излезете дебъгер тук. 836 00:40:45,415 --> 00:40:47,040 Така че нека да погледнем на нашия Псевдокод. 837 00:40:47,040 --> 00:40:50,070 838 00:40:50,070 --> 00:40:52,580 For-- ние ще започнем аз равна на 0. 839 00:40:52,580 --> 00:40:54,760 Отиваме да отидете до п минус 1. 840 00:40:54,760 --> 00:40:58,040 Нека да се провери, дали имаме това право? 841 00:40:58,040 --> 00:40:59,580 Да, това е бил прав. 842 00:40:59,580 --> 00:41:02,080 >> Така че след това вътре тук, ние сме Ще създадете минимална стойност 843 00:41:02,080 --> 00:41:03,630 и определя, че равно на аз. 844 00:41:03,630 --> 00:41:04,950 Знаете го направим? 845 00:41:04,950 --> 00:41:06,270 Да, направих това. 846 00:41:06,270 --> 00:41:10,430 Сега в нашата вътрешна за цикъл, ние сме ще направим й се равнява аз да п минус 1. 847 00:41:10,430 --> 00:41:11,950 Знаете го направим? 848 00:41:11,950 --> 00:41:15,540 Всъщност, ние сме го направили. 849 00:41:15,540 --> 00:41:19,922 >> Така обаче, ние какво сравняването тук? 850 00:41:19,922 --> 00:41:20,925 >> АУДИТОРИЯ: й плюс 1. 851 00:41:20,925 --> 00:41:21,716 АНДИ Пенг: Точно така. 852 00:41:21,716 --> 00:41:24,184 853 00:41:24,184 --> 00:41:27,350 И тогава започваш да искате да зададете минималната си равна на к плюс 1, както добре. 854 00:41:27,350 --> 00:41:31,057 855 00:41:31,057 --> 00:41:32,640 Така че аз отидох чрез които наистина бързо. 856 00:41:32,640 --> 00:41:36,190 Мислите ли разбират защо е й плюс 1? 857 00:41:36,190 --> 00:41:36,890 ДОБРЕ. 858 00:41:36,890 --> 00:41:40,700 >> Така че във вашия масив, в първата си атака през, 859 00:41:40,700 --> 00:41:44,850 Вашата за линия, за инт аз е равна на 0, нека просто 860 00:41:44,850 --> 00:41:46,740 Предполагам, че това все още не е променен. 861 00:41:46,740 --> 00:41:53,180 862 00:41:53,180 --> 00:41:56,760 Ние имаме масив от, напълно, Само за четири несортиран елементи, нали? 863 00:41:56,760 --> 00:42:00,760 Така че ние искаме да се инициализира и да е равна на 0. 864 00:42:00,760 --> 00:42:03,650 И аз ще се просто тече през този цикъл. 865 00:42:03,650 --> 00:42:08,560 И така в първото преминаване, отиваме да инициализира променлива, наречена "мин" 866 00:42:08,560 --> 00:42:11,245 че да е равен I, защото ние нямаме минимална стойност. 867 00:42:11,245 --> 00:42:12,870 Така че това е момента, равна на 0, както добре. 868 00:42:12,870 --> 00:42:16,182 869 00:42:16,182 --> 00:42:17,640 И тогава ние ще преминеш. 870 00:42:17,640 --> 00:42:19,270 И ние искаме да превъртите отново. 871 00:42:19,270 --> 00:42:22,900 Сега, когато сме намерили това, което нашата минимална е, ние искаме да превъртите през 872 00:42:22,900 --> 00:42:25,190 отново, за да се види дали това е сравняването, нали? 873 00:42:25,190 --> 00:42:40,440 Така че й, тук, ще на равно и, която е 0. 874 00:42:40,440 --> 00:42:46,320 И тогава, ако масив й плюс аз, който е този, който е в непосредствена близост над, като по-малко 875 00:42:46,320 --> 00:42:49,270 от това, което вашата настояща минимум стойност е, което искате да сменяте. 876 00:42:49,270 --> 00:42:56,850 >> Така че нека просто кажем, ние сме имам подобно, 2, 5, 1, 8. 877 00:42:56,850 --> 00:43:01,610 Точно сега, аз се равнява на 0 и к е равно на 0. 878 00:43:01,610 --> 00:43:05,210 И това е нашата минимална стойност. 879 00:43:05,210 --> 00:43:09,950 Ако масив-к плюс i-- така че ако този, това е след този, който ние не търсим най- 880 00:43:09,950 --> 00:43:13,450 е по-голям от този преди него, това ще стане минимум. 881 00:43:13,450 --> 00:43:18,120 >> Така че тук ние виждаме, че 5 е не по-малко от това. 882 00:43:18,120 --> 00:43:19,730 Така то се случва да не бъде 5. 883 00:43:19,730 --> 00:43:23,580 Ние виждаме, че един е по-малко от 2, нали? 884 00:43:23,580 --> 00:43:32,970 Така че сега ние знаем, че нашето минимум е ще бъде стойността на индекса на 0, 1, 2. 885 00:43:32,970 --> 00:43:34,030 Да? 886 00:43:34,030 --> 00:43:39,170 И тогава, когато можете да получите тук, можете да сменяте точните стойности. 887 00:43:39,170 --> 00:43:42,610 >> Така че, когато вие просто имащи J преди, ти не гледаш този, 888 00:43:42,610 --> 00:43:43,260 след това. 889 00:43:43,260 --> 00:43:44,520 Можете гледаха същата стойност, която 890 00:43:44,520 --> 00:43:46,290 защо просто не се прави нищо. 891 00:43:46,290 --> 00:43:49,721 Това прави ли смисъл за всички, Затова е необходимо, че плюс 1 до там? 892 00:43:49,721 --> 00:43:50,220 ДОБРЕ. 893 00:43:50,220 --> 00:43:53,345 Сега нека просто преминават през него, за да уверите, останалата част от кода е правилен. 894 00:43:53,345 --> 00:44:04,424 895 00:44:04,424 --> 00:44:05,340 Защо се случва? 896 00:44:05,340 --> 00:44:14,780 897 00:44:14,780 --> 00:44:16,364 Ах, това е минималната точно тук. 898 00:44:16,364 --> 00:44:17,780 Ние сравняваме грешна стойност. 899 00:44:17,780 --> 00:44:24,944 900 00:44:24,944 --> 00:44:25,906 О, не. 901 00:44:25,906 --> 00:44:30,720 902 00:44:30,720 --> 00:44:33,482 >> О, да, тук бяхме смяна погрешни стойности, както добре. 903 00:44:33,482 --> 00:44:34,940 Защото ние гледахме аз и к. 904 00:44:34,940 --> 00:44:36,440 Това са тези, които ние се проверяват. 905 00:44:36,440 --> 00:44:39,160 Ние всъщност искаме да сменяте минимум текущия минимум, 906 00:44:39,160 --> 00:44:40,550 с каквато и да е една отвън е. 907 00:44:40,550 --> 00:44:59,510 908 00:44:59,510 --> 00:45:05,402 И тъй като вие може да видите надолу Оттук имаме сортиран масив. 909 00:45:05,402 --> 00:45:07,110 Той просто трябваше да направя с факта, че когато 910 00:45:07,110 --> 00:45:09,350 бяхме проверка на стойности бяхме сравняващи, 911 00:45:09,350 --> 00:45:11,226 ние не гледаха истинските ценности. 912 00:45:11,226 --> 00:45:13,850 Търсехме в същата тук, всъщност не го смяна. 913 00:45:13,850 --> 00:45:17,135 Вие трябва да погледнете този, следващия към нея, и след това можете да сменяте. 914 00:45:17,135 --> 00:45:19,260 Така че това е, което е вид подслушване нашия кодекс преди. 915 00:45:19,260 --> 00:45:22,460 И това, което направих тук е всичко, дебъгер би могъл да направи за вас 916 00:45:22,460 --> 00:45:23,810 Току-що го направих относно борда, защото е по-лесно 917 00:45:23,810 --> 00:45:26,320 да се види, а не се опитва за да увеличите дебъгер. 918 00:45:26,320 --> 00:45:29,391 Това прави ли смисъл на всички? 919 00:45:29,391 --> 00:45:29,890 Готино. 920 00:45:29,890 --> 00:45:34,800 921 00:45:34,800 --> 00:45:35,410 >> Всичко е наред. 922 00:45:35,410 --> 00:45:41,070 Ние можем да преминем към говорим за асимптотичната нотация, която 923 00:45:41,070 --> 00:45:44,580 е само един луксозен начин на казвайки на Времето на автономна работа на всички тези видове. 924 00:45:44,580 --> 00:45:47,650 Така че аз знам, Давид, в лекция, засегна Времето на автономна работа. 925 00:45:47,650 --> 00:45:52,124 И той премина през цялата формула за това как да се изчислят Runtimes. 926 00:45:52,124 --> 00:45:53,040 Не се тревожете за това. 927 00:45:53,040 --> 00:45:54,660 Ако сте наистина любопитно за това как, който работи, 928 00:45:54,660 --> 00:45:55,810 Чувствайте се свободни да говорят с мен, след точка. 929 00:45:55,810 --> 00:45:57,560 Ние можем да преминете през формули заедно. 930 00:45:57,560 --> 00:46:00,689 Но всички вие, момчета, трябва да наистина Знам само, че п квадрат над 2 931 00:46:00,689 --> 00:46:01,980 е същото като п квадрат. 932 00:46:01,980 --> 00:46:04,710 Тъй като най-голям брой, експонентата, расте най-много. 933 00:46:04,710 --> 00:46:06,590 И така, за нашите цели, всички ние се грижим за 934 00:46:06,590 --> 00:46:09,470 е, че гигантски номер, който се разраства. 935 00:46:09,470 --> 00:46:13,340 >> Така че това, което е най-добрия случай по време на работа на подбор подреди? 936 00:46:13,340 --> 00:46:15,830 Ако ще да има да превъртите през списък 937 00:46:15,830 --> 00:46:18,712 и след това чрез обхождане останалата част от този списък, 938 00:46:18,712 --> 00:46:20,420 колко пъти са Ще вероятно, 939 00:46:20,420 --> 00:46:24,612 в най-лошия case-- в най-добрия случай, sorry-- тече през? 940 00:46:24,612 --> 00:46:27,070 Може би най-добре е въпрос да попитам, какво е най-лошия случай 941 00:46:27,070 --> 00:46:28,153 по време на работа на подбор на сортиране. 942 00:46:28,153 --> 00:46:29,366 АУДИТОРИЯ: п квадрат. 943 00:46:29,366 --> 00:46:30,740 АНДИ Пенг: Тя е п квадрат, нали. 944 00:46:30,740 --> 00:46:36,986 Така че един лесен начин да се мисли за това е като, всеки път, когато има два вложени за електрически вериги, 945 00:46:36,986 --> 00:46:38,110 това ще бъде п квадрат. 946 00:46:38,110 --> 00:46:40,386 Защото не само вие сте минава през още веднъж, 947 00:46:40,386 --> 00:46:42,260 вие трябва да се върна около и тече през него 948 00:46:42,260 --> 00:46:44,980 отново вътре за всяка стойност. 949 00:46:44,980 --> 00:46:48,640 Така че в този случай, че работите п пъти п квадрат, което is-- съжалявам, 950 00:46:48,640 --> 00:46:50,505 п п пъти, което се равнява на п квадрат. 951 00:46:50,505 --> 00:46:53,230 952 00:46:53,230 --> 00:46:56,360 >> И нещо като също е малко по- уникален в смисъл 953 00:46:56,360 --> 00:46:59,774 че това няма значение, ако те стойности вече са в ред. 954 00:46:59,774 --> 00:47:01,440 Тя все още продължава да тече през всеки случай. 955 00:47:01,440 --> 00:47:03,872 Нека просто кажем, че това е 1, 2, 3, 4. 956 00:47:03,872 --> 00:47:07,080 Независимо от това дали или не е било в ред, тя все още щеше да прерови 957 00:47:07,080 --> 00:47:08,620 и все още се проверява минималната стойност. 958 00:47:08,620 --> 00:47:10,100 Той би направил същия брой проверки 959 00:47:10,100 --> 00:47:12,780 всеки път, дори ако това е всъщност не пипай нищо. 960 00:47:12,780 --> 00:47:16,940 >> Така че в този случай, най-доброто и най-лошото Времето на автономна работа всъщност са равностойни. 961 00:47:16,940 --> 00:47:19,160 Така очакваното време на работа на избор на сортиране, 962 00:47:19,160 --> 00:47:23,790 които определят със символа на тета, тета, в този случай, 963 00:47:23,790 --> 00:47:24,790 също ще бъдат п квадрат. 964 00:47:24,790 --> 00:47:26,480 Всички три от тях ще бъдат п квадрат. 965 00:47:26,480 --> 00:47:29,653 Всички ли ясно защо Времето на работа се п квадрат? 966 00:47:29,653 --> 00:47:33,360 967 00:47:33,360 --> 00:47:33,980 >> Всичко е наред. 968 00:47:33,980 --> 00:47:39,120 Така че аз съм просто ще пресипват през останалите сортове. 969 00:47:39,120 --> 00:47:41,137 Алгоритъмът за балон sort-- спомням, 970 00:47:41,137 --> 00:47:43,220 това е първият Давид мина в лекция. 971 00:47:43,220 --> 00:47:46,000 По същество, в който стъпка през целия списък 972 00:47:46,000 --> 00:47:48,950 и вие сте просто swap-- сравни две наведнъж. 973 00:47:48,950 --> 00:47:51,350 И ако някой е по-голяма, отколкото можете просто да ги сменяте. 974 00:47:51,350 --> 00:47:53,590 Така че, ако те са по-големи, ще сменяте. 975 00:47:53,590 --> 00:47:56,180 Имам официален точно тук. 976 00:47:56,180 --> 00:47:59,100 >> Така че нека просто кажем, сте имали 8, 6, 4, 2. 977 00:47:59,100 --> 00:48:00,571 Ще сравним 8 и 6. 978 00:48:00,571 --> 00:48:01,570 Вие ще трябва да ги разменят. 979 00:48:01,570 --> 00:48:02,610 Можете да сравните 8 и 4. 980 00:48:02,610 --> 00:48:03,609 Вие ще трябва да ги разменят. 981 00:48:03,609 --> 00:48:07,000 Ако се налага да сменяте 8 и на 2, да ги промени, както добре. 982 00:48:07,000 --> 00:48:10,760 Така че в такъв смисъл, можете да видите, разиграва в продължение на дълъг период от време, 983 00:48:10,760 --> 00:48:13,730 как стойности вида на балон, за да краищата, което е защо ние го наричат 984 00:48:13,730 --> 00:48:15,320 метод на мехурчето. 985 00:48:15,320 --> 00:48:19,950 >> Ние просто ще минава през отново вторият ни пас, а третият ни пас, 986 00:48:19,950 --> 00:48:21,150 и нашето четвърто пас. 987 00:48:21,150 --> 00:48:25,820 По същество, метод на мехурчето просто минава докато не направите повече суапове. 988 00:48:25,820 --> 00:48:31,109 Така че в този смисъл, това е просто широката Псевдокод за него. 989 00:48:31,109 --> 00:48:32,650 Не се тревожете, те всички ще бъдат на линия. 990 00:48:32,650 --> 00:48:34,990 Ние не трябва да всъщност разясни това. 991 00:48:34,990 --> 00:48:38,134 >> Ние просто се инициализира брояч променлива, която започва при 0. 992 00:48:38,134 --> 00:48:39,800 И ние превъртите през целия масив. 993 00:48:39,800 --> 00:48:43,420 И ако една стойност, ако това is-- стойност е по-голяма от тази стойност, 994 00:48:43,420 --> 00:48:44,610 започваш да ги разменят. 995 00:48:44,610 --> 00:48:46,860 И тогава ти си просто ще продължи да функционира. 996 00:48:46,860 --> 00:48:47,970 И ти започваш да се разчита. 997 00:48:47,970 --> 00:48:50,845 И вие просто ще продължаваш да правиш това, докато броячът е по-голяма 998 00:48:50,845 --> 00:48:53,345 от 0, което означава, че всеки път, когато се наложи да сменяте, 999 00:48:53,345 --> 00:48:55,220 Знаете ли, че искате да отидете назад и проверете отново. 1000 00:48:55,220 --> 00:48:59,510 Вие искате да запазите проверка, докато не разберете че не е нужно да сменяте вече. 1001 00:48:59,510 --> 00:49:05,570 >> Така че това, което са най-добрите и най-лошите При Runtimes за метод на мехурчето? 1002 00:49:05,570 --> 00:49:09,300 И hint-- това всъщност е различно от селекция подредени в смисъл, 1003 00:49:09,300 --> 00:49:11,810 че тези две отговори не са еднакви. 1004 00:49:11,810 --> 00:49:14,709 Помислете за това, което ще се случи в случай, ако е бил вече сортирани. 1005 00:49:14,709 --> 00:49:16,500 И мисля за това, ще се случи, ако беше 1006 00:49:16,500 --> 00:49:18,372 в случая, в който той не е бил сортиран. 1007 00:49:18,372 --> 00:49:20,580 И вие можете да стартирате вид чрез защо това се случва. 1008 00:49:20,580 --> 00:49:22,954 Аз ще ви дам момчета, като, 30 секунди, за да мислят за това. 1009 00:49:22,954 --> 00:49:52,330 1010 00:49:52,330 --> 00:49:53,540 >> ДОБРЕ. 1011 00:49:53,540 --> 00:49:57,462 Някой има ли предположение какво най-лошия случай по време на работа на метод на мехурчето е? 1012 00:49:57,462 --> 00:49:57,962 Да. 1013 00:49:57,962 --> 00:50:07,810 >> АУДИТОРИЯ: Би ли било, като, п пъти п минус 1 или нещо подобно? 1014 00:50:07,810 --> 00:50:10,650 Както всеки път, когато той работи, това е просто, като, един суап-малко 1015 00:50:10,650 --> 00:50:10,960 че каквото и да е било. 1016 00:50:10,960 --> 00:50:12,668 >> АНДИ Пенг: Да, така ти си напълно прав. 1017 00:50:12,668 --> 00:50:15,940 И това е случай, в който си Отговорът всъщност е по-сложна 1018 00:50:15,940 --> 00:50:17,240 от тази, която трябва да дадем. 1019 00:50:17,240 --> 00:50:19,772 Така че това ще run-- съм ще изтрие всичко това тук. 1020 00:50:19,772 --> 00:50:20,480 Всички ли добър? 1021 00:50:20,480 --> 00:50:21,869 Мога ли да залича това? 1022 00:50:21,869 --> 00:50:22,368 ДОБРЕ. 1023 00:50:22,368 --> 00:50:27,904 1024 00:50:27,904 --> 00:50:30,320 Ще преминете през п пъти първия път, нали? 1025 00:50:30,320 --> 00:50:33,200 И те започват да преминават през п минус 1 втори път, нали? 1026 00:50:33,200 --> 00:50:37,130 И тогава започваш да се запази ще, п мина 2, и така нататък. 1027 00:50:37,130 --> 00:50:40,210 Давид стори това в лекция, в която, Ако сте добавили до всички тези ценности, 1028 00:50:40,210 --> 00:50:48,080 можете да получите нещо, което е like-- yeah-- над 2, които по същество просто намалява 1029 00:50:48,080 --> 00:50:49,784 до п квадрат. 1030 00:50:49,784 --> 00:50:51,700 Вие ще получите странно фракция там. 1031 00:50:51,700 --> 00:50:53,892 И така, просто знам, че п квадрат винаги 1032 00:50:53,892 --> 00:50:55,350 има предимство пред фракцията. 1033 00:50:55,350 --> 00:50:58,450 И така, в този случай, най-лошото по време на работа ще бъде п квадрат. 1034 00:50:58,450 --> 00:51:00,210 Ако това беше в низходящ ред, мисля, вие 1035 00:51:00,210 --> 00:51:02,530 Трябва да се направи суап всеки един момент. 1036 00:51:02,530 --> 00:51:05,170 >> Какво би било, потенциално, най-добрия случай Времетраене? 1037 00:51:05,170 --> 00:51:08,580 Нека просто кажем, ако списъкът е вече , за това, което ще бъде време на работа? 1038 00:51:08,580 --> 00:51:09,565 >> АУДИТОРИЯ: п. 1039 00:51:09,565 --> 00:51:10,690 АНДИ Пенг: Това е п, точно. 1040 00:51:10,690 --> 00:51:11,600 И защо е п? 1041 00:51:11,600 --> 00:51:13,850 АУДИТОРИЯ: Защото вие просто трябва да се провери за всеки един път. 1042 00:51:13,850 --> 00:51:14,770 АНДИ Пенг: Точно така. 1043 00:51:14,770 --> 00:51:17,150 Така че в най-добрия възможен време на работа, ако този списък вече беше 1044 00:51:17,150 --> 00:51:20,270 sorted-- да речем 1, 2, 3, 4-- ви Просто ще преминем, ще покажат, 1045 00:51:20,270 --> 00:51:21,720 вие ще видите, о, всички те успявам. 1046 00:51:21,720 --> 00:51:22,636 Аз не се наложи да сменяте. 1047 00:51:22,636 --> 00:51:23,370 Приключих. 1048 00:51:23,370 --> 00:51:26,500 Така че в този случай, това е просто п или броя на стъпките, които просто 1049 00:51:26,500 --> 00:51:29,870 Трябваше да се провери в първия списък. 1050 00:51:29,870 --> 00:51:33,990 >> И след това, ние сега се удари сортиране чрез вмъкване, където 1051 00:51:33,990 --> 00:51:39,260 алгоритъмът е по същество да се разделят то в сортиран и сортиран порция. 1052 00:51:39,260 --> 00:51:42,810 И след това един по един, на несортиран стойности са 1053 00:51:42,810 --> 00:51:46,880 вмъква в тяхната целесъобразност позиции в началото на списъка. 1054 00:51:46,880 --> 00:51:52,120 >> Така например, ние имаме Списък на 3, 5, 2, 6, 4 отново. 1055 00:51:52,120 --> 00:51:54,750 Ние знаем, че това е в момента сортиран, защото ние току-що 1056 00:51:54,750 --> 00:51:57,030 Започнах да търся в него. 1057 00:51:57,030 --> 00:52:00,610 Ние да разгледаме и да знаем, че първата стойност се сортира, нали? 1058 00:52:00,610 --> 00:52:04,190 Ако сте само погледнете в масив от Размер на един, вие знаете, че това е сортирани. 1059 00:52:04,190 --> 00:52:08,230 >> Така че след това ние знаем, че Другите четири са неразделени. 1060 00:52:08,230 --> 00:52:10,980 Ние проверете и ние виждаме, че стойност. 1061 00:52:10,980 --> 00:52:11,730 Нека се върнем. 1062 00:52:11,730 --> 00:52:13,130 Виж, че стойността на 5? 1063 00:52:13,130 --> 00:52:14,110 Ние да разгледаме това. 1064 00:52:14,110 --> 00:52:15,204 Ние го сравни с 3. 1065 00:52:15,204 --> 00:52:17,870 Ние знаем, че това е по-голямо от 3, така че ние знаем, че това е сортирани. 1066 00:52:17,870 --> 00:52:22,940 Така че ние вече знаем, че първите две са подредени, а последните три не са. 1067 00:52:22,940 --> 00:52:24,270 >> Ние да разгледаме 2. 1068 00:52:24,270 --> 00:52:25,720 Ние първо да го проверите с 5. 1069 00:52:25,720 --> 00:52:26,700 Дали е по-малко от 5? 1070 00:52:26,700 --> 00:52:27,240 Не е. 1071 00:52:27,240 --> 00:52:29,510 Така че ние трябва да продължим да гледа надолу. 1072 00:52:29,510 --> 00:52:30,940 Тогава сте проверили 2 на разстояние 3. 1073 00:52:30,940 --> 00:52:31,850 Дали е по-малко от? 1074 00:52:31,850 --> 00:52:32,350 Не. 1075 00:52:32,350 --> 00:52:35,430 Така ли, че на 2 трябва да бъде поставена в предната и 3 и 5 1076 00:52:35,430 --> 00:52:38,200 и двамата трябва да се избута. 1077 00:52:38,200 --> 00:52:42,190 Направете това отново с 6 и 4. 1078 00:52:42,190 --> 00:52:48,962 И ние просто да продължите да следите по същество, където ние просто проверете, проверка, проверка. 1079 00:52:48,962 --> 00:52:51,170 И докато тя е в правото позиция, ние просто вид 1080 00:52:51,170 --> 00:52:54,890 поставете го в правилната позиция, което е мястото, където името му идва от. 1081 00:52:54,890 --> 00:52:59,830 >> Така че това е само алгоритъм, Псевдокод по себе си, нещо, 1082 00:52:59,830 --> 00:53:04,990 за това как бихме приложат вмъкване на сортиране. 1083 00:53:04,990 --> 00:53:05,954 Псевдокод е тук. 1084 00:53:05,954 --> 00:53:06,620 Всичко е на линия. 1085 00:53:06,620 --> 00:53:10,720 Не се тревожете, ако вие се се опитва да копира това надолу. 1086 00:53:10,720 --> 00:53:14,500 Така че още веднъж, същото question-- какво ще бъде най-добрият и най-лошите Runtimes 1087 00:53:14,500 --> 00:53:16,120 за сортиране чрез вмъкване? 1088 00:53:16,120 --> 00:53:17,750 Това е много подобен на последния въпрос. 1089 00:53:17,750 --> 00:53:20,479 Аз ще ви дам момчета, като, 30 секунди, за да мислят за това, както добре. 1090 00:53:20,479 --> 00:53:47,150 1091 00:53:47,150 --> 00:53:50,071 >> OK Някой иска да дайте ми най-лошото време на работа? 1092 00:53:50,071 --> 00:53:50,570 Да. 1093 00:53:50,570 --> 00:53:51,490 >> АУДИТОРИЯ: п квадрат. 1094 00:53:51,490 --> 00:53:52,573 >> АНДИ Пенг: Тя е п квадрат. 1095 00:53:52,573 --> 00:53:53,730 И защо е п квадрат? 1096 00:53:53,730 --> 00:53:57,562 >> АУДИТОРИЯ: Защото в обратен ред, имате 1097 00:53:57,562 --> 00:54:02,619 да мине през п пъти п, които is-- 1098 00:54:02,619 --> 00:54:03,660 АНДИ Пенг: Да, точно така. 1099 00:54:03,660 --> 00:54:06,610 Така че едно и също нещо, както е в нещо като балон. 1100 00:54:06,610 --> 00:54:08,720 Ако този списък е в низходящ ред, вие сте 1101 00:54:08,720 --> 00:54:11,240 ще трябва да се провери първо веднъж. 1102 00:54:11,240 --> 00:54:13,470 И след това с всеки допълнителна стойност, вие сте 1103 00:54:13,470 --> 00:54:16,390 Ще трябва да го проверите срещу всяка една стойност, нали? 1104 00:54:16,390 --> 00:54:20,290 И така напълно, ти започваш да се направи един пъти п мине друг п минават, които 1105 00:54:20,290 --> 00:54:21,750 п е квадрат. 1106 00:54:21,750 --> 00:54:22,860 Какво ще кажете за най-добрия случай? 1107 00:54:22,860 --> 00:54:24,360 Да. 1108 00:54:24,360 --> 00:54:28,840 >> АУДИТОРИЯ: п минус 1, тъй като на Първият е вече на квадрат. 1109 00:54:28,840 --> 00:54:30,270 >> АНДИ Пенг: Така че, в близост. 1110 00:54:30,270 --> 00:54:31,850 Отговорът всъщност е п. 1111 00:54:31,850 --> 00:54:37,189 Тъй докато първият е сортирани, той не може да го actually-- 1112 00:54:37,189 --> 00:54:38,980 ние просто късмет, в че например, че 2 1113 00:54:38,980 --> 00:54:40,930 се случи да бъде най-малкият брой. 1114 00:54:40,930 --> 00:54:43,680 Но това не винаги е така. 1115 00:54:43,680 --> 00:54:48,040 Ако вече е 2 сортирани в началото но вие изглеждате и да има едно тук, 1116 00:54:48,040 --> 00:54:49,144 за 1 ще го избутам. 1117 00:54:49,144 --> 00:54:51,060 И това се случва до края сметка се блъсна във всеки случай. 1118 00:54:51,060 --> 00:54:56,250 >> Така че в най-добрия случай, това е всъщност просто ще бъде п. 1119 00:54:56,250 --> 00:54:59,090 Ако имате 1, 2, 3, 4, 5, 6, 7, 8, вие сте 1120 00:54:59,090 --> 00:55:00,940 Ще преминете през че целият списък веднъж 1121 00:55:00,940 --> 00:55:03,430 да проверите дали всичко е наред. 1122 00:55:03,430 --> 00:55:07,390 Всички ли ясна по бягане времена на избор, както и? 1123 00:55:07,390 --> 00:55:09,960 Знам, че преживява те много по-бързо. 1124 00:55:09,960 --> 00:55:13,330 Но просто знам, че ако знаете общи понятия, трябва да бъдат добри. 1125 00:55:13,330 --> 00:55:16,070 ДОБРЕ. 1126 00:55:16,070 --> 00:55:19,790 Така че аз просто ще ви дам момчета може би, като, една минута, за да говорите с вашите съседи 1127 00:55:19,790 --> 00:55:21,890 от това, което са само част от основните разлики 1128 00:55:21,890 --> 00:55:23,540 между тези видове сортове. 1129 00:55:23,540 --> 00:56:24,571 1130 00:56:24,571 --> 00:56:25,570 Ние ще отидем, че скоро. 1131 00:56:25,570 --> 00:56:26,444 АУДИТОРИЯ: О, OK. 1132 00:56:26,444 --> 00:56:27,320 АНДИ Пенг: Да. 1133 00:56:27,320 --> 00:56:28,380 ДОБРЕ. 1134 00:56:28,380 --> 00:56:33,420 Cool, нека да бъдат свикани отново като класа. 1135 00:56:33,420 --> 00:56:34,330 ДОБРЕ. 1136 00:56:34,330 --> 00:56:37,579 Така че това е вид на отворен въпрос, в смисъл, 1137 00:56:37,579 --> 00:56:39,120 че има много отговори на тях. 1138 00:56:39,120 --> 00:56:40,746 И ние ще отидем някои от тях за кратко. 1139 00:56:40,746 --> 00:56:43,411 Аз просто исках да получавате момчета мисля за това, което диференцира 1140 00:56:43,411 --> 00:56:44,530 всичките три вида сортове. 1141 00:56:44,530 --> 00:56:47,440 И аз чух, също Страхотен question-- какво сортиране чрез сливане направя? 1142 00:56:47,440 --> 00:56:50,110 Голям въпрос, защото това е това, което ние, обхващащ следващата. 1143 00:56:50,110 --> 00:56:52,850 >> Така сортиране чрез сливане е един вид, че функции 1144 00:56:52,850 --> 00:56:56,100 много по-различно от останалите сортове. 1145 00:56:56,100 --> 00:56:58,180 Както вие може да see-- Давид направи това демо 1146 00:56:58,180 --> 00:57:01,130 където имаше всичко прохладата шумове на виждам как се слеят 1147 00:57:01,130 --> 00:57:04,010 подреди избяга, като, безкрайно по-бързо от другите два вида? 1148 00:57:04,010 --> 00:57:04,510 ДОБРЕ. 1149 00:57:04,510 --> 00:57:07,580 Така че това е, защото се сливат подреди изпълнява посочената разделяй 1150 00:57:07,580 --> 00:57:11,020 и владей концепция, която ние сме Говорихме за много в лекция. 1151 00:57:11,020 --> 00:57:14,550 В този смисъл, че сме искали да работят по-умни, по-трудно, когато се разделят 1152 00:57:14,550 --> 00:57:18,120 и владей проблеми, и да ги разбие надолу, а след това ги съберете заедно, 1153 00:57:18,120 --> 00:57:19,930 добри неща винаги се случват. 1154 00:57:19,930 --> 00:57:21,960 >> Така че начинът, по който се слеят подреди по същество работи 1155 00:57:21,960 --> 00:57:24,660 е, че тя се разделя на сортиран масив на половина. 1156 00:57:24,660 --> 00:57:26,500 И тогава тя има две половини на масиви. 1157 00:57:26,500 --> 00:57:28,220 И тя просто сортира тези две половини. 1158 00:57:28,220 --> 00:57:31,750 Тя просто продължава да се раздели на две, в половината, на половина, докато всичко се сортира 1159 00:57:31,750 --> 00:57:33,680 и след това рекурсивно всичко това поставя заедно. 1160 00:57:33,680 --> 00:57:36,550 >> Така че това е наистина абстрактно. 1161 00:57:36,550 --> 00:57:38,750 Така че това е само малко Псевдокод. 1162 00:57:38,750 --> 00:57:41,040 Това прави ли смисъл в Между другото той се движи? 1163 00:57:41,040 --> 00:57:43,870 Така че нека просто кажем, че имате масив от наш елементи, нали? 1164 00:57:43,870 --> 00:57:45,450 Ако п е по-малко от 2, можете да се върнете. 1165 00:57:45,450 --> 00:57:49,040 Защото знаеш, че ако има само едно нещо, то трябва да бъдат сортирани. 1166 00:57:49,040 --> 00:57:52,600 Else, можете сортирате лявата половина, и тогава да сортирате дясната половина, 1167 00:57:52,600 --> 00:57:54,140 и тогава ще се слеят. 1168 00:57:54,140 --> 00:57:56,979 >> Така че, докато, който изглежда много лесно, в действителност, мисля за това е 1169 00:57:56,979 --> 00:58:00,270 вид трудно. Защото сте като, Е, това е вид работа върху себе си. 1170 00:58:00,270 --> 00:58:00,769 Нали така? 1171 00:58:00,769 --> 00:58:02,430 Тя работи върху себе си. 1172 00:58:02,430 --> 00:58:05,479 Така че в този смисъл, David докосна при рекурсия в клас. 1173 00:58:05,479 --> 00:58:07,270 И това е една концепция ние ще говорим за повече. 1174 00:58:07,270 --> 00:58:11,430 Това е, че това, тези две линии тук, всъщност е само програмата 1175 00:58:11,430 --> 00:58:13,860 го казвам, за да се стартира с различен вход. 1176 00:58:13,860 --> 00:58:17,230 Така че вместо да се работи с целостта на N елементи, 1177 00:58:17,230 --> 00:58:20,530 можете да го съборят в лявата половина и дясната половина 1178 00:58:20,530 --> 00:58:22,680 и след това да го стартирате отново. 1179 00:58:22,680 --> 00:58:26,050 >> И тогава ние ще разгледаме това визуално, защото аз съм визуален обучаем. 1180 00:58:26,050 --> 00:58:27,270 Тя работи по-добре за мен. 1181 00:58:27,270 --> 00:58:29,890 Така че ние ще разгледаме визуален пример тук. 1182 00:58:29,890 --> 00:58:36,237 >> Да кажем, че имаме масив, шест елементи, 3, 5, 2, 6, 4, 1, не сортирани. 1183 00:58:36,237 --> 00:58:37,820 Добре, че има много на тази страница. 1184 00:58:37,820 --> 00:58:43,179 Така че, ако вие може да погледнете в първа стъпка тук, 3, 5, 2, 6, 4, 1, 1185 00:58:43,179 --> 00:58:44,220 можете да го разделя на две. 1186 00:58:44,220 --> 00:58:45,976 Имате 3, 5, 2, 6, 4, 1. 1187 00:58:45,976 --> 00:58:48,850 Вие знаете, че тези реакции Ви aren't-- не знам дали те са подредени или не, 1188 00:58:48,850 --> 00:58:52,517 така че можете да ги счупи, на половина, наполовина, в половината, докато накрая, 1189 00:58:52,517 --> 00:58:53,600 имате само един елемент. 1190 00:58:53,600 --> 00:58:56,790 И един елемент е винаги подредени, нали? 1191 00:58:56,790 --> 00:59:01,560 >> Така че ние знаем, че 3, 5, 2, 4, 6, 1, сами по себе си, са подредени. 1192 00:59:01,560 --> 00:59:05,870 И сега ние можем да ги пуснат обратно заедно. 1193 00:59:05,870 --> 00:59:07,510 Така че ние знаем за 3, 5. 1194 00:59:07,510 --> 00:59:08,510 Ние събрахме онези заедно. 1195 00:59:08,510 --> 00:59:09,617 Ние знаем, че е сортиран. 1196 00:59:09,617 --> 00:59:10,450 На 2-те години все още там. 1197 00:59:10,450 --> 00:59:11,830 Можем да сложим на 4 и 6 заедно. 1198 00:59:11,830 --> 00:59:13,996 Ние знаем, че това е сортирана, така че ние се сложи това заедно. 1199 00:59:13,996 --> 00:59:14,940 И за 1 е там. 1200 00:59:14,940 --> 00:59:18,720 >> И след това просто погледнете тези две половини тук. 1201 00:59:18,720 --> 00:59:21,300 Имате 3, 5, 2, 2, 3, 5. 1202 00:59:21,300 --> 00:59:23,465 Можете просто да се сравни започващ от всичко. 1203 00:59:23,465 --> 00:59:26,340 Защото вие знаете, че това се сортира и вие знаете, че това е сортирани. 1204 00:59:26,340 --> 00:59:29,360 Така че тогава вие дори не трябва да се сравни 5, просто сравнение на 3. 1205 00:59:29,360 --> 00:59:32,070 И 2 е по-малко от 3, така че Знаете ли, че 2 трябва да отиде в края. 1206 00:59:32,070 --> 00:59:33,120 >> Същото нещо там. 1207 00:59:33,120 --> 00:59:34,740 1 трябва да отидете тук. 1208 00:59:34,740 --> 00:59:37,330 И тогава, когато отидеш да се сложи тези две стойности заедно, 1209 00:59:37,330 --> 00:59:39,950 вие знаете, че това се сортира и знаете ли, че, които се сортират. 1210 00:59:39,950 --> 00:59:43,240 Така че след това 1 и 2, за 1 е по-малко от 2. 1211 00:59:43,240 --> 00:59:45,570 Това ви казва, че за 1 трябва да отидете на края на тази 1212 00:59:45,570 --> 00:59:47,480 без дори да гледа 3 или 5. 1213 00:59:47,480 --> 00:59:50,100 И тогава на 4, може просто да провери, той минава точно тук. 1214 00:59:50,100 --> 00:59:51,480 Вие не трябва да се търси при 5. 1215 00:59:51,480 --> 00:59:52,570 Същото е и с 6. 1216 00:59:52,570 --> 00:59:55,860 Вие знаете, че той просто 6-- не трябва да бъдат разглеждани. 1217 00:59:55,860 --> 00:59:57,870 >> И така, по този начин, вие сте Просто спестяване себе си 1218 00:59:57,870 --> 00:59:59,526 много стъпки, когато сте се сравняват. 1219 00:59:59,526 --> 01:00:02,150 Не е нужно да сравнявате всеки елемент срещу други елементи. 1220 01:00:02,150 --> 01:00:05,230 Ти просто сравнение с тези, че трябва да го сравня с. 1221 01:00:05,230 --> 01:00:06,870 Така че това е вид абстрактно понятие. 1222 01:00:06,870 --> 01:00:10,540 Не се тревожете, ако това не е доста ви удари десния все още. 1223 01:00:10,540 --> 01:00:14,740 Но обикновено, това е как се сливат подреди работи. 1224 01:00:14,740 --> 01:00:17,750 Въпроси, бързи въпроса, преди да се премине? 1225 01:00:17,750 --> 01:00:18,550 Да. 1226 01:00:18,550 --> 01:00:22,230 >> АУДИТОРИЯ: Значи вие казахте, че сте приели на 1, а след това 4 и 6 1227 01:00:22,230 --> 01:00:23,860 и ги поставя инча 1228 01:00:23,860 --> 01:00:26,800 Така че не сме those-- са не можете да ги погледне 1229 01:00:26,800 --> 01:00:28,544 като отделни елементи, а не като цяла? 1230 01:00:28,544 --> 01:00:29,210 АНДИ Пенг: Да. 1231 01:00:29,210 --> 01:00:32,020 Така че това, което се случва е, че в общи линии 1232 01:00:32,020 --> 01:00:33,650 създавате чисто нов масив. 1233 01:00:33,650 --> 01:00:36,690 Така че вие ​​знаете, че, ето, аз имам два масива с размер 3, нали? 1234 01:00:36,690 --> 01:00:39,600 Така че вие ​​знаете, че ми сортиран масив трябва да разполага с шест елемента. 1235 01:00:39,600 --> 01:00:42,270 Така че можете просто да се създаде ново количество памет. 1236 01:00:42,270 --> 01:00:44,270 Значи вие сте нещо като е разточителство на паметта, 1237 01:00:44,270 --> 01:00:46,186 но това не е от значение защото това е толкова малка. 1238 01:00:46,186 --> 01:00:48,590 Така се вгледате в 1 и се вгледате в 2. 1239 01:00:48,590 --> 01:00:50,770 И знаете ли, че 1 е по-малко от 2. 1240 01:00:50,770 --> 01:00:53,840 Така че вие ​​знаете, че трябва да отиде в 1 началото на всички тези. 1241 01:00:53,840 --> 01:00:55,850 >> Ти дори не трябва да се Посетете 3 и 5. 1242 01:00:55,850 --> 01:00:57,400 Така ли, че един отива там. 1243 01:00:57,400 --> 01:00:59,300 Тогава вие основно отсечем за 1. 1244 01:00:59,300 --> 01:01:00,370 Това е, като, мъртъв за нас. 1245 01:01:00,370 --> 01:01:03,690 Тогава ние просто трябва 2, 3, 5, и след това 4 и 6. 1246 01:01:03,690 --> 01:01:06,270 И тогава знаете, че можете Сравняване на 4 и 2, 1247 01:01:06,270 --> 01:01:07,560 о, на 2 трябва да отида там. 1248 01:01:07,560 --> 01:01:09,685 Така че можете плясване на 2 надолу, можете да го отреже. 1249 01:01:09,685 --> 01:01:12,060 Тогава просто трябва 3 и 5 в 4 и 6. 1250 01:01:12,060 --> 01:01:14,650 А ти само да го отсече докато не ги сложи в масива. 1251 01:01:14,650 --> 01:01:17,110 >> АУДИТОРИЯ: Значи вие сте просто винаги сравняване на [недоловим]? 1252 01:01:17,110 --> 01:01:17,710 >> АНДИ Пенг: Точно така. 1253 01:01:17,710 --> 01:01:19,590 Така че в този смисъл, вие сте Просто сравняване, по същество, 1254 01:01:19,590 --> 01:01:21,240 един брой срещу друг номер. 1255 01:01:21,240 --> 01:01:22,990 И тъй като вие знаете че това е сортирана, можете 1256 01:01:22,990 --> 01:01:24,350 не е нужно да търсите чрез всички номера. 1257 01:01:24,350 --> 01:01:25,870 Ти просто трябва да погледнете на първата. 1258 01:01:25,870 --> 01:01:27,582 И след това може просто плясване да ги надолу, защото знаеш, 1259 01:01:27,582 --> 01:01:29,640 те принадлежат, където те трябва да принадлежат. 1260 01:01:29,640 --> 01:01:31,030 Да. 1261 01:01:31,030 --> 01:01:32,920 Добър въпрос. 1262 01:01:32,920 --> 01:01:35,290 >> И тогава, ако някой от вас са малко амбициозни, 1263 01:01:35,290 --> 01:01:38,660 Чувствайте се свободни да погледнете този кодекс. 1264 01:01:38,660 --> 01:01:40,680 Това е всъщност най- физическо изпълнение 1265 01:01:40,680 --> 01:01:42,150 за това как ние ще напише сортиране чрез сливане. 1266 01:01:42,150 --> 01:01:44,070 И можете да видите, че е много кратък. 1267 01:01:44,070 --> 01:01:46,310 Но идеите зад това са доста сложни. 1268 01:01:46,310 --> 01:01:50,865 Така че, ако се чувстваш като изготвянето на този във вашата домашна работа тази вечер, не се колебайте да. 1269 01:01:50,865 --> 01:01:54,050 1270 01:01:54,050 --> 01:01:54,740 >> ДОБРЕ. 1271 01:01:54,740 --> 01:01:58,070 Така Давид отиде в тази лекция. 1272 01:01:58,070 --> 01:02:00,660 Какви са най-добрия случай Времето на автономна работа, най-лошия случай Времето на автономна работа, 1273 01:02:00,660 --> 01:02:05,680 и очакваните Runtimes на сортиране чрез сливане? 1274 01:02:05,680 --> 01:02:07,260 Няколко секунди, за да мислят. 1275 01:02:07,260 --> 01:02:11,198 Това е доста трудно, но вид интуитивно, ако си мислиш за него. 1276 01:02:11,198 --> 01:02:20,090 1277 01:02:20,090 --> 01:02:23,054 Всичко е наред. 1278 01:02:23,054 --> 01:02:25,269 >> АУДИТОРИЯ: Дали най-лошия случай п дневник п? 1279 01:02:25,269 --> 01:02:26,060 АНДИ Пенг: Точно така. 1280 01:02:26,060 --> 01:02:29,380 И защо е п влезте п. 1281 01:02:29,380 --> 01:02:32,230 >> АУДИТОРИЯ: Не е ли защото тя експоненциално става по-бързо, 1282 01:02:32,230 --> 01:02:35,390 така че това е като функция на това вместо просто да бъде п 1283 01:02:35,390 --> 01:02:37,529 квадрат или нещо такова? 1284 01:02:37,529 --> 01:02:38,320 АНДИ Пенг: Точно така. 1285 01:02:38,320 --> 01:02:40,750 Така че причината, поради която по време на работа по този въпрос е п дневник 1286 01:02:40,750 --> 01:02:44,310 п е because-- това, което са прави във всички тези стъпки? 1287 01:02:44,310 --> 01:02:46,190 Вие просто го кълцане на половина, нали? 1288 01:02:46,190 --> 01:02:48,750 И така, когато Правим влезте, всичко, което го прави 1289 01:02:48,750 --> 01:02:53,150 се раздели проблем на половина, наполовина, в половината, в повече половини. 1290 01:02:53,150 --> 01:02:56,430 И в този смисъл, можете да вид на премахване на линеен модел 1291 01:02:56,430 --> 01:02:57,510 че ние сме били използвате. 1292 01:02:57,510 --> 01:03:00,254 Защото, когато посегнат неща в половината, това е дневник. 1293 01:03:00,254 --> 01:03:02,420 Това е само математическата начин да го представлява. 1294 01:03:02,420 --> 01:03:06,310 >> И накрая, в края, ти си просто направи едно последно атака през 1295 01:03:06,310 --> 01:03:07,930 да постави всички от тях, с цел, нали? 1296 01:03:07,930 --> 01:03:10,330 И така, ако сте просто трябва да проверите едно нещо, това е п. 1297 01:03:10,330 --> 01:03:13,420 И така, вие сте вид умножаване двете заедно. 1298 01:03:13,420 --> 01:03:17,660 Така че това е като да имаш, че окончателното проверите за п тук долу с дневника на п 1299 01:03:17,660 --> 01:03:18,390 тук. 1300 01:03:18,390 --> 01:03:21,060 И ако се размножават тях, която е п влезте п. 1301 01:03:21,060 --> 01:03:26,100 >> И така най-добрия случай и най-лошото случай и очаква всички са п влезте п. 1302 01:03:26,100 --> 01:03:27,943 То също е като друг вид. 1303 01:03:27,943 --> 01:03:30,090 Това е като избор на сортиране в смисъл, че 1304 01:03:30,090 --> 01:03:32,131 Няма значение какъв е вашият списък е, тя просто ще 1305 01:03:32,131 --> 01:03:34,801 да направи същото нещо всеки път. 1306 01:03:34,801 --> 01:03:35,300 ДОБРЕ. 1307 01:03:35,300 --> 01:03:39,950 Така че, както вие може да видите, въпреки че сортовете, че сме отишли ​​through-- п 1308 01:03:39,950 --> 01:03:41,660 квадрат, това не е много ефективен. 1309 01:03:41,660 --> 01:03:47,060 И дори това п дневник п е не най-ефективно. 1310 01:03:47,060 --> 01:03:49,720 Ако вие, момчета са любопитни, там е един вид механизми 1311 01:03:49,720 --> 01:03:54,310 които са толкова ефективна, че те са почти основно жилище в изпълнение. 1312 01:03:54,310 --> 01:03:55,420 >> Имаш някои дневник п е. 1313 01:03:55,420 --> 01:03:58,190 Имаш някои дневник дневник п е. 1314 01:03:58,190 --> 01:04:00,330 Ние не се докоснете до тях в този клас в момента. 1315 01:04:00,330 --> 01:04:02,663 Но ако вие са любопитни, Чувствайте се свободни да Google, това, което е 1316 01:04:02,663 --> 01:04:04,392 най-ефективните сортиране механизми. 1317 01:04:04,392 --> 01:04:06,350 Аз не знам, има някои наистина смешни такива, 1318 01:04:06,350 --> 01:04:09,860 like-- има някои наистина смешни тези, които хората правят. 1319 01:04:09,860 --> 01:04:12,210 И ти се чудя как те някога мисълта за това. 1320 01:04:12,210 --> 01:04:15,730 Така Google, ако имате някои резервни време, за това, което са някои забавни начини 1321 01:04:15,730 --> 01:04:17,730 че people-- както и ефикасни ways-- хората 1322 01:04:17,730 --> 01:04:20,371 са били в състояние да приложат различни. 1323 01:04:20,371 --> 01:04:20,870 ДОБРЕ. 1324 01:04:20,870 --> 01:04:22,880 И тук е просто удобен малък диаграма. 1325 01:04:22,880 --> 01:04:26,850 Знам, че всички от вас, преди тази викторина 0, ще бъде в стаята си, вероятно опитвайки 1326 01:04:26,850 --> 01:04:27,960 да запомня това. 1327 01:04:27,960 --> 01:04:30,940 Така че това е хубаво там за вас, момчета. 1328 01:04:30,940 --> 01:04:37,120 Само не забравяйте, че логиката made-- защо тези номера бяха срещащи. 1329 01:04:37,120 --> 01:04:39,870 Ако винаги сте загубили, просто се сигурни, че знаете какво сортовете са. 1330 01:04:39,870 --> 01:04:40,820 И вие можете да преминете през ги в ума си 1331 01:04:40,820 --> 01:04:42,903 да разбера защо тези, отговори са тези отговори. 1332 01:04:42,903 --> 01:04:46,250 1333 01:04:46,250 --> 01:04:47,600 >> Всичко е наред. 1334 01:04:47,600 --> 01:04:49,680 Така че ние ще се движат на последно място, да се търсене. 1335 01:04:49,680 --> 01:04:51,638 Тъй като тези от вас, които са чели pset, 1336 01:04:51,638 --> 01:04:55,175 търсене също е част от проблем тази седмица задава. 1337 01:04:55,175 --> 01:04:57,300 Вие ще бъдете помолени да приложи два вида търсения. 1338 01:04:57,300 --> 01:05:00,070 Един от тях е линеен търсене и един е двоичен търсене. 1339 01:05:00,070 --> 01:05:01,760 >> Така че линейната търсенето е сравнително лесно. 1340 01:05:01,760 --> 01:05:04,070 Вие просто искате да търсите елемент на списък, за да видите дали можете да го получи. 1341 01:05:04,070 --> 01:05:05,444 Просто трябва да превъртите през. 1342 01:05:05,444 --> 01:05:08,170 И ако това се равнява на нещо, може просто да го върне, нали? 1343 01:05:08,170 --> 01:05:10,890 Но този, който ние сме най- интересуват от говорим за 1344 01:05:10,890 --> 01:05:14,550 е двоично търсене, полето, което е най- разделяй и владей механизъм, който 1345 01:05:14,550 --> 01:05:18,190 Дейвид се демонстрира в лекция. 1346 01:05:18,190 --> 01:05:20,810 >> Не забравяйте примера на телефонния указател че той продължава отглеждането, 1347 01:05:20,810 --> 01:05:23,960 този, който той вид бореше малко по последната година, 1348 01:05:23,960 --> 01:05:27,530 където можете да раздели проблема на половина, на половина, на половина, отново и отново, 1349 01:05:27,530 --> 01:05:30,730 докато не намерите това, което търсите? 1350 01:05:30,730 --> 01:05:33,727 И имаш време на изпълнение на това, както добре. 1351 01:05:33,727 --> 01:05:35,810 И можете да видите, че е значително по-ефективно 1352 01:05:35,810 --> 01:05:39,080 от всеки друг вид търсене. 1353 01:05:39,080 --> 01:05:41,880 >> Така че начинът, по който ние ще отида за прилагане двоичен търсене 1354 01:05:41,880 --> 01:05:46,510 е, ако имахме масив, индекс от 0 до 6, седем елементи, 1355 01:05:46,510 --> 01:05:49,790 ние можем да погледнем в средата, right-- Съжалявам, ако ни въпрос first-- 1356 01:05:49,790 --> 01:05:53,840 ако искаме да зададем въпроса на, прави масива съдържа елемент 7, 1357 01:05:53,840 --> 01:05:56,840 Очевидно е, че са хора, и като такъв малък масив, това е лесно за нас 1358 01:05:56,840 --> 01:05:58,210 да се каже, да. 1359 01:05:58,210 --> 01:06:05,750 Но начинът за прилагане на двоичен търсене е да се погледне в центъра. 1360 01:06:05,750 --> 01:06:08,020 >> Ние знаем, че индексът е 3 средата, защото ние 1361 01:06:08,020 --> 01:06:09,270 знаем, че има седем елемента. 1362 01:06:09,270 --> 01:06:10,670 Какво 7 разделена на 2? 1363 01:06:10,670 --> 01:06:12,850 Можете да отсечем, че допълнително 1. 1364 01:06:12,850 --> 01:06:14,850 Имаш 3 в средата. 1365 01:06:14,850 --> 01:06:17,590 Така че е набор от 3 равна на 7? 1366 01:06:17,590 --> 01:06:18,900 Не е правилно? 1367 01:06:18,900 --> 01:06:21,050 Но ние можем да направим няколко проверки. 1368 01:06:21,050 --> 01:06:25,380 Е набор от 3 или по-малко от 7 е масив от 3-голяма от 7? 1369 01:06:25,380 --> 01:06:27,240 >> И ние знаем, че това е по-малко от 7. 1370 01:06:27,240 --> 01:06:30,259 Така че ние знаем, че, о, тя трябва не е в лявата половина. 1371 01:06:30,259 --> 01:06:32,300 Ние знаем, че тя трябва да бъде в дясната половина, нали? 1372 01:06:32,300 --> 01:06:34,662 Така че ние можем просто да отреже половината от масива. 1373 01:06:34,662 --> 01:06:36,370 Ние дори не трябва да се гледам на него вече. 1374 01:06:36,370 --> 01:06:38,711 Защото ние знаем, че половината от нашия problem-- 1375 01:06:38,711 --> 01:06:41,210 ние знаем, че отговорът е в дясната половина на нашия проблем. 1376 01:06:41,210 --> 01:06:42,580 Така че ние просто погледнете това сега. 1377 01:06:42,580 --> 01:06:44,860 >> Така че сега погледнем средата на това, което е останало. 1378 01:06:44,860 --> 01:06:46,880 Това индекс 5. 1379 01:06:46,880 --> 01:06:50,200 Ние правим едно и също проверката отново и ние виждаме, че това е по-малък. 1380 01:06:50,200 --> 01:06:52,050 Така че ние с нетърпение в ляво от това. 1381 01:06:52,050 --> 01:06:53,430 И тогава ние виждаме, че проверка. 1382 01:06:53,430 --> 01:06:57,600 Е стойността на масив в индекс 4, равен на 7? 1383 01:06:57,600 --> 01:06:58,260 То е. 1384 01:06:58,260 --> 01:07:03,580 Така че можем да се върнем вярно, защото ние открихме, че стойността в нашия списък. 1385 01:07:03,580 --> 01:07:06,738 Дали начинът, минах през които имат смисъл за всички? 1386 01:07:06,738 --> 01:07:08,760 ДОБРЕ. 1387 01:07:08,760 --> 01:07:11,670 Аз ще ви дам момчета може би, като, три, четири минути, за да разбера 1388 01:07:11,670 --> 01:07:13,270 как да Псевдокод този инча 1389 01:07:13,270 --> 01:07:18,070 >> Така че представете си те помолих да напише функция, наречена търсене (), който се завръща 1390 01:07:18,070 --> 01:07:20,640 на стойност, булева стойност, това беше вярно или false-- харесват, 1391 01:07:20,640 --> 01:07:22,970 вярно, ако сте намерили стойност, невярно, ако не го направи. 1392 01:07:22,970 --> 01:07:25,230 И тогава бяхте преминали в стойността, която 1393 01:07:25,230 --> 01:07:28,410 търсите в стойности, които е array-- о, аз определено сложи 1394 01:07:28,410 --> 01:07:29,410 че на грешното място. 1395 01:07:29,410 --> 01:07:29,580 ДОБРЕ. 1396 01:07:29,580 --> 01:07:31,829 Както и да е, че трябва да има бил в правото на ценности. 1397 01:07:31,829 --> 01:07:36,280 След това междинно съединение п е броя на елементи в тази масив. 1398 01:07:36,280 --> 01:07:39,430 Как бихте отишли ​​за опитват да Псевдокод, че проблем в? 1399 01:07:39,430 --> 01:07:41,630 Аз ще ви дам хора като три минути, за да направите това. 1400 01:07:41,630 --> 01:08:00,137 1401 01:08:00,137 --> 01:08:02,595 Не, аз мисля, че има only-- Да, има един чак до тук. 1402 01:08:02,595 --> 01:08:03,261 АУДИТОРИЯ: Мога ли? 1403 01:08:03,261 --> 01:08:04,388 АНДИ Пенг: Да, имам теб. 1404 01:08:04,388 --> 01:08:09,410 1405 01:08:09,410 --> 01:08:11,050 Е, че работната? 1406 01:08:11,050 --> 01:08:12,290 ОК готино. 1407 01:08:12,290 --> 01:10:43,590 1408 01:10:43,590 --> 01:10:44,720 >> ДОБРЕ. 1409 01:10:44,720 --> 01:10:47,630 Добре момчета, ние сме ще го обуздае инча 1410 01:10:47,630 --> 01:10:49,730 ДОБРЕ. 1411 01:10:49,730 --> 01:10:54,020 Така се предположи, че имаме тази прекрасна Малко масив с п ценности в него. 1412 01:10:54,020 --> 01:10:55,170 Аз не направил линиите. 1413 01:10:55,170 --> 01:10:58,649 Но как ще отида за опитвайки се да напиша това? 1414 01:10:58,649 --> 01:11:00,440 Някой иска да дай ми на първия ред? 1415 01:11:00,440 --> 01:11:02,814 Ако искате да ми дадете първа линия на този Псевдокод. 1416 01:11:02,814 --> 01:11:06,563 1417 01:11:06,563 --> 01:11:08,430 >> АУДИТОРИЯ: [недоловим] 1418 01:11:08,430 --> 01:11:10,138 АУДИТОРИЯ: Вие ще искате да превъртите through-- 1419 01:11:10,138 --> 01:11:11,094 АУДИТОРИЯ: Просто още за цикъл? 1420 01:11:11,094 --> 01:11:11,760 АУДИТОРИЯ: --for. 1421 01:11:11,760 --> 01:11:15,880 1422 01:11:15,880 --> 01:11:17,780 >> АНДИ Пенг: Така че това е един доста труден. 1423 01:11:17,780 --> 01:11:23,130 Помислете about-- искате продължава да работи, този цикъл 1424 01:11:23,130 --> 01:11:27,950 отново и отново, докато, когато? 1425 01:11:27,950 --> 01:11:30,819 >> АУДИТОРИЯ: До [недоловим] стойност е равна на тази стойност. 1426 01:11:30,819 --> 01:11:31,610 АНДИ Пенг: Точно така. 1427 01:11:31,610 --> 01:11:33,900 Така че всъщност можете да просто write-- ние дори може да го опрости повече. 1428 01:11:33,900 --> 01:11:35,630 Ние можем просто да се направи линия, докато, нали? 1429 01:11:35,630 --> 01:11:39,380 Така че можете да просто трябва loop-- ние знаем, че това е малко. 1430 01:11:39,380 --> 01:11:42,850 Но за сега, аз ще съм да се каже, "контур" - чрез това, което? 1431 01:11:42,850 --> 01:11:46,640 Loop until-- това, което е нашата приключва състояние? 1432 01:11:46,640 --> 01:11:47,510 Мисля, че го чух. 1433 01:11:47,510 --> 01:11:48,530 Чух някой да го каже. 1434 01:11:48,530 --> 01:11:51,255 >> Публика: Стойностите се равнява на средната. 1435 01:11:51,255 --> 01:11:52,255 АНДИ Пенг: Кажи го отново. 1436 01:11:52,255 --> 01:11:54,470 АУДИТОРИЯ: Или, до стойност, които търсите 1437 01:11:54,470 --> 01:11:58,470 е равен на средната стойност. 1438 01:11:58,470 --> 01:12:00,280 >> АНДИ Пенг: Какво става, ако то не е там? 1439 01:12:00,280 --> 01:12:03,113 Какво става, ако стойността, които търсите не е всъщност в този масив? 1440 01:12:03,113 --> 01:12:05,890 АУДИТОРИЯ: Ще се върнете 1. 1441 01:12:05,890 --> 01:12:08,850 >> АНДИ Пенг: Но това, което искаме да линия, докато ако имаме състояние? 1442 01:12:08,850 --> 01:12:09,350 Да. 1443 01:12:09,350 --> 01:12:11,239 >> АУДИТОРИЯ: До има само едно качество? 1444 01:12:11,239 --> 01:12:13,530 АНДИ Пенг: Можете линия until-- така че знам, че ти си 1445 01:12:13,530 --> 01:12:15,714 ще имат стойност макс, нали? 1446 01:12:15,714 --> 01:12:18,130 И знаеш ли, че ти започваш да имат стойност мин, нали? 1447 01:12:18,130 --> 01:12:20,379 Тъй също, че е нещо, Забравих да кажа, преди, 1448 01:12:20,379 --> 01:12:22,640 че нещо, което е критична за двоично търсене 1449 01:12:22,640 --> 01:12:24,182 е, че вашият масив е вече сортирани. 1450 01:12:24,182 --> 01:12:26,973 Защото няма начин за правене това, ако те са просто случайни стойности. 1451 01:12:26,973 --> 01:12:29,190 Ти не знаеш, ако един е голяма от другата, нали? 1452 01:12:29,190 --> 01:12:32,720 >> Така че вие ​​знаете, че вашето макс и Вашите минути са тук, нали? 1453 01:12:32,720 --> 01:12:35,590 Ако ти започваш да се коригиране Вашата макс във вашите минути и mid-- 1454 01:12:35,590 --> 01:12:38,470 нека просто приемем Вашата средата на стойност не е прав here-- 1455 01:12:38,470 --> 01:12:43,910 започваш да се основно линия до минималната си е 1456 01:12:43,910 --> 01:12:47,510 почти същото като вашето макс, нали, или ако вашият макс не е същото като вашето мин. 1457 01:12:47,510 --> 01:12:48,040 Нали така? 1458 01:12:48,040 --> 01:12:51,340 Защото, когато това се случи, вие знаете, че в крайна сметка съм удари една и съща стойност. 1459 01:12:51,340 --> 01:12:59,135 Значи вие искате да линия до вашата мин е по-малка от или равна to-- Опа, 1460 01:12:59,135 --> 01:13:01,510 не по-малко от или равно на, по друг начин around-- макс е. 1461 01:13:01,510 --> 01:13:15,110 1462 01:13:15,110 --> 01:13:16,160 >> Знаете, че да има смисъл? 1463 01:13:16,160 --> 01:13:18,810 Взех няколко опита, за да получите това право. 1464 01:13:18,810 --> 01:13:21,869 Но цикъл, докато си макс стойност е по-малко по същество почти 1465 01:13:21,869 --> 01:13:23,410 малка или равна на минималната си, нали? 1466 01:13:23,410 --> 01:13:25,201 Това е, когато знаеш, че сте се сближили. 1467 01:13:25,201 --> 01:13:29,290 АУДИТОРИЯ: Кога бихте си за максимална стойност е по-малко от минимума? 1468 01:13:29,290 --> 01:13:31,040 АНДИ Пенг: Ако държите като го коригира, които 1469 01:13:31,040 --> 01:13:32,380 е това, което ние ще да се прави в тази посока. 1470 01:13:32,380 --> 01:13:33,460 Това прави ли смисъл? 1471 01:13:33,460 --> 01:13:35,750 Минимален и максимален са само числа, че ние сме най-вероятно 1472 01:13:35,750 --> 01:13:39,260 ще искате да създадете, за да следите къде ние не търсим. 1473 01:13:39,260 --> 01:13:41,790 Тъй като съществува масива независимо от това, което правим. 1474 01:13:41,790 --> 01:13:45,030 Подобно, не сме всъщност физически отсичайки масива, нали? 1475 01:13:45,030 --> 01:13:47,261 Ние просто адаптиране където ние не търсим. 1476 01:13:47,261 --> 01:13:48,136 Това прави ли смисъл? 1477 01:13:48,136 --> 01:13:48,472 >> АУДИТОРИЯ: Да. 1478 01:13:48,472 --> 01:13:49,110 >> АНДИ Пенг: OK. 1479 01:13:49,110 --> 01:13:57,090 Така че, ако това е условието за нашата линия, какво искаме вътре в този цикъл? 1480 01:13:57,090 --> 01:13:58,700 Какво ще се иска да направя? 1481 01:13:58,700 --> 01:14:02,390 Така че в момента, ние имаме макс и мин, нали, 1482 01:14:02,390 --> 01:14:04,962 Вероятно е създаден тук някъде. 1483 01:14:04,962 --> 01:14:07,170 Отиваме да вероятно ще пожелаете да се намери средата, нали? 1484 01:14:07,170 --> 01:14:08,450 Как ще да е може да се намери в средата? 1485 01:14:08,450 --> 01:14:09,491 Каква е mathematical-- 1486 01:14:09,491 --> 01:14:11,079 АУДИТОРИЯ: Макс плюс минути, разделени на две. 1487 01:14:11,079 --> 01:14:11,870 АНДИ Пенг: Точно така. 1488 01:14:11,870 --> 01:14:20,300 1489 01:14:20,300 --> 01:14:21,620 Това прави ли смисъл? 1490 01:14:21,620 --> 01:14:25,780 И знаете вие, момчета, да видят защо ние не само use-- защо ние направихме това 1491 01:14:25,780 --> 01:14:27,850 вместо да правиш точно п разделена на 2? 1492 01:14:27,850 --> 01:14:30,310 Това е така, защото п е на стойност че ще останат същите. 1493 01:14:30,310 --> 01:14:30,979 Нали така? 1494 01:14:30,979 --> 01:14:34,020 Но тъй като ние се коригира нашата минимална и максимални стойности, те ще се променят. 1495 01:14:34,020 --> 01:14:36,040 И като резултат, нашата средна няма да се промени също. 1496 01:14:36,040 --> 01:14:37,873 Така че това е защо ние искаме да се направи това точно тук. 1497 01:14:37,873 --> 01:14:38,510 ДОБРЕ. 1498 01:14:38,510 --> 01:14:41,600 >> И тогава, сега, ние открихме our-- да. 1499 01:14:41,600 --> 01:14:44,270 >> АУДИТОРИЯ: Само един бърз question-- когато казвате мин и макс, 1500 01:14:44,270 --> 01:14:46,410 се предполага, че ние тя вече сортирани? 1501 01:14:46,410 --> 01:14:48,400 >> АНДИ Пенг: Да, това е всъщност предпоставка за двоично търсене, 1502 01:14:48,400 --> 01:14:49,816 че трябва да се знае, че е сортирани. 1503 01:14:49,816 --> 01:14:53,660 Ето защо сортиране, пишете във вашия проблем поставената пред вашия двоично търсене. 1504 01:14:53,660 --> 01:14:55,910 ДОБРЕ. 1505 01:14:55,910 --> 01:14:58,876 Така че сега ние знаем къде нашата средна точка е, какво искаш да правим тук? 1506 01:14:58,876 --> 01:15:01,789 1507 01:15:01,789 --> 01:15:04,319 >> АУДИТОРИЯ: Искаме да сравнявате че на другия. 1508 01:15:04,319 --> 01:15:05,110 АНДИ Пенг: Точно така. 1509 01:15:05,110 --> 01:15:12,280 Така че ти започваш да се сравни средата на стойност, нали? 1510 01:15:12,280 --> 01:15:14,900 1511 01:15:14,900 --> 01:15:18,670 И какво значи това кажи нас, когато сравнявате? 1512 01:15:18,670 --> 01:15:22,226 Какво искаме да правим след това? 1513 01:15:22,226 --> 01:15:25,389 >> АУДИТОРИЯ: Ако стойността е по-голям от средата, искаме да го прекъсна. 1514 01:15:25,389 --> 01:15:26,180 АНДИ Пенг: Точно така. 1515 01:15:26,180 --> 01:15:33,940 Така че, ако стойността е по-голям от средата, ние сме 1516 01:15:33,940 --> 01:15:36,550 ще искате да ги промените минимум и maxes, нали? 1517 01:15:36,550 --> 01:15:38,980 Какво искаме да се промени? 1518 01:15:38,980 --> 01:15:42,145 Така че, ако ние знаем стойността е някъде тук, това, което правите, ние да се промени? 1519 01:15:42,145 --> 01:15:44,758 Ние искаме да променим минимум, за да бъде средата, нали? 1520 01:15:44,758 --> 01:15:49,420 1521 01:15:49,420 --> 01:15:54,292 И после друго, ако това е в този половината, какво искаме да се промени? 1522 01:15:54,292 --> 01:15:55,306 >> АУДИТОРИЯ: Вашият максимум. 1523 01:15:55,306 --> 01:15:55,972 АНДИ Пенг: Да. 1524 01:15:55,972 --> 01:16:02,597 1525 01:16:02,597 --> 01:16:04,680 И след това просто ще да запази примка, нали? 1526 01:16:04,680 --> 01:16:08,920 Защото сега, след една итерация чрез, имаш макс тук. 1527 01:16:08,920 --> 01:16:10,760 И тогава може да се преизчисли в средата. 1528 01:16:10,760 --> 01:16:11,990 И тогава ще може да се сравни. 1529 01:16:11,990 --> 01:16:14,766 И ти започваш да продължава напред докато минути и maxes 1530 01:16:14,766 --> 01:16:15,890 са по същество се сближили. 1531 01:16:15,890 --> 01:16:17,890 И това е, когато знаеш, че сте се удари в края на това. 1532 01:16:17,890 --> 01:16:20,280 И двете сте го намерили или не сте в този момент. 1533 01:16:20,280 --> 01:16:23,170 >> Прави ли това чувство на всички? 1534 01:16:23,170 --> 01:16:26,020 1535 01:16:26,020 --> 01:16:26,770 ДОБРЕ. 1536 01:16:26,770 --> 01:16:27,900 Това е доста важно, защото ще имате 1537 01:16:27,900 --> 01:16:29,760 да напиша това в кода си тази вечер. 1538 01:16:29,760 --> 01:16:32,660 Но вие имате доста добър усещане за това какво трябва да се прави, 1539 01:16:32,660 --> 01:16:34,051 кое е добре. 1540 01:16:34,051 --> 01:16:34,550 ДОБРЕ. 1541 01:16:34,550 --> 01:16:38,840 Така че ние имаме около седем минути преди края раздел. 1542 01:16:38,840 --> 01:16:43,170 Така че ние ще говорим за това pset, че ние ще се прави. 1543 01:16:43,170 --> 01:16:46,410 Така pset е разделена на две половини. 1544 01:16:46,410 --> 01:16:50,230 Първото полувреме включва прилагане на находката 1545 01:16:50,230 --> 01:16:54,210 , на който пишете линейно търсене, а двоично търсене и сортиране алгоритъм. 1546 01:16:54,210 --> 01:16:56,690 >> Така че това е първият време в pset където 1547 01:16:56,690 --> 01:17:00,050 ние ще бъдем като вас, момчета, което се нарича код разпределение, което е код 1548 01:17:00,050 --> 01:17:02,740 че сме предварително писмено, но просто остави някои части на разстояние 1549 01:17:02,740 --> 01:17:04,635 за вас, за да продължи писмена форма. 1550 01:17:04,635 --> 01:17:07,510 Така че вие, момчета, когато се вгледате в тази код, може да получите наистина уплашен. 1551 01:17:07,510 --> 01:17:08,630 Ако сте просто искал, Ааа, аз не знам какво, че се справя, 1552 01:17:08,630 --> 01:17:11,670 Аз не знам, като, че изглежда толкова сложно, Ааа, да се отпуснете. 1553 01:17:11,670 --> 01:17:12,170 ОК е. 1554 01:17:12,170 --> 01:17:12,930 Прочетете спец. 1555 01:17:12,930 --> 01:17:16,920 Спецификацията ще ви обясня точно това, което всички тези програми са прави. 1556 01:17:16,920 --> 01:17:20,560 >> Например, generate.c е програма че ще дойде с вашия pset. 1557 01:17:20,560 --> 01:17:24,060 Вие всъщност не трябва да го докосне, но трябва да се разбере това, което прави. 1558 01:17:24,060 --> 01:17:28,550 И generate.c, всичко, което прави, е или генериране на случайни числа 1559 01:17:28,550 --> 01:17:32,400 или може да го даде на семена, като предварително определени номера, че са необходими, 1560 01:17:32,400 --> 01:17:34,140 и тя генерира повече номера. 1561 01:17:34,140 --> 01:17:37,170 Така че има специфичен начин за приложат generate.c, в която 1562 01:17:37,170 --> 01:17:42,760 може просто да направи един куп номера за да можете да тествате вашите други методи на. 1563 01:17:42,760 --> 01:17:45,900 >> Така че, ако искате да, за Например, тества вашата находка, 1564 01:17:45,900 --> 01:17:48,970 вие ще искате да стартирате generate.c, генерира един куп номера, 1565 01:17:48,970 --> 01:17:50,880 и след това пуснете си помощници функция. 1566 01:17:50,880 --> 01:17:53,930 Вашият помощници функция е мястото, където сте всъщност физически пишете код. 1567 01:17:53,930 --> 01:17:59,330 И мисля, че на помощници като библиотека файл пишеш, че находката се обажда. 1568 01:17:59,330 --> 01:18:02,950 И така, в рамките на helpers.c, ще направите търсене и сортиране. 1569 01:18:02,950 --> 01:18:06,500 >> И тогава започваш да се същество Просто всички тях, взети заедно. 1570 01:18:06,500 --> 01:18:10,350 Спецификацията ще ви кажа как да сложи това в командния ред. 1571 01:18:10,350 --> 01:18:14,880 И вие ще бъдете в състояние да се тества дали Не си вид и търсене работим. 1572 01:18:14,880 --> 01:18:15,870 Готино. 1573 01:18:15,870 --> 01:18:18,720 Вече започна и всеки, срещани проблеми или въпроси 1574 01:18:18,720 --> 01:18:20,520 те имат точно сега с това? 1575 01:18:20,520 --> 01:18:21,020 ДОБРЕ. 1576 01:18:21,020 --> 01:18:21,476 >> АУДИТОРИЯ: Изчакайте. 1577 01:18:21,476 --> 01:18:21,932 Имам въпрос. 1578 01:18:21,932 --> 01:18:22,844 >> АНДИ Пенг: Да. 1579 01:18:22,844 --> 01:18:28,390 >> АУДИТОРИЯ: Така че аз започнах да правя търсачката линейна в helpers.c 1580 01:18:28,390 --> 01:18:29,670 и това не е наистина работи. 1581 01:18:29,670 --> 01:18:34,590 Но след това по-късно разбрах, че ние просто трябва да го изтриете и да направим двоичен търсене. 1582 01:18:34,590 --> 01:18:36,991 Така че това е от значение, ако тя не работи? 1583 01:18:36,991 --> 01:18:39,700 1584 01:18:39,700 --> 01:18:41,510 >> АНДИ Пенг: Кратък отговор е не. 1585 01:18:41,510 --> 01:18:42,642 Но тъй като ние сме not-- 1586 01:18:42,642 --> 01:18:44,350 АУДИТОРИЯ: Но никой не е фактическа проверка. 1587 01:18:44,350 --> 01:18:46,058 АНДИ Пенг: Ние никога не сме Ще видите, че. 1588 01:18:46,058 --> 01:18:49,590 Но вие може би искате да направите сигурен търсенето си работи. 1589 01:18:49,590 --> 01:18:51,700 Защото ако си линейна търсене не работи, 1590 01:18:51,700 --> 01:18:54,410 тогава шансовете са ви двоичен търсене няма да работи, както добре. 1591 01:18:54,410 --> 01:18:56,646 Защото имате подобна логика в двете. 1592 01:18:56,646 --> 01:18:58,020 И не, това няма значение. 1593 01:18:58,020 --> 01:19:01,300 Така единствените, които ще се превърнат в са подредени и двоично търсене. 1594 01:19:01,300 --> 01:19:02,490 Да. 1595 01:19:02,490 --> 01:19:06,610 >> И също така, много от децата са били опитвайки се да се съберат helpers.c. 1596 01:19:06,610 --> 01:19:09,550 Вие не сте действително оставя да направи това, защото helpers.c 1597 01:19:09,550 --> 01:19:11,200 не разполага с основна функция. 1598 01:19:11,200 --> 01:19:13,550 И така, вие само трябва да да бъде действително съставянето 1599 01:19:13,550 --> 01:19:18,670 генерират и да се намери, защото намерите повиквания helpers.c и функциите в него. 1600 01:19:18,670 --> 01:19:20,790 Така, че прави грешки трън в задника. 1601 01:19:20,790 --> 01:19:22,422 Но това е, което трябва да направим. 1602 01:19:22,422 --> 01:19:23,880 АУДИТОРИЯ: Ти просто направи всичко, нали? 1603 01:19:23,880 --> 01:19:27,290 АНДИ Пенг: Можете просто направи всичко, както, да. 1604 01:19:27,290 --> 01:19:28,060 ДОБРЕ. 1605 01:19:28,060 --> 01:19:32,570 Така, че това е от гледна точка на това, което на pset иска всички да се направи. 1606 01:19:32,570 --> 01:19:35,160 Ако имате някакви въпроси, не се колебайте свободни да ме питате, след точка. 1607 01:19:35,160 --> 01:19:37,580 Аз ще бъда тук за подобно, на 20 минути. 1608 01:19:37,580 --> 01:19:40,500 >> И да, pset на наистина не е толкова зле. 1609 01:19:40,500 --> 01:19:41,680 Вие, момчета, трябва да се оправи. 1610 01:19:41,680 --> 01:19:43,250 Те, просто следвайте указанията. 1611 01:19:43,250 --> 01:19:47,840 Вид на имате чувство за логично, това, което трябва да се случва и ще се оправи. 1612 01:19:47,840 --> 01:19:48,690 Не бъдете прекалено уплашен. 1613 01:19:48,690 --> 01:19:50,220 Има много код вече написано там. 1614 01:19:50,220 --> 01:19:53,011 Не бъдете прекалено уплашена, ако не разбере какво означава всичко това. 1615 01:19:53,011 --> 01:19:54,749 Ако това е много, това е напълно наред. 1616 01:19:54,749 --> 01:19:55,790 И дойде в работно време. 1617 01:19:55,790 --> 01:19:57,520 Ние ще ви помогне да погледнете. 1618 01:19:57,520 --> 01:20:00,810 >> АУДИТОРИЯ: С допълнителната функции, да погледнем тези нагоре? 1619 01:20:00,810 --> 01:20:03,417 >> АНДИ Пенг: Да, тези, които са в кода. 1620 01:20:03,417 --> 01:20:05,750 В началото на срещата от 15, половината от той вече е написана за вас. 1621 01:20:05,750 --> 01:20:09,310 Така че тези функции са вече в кода. 1622 01:20:09,310 --> 01:20:12,020 Да. 1623 01:20:12,020 --> 01:20:12,520 Всичко е наред. 1624 01:20:12,520 --> 01:20:14,000 Е, най-доброто от късмет. 1625 01:20:14,000 --> 01:20:15,180 Това е отвратително ден. 1626 01:20:15,180 --> 01:20:19,370 Така че да се надяваме вие, момчета, не се чувстват твърде лошо за пребиваващи в и кодиране. 1627 01:20:19,370 --> 01:20:22,133