[Powered by Google Translate] [Sezzjoni 3 - aktar komdi]
[Rob Bowden - Università ta 'Harvard]
>> [Dan huwa CS50. - CS50.TV]
>> Allura l-ewwel domanda hija fformulata stramba.
GDB ihallik "debug" programm, iżda, b'mod aktar speċifiku, dak ma let inti tagħmel?
I ser tingħata risposta għal din waħda, u jien ma nafx x'inhu eżattament mistenni,
hekk jien guessing huwa xi ħaġa fuq il-linji ta ihallik pass pass
jimxu permezz tal-programm, jinteraġixxu ma 'dan, varjabbli bidla, tagħmel dawn l-affarijiet -
bażikament kompletament kontroll eżekuzzjoni ta 'programm
u jispezzjona kull parti partikolari tan-esekuzzjoni tal-programm.
Allura dawk il-karatteristiċi tavżak debug affarijiet.
Okay.
Għaliex ma tfittxija binarju jeħtieġu li l-firxa tiġi riżolta?
Min jixtieq li tingħata risposta għal din?
[Student] Minħabba li ma jaħdimx jekk ma jkunx magħżula. >> Yeah. [Daħk]
Jekk huwa ma jintgħażlux, allura huwa impossibbli li jaqsam min-nofs
u jafu li kollox lejn ix-xellug huwa inqas u kollox lejn il-lemin
huwa akbar mill-valur medju.
Għalhekk jeħtieġ li jiġu magħżula.
Okay.
Għaliex huwa tip bużżieqa fil O ta 'n kwadrat?
Hawn xi ħadd l-ewwel trid tagħti malajr ħafna ta 'livell għoli ħarsa ġenerali ta' dak it-tip bużżieqa hu?
[Student] Inti bażikament jmorru permezz ta 'kull element u inti tiċċekkja l-elementi ewwel ftit.
Jekk dawn qed barra ta 'fejn inti tpartit lilhom, allura inti tiċċekkja l-elementi li ġejjin u l-bqija.
Meta inti jilħqu t-tmiem, imbagħad inti taf li l-ikbar element jitqiegħed fl-aħħar,
sabiex inti jinjora li wieħed imbagħad inti żżomm fuq għaddejjin,
u kull darba li inti għandek tiċċekkja element wieħed inqas sakemm inti tagħmel l-ebda tibdil. >> Yeah.
Huwa sejjaħ tip bużżieqa għaliex jekk inti flip-firxa fuq il-ġenb tiegħu hekk huwa u 'l isfel, vertikali,
il-valuri kbar se sink mal-qiegħ u l-valuri żgħar se buzzieqa sal-quċċata.
Li kif ltqajna l-isem tagħha.
U yeah, inti biss jgħaddu.
Inti żżomm għaddejja l-array, jagħmlu skambju ta 'l-akbar valur
biex jiksbu l-valuri akbar mal-qiegħ.
>> Għaliex huwa O ta 'n kwadrat?
L-ewwel, ħadd ma jridu jgħidu għaliex huwa O ta 'n kwadrat?
[Student] Minħabba għal kull ġirja tmur n darbiet.
Inti tista 'biss tkun żgur li ħadt l-element akbar it-triq kollha,
imbagħad inti għandek jirrepetu li għal kemm ħafna elementi. >> Yeah.
Allura wieħed iżomm f'moħħu dak big O mezzi u dak li tfisser Omega kbar.
Il O big huwa bħall-upper marbuta fuq kif bil-mod li jista 'tmexxi effettivament.
Allura billi qal O huwa n kwadrat, mhuwiex O ta 'n jew inkella jkun kapaċi li jimxu
fil-ħin lineari, iżda huwa O ta 'n kubiku
minħabba li hija limitata bir O ta 'n kubiku.
Jekk huwa mdawwar bil O ta 'n kwadrat, allura huwa tmiss wkoll mill n kubiku.
Għalhekk huwa n kwadrat, u fil-każ assoluta agħar ma tistax tagħmel aħjar minn n kwadrat,
li hija għaliex huwa O ta 'n kwadru.
Allura biex tara matematika żgħir lejn kif niġu biex tkun n kwadrat,
jekk għandna ħames affarijiet fil-lista tagħna, l-ewwel darba kemm swaps nistgħu potenzjalment bżonn li jagħmlu
sabiex tikseb dan? Ejja attwalment biss -
Kemm tpartit aħna se jkollhom jagħmlu fl-ewwel ġirja tal sort bużżieqa permezz tal-firxa?
[Student] n - 1. >> Yeah.
>> Jekk ikun hemm 5 elementi, aħna qed tmur biex jeħtieġu jagħmlu n - 1.
Imbagħad fuq it-tieni waħda kemm swaps huma aħna se jkollhom jagħmlu?
[Student] n - 2. >> Yeah.
U t-tielet se tkun n - 3, u mbagħad għall-konvenjenza I se jikteb l-aħħar tnejn
kif allura aħna qed tmur għall-ħtieġa li tagħmel 2 tpartit u 1 tpartit.
I raden l-aħħar wieħed jistgħu jew ma jistgħux attwalment ħtieġa li jiġri.
Huwa ta 'swap? I do not know.
Allura dawn huma l-ammonti totali ta 'swaps jew inqas paraguni għandek tagħmel.
Anki jekk inti ma tpartit, inti xorta jkollok bżonn biex tqabbel il-valuri.
Allura hemm n - 1 tqabbil fl-ewwel ġirja permezz tal-firxa.
Jekk inti rranġati mill-ġdid dawn l-affarijiet, ejja tagħmel attwalment minnu sitt affarijiet affarijiet munzell up nicely,
u mbagħad I ser tagħmel 3, 2, 1.
Hekk biss titranġa dawn is-somom, irridu naraw kemm paraguni nagħmlu
fil-algoritmu kollu.
Allura jekk aħna idaħħlu dawn guys stabbiliti hawn,
allura aħna qed għadhom biss jingħaddu l-paraguni madankollu ħafna kien hemm.
Imma jekk aħna qosor dawn u aħna qosor dawn u aħna qosor dawn,
huwa għadu l-istess problema. Aħna biss is-somma dawk il-gruppi partikolari.
>> Allura issa aħna qed jingħaddu 3 ta n. Huwa mhux biss 3 s n.
Huwa dejjem se jkunu n / 2 tal-n.
Allura hawnhekk għandna jiġri li jkollhom 6.
Jekk kellna 10 affarijiet, allura stajna nagħmlu dan il-grupp għal 5 pari differenti ta 'affarijiet
u tispiċċa bil n + n + n + n + n.
Allura int dejjem se tikseb n / 2 tal-n, u għalhekk dan aħna ser LOGHOME out għal n kwadrat / 2.
U għalhekk anki jekk huwa l-fattur ta 'nofs, li jiġri li jaqgħu fl-
minħabba l-fatt li permezz ta 'kull iterazzjoni fuq il-firxa inqabblu 1 inqas
b'tali mod li l-mod kif nagħmlu l-aktar minn 2, iżda xorta huwa n kwadru.
Aħna ma jimpurtahom dwar il-fattur kostanti ta 'nofs.
Allura ħafna ta 'O għalf kbar bħal din tistrieħ fuq biss tip ta' kif isir dan it-tip ta 'matematika,
jagħmlu somom aritmetika u l-għalf serje ġeometrika,
iżda ħafna minnhom f'dan il-kors huma pjuttost sempliċi.
Okay.
Għaliex huwa tip inserzjoni fl-Omega n? X'tagħmel omega jfisser?
[2 istudenti jitkellmu f'daqqa - mhux intelliġibbli] Yeah >>.
Omega inti tista 'taħseb bħala l-aktar baxx marbut.
>> Allura l-ebda kwistjoni kif effiċjenti algoritmu tiegħek tip inserzjoni hija,
irrispettivament mill-lista li l-għadda fi, dejjem irid iqabbel l-inqas n affarijiet
jew għandu jtenni fuq affarijiet n.
Għaliex huwa li?
[Student] Minħabba li jekk il-lista hija diġà magħżula, imbagħad permezz l-ewwel iterazzjoni
inti tista 'biss tiggarantixxi li l-element ewwel huwa l-inqas,
u l-tieni iterazzjoni inti tista 'biss jiggarantixxu l-ewwel tnejn huma
għaliex inti ma taf li l-bqija tal-lista hija magħżula. >> Yeah.
Jekk inti tgħaddi f'lista kompletament magħżula, għall-inqas ikollok tmur fuq l-elementi kollha
biex tara li xejn jeħtieġ li jiġu mċaqalqa madwar.
Allura tgħaddi minn fuq il-lista u qal oh, dan diġà magħżula,
huwa impossibbli li tkun taf huwa magħżul sakemm inti tiċċekkja kull element
biex tara li dawn huma fl-ordni magħżula.
Allura l-aktar baxx marbut fuq tip inserzjoni huwa Omega ta 'n.
X'hemm l-agħar każ running time ta 'tip jingħaqdu,
agħar każ hija O kbar mill-ġdid?
Allura fil-agħar każ, kif ma sort jingħaqdu run?
[Student] N log n. >> Yeah.
L-algoritmi aktar mgħaġġla issortjar ġenerali huma n log n. Inti ma tistax tagħmel aħjar.
>> Hemm każijiet speċjali, u jekk ikollna ħin llum - iżda aħna probabbilment won't -
nistgħu naraw dak li ma aħjar minn n log n.
Iżda fil-każ ġenerali, inti ma tistax tagħmel aħjar minn n log n.
U jingħaqdu tip jiġri li jkun il-wieħed inti għandek tkun taf għal dan il-kors li hu n log n.
U hekk aħna ser ikunu fil-fatt jimplimentaw dik llum.
U fl-aħħarnett, f'mhux aktar minn tliet sentenzi, kif jaħdem it-tip ta 'għażla?
Ma xi ħadd tixtieq li tingħata risposta, u jien ser joqgħod sentenzi tiegħek
għaliex jekk inti tmur fuq 3 -
Hawn xi ħadd ftakar sort għażla?
Sort Għażla normalment huwa pjuttost faċli biex tiftakar ftit mill-isem.
Inti biss ttenni fuq il-firxa, isibu ikun x'ikun l-akbar valur huwa jew iżgħar -
tkun xi ordni int issortjar pulzieri
Mela ejja ngħidu aħna qed issortjar minn iżgħar sa l-akbar.
Inti ttenni fuq il-firxa, ifittxu ikun x'ikun l-element minimu huwa,
tagħżel hija, u mbagħad biss tpartit huwa dak kollu li huwa fl-ewwel post.
U mbagħad fuq il-pass 2 fuq il-firxa, tfittex l-element minimu mill-ġdid,
tagħżel hija, u mbagħad tpartit ma 'dak fil-pożizzjoni 2.
Allura aħna biss picking u jagħżlu l-valuri minimi
u dawn jiddaħħlu fil-faċċata tal-array sakemm huwa magħżul.
Mistoqsijiet dwar li?
>> Dawn inevitabbilment jidhru fil-forom ikollok biex jimlew meta int tissottometti l-pset.
Dawk huma bażikament l-tweġibiet għal dawk.
Okay, hekk issa kodifikazzjoni problemi.
I diġà bagħtet matul email - Did ħadd ma nikseb li email? Okay.
I diġà bagħtet fuq email-ispazju li aħna qed tmur biex tkun qed tuża,
u jekk tikklikkja fuq isem tiegħi - hekk naħseb jien ser tkun fil-qiegħ
minħabba lr lura - imma jekk tikklikkja fuq isem tiegħi tkun taf tara 2 reviżjonijiet.
Reviżjoni 1 se tkun diġà I kkupjati u pasted l-kodiċi fis Spazji
għall-ħaġa tiftix int ser jkollhom jimplimentaw.
U Reviżjoni 2 se jkun il-ħaġa tip li nimplimentaw wara dik.
Allura inti tista 'tikklikkja fuq Reviżjoni tiegħi 1 u jaħdmu minn hemm.
U issa irridu li jimplimentaw tfittxija binarja.
>> Hawn xi ħadd jridux biss jagħtu pseudocode ta 'livell għoli spjegazzjoni
ta 'dak li aħna qed tmur biex ikollhom jagħmlu għall-tiftix? Yeah.
[Student] Inti biss tieħu l-nofs tal-firxa u ara jekk dak li qed tfittex
huwa inqas minn dak jew aktar minn dak.
U jekk huwa inqas, inti tmur għall-nofs li l-anqas,
u jekk huwa aktar, inti tmur man-nofs li l-aktar u inti irrepeti li sakemm inti biss tikseb wieħed ħaġa.
[Bowden] Yeah.
Avviż li n-numri firxa tagħna huwa diġà magħżula,
u sabiex dan ifisser li nistgħu nieħdu vantaġġ ta 'dan u nistgħu ewwel jivverifika,
okay, jien infittxu l-għadd 50.
So I tista 'tmur fil-nofs.
Nofsani huwa diffiċli li jiġu ddefiniti meta huwa anke numru ta 'affarijiet,
imma ejja biss jgħidu aħna ser dejjem truncate l-nofs.
Allura hawnhekk għandna 8 affarijiet, sabiex il-middle ikun 16.
I infittex 50, hekk 50 huwa akbar minn 16.
Allura issa I jistgħu bażikament jittrattaw firxa tiegħi bħala dawn l-elementi.
I tista tarmi l bogħod kollox mill-16 fuq.
Issa firxa tiegħi huwa biss dawn l-elementi 4, u nirrepeti.
Allura mbagħad I jridu jsibu l-nofs mill-ġdid, li se tkun 42.
42 huwa anqas minn 50, so I tista tarmi l bogħod dawn iż-żewġ elementi.
Dan huwa array li jifdal tiegħi.
Jien ser isibu l-nofs mill-ġdid.
I raden 50 kien eżempju ħażin minħabba I kien dejjem tarmi l-affarijiet lejn ix-xellug,
iżda mill-istess miżura, jekk jien tfittex xi ħaġa
u huwa inqas mill-element jien bħalissa tħares lejn,
allura jien ser tarmi kollox lejn il-lemin.
Allura issa għandna bżonn li jimplimentaw dik.
Avviż li għandna bżonn li tgħaddi fid-daqs.
Nistgħu wkoll ma jeħtiġux li hard-kodiċi ta 'daqs.
Allura jekk aħna teħles minn dik # jiddefinixxu -
Okay.
Kif nista nicely ċifra barra dak id-daqs tal-array numri bħalissa hu?
>> Kemm l-elementi huma fil-firxa numri?
[Student] Numri, brazzi,. Tul?
[Bowden] Dan ma jeżistix fil C.
Ħtieġa. Tul.
Arrays m'għandhomx proprjetajiet, b'hekk m'hemm l-ebda proprjetà tul ta 'arrays
li se biss jagħtik madankollu żmien li jiġri li jkun.
[Student] Ara kemm memorja huwa għandu u iddividi kemm - Yeah. >>
Allura kif nistgħu tara kemm memorja li tkun? >> [Student] Sizeof. >> Yeah, sizeof.
Sizeof huwa l-operatur li għaddej biex jirritorna l-daqs tal-array numri.
U li għaddej biex jiġu interi madankollu ħafna hemm darbiet id-daqs ta 'numru sħiħ
peress li l-kemm memorja huwa attwalment bidu.
Mela jekk irrid in-numru ta 'affarijiet fil-firxa,
allura jien ser jridu iddividi-daqs ta 'numru sħiħ.
Okay. Allura li tikri me jgħaddu fid-daqs hawnhekk.
Għaliex għandi bżonn li tgħaddi fid-daqs fil-livelli kollha?
Għaliex ma nistax nara biss tagħmel up here daqs int = sizeof (haystack) / sizeof (int)?
Għaliex ma dan ma taħdimx?
[Student] Mhuwiex varjabbli globali.
[Bowden] Haystack jeżisti u aħna qed jgħaddi f'numri kif haystack,
u dan huwa tip ta 'foreshadowing ta' x'inhu li ġejjin. Yeah.
[Istudent] Haystack huwa biss ir-referenza għaliha, u għalhekk se jerġa 'lura kemm hu kbir dan ir-referenza.
Yeah.
I dubju fir lecture li inti stajt tidher l-munzell għadhom verament, id-dritt?
Imxejna biss mitkellma dwar dan.
Allura l-munzell huwa fejn kollha ta 'varjabbli tiegħek ser jiġu maħżuna.
>> Kull memorja li s allokat għal varjazzjonijiet lokali sejra fid-munzell,
u kull funzjoni gets spazju tagħha stess fuq il-munzell, il-qafas tagħha stess munzell huwa dak li sejjaħ.
Allura prinċipali għandha qafas munzell tagħha, u ġewwa ta 'dan huwa ser jeżistu f'dan firxa numri,
u li għaddej biex tkun ta 'sizeof daqs (numri).
Huwa ser ikollhom daqs ta 'numri diviż skond id-daqs ta' elementi,
iżda li l-ħajja fi ħdan il-qafas munzell prinċipali tal.
Meta nitolbu tfittxija, tfittxija gets frejm tagħha munzell stess,
ispazju tagħha stess taħżen kollha ta 'varjabbli lokali tiegħu.
Iżda dawn l-argumenti - sabiex haystack mhux kopja ta 'din il-firxa sħiħa.
Aħna ma jgħaddu fil-firxa sħiħa bħala kopja fl-tfittxija.
Hija biss tgħaddi referenza għal dak array.
Allura tfittxija tista 'aċċess dawn in-numri ta' referenza permezz ta 'dan.
Huwa għadu aċċess għall-affarijiet li jgħixu ġewwa tal-qafas munzell prinċipali, il-
imma bażikament, meta irridu jiksbu l pointers, li għandu jkun malajr,
dan huwa dak pointers huma.
Pointers huma biss referenzi għal affarijiet, u tista 'tuża indikaturi għall-aċċess affarijiet
li huma frames munzell affarijiet oħra ".
Allura anke jekk in-numri hija lokali għal main, aħna xorta jistgħu jkollhom aċċess għaliha permezz ta 'dan pointer.
Iżda peress li huwa biss pointer u huwa biss ta 'referenza,
sizeof (haystack) jirritorna d-daqs tar-referenza innifsu.
Ma lura id-daqs tal-ħaġa huwa li tipponta lejn.
Hija ma jirritorna l-daqs attwali ta 'numri.
U hekk dan mhux sejjer jaħdem kif aħna tixtieq li.
>> Mistoqsijiet dwar li?
Pointers se tkun marret fi f'aktar dettall sinifikament aktar rija fil-ġimgħat li ġejjin.
U dan huwa għaliex ħafna affarijiet li tara, affarijiet tat-tiftix aktar jew affarijiet sort,
dawn qed kważi kollha ser ikollok bżonn tieħu l-daqs attwali tal-firxa,
minħabba fis-C, aħna għandna ebda idea x'inhi l-daqs tal-array huwa.
Ikollok bżonn li manwalment jgħaddu hija pulzieri
U inti ma tistax manwalment jgħaddu fil-firxa sħiħa għax int biss tgħaddi fir-referenza
u hija ma tistax tikseb id-daqs mir-referenza.
Okay.
Allura issa rridu li jimplimentaw dak li kien spjegat qabel.
Tista 'taħdem fuq dan għal minuta,
u inti ma għandekx għalfejn tinkwieta dwar jkollna kollox perfettament 100% tax-xogħol.
Just tikteb l-pseudocode nofs għal kif taħseb li għandha taħdem.
Okay.
Ebda ħtieġa biex jiġu kompletament jsir ma 'din s'issa.
Iżda ħadd ma jħossuhom komdi ma 'dak li s'issa,
bħal xi ħaġa nistgħu naħdmu flimkien?
Hawn xi ħadd jixtiequ jagħmlu volontarjat? Jew I se saltwarjament pick.
Ma għandhom ikunu id-dritt b'xi miżura imma xi ħaġa li nistgħu timmodifika fi stat ta 'ħidma.
[Student] Sure. Okay. >>
Allura tista 'tfaddal-reviżjoni billi tikklikkja fuq l-ikona Save ftit.
Inti Ramya, id-dritt? >> [Student] Yeah. >> [Bowden] Okay.
Allura issa I jista 'jara r-reviżjoni tiegħek u kulħadd jista' pull up-reviżjoni.
U hawn aħna għandna - Okay.
Allura Ramya marru bis-soluzzjoni rikursivi, li huwa definittivament soluzzjoni valida.
Hemm żewġ modi kif inti tista 'tagħmel din il-problema.
Inti tista 'jew tagħmel dan iteratively jew recursively.
Ħafna mill-problemi li inti tiltaqa li jista 'jsir recursively jista' jsir ukoll iteratively.
Allura hawnhekk għandna ghamilt recursively.
>> Ma xi ħadd tixtieq li jiddefinixxu dak li tfisser li tagħmel funzjoni jirrikorri?
[Student] Meta għandek funzjoni sejħa nnifisha
u mbagħad sejħa nnifisha sakemm toħroġ ma 'vera u vera. >> Yeah.
Funzjoni jirrikorri hija biss funzjoni li jitlob huwa stess.
Hemm tliet affarijiet kbar li funzjoni rikursivi għandu jkollu.
L-ewwel huwa ovvjament, hija ssejjaħ lilha nnifisha.
It-tieni huwa l-każ bażi.
Allura f'xi punt l-funzjoni jeħtieġ li tieqaf ssejjaħ lilha nnifisha,
u dan huwa dak l-każ bażi huwa għall.
Allura hawnhekk aħna nafu li aħna għandu jieqaf, għandna jieqfu fit-tfittxija tagħna
meta bidu huwa ugwali għan - u aħna ser jmorru fuq dak li tfisser.
Iżda fl-aħħar, l-aħħar ħaġa li l-importanti għall-funzjonijiet jirrikorri:
il-funzjonijiet għandhom b'xi mod approċċ il-każ bażi.
Bħal jekk int ma fil-fatt aġġornament xejn meta inti tagħmel is-sejħa rikursivi 2,
jekk int litteralment biss li ssejjaħ il-funzjoni mill-ġdid ma 'l-istess argumenti
u l-ebda varjabbli globali nbidlu jew xejn,
int qatt mhi ser tilħaq il-każ bażi, f'liema każ l-ħażina.
Din se tkun recursion infinita u overflow munzell.
Imma hawn naraw li l-aġġornament qed jiġri peress li aħna qed jaġġornaw tibda + tmiem / 2,
aħna qed taġġorna l-argument aħħar hawnhekk, aħna qed taġġorna l-argument bidu hawnhekk.
Għalhekk fl-sejħiet kollha rikursivi aħna aġġornament xi ħaġa. Okay.
Tixtieq li jimxu magħna permezz soluzzjoni tiegħek? >> Sure.
Jien jużaw SearchHelp hekk li kull darba nagħmel din is-sejħa funzjoni
Għandi l-bidu ta 'fejn jien tfittex fil-firxa u t-tmiem
ta 'fejn jien tfittex l-array.
>> F'kull pass fejn huwa qal li huwa l-element tan-nofs, li huwa bidu + tmiem / 2,
hija li daqs dak li aħna qed tfittex?
U jekk huwa, imbagħad sibna, u I raden li gets mgħoddija l-livelli ta 'recursion.
U jekk dan mhux veru, allura aħna tivverifika jekk dak il-valur tan-nofs tal-firxa hija kbira wisq,
f'liema każ aħna nħarsu lejn in-nofs tax-xellug tal-firxa billi tmur mill-bidu sat-indiċi tan-nofs.
U inkella nagħmlu l-nofs aħħar.
[Bowden] Okay.
Li ħsejjes tajba.
Okay, so a koppja affarijiet, u fil-fatt, din hija ħaġa ħafna ta 'livell għoli
li qatt mhu ser ikollok bżonn li tkun taf għal dan il-kors, iżda huwa veru.
Funzjonijiet jirrikorri, inti dejjem tisma li dawn qed ftehim ħażin
għaliex jekk inti recursively sejħa lilek innifsek wisq drabi, ikollok overflow munzell
peress li, kif għidt qabel, kull funzjoni gets frejm tagħha munzell stess.
Allura kull sejħa tal-funzjoni jirrikorri gets frejm tagħha munzell stess.
Mela jekk inti tagħmel sejħiet 1000 rikursivi, ikollok frejms munzell 1000,
u malajr inti twassal biex wara frames wisq munzell u affarijiet biss break.
Allura hu għalhekk li l-funzjonijiet rikursivi huma ġeneralment ħżiena.
Iżda hemm subsett sbieħ ta 'funzjonijiet jirrikorri imsejħa tail-funzjonijiet rikursivi,
u dan jiġri li jkun eżempju ta 'waħda fejn jekk il-kumpilatur avviżi din
u dan għandu, naħseb - fil clang jekk inti tgħaddi din l-O2 bandiera
allura se Avviż dan huwa denb rikursivi u tagħmel l-affarijiet tajba.
>> Se użu mill-ġdid il-qafas munzell istess tul u aktar mill-ġdid għal kull sejħa rikursivi.
U hekk peress li inti qed tuża l-qafas munzell istess, inti m'għandekx bżonn ninkwetaw dwar
qatt munzell overflowing, u fl-istess ħin, bħalek qal qabel,
fejn ladarba inti tirritorna veru, allura għandu jirritorna up kollha ta 'dawn il-frejms munzell
u s-sejħa 10 sa SearchHelp għandha tirritorna lill-9, għandu jirritorna t-8.
Allura li ma għandux bżonn li jiġri meta l-funzjonijiet huma denb rikursivi.
U hekk dak li jagħmel dan denb funzjoni jirrikorri huwa avviż li għal kwalunkwe sejħa għal searchHelp
-sejħa jirrikorri li huwa jagħmel huwa dak li huwa jirritorna.
Għalhekk fl-ewwel sejħa għall-SearchHelp, aħna jew immedjetament jibgħatu lura falza,
immedjatament lura vera, jew nagħmlu sejħa jirrikorri għall SearchHelp
fejn dak li aħna qed jirritornaw huwa dak li sejħa huwa jirritorna.
U aħna ma setgħux jagħmlu dan jekk aħna ma xi ħaġa simili int x = SearchHelp, ritorn x * 2,
biss ftit każwali bidla.
>> Allura issa din is-sejħa rikursivi, dan int x = sejħa SearchHelp rikursivi,
m'għadhiex denb rikursivi għaliex fil-fatt ma jkollhomx għalfejn imorru lura
lura għal qafas munzell ta 'qabel b'tali mod li dik is-sejħa preċedenti għall-funzjoni
tista 'mbagħad tagħmel xi ħaġa bil-valur tar-ritorn.
Allura dan mhux denb rikursivi, imma dak li kellna qabel huwa nicely denb rikursivi. Yeah.
[Student] ma Jekk il-każ bażi tat-tieni jiġu ċċekkjati 1
għaliex jista 'jkun hemm sitwazzjoni fejn meta inti tgħaddi dan l-argument
inti għandek tibda = il-għan, iżda huma l-valur tal-labra.
Il-kwistjoni ma tistax we run fis-każ fejn aħħari huwa l-valur tal-labra
jew jibdew = il-għan, kif xieraq, bidu = tmiem
u int ma attwalment ivverifikat li valur partikolari għadhom,
imbagħad tibda + tarf / 2 huwa biss se tkun l-istess valur.
Imma konna diġà lura foloz u aħna qatt verament ċċekkjati l-valur.
Allura għall-inqas, fl-ewwel sejħa, jekk id-daqs huwa 0, allura aħna rridu li jirritornaw falza.
Iżda jekk id-daqs huwa 1, allura bidu mhux se aħħar ugwali,
u aħna ser jiċċekkja l-inqas l-element wieħed.
Imma naħseb inti dritt f'dak nistgħu jispiċċaw fil-każ fejn tibda + tmiem / 2,
bidu jispiċċa jkun l-istess bħal bidu + tmiem / 2,
imma aħna qatt ma attwalment ċċekkjati dan l-element.
>> Allura jekk aħna l-ewwel jivverifika l-element nofs il-valur aħna qed tfittex,
allura nistgħu immedjatament lura veru.
Else jekk dawn qed ugwali, allura hemm l-ebda punt fil-kontinwazzjoni
peress li aħna qed biss jmorru biex taġġorna għal każ fejn ninsabu fuq firxa waħda element.
Jekk dan l-element waħdieni ma jkunx dak li aħna qed tfittex,
allura kollox huwa ħażin. Yeah.
[Student] Il-ħaġa hija li peress li d-daqs huwa attwalment akbar mill-għadd ta 'elementi fil-firxa,
diġà jkun hemm offset - >> Allura se-daqs -
[Student] Jiġifieri jekk il-firxa kienet daqs 0, allura l-SearchHelp fatt se jiċċekkja haystack ta '0
fuq l-ewwel sejħa.
Il-firxa għandha daqs 0, sabiex il-0 hija - >> Yeah.
Hemm ħaġa oħra li - jista 'jkun tajjeb. Ejja jaħsbu.
Allura jekk il-firxa kienet 10 Elementi u tan-nofs aħna qed tmur biex jivverifikaw huwa indiċi 5,
hekk aħna qed iċċekkjar 5, u ejja ngħidu li l-valur ikun inqas.
Allura aħna qed jitfg kollox bogħod minn 5 'il quddiem.
Allura tibda + tarf / 2 se tkun il-għan il-ġdid tagħna,
hekk yeah, huwa dejjem ser jibqgħu hinn mit-tmiem tal-firxa.
Jekk huwa każ jekk kien saħansitra jew fard, allura aħna se check, jiġifieri, 4,
iżda aħna qed għadhom jitfg bogħod -
So yeah, aħħar huwa dejjem se jkunu lil hinn mill-aħħar attwali ta 'l-array.
Allura l-elementi qegħdin jiffokaw fuq, tarf huwa dejjem se jkun il-wieħed wara dik.
U hekk jekk bidu ma qatt tmiem ugwali, aħna fil-firxa ta 'daqs 0.
>> Il-ħaġa oħra I kienet taħseb hija li aħna aġġornament bidu li tibda + tmiem / 2,
għalhekk dan huwa l-każ li jien trouble wara ma ', fejn tibda + tarf / 2
huwa l-element aħna qed iċċekkjar.
Ejja ngħidu li kellna din array 10-element. Tkun xi tkun.
Allura tibda + tarf / 2 se tkun xi ħaġa bħal dan wieħed,
u jekk dan mhux il-valur, ngħidu aħna rridu li taġġorna.
Il-valur huwa ikbar, hekk aħna tixtieq li tħares lejn dan nofs il-firxa.
Allura kif aħna qed aġġornament bidu, aħna qed taġġorna bidu sa issa jkun dan l-element.
Iżda dan jista 'xorta taħdem, jew għall-inqas, inti tista' tagħmel bidu + tmiem / 2 + 1.
[Student] Inti ma għandekx bżonn li jiġu jibdew + tmiem [inaudible] >> Yeah.
Aħna diġà ċċekkjati dan l-element u jafu mhuwiex l-waħda aħna qed tfittex.
Allura aħna ma bżonn li jaġġornaw bidu sabiex tkun dan l-element.
Nistgħu biss skip dan u taġġorna jibdew ikunu dan l-element.
U hemm qatt każ, ejja ngħidu, li dan kien il-għan,
hekk imbagħad tibda tkun din, tibda + tmiem / 2 tkun din,
bidu + finali - Yeah, naħseb li jista 'jispiċċa fil-recursion infinita.
Ejja ngħidu huwa biss firxa ta 'daqs 2 jew firxa ta' daqs 1. Naħseb li dan se taħdem.
Allura bħalissa, bidu huwa dan l-element u għan huwa 1 lil hinn minnha.
Allura l-element li aħna qed tmur biex jivverifikaw huwa dan wieħed,
u mbagħad meta aħna aġġornament bidu, aħna qed aġġornament bidu sabiex tkun 0 + 1/2,
li se jispiċċaw us lura ma jibda dan l-element tkun.
>> Allura aħna qed iċċekkjar tal-element istess tul u aktar mill-ġdid.
Allura dan huwa l-każ fejn kull sejħa jirrikorri għandu tabilħaqq taġġorna xi ħaġa.
Għalhekk għandna bżonn li nagħmlu bidu + tmiem / 2 + 1, jew inkella hemm każ
fejn aħna mhux qed attwalment aġġornament bidu.
Kulħadd tara li?
Okay.
Ħadd ma jkollu mistoqsijiet dwar din is-soluzzjoni jew kummenti kwalunkwe aktar?
Okay. Hawn xi ħadd li iterattiv soluzzjoni li aħna lkoll nistgħu nħarsu lejn?
Did aħna kollha jagħmlu dan recursively?
Jew ukoll I raden jekk inti miftuħa ont, allura inti jista 'jkollok megħluba waħda preċedenti tiegħek.
Ma awtomatikament jiffranka? Jien ma pożittiv.
Hawn xi ħadd li iterattiv?
Nistgħu jimxu permezz ta 'dan flimkien jekk le.
L-idea se tkun l-istess.
Iterattiv soluzzjoni.
Aħna qed tmur jridu bażikament jagħmlu l-istess idea
fejn irridu jżommu rekord ta 'l-aħħar il-ġdid tal-firxa u l-bidu ġdid ta' l-array
u tagħmel dan aktar u aktar.
U jekk dak li aħna qed iżżomm rekord ta 'kif il-bidu u t-tmiem qatt jiltaqgħu,
allura aħna ma jsibuha u nistgħu ritorn foloz.
Allura kif nista 'nagħmlu? Kull min ikollu suġġerimenti jew kodiċi għalija biex pull up?
[Student] Do loop waqt. >> Yeah.
Inti tmur tixtieq li tagħmel loop.
>> Kellek kodiċi I tista 'pull up, jew dak li inti kienu ser jissuġġerixxu?
[Student] I think so. >> Kull dritt. Dan jagħmel l-affarijiet eħfef. Liema kien l-isem tiegħek?
[Student] Lucas.
Reviżjoni 1. Okay.
Low huwa dak li aħna msejħa tibda qabel.
Up huwa pjuttost mhux dak li aħna imsejjaħ il-għan qabel.
Attwalment, l-aħħar issa hija fil-firxa. Huwa element għandna jikkunsidraw.
Allura baxx huwa 0, up huwa l-daqs tal-array - 1,
u issa aħna qed looping, u aħna verifika -
I raden inti tista 'timxi permezz tiegħu.
Liema kienet ħsieb tiegħek permezz ta 'dan? Walk lilna permezz ta 'kodiċi tiegħek.
[Student] Sure. Ħares lejn il-valur haystack fin-nofs u jqabbilha lil labra.
Mela jekk huwa ikbar minn labra tiegħek, allura inti tixtieq li - oh, fil-fatt, li għandu jkun lura.
Inti qed tmur jridu tarmi l-nofs tal-lemin, u hekk yeah, li għandu jkun il-mod.
[Bowden] Għalhekk dan għandu jkun inqas? Hija li dak li qal? >> [Student] Yeah.
[Bowden] Okay. Inqas.
Mela jekk dak li aħna qed tħares lejn huwa iżgħar minn dak li rridu,
allura yeah, irridu li tarmi l-nofs tax-xellug,
li jfisser aħna aġġornament kollox aħna qed jikkunsidraw
billi jiċċaqilqu baxx għad-dritt tal-firxa.
Dan jidher tajjeb.
Naħseb li għandu l-istess kwistjoni li għidna fuq dak preċedenti,
fejn jekk baxxa hija 0 u up huwa 1, imbagħad baxxa + up / 2 se jitwaqqaf l-istess ħaġa mill-ġdid.
>> U anki jekk dan mhux il-każ, hija għadha aktar effiċjenti għall-inqas
li biss tarmi l bogħod l-element aħna biss ħares lejn li nafu hija żbaljata.
Allura baxx + up / 2 + 1 - >> [student] Li għandu jkun il-mod ieħor.
[Bowden] Jew dan għandu jkun - 1 u l-ieħor għandu jkun + 1.
[Student] U għandu jkun hemm double ugwali sinjal. >> [Bowden] Yeah.
[Student] Yeah.
Okay.
U fl-aħħarnett, issa li għandna dan 1 + - 1 ħaġa,
huwa - jista 'ma jkunx - huwa dejjem possibbli għall baxx li tispiċċa bil-valur akbar minn up?
Naħseb li l-uniku mod li jista 'jiġri - Huwa possibbli? >> [Student] I do not know.
Iżda jekk jiġrilha maqtugħ u mbagħad gets minus li 1 u mbagħad - >> Yeah.
[Student] Ikun possibilment nikseb messed up.
Naħseb li għandu jkun tajjeb biss għax
biex din jispiċċaw aktar baxxi huma jkollhom tkun ugwali, naħseb.
Imma jekk huma ugwali, allura aħna ma għamlu l-linja filwaqt li tibda bil
u aħna biss kienu lura l-valur. So I think we qed tajba issa.
Avviż li anki jekk din il-problema ma tibqax rikursivi,
l-istess tip ta 'ideat japplika fejn nistgħu naraw kif dan daqshekk faċilment jippresta ruħu
għal soluzzjoni rikursivi mill-fatt li aħna qed biss aġġornament tal-indiċi fuq u aktar mill-ġdid,
aħna qed jagħmlu l-problema iżgħar, aħna qed jiffokaw fuq subsett ta 'l-array.
[Student] Jekk baxxa hija 0 u up huwa 1, dawn it-tnejn ikunu 0 + 1/2, li tmur għal 0,
u mbagħad wieħed ikun + 1, wieħed ikun - 1.
[Student] Fejn ninsabu verifika ugwaljanza?
Bħal jekk il-wieħed nofs huwa attwalment labra?
Aħna bħalissa ma tagħmel dan? Oh!
Jekk it's -
Iva. Ma nistgħux sempliċement jagħmel it-test stabbiliti hawnhekk għaliex ejja ngħidu l-nofs 1 -
[Student] Huwa fil-fatt simili ma tarmi l-bound.
Mela jekk inti tarmi l-illegat, inti għandek tiċċekkja l-ewwel jew kwalunkwe.
Ah. Yeah. >> [Student] Yeah.
Allura issa għandna tintrema l-waħda għandna attwalment ħares lejn,
li jfisser li għandna issa jeħtieġ li jkollhom ukoll
jekk (haystack [(Baxx + up) / 2] == labra), allura nistgħu jirritornaw veru.
U jekk nressaq ieħor jew biss jekk, dan ifisser litteralment l-istess ħaġa
għaliex dan kien lura veru.
So I ser jitqiegħdu inkella jekk, iżda ma jimpurtax.
>> Mela inkella jekk dan, inkella dan, u din hija ħaġa komuni nagħmel
fejn anki jekk huwa l-każ fejn kollox huwa tajjeb hawn,
bħal baxxi qatt ma jista 'jkun ikbar minn up, mhuwiex raġunament jiswew madwar jekk dan huwa veru.
Allura inti tista 'ukoll jgħidu filwaqt li huwa baxx inqas minn jew ugwali għal
jew waqt baxxa hija anqas minn
hekk jekk huma qatt ugwali jew baxxa jiġri biex jiġu rrinunzjati,
allura nistgħu break out ta 'dan loop.
Mistoqsijiet, tħassib, il-kummenti?
Okay. Dan jidher tajjeb.
Issa rridu nagħmlu tip.
Jekk immorru tieni reviżjoni tiegħi, naraw dawn in-numri l-istess,
iżda issa dawn m'għadhomx sabiex magħżula.
U aħna rridu li jimplimentaw it-tip tuża kwalunkwe algoritmu fil O n log n.
Allura liema algoritmu do you think we għandhom jimplimentaw hawn? >> [Student] sort Merge.
[Bowden] Yeah. Jingħaqdu tip huwa O (n log n), b'tali mod li dak li aħna qed tmur biex tagħmel.
U l-problema se tkun pjuttost simili,
fejn faċilment jippresta ruħu għal soluzzjoni rikursivi.
Nistgħu wkoll toħroġ bi soluzzjoni iterattiv jekk irridu,
iżda recursion se jkun aktar faċli hawn u għandna nagħmlu recursion.
I raden aħna se jimxu permezz sort jingħaqdu l-ewwel,
għalkemm hemm video sabiħ fuq tip jingħaqdu diġà. [Daħk]
Allura jingħaqdu sort hemm - I am ħela tant ta 'dan id-dokument.
Oh, hemm wieħed biss xellug.
Allura jingħaqdu.
Oh, 1, 3, 5.
Okay.
Jingħaqdu jieħu żewġ arrays separati.
Individwalment dawk arrays 2 huma t-tnejn magħżula.
Allura dan array, 1, 3, 5, magħżula. Dan firxa, 0, 2, 4, magħżula.
Issa dak jingħaqdu għandha tagħmel huwa jinġabru flimkien ġo firxa unika li huwa nnifsu magħżula.
Allura rridu firxa ta 'daqs 6 li huwa se jkollu dawn l-elementi ġewwa ta' dan
sabiex magħżula.
>> U hekk nistgħu nieħdu vantaġġ mill-fatt li dawn arrays 2 huma magħżula
biex jagħmlu dan fil-ħin lineari,
tifsira żmien lineari jekk dan array huwa x daqs u dan huwa y daqs,
allura l-algoritmu totali għandu jkun O (x + y). Okay.
Allura suġġerimenti.
[Student] Jista nibdew mix-xellug?
Allura inti ser tpoġġi l-isfel 0 ewwel u allura l-1 u allura hawnhekk int fil-2.
Allura huwa tip simili ikollok tab li l-mixja lejn il-lemin. >> [Bowden] Yeah.
Għal dawn iż-żewġ arrays jekk aħna biss jiffoka fuq l-element leftmost.
Minħabba ż-żewġ arrays huma magħżula, nafu li dawn l-elementi 2
huma l-elementi iżgħar fi kwalunkwe firxa.
Allura dan ifisser li 1 ta 'dawn l-elementi 2 għandha tkun l-element iżgħar firxa magħquda tagħna.
Huwa biss hekk jiġri li l-iżgħar huwa dak fuq il-lemin din id-darba.
Allura aħna jieħdu 0, daħħalha fuq ix-xellug minħabba 0 hija inqas minn 1,
sabiex jieħdu 0, daħħalha fil-pożizzjoni ewwel tagħna, u allura aħna taġġorna dan
li issa jiffokaw fuq l-ewwel element.
U issa aħna jirrepetu.
Allura issa nqabblu 2 u 1. 1 huwa iżgħar, hekk aħna ser daħħal 1.
Aħna taġġorna dan il-werrej għall-punt li dan Guy.
Issa nagħmlu dan mill-ġdid, hekk 2. Dan se taġġorna, iqabblu dawn 2, 3.
Din taġġorna, imbagħad 4 u 5.
Allura dan huwa jingħaqdu.
>> Għandu jkun pjuttost ovvju li huwa żmien lineari peress li aħna biss jmorru madwar kull element darba.
U li huwa l-pass akbar biex timplimenta tip jingħaqdu qed tagħmel dan.
U mhuwiex li diffiċli.
A affarijiet ftit li jinkwetaw dwar huwa ejja ngħidu aħna kienu qed jingħaqdu 1, 2, 3, 4, 5, 6.
F'dan il-każ aħna jispiċċaw fix-xenarju fejn dan wieħed se tkun iżgħar,
allura aħna aġġornament dan il-werrej, dan wieħed se tkun iżgħar, jaġġornaw dan,
dan wieħed iżgħar, u issa inti għandek jirrikonoxxu
meta inti ħadthom attwalment jispiċċaw ta 'elementi li tqabbel magħhom.
Peress li aħna diġà użaw dan array kollu,
kollox f'dan array issa huwa biss mdaħħla hawn.
Allura jekk aħna qatt run fis-punt fejn wieħed mill arrays tagħna huwa jagħqad kompletament diġà,
allura aħna biss jieħdu l-elementi tal-firxa l-oħra u daħħal minnhom fil-tmiem tal-firxa.
Allura nistgħu biss daħħal 4, 5, 6. Okay.
Din hija ħaġa waħda li toqgħod attent għalihom.
Implimentazzjoni li għandu jkun pass 1.
Jingħaqdu sort allura bbażata fuq dan, huwa 2 passi, 2 passi iblah.
Ejja biss jagħtu din array.
Allura jingħaqdu sort, pass 1 huwa li recursively jiksru l-firxa fil-nofsijiet.
Allura maqsuma din array in nofsijiet.
Issa għandna 4, 15, 16, 50 u 8, 23, 42, 108.
U issa aħna tagħmel dan mill-ġdid u aħna maqsuma dawn fis nofsijiet.
I biss ser tagħmel dan fuq din in-naħa.
Allura 4, 15 u 16, 50.
Aħna se nagħmlu l-istess ħaġa fuq hawn.
U issa aħna qasmitha fis nofsijiet mill-ġdid.
U aħna għandna 4, 15, 16, 50.
Allura dan huwa każ bażi tagħna.
Ladarba l-arrays huma ta 'daqs 1, allura aħna tieqaf mal-qsim fis nofsijiet.
>> Issa dak li nagħmlu ma 'dan?
Aħna jispiċċaw dan ukoll se jitqassmu 8, 23, 42, u 108.
Allura issa li aħna qed f'dan il-punt, issa pass tnejn tip jingħaqdu huwa biss jingħaqdu pari għal-listi.
Allura aħna rridu li jingħaqdu dawn. Aħna biss sejħa jingħaqdu.
Nafu jingħaqdu se terġa 'lura dawn fl-ordni magħżula.
4, 15.
Issa rridu li jingħaqdu dawn, u li se terġa 'lura lista ma' dawk sabiex magħżula,
16, 50.
Aħna jingħaqdu dawk - I ma tistax tikteb - 8, 23 u 42, 108.
Allura aħna għandna pari amalgamati darba.
Issa aħna biss jingħaqdu mill-ġdid.
Avviż li kull wieħed minn dawn il-listi huwa magħżul minnha nnifisha,
u allura nistgħu biss jingħaqdu dawn il-listi biex tikseb lista ta 'daqs 4 li huwa magħżul
u jingħaqdu dawn iż-żewġ listi li tikseb lista ta 'daqs 4 li huwa magħżul.
U fl-aħħarnett, nistgħu jingħaqdu dawn iż-żewġ listi ta 'daqs 4 li tikseb wieħed lista ta' daqs 8 li huwa magħżul.
Allura biex tara li dan huwa b'mod ġenerali n log n, aħna diġà raw li jingħaqdu huwa lineari,
hekk meta aħna qed jittrattaw ma 'li qed jingħaqdu dawn, hekk bħall-ispiża globali ta' inkorporazzjoni
għal dawn iż-żewġ listi huwa biss 2 minħabba -
Jew ukoll, huwa O ta 'n, iżda n hawnhekk hija biss dawn l-elementi 2, dan huwa 2.
U dawn 2 ser ikunu 2 u dawn 2 se jkunu 2 u dawn 2 se jkun 2,
hekk firxa kollha tas-tamalgama li għandna bżonn li tagħmel, aħna jispiċċaw jagħmlu n.
Bħal 2 + 2 + 2 + 2 huwa 8, li huwa n,
sabiex l-ispiża ta 'amalgamazzjoni f'dan is-sett huwa n.
U allura l-istess ħaġa hawn.
Aħna ser jingħaqdu dawn 2, allura dawn 2, u individwalment din l-inkorporazzjoni se jieħu erba 'operazzjonijiet,
din l-inkorporazzjoni se jieħu erba 'operazzjonijiet, iżda għal darb'oħra, bejn dawn kollha,
aħna jispiċċaw jingħaqdu n affarijiet totali, u għalhekk dan il-pass jieħu n.
U hekk kull livell jieħu elementi n jkunu magħquda.
>> U kif ħafna livelli huma hemmhekk?
F'kull livell, array tagħna tikber skond id-daqs 2.
Hawnhekk arrays tagħna huma ta 'daqs 1, hawn dawn qed ta' daqs 2, hawn dawn qed ta 'daqs 4,
u finalment, dawn qed ta 'daqs 8.
Allura peress li huwa irduppjar, hemm ser jkun hemm total ta 'log n ta' dawn il-livelli.
Allura ma log n-livelli, kull livell individwali tieħu n-operazzjonijiet kollha,
irridu jiksbu l-log n n algoritmu.
Mistoqsijiet?
Have nies li diġà għamlu progress fuq kif jiġi implimentat dan?
Huwa xi ħadd diġà tinsab fi stat fejn nista 'biss pull up kodiċi tagħhom?
I jistgħu jagħtuk minuta.
Dan wieħed se jkun itwal.
I jirrakkomanda ħafna jerġgħu jitfaċċaw -
Inti ma għandekx tagħmel recursion għall jingħaqdu
minħabba li jekk isir recursion għall jingħaqdu, int ser ikollhom jgħaddu minn mazz ta 'daqsijiet differenti.
Tista ', iżda huwa annoying.
Iżda recursion għal tip nnifisha hija pjuttost faċli.
Inti biss litteralment sejħa sort fuq nofs tax-xellug, sort fuq nofs tal-lemin. Okay.
Kull min ikollu xi ħaġa I tista 'pull up għadhom?
Jew inkella I ser jagħti minuta.
Okay.
Kull min ikollu xi ħaġa nistgħu naħdmu ma?
Jew inkella aħna ser biss xogħol ma 'dan u mbagħad jespandu minn hemm.
>> Kull min ikollu aktar minn dan li nista 'pull up?
[Student] Yeah. Inti tista 'pull up minjiera. >> Kull dritt.
Iva!
[Student] Kien hemm ħafna ta 'kondizzjonijiet. >> Oh, rimja. Tista inti -
[Student] Għandi biex isalvawh. >> Yeah.
Allura għamilna jagħmlu l-inkorporazzjoni separatament.
Oh, iżda mhux dik ħażina.
Okay.
Allura xorta huwa nnifsu biss sejħa mergeSortHelp.
Spjega lilna dak mergeSortHelp ma.
[Student] MergeSortHelp pretty ħafna ma l-passi żewġ prinċipali,
li huwa li sort kull nofs tal-firxa u mbagħad jingħaqdu tnejn minnhom.
[Bowden] Okay, so tagħti me a 2.
Naħseb li dan - >> [student] I bżonn -
Yeah. Jien xi ħaġa nieqsa.
Fil jingħaqdu, I jirrealizzaw li għandi bżonn li jinħoloq firxa ġdida
minħabba I ma setgħux jagħmlu dan fil-post. >> Iva. Inti ma tistax. Ikkoreġi.
[Student] So I joħolqu firxa ġdida.
I nesa fl-aħħar tal jingħaqdu biex terġa 'bidla.
Okay. Għandna bżonn firxa ġdida.
Fil-tip jingħaqdu, dan huwa kważi dejjem veru.
Parti mill-ispiża ta 'l-algoritmu aħjar ħin għaqli
huwa kważi dejjem jeħtieġu li jużaw memorja ftit aktar.
Allura hawn, ma jimpurtax kif inti tagħmel jingħaqdu sort,
inti inevitabbilment jeħtieġ li tuża xi memorja żejda.
Hu jew hi maħluqa firxa ġdida.
U allura inti tgħidli fl-aħħar aħna biss bżonn li kopja firxa ġdida fil-firxa oriġinali.
[Student] I think so, yeah.
I do not know jekk li jaħdem f'termini ta 'għadd b'referenza jew kwalunkwe -
Yeah, din se taħdem. >> [Student] Okay.
Ridt tipprova taħdem din? >> [Student] Nru, li għadha ma ġietx. Okay. >>
Ipprova running, u mbagħad I ser nitkellmu dwar dan għat-tieni.
[Student] I-ħtieġa li jkollhom l-prototipi funzjoni u kollox, għalkemm, id-dritt?
Il-prototipi funzjoni. Oh, inti tfisser simili - Iva.
Sort qed titlob mergeSortHelp.
>> Allura sabiex tip li jsejħu mergeSortHelp, mergeSortHelp għandu jew ġew definiti
qabel sort jew aħna biss bżonn il-prototip. Just kopja u paste dan.
U bl-istess mod, mergeSortHelp qed titlob jingħaqdu,
iżda jingħaqdu ma ġiex definit għadhom, hekk nistgħu biss let mergeSortHelp jafu
li dan huwa dak jingħaqdu se look like, u li li.
Allura mergeSortHelp.
Għandna kwistjoni hawnhekk fejn għandna l-ebda każ bażi.
MergeSortHelp huwa rikursivi, sabiex kwalunkwe rikursivi funzjoni
se jeħtieġu xi tip ta 'każ bażi li tkun taf meta tieqaf recursively ssejjaħ lilha nnifisha.
X'inhu każ bażi tagħna se tkun hawn? Yeah.
[Student] Jekk id-daqs huwa 1? >> [Bowden] Iva.
Allura bħal rajna hemm dritt, aħna waqfet arrays qsim
ladarba aħna ltqajna fis arrays ta 'daqs 1, li inevitabbilment huma magħżula infushom.
Mela jekk id-daqs huwa ugwali għal 1, nafu l-array huwa diġà magħżula,
hekk nistgħu biss ritorn.
>> Avviż li s null, hekk aħna ma jirritornawx xejn partikolari, aħna biss ritorn.
Okay. Allura dak il-każ bażi tagħna.
I raden każ bażiku tagħna tista 'wkoll tkun jekk aħna jiġri li jkun jingħaqdu firxa ta' daqs 0,
aħna probabbilment jixtiequ jieqfu f'xi punt,
hekk nistgħu biss jgħidu daqs inqas minn 2 jew inqas minn jew ugwali għal 1
sabiex din se taħdem għal kwalunkwe firxa issa.
Okay.
Allura dak il-każ bażi tagħna.
Issa tridu jimxu lilna permezz jingħaqdu?
What do kollha dawn il-każijiet jfisser?
Up hawn, aħna qed biss tagħmel l-istess idea, il -
[Student] I ħtieġa li tkun tgħaddi daqs ma 'l-sejħiet mergeSortHelp.
I miżjuda daqs bħala primarja addizzjonali u mhuwiex hemmhekk, bħal daqs / 2.
[Bowden] Oh, id-daqs / 2, id-daqs / 2. >> [Student] Yeah, u wkoll fil-funzjoni ta 'hawn fuq kif ukoll.
[Bowden] Here? >> [Student] Just daqs. >> [Bowden] Oh. Daqs? Daqs, >> [Student] Yeah.
[Bowden] Okay.
Let me think għat-tieni.
Do we run fi kwistjoni?
Aħna dejjem trattament fuq ix-xellug bħala 0. >> [Student] No
Dak ħażin wisq. Jiddispjacini. Għandu jkun bidu. Yeah.
[Bowden] Okay. I simili li aħjar.
U t-tmiem. Okay.
Allura issa inti tixtieq li jimxu lilna permezz jingħaqdu? >> [Student] Okay.
Jien biss mixi permezz ta 'dan firxa ġdida li stajt maħluqa.
Id-daqs tiegħu huwa d-daqs tal-porzjon ta 'l-array li aħna rridu li jiġu magħżula
u tipprova ssib l-element li għandi tpoġġi fil-pass firxa ġdida.
Allura biex tagħmel dan, l-ewwel jien iċċekkjar jekk l-nofs tax-xellug ta 'l-array għad għandha elementi kwalunkwe aktar,
u jekk ma jiġrix dan, allura inti jinżlu għal din il-kundizzjoni inkella, li sempliċiment jgħid
okay, dan għandu jkun fil-firxa dritt, u aħna ser tpoġġi li fl-indiċi attwali ta 'newArray.
>> U mbagħad mod ieħor, jien verifika jekk il-lemin tal-firxa hija wkoll lest,
f'liema każ I biss jitqiegħed fil-xellug.
Dan ma jista 'attwalment tkun meħtieġa. M'inix ċert.
Iżda xorta waħda, tnejn l-oħra verifika li l-tnejn huma iżgħar fid-xellug jew il-lemin.
U wkoll f'kull każ, jien inkrementazzjoni liema minnhom placeholder I inkrement.
[Bowden] Okay.
Li jidher tajjeb.
Ħadd ma jkollu kummenti jew tħassib jew mistoqsijiet?
Allura l-erba 'każijiet li għandna biex iġibu l-affarijiet fil biss qed - jew jidher qisu 5 -
iżda aħna għandna biex jikkunsidraw jekk il-firxa tax-xellug tkun jispiċċaw ta 'affarijiet li rridu li jingħaqdu,
jekk il-firxa dritt jispiċċaw ta 'affarijiet li rridu jingħaqdu -
Jien tipponta lejn xejn.
Allura jekk il-firxa tax-xellug tkun jispiċċaw ta 'affarijiet jew il-firxa dritt ikun jispiċċaw ta' affarijiet.
Dawn huma żewġ każijiet.
Għandna bżonn ukoll il-każ trivjali ta 'jekk il-ħaġa xellug huwa inqas mill-aħjar ħaġa.
Imbagħad irridu li jagħżlu l-ħaġa xellug.
Dawn huma l-każijiet.
Allura dan kien dritt, b'tali mod li li.
Array xellug. Huwa 1, 2, 3. Okay. So yeah, dawn huma l-affarijiet erba nistgħu trid tagħmel.
U aħna mhux se jmorru fuq iterattiv soluzzjoni.
I ma jirrakkomandaw -
Jingħaqdu tip huwa eżempju ta 'funzjoni li huwa kemm le denb rikursivi,
mhuwiex faċli li tagħmel dan denb rikursivi,
iżda wkoll mhuwiex faċli ħafna biex jagħmlu dan iterattiv.
Dan huwa faċli ħafna.
Din l-implimentazzjoni ta 'tip jingħaqdu,
jingħaqdu, l-ebda kwistjoni dak li inti tagħmel, int ser tibni jingħaqdu.
>> Allura jingħaqdu tip mibnija fuq quċċata ta 'inkorporazzjoni recursively huwa biss dawn il-linji tlieta.
Iteratively, huwa aktar tedjanti u aktar diffiċli biex jaħsbu.
Iżda avviż li din mhix denb rikursivi peress mergeSortHelp - meta jitlob huwa stess -
għad jeħtieġ li tagħmel affarijiet wara dan prospetti sejħa jirrikorri.
Allura dan il-qafas munzell għandhom jibqgħu eżistenti anki wara li ssejjaħ dan.
U allura meta inti sejħa dan, il-qafas munzell għandha tkompli teżisti
minħabba li, anki wara li sejħa, għad għandna bżonn li jingħaqdu.
U huwa nontrivial biex jagħmlu dan denb rikursivi.
Mistoqsijiet?
Kull dritt.
Allura jmorru lura biex issolvi - oh, hemm żewġ affarijiet nixtieq li juru. Okay.
Li jmorru lura sa sort, aħna ser tagħmel dan malajr.
. Tfittxija jew Sort? Sort. Yeah.
Tmur lura għall-bidu ta 'tip.
Aħna rridu li joħolqu algoritmu li xorta l-firxa jużaw kwalunkwe algoritmu
fil O ta 'n.
Allura kif dan huwa possibbli? Ħadd ma jkollu xi tip ta '-
I aċċennata qabel fi -
Jekk aħna qed madwar biex jitjieb minn n log n sa O ta 'ln,
aħna tejbu algoritmu tagħna ħin għaqli,
li jfisser dak li aħna se bżonn tagħmel biex tpatti għal dan?
[Student] Ispazju. >> Yeah. Aħna ser tkun qed tuża aktar spazju.
U lanqas biss aktar spazju, huwa spazju b'mod esponenzjali aktar.
Għalhekk naħseb dan it-tip ta 'algoritmu hija xi ħaġa psewdo, polynom psewdo -
psewdo - I ma tistax tiftakar. Psewdo xi ħaġa.
Iżda huwa għaliex għandna bżonn l-użu spazju tant
li dan jista 'jinkiseb iżda mhux realistiku.
>> U kif nistgħu jintlaħaq dan?
Aħna tista 'tikseb dan jekk aħna jiggarantixxu li kull element partikolari fil-firxa
huwa taħt ċertu daqs.
Mela ejja biss jgħidu li d-daqs huwa ta '200,
kwalunkwe element fil-firxa hija taħt id-daqs 200.
U dan huwa attwalment ħafna realistiku.
Tista 'faċilment jkollhom firxa li taf kollox fiha
se tkun anqas minn ċertu numru.
Bħal jekk ikollok xi vector assolutament massiva jew xi ħaġa
imma inti taf kollox se tkun bejn 0 u 5,
allura huwa għaddej biex tkun ħafna aktar mgħaġġla biex jagħmlu dan.
U l-marbuta fuq kwalunkwe mill-elementi huwa 5,
għalhekk dan marbuta, li hija kemm memorja int se tkun qed tuża.
Allura l-marbuta huwa 200.
Fit-teorija dejjem ikun hemm marbut peress integer tista 'biss tkun sa 4 biljun,
iżda li mhux realistiku minn dakinhar aħna'd tkun qed tuża l-ispazju
dwar l-ordni ta '4 biljun. Allura dak realistiku.
Imma hawn aħna ser ngħidu marbut tagħna huwa 200.
Il-trick li tagħmel dan fil-parti O ta 'n hija li nagħmlu ieħor array imsejħa għadd ta' daqs BOUND.
Allura fil-fatt, dan huwa shortcut għal - I attwalment do not know jekk clang ma dan.
Iżda fil GCC almenu - I'm clang jekk wieħed jassumi tagħmlu wisq -
dan se biss initialize-firxa sħiħa li jkun 0s.
Mela jekk jien ma tridx tagħmel dan, imbagħad I tista 'tagħmel separatament għal (i int = 0;
i <MARBUTIN; i + +) u għadd [i] = 0;
Allura issa kollox huwa initialized għal 0.
I jtenni fuq firxa tiegħi,
u dak li qed nagħmel huwa jien għadd tan-numru ta 'kull - Ejja jinżlu hawn.
Aħna 4, 15, 16, 50, 8, 23, 42, 108.
Dak li jien għadd huwa n-numru ta 'okkorrenzi ta' kull wieħed minn dawn l-elementi.
Ejja attwalment żid ftit aktar fil hawn ma 'xi jirrepeti.
Allura l-valur għandna hawnhekk, il-valur ta 'dik se tkun array [i].
Allura val jista 'jkun 4 jew 8 jew ikun x'ikun.
U issa jien għadd kemm ta 'dak il-valur stajt tidher,
hekk għadd [val] + +;
Wara dan isir, l-għadd huwa ser tfittex xi ħaġa bħal 0001.
Ejja nagħmlu jgħodd [val] - BOUND + 1.
>> Issa li jinsab biss li jagħtu kont għall-fatt li aħna qed jibdew minn 0.
Mela jekk 200 hija se tkun akbar numru tagħna,
imbagħad 0-200 huwa 201 affarijiet.
Għalhekk għadd, dan ser look like 00001 għaliex aħna għandna waħda 4.
Imbagħad aħna ser ikollhom 0001 fejn aħna ser ikollhom 1 fl-indiċi 8 ta 'għadd.
Aħna ser ikollhom 2 fl-indiċi 23 ta 'għadd.
Aħna ser ikollhom 2 fl-indiċi 42 ta 'għadd.
Allura nistgħu nużaw għadd.
Allura num_of_item = għadd [i].
U għalhekk jekk num_of_item huwa 2, li jfisser irridu li daħħal 2 ta 'l-għadd i
fis firxa magħżula tagħna.
Għalhekk għandna bżonn li jżommu rekord ta 'kemm aħna fil-firxa.
= Indiċi Allura 0.
Array - I taf biss tiktibha.
Counts -
array [indiċi + +] = i;
Hija li dak li nixtieq? Naħseb li dak li nixtieq.
Iva, dan jidher tajjeb. Okay.
Allura ma kulħadd jifhem dak li l-iskop ta 'firxa għadd tiegħi hu?
Huwa għadd tan-numru ta 'okkorrenzi ta' kull wieħed minn dawn in-numri.
Imbagħad I am iterazzjoni fuq dak array jgħodd,
u l-pożizzjoni ith fil-firxa għadd
huwa n-numru ta 'i i li għandhom jidhru fir firxa magħżula tiegħi.
C'est pourquoi għadd ta '4 se tkun 1
u l-għadd ta '8 se tkun l-1, l-għadd tat-23 se tkun 2.
Allura dak kemm minnhom nixtieq li daħħal fis firxa magħżula tiegħi.
Imbagħad I biss tagħmel dan.
I am ddaħħal num_of_item i s fis firxa magħżula tiegħi.
>> Mistoqsijiet?
U hekk darb'oħra, dan huwa żmien lineari peress li aħna huma biss iterazzjoni fuq dan darba,
imma hija wkoll lineari fil dak dan in-numru jiġri li jkun,
u għalhekk tiddependi ħafna fuq dak marbut tiegħek.
Bil marbuta ta '200, li mhux dik ħażina.
Jekk marbuta tiegħek se tkun 10,000, allura dak l-ftit agħar,
imma jekk marbuta tiegħek se jkun ta '4 biljun, li l-kompletament mhux realistiku
u dan array se jkollhom ikunu ta 'daqs 4 biljuni, li mhijiex realistika.
Allura dak li. Mistoqsijiet?
[Rispons istudent inaudible] >> Okay.
I realizzati ħaġa waħda oħra meta konna għaddejjin.
Naħseb li l-problema kienet fil-s Lucas u probabbilment kull wieħed Rajna.
I kompletament nesa.
L-unika ħaġa jien ridt li jikkummenta fuq hija li meta inti qed jittrattaw ma 'affarijiet bħal indiċijiet,
int qatt ma verament tara dan meta int bil-miktub ta 'għall-loop,
iżda teknikament, kull meta inti qed jittrattaw ma 'dawn l-indiċi
għandek pretty ħafna dejjem jittrattaw interi mhux iffirmat.
Ir-raġuni għal dan hija meta inti qed jittrattaw ma 'interi iffirmat,
hekk jekk ikollok 2 interi iffirmati u inti żid flimkien
u dawn jispiċċaw kbira wisq, allura inti tispiċċa ma 'numru negattiv.
Allura dak hu li jfur numru sħiħ huwa.
>> Jekk I żid 2 biljun u 1 biljun, I jispiċċaw ma negattiva 1 biljun.
Thats kif interi jaħdmu fuq il-kompjuters.
Allura l-problema bl-użu -
Dik il-multa ħlief jekk baxxa jiġri li jkun 2 biljun u sa jiġri li jkun 1 biljun,
allura dan se jkun negattiv 1 biljun u mbagħad aħna qed tmur biex jaqsmu dan bi 2
u tispiċċa bil negattiva 500 miljun.
Allura dan huwa biss kwistjoni jekk jiġri li tkun tiftix permezz ta 'firxa
ta 'biljuni ta' affarijiet.
Iżda jekk + baxxa sa jiġri li jfur, allura dak l-problema.
Hekk kif aħna jagħmluhom mhux iffirmat, allura 2000000000 flimkien ma '1 biljun 3 biljun.
3000000000 diviż bi 2 huwa 1.5 biljun.
Allura hekk kif dawn qed mhux iffirmat, kollox huwa perfett.
U hekk dan huwa wkoll kwistjoni meta int bil-miktub tiegħek għall-linji,
u fil-fatt, hija probabbilment ma dan awtomatikament.
Hija fil-fatt se biss Yell fi inti.
Allura jekk dan in-numru huwa kbir wisq biex tkun biss numru sħiħ iżda se tajbin fil integer mhux iffirmat,
se Yell fi inti, hekk hu għalhekk li inti qatt ma jinżel fit-kwistjoni.
Tista 'tara li l-indiċi jkun qatt ser tkun negattiva,
u hekk meta int iterazzjoni fuq firxa,
inti tista 'kważi dejjem ngħid mhux iffirmat int i, imma inti ma verament ikollhom.
Affarijiet huma ser jaħdmu pretty ħafna biss ukoll.
Okay. [Whispers] Liema ħin huwa?
L-aħħar ħaġa li ridt li juru - u jien ser biss tagħmel dan verament malajr.
Inti taf kif għandna # jiddefinixxu hekk nistgħu # tiddefinixxi MAX bħala 5 jew xi ħaġa?
Ejja ma tagħmel MAX. # Tiddefinixxi BOUND bħala 200. Dan huwa dak li għamilna qabel.
Dan jiddefinixxi kostanti, li huwa biss se jiġu kkupjati u pasted
fejn aħna jiġri li tikteb BOUND.
>> Allura aħna jistgħu attwalment jagħmlu aktar ma # jiddefinixxi.
Nistgħu # jiddefinixxi l-funzjonijiet.
Huma qed mhux verament funzjonijiet, imma aħna ser jsejħulhom funzjonijiet.
Ta 'eżempju tkun xi ħaġa bħal MAX (x, y) huwa definit bħala (x <y y:? X). Okay.
Allura inti għandek tikseb użati biex sintassi operatur tlett fibri,
iżda huwa x inqas minn y? Ritorn y, inkella ritorn x.
Allura tista 'tara inti tista' tagħmel din il-funzjoni separata,
u l-funzjoni tista 'tkun simili bool MAX tieħu 2 argumenti, jirritorna din.
Din hija waħda mill-aktar komuni nara jsir bħal dan. Aħna jsejħulhom macros.
Din hija makro.
Dan huwa biss l-sintassi għal dan.
Tista 'tikteb makro biex jagħmlu dak kollu li trid.
You spiss tara macros għal debugging printfs u l-għalf.
Allura tip ta 'printf, hemm kostanti speċjali C bħall jenfasizzaw LINE jenfasizzaw,
2 jenfasizza LINJA jenfasizzaw,
u hemm ukoll naħseb 2 jenfasizza funzjonijiet. Li jista 'jkun fiha. Xi ħaġa bħal dik.
Dawk l-affarijiet se jiġu sostitwiti bl-isem tal-funzjoni
jew in-numru tal-linja li int fuq.
Spiss, tikteb printfs debugging li stabbiliti hawn I jistgħu mbagħad biss tikteb
Debug u se jistampaw il-numru linja u l-funzjoni li I jiġri li jkun fil-
li ltaqgħu magħhom tali dikjarazzjoni debug.
U inti tista 'jistampa wkoll affarijiet oħra.
Allura wieħed ħaġa li għandek toqgħod attent għalihom hija jekk I jiġri li jiddefinixxu # DOUBLE_MAX
bħala xi ħaġa simili 2 * y u 2 * x.
Allura għal raġuni kwalunkwe, jiġri li tagħmel dan ħafna.
Sabiex tagħmel dan makro.
Dan huwa attwalment maqsuma.
I call dan billi tagħmel xi ħaġa simili DOUBLE_MAX (3, 6).
Allura dak li għandhom jingħataw lura?
[Student] 12.
Iva, 12 għandhom jiġu rritornati, u 12 huwa rritornat.
3 gets mibdula għal x, 6 gets mibdula għall y, u nerġgħu lura 2 * 6, li huwa 12.
Issa dak dwar dan? Liema għandhom jingħataw lura?
[Student] 14. >> Idealment, 14.
Il-kwistjoni hija li kif hash jiddefinixxi x-xogħol, ftakar huwa kopja u paste litterali
ta 'kollox pretty ħafna, hekk dak li dan ikun ser jiġi interpretat bħala li
huwa 3 inqas minn 1 flimkien 6, 2 darbiet 1 flimkien 6, 2 darbiet 3.
>> Allura għal din ir-raġuni inti kważi dejjem wrap kollox fil-parentesi.
Kwalunkwe varjabbli inti kważi dejjem wrap fil-parentesi.
Hemm każijiet fejn inti ma għandekx, bħal naf li jien ma bżonn tagħmel li hawn
minħabba inqas milli huwa pretty ħafna dejjem biss imur għax-xogħol,
għalkemm dan ma jista 'anke jkun veru.
Jekk ikun hemm xi ħaġa redikola simili DOUBLE_MAX (1 == 2),
allura li għaddej biex tikseb sostitwiti bi 3 anqas minn 1 huwa ugwali 2,
u hekk allura li għaddej biex tagħmel 3 anqas minn 1, ma li 2 indaqs,
li ma jkunx dak li rridu.
Allura biex jevitaw kwalunkwe problemi operatur preċedenza,
dejjem wrap fil-parentesi.
Okay. U li dan, 5:30.
Jekk għandek xi mistoqsijiet dwar il-pset, let us know.
Għandu jkun gost, u l-edizzjoni Hacker wkoll huwa ħafna aktar realistiku
mill-edizzjoni Hacker tas-sena li għaddiet, hekk aħna nittamaw li ħafna inti tipprova dan.
S-sena li għaddiet kien kbir ħafna.
>> [CS50.TV]