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 прашања, debrief, такви работи. 10 00:00:28,910 --> 00:00:30,250 А потоа ќе се нурне во право. 11 00:00:30,250 --> 00:00:34,710 Ќе искористиме дебагер наречен GDB да почне откривајќи нашиот код, што Давид 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 е само стилизиран начин на велејќи: "runtimes" 19 00:00:55,944 --> 00:00:58,360 каде што имаме голема О, што Дејвид е објаснето во предавањето. 20 00:00:58,360 --> 00:01:01,550 А имаме и Омега, која е долната граница на извршувањето. 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 Се оценува првиот pset за вас момци минатата недела, а вие момци направија неверојатна. 37 00:01:55,800 --> 00:01:58,290 >> Стил беше на точка Покрај неколку коментари. 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 Па јас сум минувајќи низ мојата благодарност за остатокот од Тас. 45 00:02:16,450 --> 00:02:19,210 >> Сепак постојат debrief неколку прашања 46 00:02:19,210 --> 00:02:22,010 Јас само сакам да одам во текот на тој ќе го направи и мојот живот 47 00:02:22,010 --> 00:02:24,900 и голем број на други TAS "живее малку полесно. 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 Па се вратив и рачно regraded код на сите. 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 Затоа што тоа е еден вид на болка за ТС да треба да се вратиш назад и рачно regrade 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 По Харвард време, им е дозволено да биде седум минути доцна за се. 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 само ќе биде автоматски zeroed страна на компјутер. 83 00:04:02,270 --> 00:04:04,490 >> Ова го правиме од две причини. 84 00:04:04,490 --> 00:04:09,220 Една, понекогаш добиваме оправдани, како изговори деканот, 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 Christabel дојде до на работното време од минатата ноќ. 116 00:05:28,700 --> 00:05:29,691 Да, Christabel. 117 00:05:29,691 --> 00:05:32,190 И што имаме во канцеларијата часа минатата ноќ, Christabel? 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 подобро студент сооднос ТА да. 123 00:05:45,380 --> 00:05:47,650 Како legit, тоа е како 00: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 Без оглед на она TAS, јас мислам, се вели, 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 што треба да биде, така што TAS може да ве водиме заедно, 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 Па јас ќе одам да се биде дека ТС што потсетува сите дека квиз 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 О, јас добив неколку chuckles на оној. 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 Значи, вие не мора да дојде во на, како, на случаен 07: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" на врвот на вашиот ИРО? 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 Еден, тие или го додадете во printf () - па на секои неколку линии, 185 00:08:27,635 --> 00:08:29,760 тие го додадете во printf () - О, каква е оваа променлива? 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 она што се случува, наместо на printf-ИНГ или пишување одредување на своите изјави. 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 поделат во modulo. 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-- OOP. 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 >> И тогаш ќе можам да одам до мојот копчето грешки. 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 >> Значи имаш центи, монети, n, сите прогласени за различни работи 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 ох, 32767 била последната користи функцијата на тој простор меморија во мојот компјутер. 293 00:13:14,376 --> 00:13:16,000 И така тоа е каде центи во моментов е. 294 00:13:16,000 --> 00:13:19,360 Но не и дека откако ќе се кандидира на кодот, тоа треба да стане иницијализира. 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 Имаш на претставата, или функција во бегство, копчето, имате чекор преку копче, 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 Така на пример, како printf (), тоа е во функција, нели? 316 00:14:19,070 --> 00:14:21,980 Ако сакав да се физички чекор во () функцијата на printf, 317 00:14:21,980 --> 00:14:25,610 Јас би, всушност, оди во парче код каде printf () беше напишано и да видиме 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 Ние се претпостави на printf () работи. 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 >> Така n, што е наша плови дека ние сме 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 По тука, n стана заоблени и центи стана 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 Ние одиме во текот dimes. 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 Трчам грешки. 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 ние ќе треба да pseudocode ова. 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 за тоа како ние би можеле да бидат способни за спроведување на pseudocode да се напише еден вид селекција. 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 >> Значи, ако ние би сакале да се, како класа, пишува pseudocode 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 Па ви се случува да сакаат да iterate преку секој простор, нели? 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 ПУБЛИКАТА: Па, тогаш ќе сакате да iterate преку остатокот од низата. 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 Па ние сме веројатно нема да сакате да iterate 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 >> Така што вие момци да видите, ние само да има општа pseudocode 536 00:27:39,190 --> 00:27:41,480 за тоа како сакаме оваа програма да се погледне. 537 00:27:41,480 --> 00:27:46,646 Оваа iterate тука, она што го правиме обично треба да се напише во нашиот код 538 00:27:46,646 --> 00:27:49,270 ако сакаме да iterate преку низа, каков тип на структура? 539 00:27:49,270 --> 00:27:51,030 Мислам Christabel веќе реков тоа порано. 540 00:27:51,030 --> 00:27:51,500 >> ПУБЛИКАТА: А за телефонска линија. 541 00:27:51,500 --> 00:27:52,160 >> АНДИ Пенг: за телефонска линија? 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 >> АНДИ Пенг: Еден ако, нели? 548 00:28:06,790 --> 00:28:10,790 А потоа на swap тука, ние ќе одиме во текот подоцна, бидејќи Дејвид 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 Па јас сум само генерално напишан кодекс pseudocode тука. 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 Да се ​​вратиме во оваа ИРО. 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 n е и ќе биде оној број кој ви кажува износот на вредности 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 >> Значи имаме нашите pseudocode тука. 581 00:29:43,410 --> 00:29:46,090 Сака ли некој to-- Јас сум само случува да одам да побара volunteers-- 582 00:29:46,090 --> 00:29:49,540 ми каже точно што да напишеш ако ние сакаме да се, прво, само да iterate 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 >> ПУБЛИКАТА: За int i еднаква 0-- 589 00:30:08,190 --> 00:30:10,690 >> АНДИ Пенг: Да, добро. 590 00:30:10,690 --> 00:30:15,220 >> ПУБЛИКАТА: i е помал од должината на низата. 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 >> ПУБЛИКАТА: Зарем не би било n 1 минус? 603 00:30:51,948 --> 00:30:54,440 АНДИ Пенг: Тоа се случува n минус 1, точно. 604 00:30:54,440 --> 00:30:57,379 Дали тоа има смисла, зошто тоа е n минус 1, секој? 605 00:30:57,379 --> 00:30:58,920 Тоа е затоа што низите се нула-индексирани. 606 00:30:58,920 --> 00:31:02,010 Тие почнуваат во 0 и работи до минус 1 до n. 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 Whoops. 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-- "temp" целосно 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 ПУБЛИКАТА: i. 644 00:32:22,802 --> 00:32:24,790 АНДИ Пенг: Јас, точно. 645 00:32:24,790 --> 00:32:27,040 Christabel, зошто сакаме да се иницијализира на i? 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 ќе iterate преку несортиран, или остатокот од оваа низа. 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 бидејќи ние сме трчање низ остатокот на низата наместо з, па можеби 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-- па повторно, j е помалку од n минус 1, а потоа и j ++. 674 00:33:40,395 --> 00:33:41,103 АНДИ Пенг: Велики. 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 >> ПУБЛИКАТА: Еден ако соопштението. 686 00:34:09,360 --> 00:34:10,485 >> АНДИ Пенг: Еден ако соопштението. 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 И сега овде, ние всушност сакате да се спроведе на swap, нели? 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 >> ПУБЛИКАТА: Привремен променлива. 714 00:35:19,820 --> 00:35:21,370 >> АНДИ Пенг: Привремен променлива. 715 00:35:21,370 --> 00:35:22,570 Значи, да се направи int Temp. 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 Значи, да се направи int Temp. 720 00:35:30,730 --> 00:35:32,563 Што ќе се дојде до постави temp еднаква тука? 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 >> ПУБЛИКАТА: Тоа може да биде низа-i. 730 00:35:52,250 --> 00:35:53,666 >> АНДИ Пенг: Да, ајде да направиме низа-i. 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 ПУБЛИКАТА: Низа-ѕ еднаква низа-i. 737 00:36:12,070 --> 00:36:14,525 ПУБЛИКАТА: Или низа-ѕ еднаквите низа-temp-- или, темп. 738 00:36:14,525 --> 00:36:17,135 739 00:36:17,135 --> 00:36:19,430 >> АНДИ Пенг: Во ред. 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 >> ПУБЛИКАТА: Во ред. 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 АНДИ Пенг: Во ред. 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 Ahh. 777 00:38:16,030 --> 00:38:17,184 Што ќе правиме? 778 00:38:17,184 --> 00:38:17,850 ПУБЛИКАТА: грешки. 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 Можеме да debug. 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-- ОК. 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 OOP, дозволете ми да се ослободи од тоа. 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 АНДИ Пенг: Или запира. 794 00:38:54,890 --> 00:38:55,670 ПУБЛИКАТА: Или запира. 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 А потоа можеме да влезат во нашиот втор за јамка, во низа-ѕ е помалку од низа-I, 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 Па сега сте одјавувањето за низа индекс на J е помалку од низа 831 00:40:32,510 --> 00:40:33,970 Индекс на i. 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 Па ајде да ги разгледаме во нашата pseudocode. 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 Ние ќе треба да се оди до n 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 и да го поставите еднаква на i. 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 Сега во нашата внатрешна за телефонска линија, ние сме случува да се направи з ѕ еднаква на n 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 Вашиот за телефонска линија, за int Јас еднакво на 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 кои, исто така, е еднаква јас, затоа немаме минимална вредност. 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 И ние сакаме да iterate повторно. 871 00:42:19,270 --> 00:42:22,900 Сега дека ние сме го најдовте тоа што нашите минимални е, ние сакаме да iterate преку 872 00:42:22,900 --> 00:42:25,190 повторно за да се види дали тоа е споредување, нели? 873 00:42:25,190 --> 00:42:40,440 Па ј, тука, се случува за да се еднакви i, која е 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 Гледаме дека 1 е помалку од 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 >> Па кога ќе момци беа само имаат ѕ пред, вие не се гледа во еден 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 >> Oh yeah, овде бевме Замена на погрешни вредности, како и. 903 00:44:33,482 --> 00:44:34,940 Бидејќи бевме во потрага на i и j. 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 Значи, тоа беше вид на bugging нашиот код порано. 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 е само фенси начин да се каже на runtimes на сите од овие видови. 924 00:45:44,580 --> 00:45:47,650 Па знам Давид, во предавањето, начнавте runtimes. 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 Но сите вие ​​момци мора навистина знаеме е дека n квадрат повеќе од 2 931 00:46:00,689 --> 00:46:01,980 е истото што и N на квадрат. 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 Ако си оди за да се има да iterate преку листа 937 00:46:15,830 --> 00:46:18,712 а потоа iterate преку остатокот од таа листа, 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 ПУБЛИКАТА: n квадрат. 943 00:46:29,366 --> 00:46:30,740 АНДИ Пенг: Тоа е n квадрат, во право. 944 00:46:30,740 --> 00:46:36,986 Така е одличен начин да се размислува за ова е како, секое време имате два за вгнездени јамки, 945 00:46:36,986 --> 00:46:38,110 тоа се случува да биде N на квадрат. 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 Па во тој случај, си работи n Времето n квадрат, што is-- ми е, 950 00:46:48,640 --> 00:46:50,505 n n пати, што е еднакво n квадрат. 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 >> Па во таков случај, најдобро и најлошо runtimes се всушност еквивалентни. 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 исто така, ќе биде n квадрат. 964 00:47:24,790 --> 00:47:26,480 Сите три од овие ќе биде n квадрат. 965 00:47:26,480 --> 00:47:29,653 Е јасно на сите зошто на траење е N на квадрат? 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 Па во таа смисла, ова е само општата pseudocode за тоа. 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 И ние iterate преку целата низа. 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 >> ПУБЛИКАТА: Дали тоа ќе биде, како, n пати n 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 Ви се случува да се кандидира до n пати прв пат, право? 1025 00:50:30,320 --> 00:50:33,200 И тие се случува да се кандидира преку n 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 надолу до n квадрат. 1030 00:50:49,784 --> 00:50:51,700 Си оди за да се добие чудни дел во таму. 1031 00:50:51,700 --> 00:50:53,892 И така само знам дека на n квадрат секогаш 1032 00:50:53,892 --> 00:50:55,350 има приоритет над дел. 1033 00:50:55,350 --> 00:50:58,450 И така во овој случај, на најлошото траење ќе биде n квадрат. 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 >> ПУБЛИКАТА: n. 1039 00:51:09,565 --> 00:51:10,690 АНДИ Пенг: Тоа е n, точно. 1040 00:51:10,690 --> 00:51:11,600 И зошто тоа е n? 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 Па во тој случај, тоа е само n или бројот на чекори што само 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 >> Па тоа е само алгоритам, pseudocode по себе, вид, 1082 00:52:59,830 --> 00:53:04,990 за тоа како ние ќе се имплементираат вметнување вид. 1083 00:53:04,990 --> 00:53:05,954 Pseudocode е тука. 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 >> Добро Сака ли некој да дај ми најлошите траење? 1092 00:53:50,071 --> 00:53:50,570 Је. 1093 00:53:50,570 --> 00:53:51,490 >> ПУБЛИКАТА: n квадрат. 1094 00:53:51,490 --> 00:53:52,573 >> АНДИ Пенг: Тоа е n квадрат. 1095 00:53:52,573 --> 00:53:53,730 И зошто е тоа n квадрат? 1096 00:53:53,730 --> 00:53:57,562 >> ПУБЛИКАТА: Затоа што во обратен редослед, имаш 1097 00:53:57,562 --> 00:54:02,619 да се оди преку n n пати, што 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 И така целосно, си оди за да се направи на пати n помине уште n помине, која 1105 00:54:20,290 --> 00:54:21,750 е N на квадрат. 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 >> ПУБЛИКАТА: N минус 1, бидејќи Првиот е веќе на квадрат. 1109 00:54:28,840 --> 00:54:30,270 >> АНДИ Пенг: Значи, во близина. 1110 00:54:30,270 --> 00:54:31,850 Одговорот е всушност n. 1111 00:54:31,850 --> 00:54:37,189 Бидејќи додека првата е подредени, тоа не може да го actually-- 1112 00:54:37,189 --> 00:54:38,980 ние само lucked надвор, во дека на пример, дека 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 ако е веќе сортирана на почетокот но ќе се погледне и има 1 тука, 1116 00:54:48,040 --> 00:54:49,144 1 ќе се судрат. 1117 00:54:49,144 --> 00:54:51,060 И тоа се случува да се стави крај Регистрација се bumped онака. 1118 00:54:51,060 --> 00:54:56,250 >> Значи, во најдобар случај, тоа е всушност само ќе биде n. 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 ПУБЛИКАТА: Ох, ОК. 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 Кул, да свикува нови повторно како класа. 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 Значи ова е само малку pseudocode. 1162 00:57:38,750 --> 00:57:41,040 Дали тоа има смисла во начинот на кој се работи? 1163 00:57:41,040 --> 00:57:43,870 Па да речеме дека имате низа од n елементи, нели? 1164 00:57:43,870 --> 00:57:45,450 Ако n е помалку од 2, може да се врати. 1165 00:57:45,450 --> 00:57:49,040 Затоа што знаете дека ако има само едно нешто, тоа мора да се решат. 1166 00:57:49,040 --> 00:57:52,600 Друго, ќе се најде решение за левата половина, а потоа ќе се најде решение за десната половина, 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 Па во таа смисла, Дејвид допре по рекурзија во класата. 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 Па да знаете 1 оди таму. 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 Кои се најдобрите случај runtimes, најлош случај runtimes, 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 >> ПУБЛИКАТА: е најлош случај n log n? 1279 01:02:25,269 --> 01:02:26,060 АНДИ Пенг: Токму така. 1280 01:02:26,060 --> 01:02:29,380 И зошто е тоа n log n. 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 Па заради тоа траење на оваа е n најавите 1286 01:02:40,750 --> 01:02:44,310 n е 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 И така, ако вие само треба да проверете една работа, тоа е n. 1297 01:03:10,330 --> 01:03:13,420 И така ти си вид на множење на двете заедно. 1298 01:03:13,420 --> 01:03:17,660 Па тоа е како ќе го добивме тоа конечна проверете за N овде долу со најавите на n 1299 01:03:17,660 --> 01:03:18,390 до тука. 1300 01:03:18,390 --> 01:03:21,060 И ако се размножуваат нив, тоа е n log n. 1301 01:03:21,060 --> 01:03:26,100 >> И така на најдобар случај и најлош случај и се очекува сите n log n. 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-- n 1308 01:03:39,950 --> 01:03:41,660 квадрат, тоа не е многу ефикасен. 1309 01:03:41,660 --> 01:03:47,060 Па дури и овој n log n е не најефикасен. 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 >> Имаш некои најавите n е. 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 Вие само треба да iterate преку. 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 како да pseudocode ова. 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 И тогаш int n е број на елементите во таа низа. 1398 01:07:36,280 --> 01:07:39,430 Како ќе одат за обидот да pseudocode тој проблем во? 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 Така претпоставуваат имаме оваа прекрасна малку низа со n вредности во него. 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 Ако сакате да ми даде првата линија на овој pseudocode. 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 Публика: Вие би сакале да iterate 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 Јамка 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 >> АНДИ Пенг: Во ред. 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 ПУБЛИКАТА: Макс плус поделено со 2 мин. 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 наместо да го прават само n поделено со 2? 1492 01:14:27,850 --> 01:14:30,310 Тоа е затоа што n е вредност кој ќе остане иста. 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 И тогаш ти си само ќе да се задржи looping, нели? 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 Ако сте само се допаѓа, ahh, јас не знам што тој го прави, 1552 01:17:08,630 --> 01:17:11,670 Не знам, како, што се чини дека толку комплицирано, Ahh, да се релаксираат. 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