[Powered by Google Translate] [Seminaar: Tegnies Onderhoude] [Kenny Yu, Harvard Universiteit] [Hierdie is CS50.] [CS50.TV] Hi almal, Ek is Kenny. Ek is tans 'n junior bestudering van Rekenaarwetenskap. Ek is 'n voormalige CS TF, en ek wens ek het toe ek 'n underclassman, en dit is hoekom ek hierdie seminaar. So ek hoop jy geniet dit. Hierdie seminaar is oor die tegniese onderhoude, en al my hulpbronne kan gevind word by hierdie skakel, hierdie skakel reg hier, 'n paar van hulpbronne. So ek het 'n lys van probleme, eintlik 'n hele paar probleme. Ook 'n algemene hulpbronne bladsy waar ons kan kry wenke oor hoe om voor te berei vir 'n onderhoud, wenke oor wat jy moet doen tydens 'n werklike onderhoud, asook hoe om probleme en hulpbronne vir toekomstige verwysing te benader. Dit is al online. En net hierdie seminaar, 'n disclaimer voorwoord, soos dit behoort nie - jou onderhoud voorbereiding moet nie beperk word tot die lys. Dit is slegs bedoel om 'n gids te wees, en dan moet jy seker alles wat ek sê met 'n korrel sout, maar ook alles wat ek gebruik om jou te help in jou onderhoud voorbereiding gebruik. 

Ek gaan om te versnel deur die volgende paar skyfies sodat ons kan kry om die werklike gevallestudies. Die struktuur van 'n onderhoud vir 'n sagteware-ingenieurswese posisie, dit is tipies 30 tot 45 minute, verskeie rondes, afhangende van die maatskappy. Dikwels sal jy kodering word op 'n wit bord. So 'n wit bord soos hierdie, maar dikwels op 'n kleiner skaal. As jy 'n telefoon-onderhoud, sal jy waarskynlik gebruik word om óf collabedit of 'n Google Doc sodat hulle kan sien jy leef kodering terwyl jy 'n onderhoud oor die telefoon. 'N onderhoud self is gewoonlik 2 of 3 probleme toets jou rekenaar wetenskaplike kennis. En dit sal byna beslis betrek kodering. Die tipe vrae wat jy sien is gewoonlik datastrukture en algoritmes. En in die doen van hierdie soort probleme, sal hulle jou vra, wil, wat is die tyd en ruimte kompleksiteit, groot O? Dikwels is hulle ook hoër-vlak vrae vra, so, die ontwerp van 'n stelsel, hoe sou jy jou kode uit te lê? Watter interfaces, wat klasse, wat modules het jy in jou stelsel, en hoe hierdie interaksie saam? So datastrukture en algoritmes sowel as die ontwerp stelsels. 

N paar algemene wenke voor ons duik in ons gevallestudies. Ek dink die belangrikste reël altyd dink hardop. Die onderhoud is veronderstel om jou kans om te wys af jou denke proses. Die punt van die onderhoud is vir die onderhoudvoerder te meet hoe jy dink en hoe jy gaan deur middel van 'n probleem. Die ergste ding wat jy kan doen, is om stil te bly oor die hele onderhoud. Dit is net nie goed. As jy 'n vraag gegee word, jy wil ook om seker te maak jy verstaan ​​die vraag. So herhaal die vraag terug in jou eie woorde en poging om deeglike 'n paar eenvoudige toets gevalle te werk om seker te maak jy verstaan ​​die vraag. Werk deur middel van 'n paar toets-gevalle sal ook vir jou 'n intuïsie oor hoe om hierdie probleem op te los. Jy kan selfs 'n paar patrone ontdek om jou te help om die probleem op te los. Hul groot tip is om geen gefrustreerd. Moet nie gefrustreerd. Onderhoude is uitdagend, maar die ergste ding wat jy kan doen, Bykomend tot die stil, sigbaar gefrustreerd is om te word. Jy wil nie die indruk te gee aan 'n onderhoudvoerder. Een ding wat jy - so, baie mense, wanneer hulle in 'n onderhoud, hulle probeer om te probeer om die beste oplossing te vind, wanneer regtig, daar is gewoonlik 'n paal bo water oplossing. Dit mag stadig wees, kan dit ondoeltreffend, maar jy moet net noem dit, net sodat jy het 'n beginpunt om 'n beter werk. Ook daarop te wys die oplossing is stadig, in terme van Big O kompleksiteit of ruimte kompleksiteit, sal demonstreer aan die onderhoudvoerder dat jy verstaan hierdie kwessies wanneer jou kode skryf. So moenie bang wees nie om te kom met die eenvoudigste algoritme 1 en dan beter werk van daar af. Enige vrae tot dusver? Okay. 

So laat ons duik in ons eerste probleem. "Gegewe 'n verskeidenheid van n heelgetalle, skryf 'n funksie wat die skikking skud in die plek van so 'n aard dat alle permutasies van n heelgetalle ewe waarskynlik is. " En aanvaar wat jy beskikbaar het 'n ewekansige heelgetal generator wat verwek 'n heelgetal in 'n reeks van 0 tot i, 1/2 reeks. Verstaan ​​almal hierdie vraag? Ek gee jou 'n verskeidenheid van n heelgetalle, en ek wil hê jy moet shuffle dit. In my gids, het ek 'n paar programme om te demonstreer wat ek bedoel. Ek gaan om 'n skikking van 20 elemente te shuffle, van -10 tot 9, en ek wil hê dat jy 'n lys soos hierdie tot uitvoer. So dit is my gesorteer insette array, en ek wil hê jy moet shuffle dit. Ons sal dit weer doen. Nie almal verstaan ​​die vraag? Okay. So dit is aan jou. Wat is 'n paar idees? Kan jy dit doen as n ^ 2, n log N, N? Oop vir voorstelle. Okay. So 'n idee, voorgestel deur Emmy, is eers bereken 'n ewekansige getal, ewekansige heelgetal is, in 'n reeks van 0 tot 20. So aanvaar ons verskeidenheid het 'n lengte van 20. In ons diagram van 20 elemente, Dit is ons insette skikking. En nou, haar voorstel is om 'n nuwe skikking te skep, so dit sal die uitset skikking wees. En gebaseer op die i teruggekeer deur rand - So as ek was, kom ons sê, 17, Kopieer die 17de element in die eerste posisie. Nou het ons nodig het om te verwyder - ons moet al die elemente om hier te skuif oor so dat ons 'n gaping aan die einde en geen gate in die middel. En nou is ons herhaal die proses. Nou is ons kies 'n nuwe ewekansige heelgetal tussen 0 en 19. Ons het 'n nuwe ek hier, en ons kopie van hierdie element in hierdie posisie. Dan sal ons skuif items oor en ons herhaal die proses totdat ons het ons volle nuwe skikking. Wat is die aanloop tyd van hierdie algoritme? Wel, laat ons kyk na die impak van hierdie. Ons is die verskuiwing van elke element. Wanneer ons dit Ek, ons skuif al die elemente na aan die linkerkant. En dit is 'n O (n)-koste want wat as ons die eerste element verwyder? Dus, vir elke verwydering, verwyder ons - elke verwydering aangegaan 'n O (n) werking, en aangesien ons het N verskuiwings, dit lei tot 'n O (n ^ 2) shuffle. Okay. So goed begin. N goeie begin. 

Nog 'n voorstel is iets wat bekend staan ​​as die Knuth shuffle te gebruik, of die Fisher-Yates shuffle. En dit is eintlik 'n lineêre tyd shuffle. En die idee is baie soortgelyk. Weereens, ons het ons insette skikking, maar in plaas van die gebruik van twee skikkings vir ons input / output, ons die eerste gedeelte van die skikking gebruik om tred te hou van ons skuifel gedeelte, en ons hou, en dan laat ons die res van ons verskeidenheid vir die unshuffled gedeelte. So hier is wat ek bedoel. Ons begin met ons kies 'n i, 'n verskeidenheid 0-20. Ons huidige wyser wys na die eerste indeks. Ons kies 'n paar ek hier en nou is ons ruil. So as dit was 5 en dit was 4, die gevolglike skikking 5 here en 4 hier. En nou het ons kennis neem van 'n merker hier. Alles aan die linkerkant is skuifel, en alles wat aan die regterkant is unshuffled. En nou kan ons herhaal die proses. Ons kies 'n ewekansige indeks tussen 1 en 20 nou. So veronderstel ons nuwe ek hier is. Nou ruil ons hierdie i met ons huidige nuwe posisie. Sodat ons 'n uitruiling heen en weer soos hierdie. Laat my bring die kode om dit meer konkreet te maak. Ons begin met ons keuse van i - ons begin met i gelyk aan 0, ons kies 'n ewekansige plek j in die unshuffled gedeelte van die skikking, i n-1. So as ek hier is, kies 'n ewekansige indeks tussen hier en die res van die skikking, en ons ruil. Dit is al die kode wat nodig is om shuffle jou skikking. Enige vrae? 

Wel, een nodig vraag is hoekom, is dit korrek? Hoekom is elke permutasie ewe waarskynlik is? En Ek sal nie gaan nie deur die bewys van hierdie, maar baie probleme in die rekenaar wetenskap bewys kan word deur middel van induksie. Hoeveel van julle is vertroud met induksie? Okay. Cool. Sodat jy kan die korrektheid van hierdie algoritme deur eenvoudige induksie bewys, waar jou induksie hipotese sou wees, aanvaar dat my shuffle terug elke permutasie ewe waarskynlik tot die eerste i-elemente. Nou, oorweeg i + 1. En deur die manier waarop ons kies om ons indeks j te ruil, dit lei tot - en dan moet jy die besonderhede uit te werk, ten minste 'n volle bewys van waarom hierdie algoritme terugkeer elke permutasie met ewe waarskynlike waarskynlikheid. 

Alle reg, volgende probleem. So "'n skikking van heelgetalle, positief, nul, negatiewe, Skryf 'n funksie wat die maksimum bedrag bereken van enige continueous subarray van die inset-skikking. " 'N voorbeeld hier is, in die geval waar al die syfers is positief, dan is tans die beste keuse is om die hele skikking te neem. 1, 2, 3, 4, is gelyk aan 10. As jy het 'n paar negatiewe daar, in hierdie geval wil ons net die eerste twee want -1 en / of -3 te kies sal ons som bring. Soms het ons kan hê om te begin in die middel van die skikking. Soms wil ons niks te kies, dit is die beste om nie enigiets. En soms is dit beter om die val te neem, omdat die saak nadat dit is super groot. So enige idees? (Student, onverstaanbare) >> Ja. Gestel ek nie -1 nie. Ek kies dan óf 1.000 en 20.000, of ek het net die 3 miljard kies. Wel, die beste keuse is om al die nommers te neem. Dit -1, ten spyte van die negatiewe, die hele bedrag is beter as ek nie -1 te neem. So een van die punte wat ek vroeër genoem was die duidelik voor die hand liggend te stel en die brute krag oplossing eerste. Wat is die brute krag oplossing in hierdie probleem? Ja? [Jane] Wel, ek dink die brute krag oplossing sou wees om toe te voeg tot al die moontlike kombinasies (onverstaanbaar). [Yu] Goed. So Jane se idee is om elke moontlike te neem - Ek is parafrasering - is elke moontlike deurlopende subarray te neem, bereken die som, en dan neem om die maksimum van al die moontlike deurlopende subarrays. Wat as unieke identifikasie van 'n subarray in my insette array? Soos, watter twee dinge het ek nodig? Ja? (Student, onverstaanbare) >> Reg. 'N ondergrens op die indeks en 'n bogrens-indeks unieke bepaal 'n deurlopende subarray. [Vroulik student] Is ons beraming dit is 'n verskeidenheid van unieke nommers? [Yu] No So haar vraag is, is ons die aanvaarding van ons verskeidenheid - is ons verskeidenheid unieke nommers, en die antwoord is nee. 

As ons ons brute krag oplossing, dan is die begin / einde indekse gebruik unieke bepaal ons deurlopende subarray. So as ons itereer vir alle moontlike begin inskrywings, en vir al die einde inskrywings> of = om te begin, en <n jy bereken die som, en dan moet ons neem om die maksimum bedrag wat ons tot dusver gesien het. Is dit duidelik? Wat is die groot O van hierdie oplossing? Kwa tyd. Nie heeltemal n ^ 2. Let daarop dat ons van 0 tot n itereer so dit is een lus. Ons het weer itereer van byna die begin tot die einde, 'n ander vir die lus. En nou, binne daardie, ons het elke inskrywing op te som, so dit is 'n ander loop. So het ons drie geneste vir loops, n ^ 3. Okay. Dit gaan as 'n beginpunt. Ons oplossing is nie erger as n ^ 3. Verstaan ​​almal die brute krag oplossing? 

Okay. 'N beter oplossing is met behulp van 'n idee met die naam van dinamiese programmering. As jy 'CS124, wat algoritmes en datastrukture, sal jy baie vertroud is met hierdie tegniek. En die idee is, probeer om die opbou oplossings vir kleiner probleme vir die eerste keer. Wat ek bedoel is, het ons tans hoef te bekommer oor twee dinge: begin en die einde. En dit is vervelend. Wat gebeur as ons kan ontslae te raak van een van daardie parameters? Een idee is om - we're ons oorspronklike probleem, vind die maksimum bedrag van enige subarray in 'n reeks [O, n-1]. En nou het ons 'n nuwe subproblem, waar ons weet, in ons huidige indeks i ons weet dat ons daar moet sluit. Ons subarray moet 'n einde aan die huidige indeks. So die oorblywende probleem is, waar moet ons begin ons subarray? Maak dit sin? Okay. So ek het gekodeer hierdie up, en laat ons kyk na wat dit beteken. In die codirectory, daar is 'n program met die naam subarray, en dit neem die aantal items, en dit gee die maksimale subarray som in my skuifel lys. Dus, in hierdie geval, ons maksimale subarray 3. En dit is geneem deur net met 2 en 1. Kom ons loop dit weer. Dit is ook 3. Maar hierdie keer, let op hoe ons het die 3. Ons het die - ons het net die 3 self want dit is aan beide kante omring deur negatiewe, wat sal 'n som te bring <3. Kom ons loop op 10 items. Hierdie keer is dit 7, neem ons die voorste 3 en 4. Hierdie keer is dit 8, en kry ons dat deur die neem van 1, 3 en 4. Te gee jy 'n intuïsie oor hoe ons kan hierdie getransformeerde probleem op te los, Kom ons neem 'n blik op hierdie subarray. Ons is hierdie insette array, en ons weet die antwoord is 8. Ons neem die 1, 4, en 3. Maar laat ons kyk na hoe ons eintlik die antwoord gekry het. Kom ons kyk na die maksimum subarray wat by elk van hierdie indekse geëindig. Wat is die maksimum subarray wat by die eerste posisie aan die einde? [Studente] Zero. >> Zero. Net nie die -5. Hier is dit gaan wees 0 sowel. Ja? (Student, onverstaanbaar) [Yu] O, jammer, dit is 'n -3. So, dit is 'n 2, dit is 'n -3. Okay. So -4, wat is die maksimum subarray daardie posisie aan die einde waar -4 is? Zero. Een? 1, 5, 8. Nou moet ek uiteindelik by die plek waar -2 is by. So 6, 5, 7, en die laaste een is 4. Die wete dat dit is my inskrywings vir die getransformeerde probleem waar ek moet eindig by elk van hierdie indekse, dan is my finale antwoord net, neem 'n sweep oor en neem die maksimum aantal. So in hierdie geval is dit 8. Dit impliseer dat die maksimale subarray eindig by hierdie indeks, en begin iewers voor dit. Verstaan ​​almal hierdie getransformeerde subarray? 

Okay. Wel, laat ons uit te vind die herhaling hiervoor. Kom ons kyk na net die eerste paar inskrywings. So hier is dit was 0, 0, 0, 1, 5, 8. En dan was daar 'n -2 hier, en wat dit tot 6. So as ek noem die inskrywing by posisie i subproblem (i), hoe kan ek gebruik om die antwoord op 'n vorige subproblem om hierdie subproblem te beantwoord? As ek kyk na die, kom ons sê, hierdie item. Hoe kan ek bereken deur te kyk na die antwoord 6 'n kombinasie van die skikking en die antwoorde op vorige subprobleme in hierdie skikking? Ja? [Vroulik student] Jy neem die skikking van somme in die posisie reg voor dit, so die 8, en dan moet jy voeg die huidige subproblem. [Yu] haar voorstel is dus om te kyk na hierdie twee getalle, hierdie nommer en hierdie getal. So, dit 8 verwys na die antwoord vir die subproblem (i - 1). En laat ons bel my insette array A. Ten einde 'n maksimale subarray wat eindig by posisie i te vind, Ek het twee keuses: Ek kan voortgaan om die subarray wat geëindig het op die vorige indeks, of begin 'n nuwe skikking. As ek was die subarray wat begin het by die vorige indeks om voort te gaan, dan is die maksimum bedrag wat ek kan bereik, is die antwoord op die vorige subproblem plus die huidige verskeidenheid inskrywing. , Maar ek het ook die keuse van die begin van 'n nuwe subarray, in welke geval die bedrag is 0. So die antwoord is maksimum van 0, subproblem i - 1, plus die huidige verskeidenheid inskrywing. Is hierdie herhaling sin maak? Ons herhaling, as ons net ontdek, is subproblem i is gelyk aan die maksimum van die vorige subproblem plus my huidige skikking inskrywing, wat beteken voortgaan die vorige subarray, of 0, begin 'n nuwe subarray by my huidige indeks. En sodra ons opgebou hierdie tabel van oplossings, dan is ons finale antwoord, doen net 'n lineêre sweep oor die subproblem skikking en neem die maksimum aantal. Dit is 'n presiese uitvoering van wat ek nou net gesê. So skep ons 'n nuwe subproblem skikking, subprobleme. Die eerste inskrywing is óf 0 of die eerste inskrywing, die maksimum van die twee. En vir die res van die subprobleme ons gebruik die presiese herhaling wat ons net ontdek. Nou het ons bereken die maksimum van ons subprobleme verskeidenheid, en dit is ons finale antwoord. 

So hoeveel ruimte gebruik ons ​​in hierdie algoritme? As jy net CS50 geneem word, dan is jy dalk nie bespreek het ruimte baie. Wel, een ding om op te let is dat ek hier genoem malloc met die grootte n. Wat beteken dat raai u aan? Hierdie algoritme gebruik lineêre ruimte. Kan ons beter doen? Is daar enigiets wat jy sien dat dit onnodig om die finale antwoord te bereken? Ek dink 'n beter vraag is, watter inligting hoef ons nie al die pad deur te voer aan die einde? Nou, as ons kyk na hierdie twee lyne, ons net oor die vorige subproblem, en ons het net sorg oor die maksimum wat ons nog ooit gesien het so ver. Ons finale antwoord te bereken, het ons nie nodig om die hele skikking. Ons moet net die laaste nommer, die laaste twee getalle. Laaste nommer vir die subproblem array, en die laaste nommer vir die maksimum. Dus, in werklikheid, kan ons versmelt hierdie loops saam en gaan van lineêre ruimte konstante ruimte. Huidige som tot dusver hier, vervang die rol van subproblem, ons subproblem verskeidenheid. So huidige som, tot dusver, is die antwoord op die vorige subproblem. En daardie som, so ver, neem die plek van ons max. Ons bereken die maksimum as ons gaan saam. En so gaan ons van lineêre ruimte konstante ruimte, en ons het ook 'n lineêre oplossing vir ons subarray probleem. 

Hierdie soort vrae wat jy sal kry tydens 'n onderhoud. Wat is die tyd kompleksiteit, wat is die ruimte kompleksiteit? Kan jy beter doen? Is daar dinge wat onnodig te hou rond? Ek het hierdie ontleding na vore te bring, dat jy op jou eie moet neem as jy werk deur middel van hierdie probleme. Altyd vra jouself, "Kan ek beter doen?" In feite, kan ons beter doen as dit? Soort van 'n truuk vraag. Jy kan nie, want jy moet ten minste die inset vir die probleem te lees. En die feit dat jy nodig het om te lees ten minste die inset vir die probleem beteken dat jy nie beter kan doen as lineêre tyd, en jy kan dit nie doen beter as konstante ruimte. So, dit is, in werklikheid, die beste oplossing vir hierdie probleem. Vrae? Okay. 

Aandelemark probleem: "Gegewe 'n verskeidenheid van n heelgetalle, positiewe, nul of negatief, wat die prys van 'n voorraad oor n dae, Skryf 'n funksie om die maksimum wins te bereken wat jy kan maak gegee dat jy presies 1 voorraad te koop en te verkoop binne hierdie N dae. " Wese, ons wil koop laag, verkoop hoog. En ons wil om uit te vind die beste wins wat ons kan maak. Terug te gaan na my punt, wat is die onmiddellik duidelik, die eenvoudigste antwoord, maar dit is stadig? Ja? (Student, onverstaanbare) >> Ja. >> So jy wil net al gaan kyk na die voorraad pryse by elke punt in tyd, (onverstaanbaar). [Yu] Okay, so haar oplossing - haar voorstel van die rekenaar die laagste en die berekening van die hoogste nie noodwendig werk want die hoogste mag voorkom voor die laagste. So, wat is die brute krag oplossing vir hierdie probleem? Wat is die twee dinge wat ek nodig het om 'n unieke bepaal die wins wat ek maak? Reg. Die brute krag oplossing is - oh, so, George se voorstel is dat ons moet net twee dae unieke bepaal die wins van die twee dae. Dus bereken ons elke paar, wil koop / verkoop, bereken die wins, wat negatief of positief of nul kan wees. Bereken die maksimum wins wat ons maak na die iterating oor alle pare van dae. Dit sal ons finale antwoord wees. En dat die oplossing sal wees O (n ^ 2), want daar is 'n kies twee pare - dae wat jy kan kies tussen die einde dae. Okay, so ek is nie gaan om te gaan oor die brute krag oplossing hier. Ek gaan jou te vertel dat daar is 'n log n oplossing. Wat algoritme jy tans weet wat 'n log n? Dit is nie 'n truuk vraag. 

Merge soort. Merge soort is n log n, en in die feit, een manier om hierdie probleem op te los, is om te gebruik 'n merge soort soort van die idee genoem, in die algemeen, te verdeel en oorwin. En die idee is soos volg. Jy wil die beste koop te bereken / paar verkoop in die linker helfte. Vind die beste wins wat jy kan maak, net met die eerste n oor twee dae. Dan is jy die beste koop oompute / paar verkoop op die regter helfte, sodat die laaste n oor twee dae. En nou is die vraag, hoe saamsmelt ons hierdie oplossings terug saam? Ja? (Student, onverstaanbaar) >> Goed. So laat my 'n prentjie teken. Ja? (George, onverstaanbaar) >> Presies. George se oplossing is presies reg. So het sy voorstel is, in die eerste bereken die beste koop / verkoop denim, en wat plaasvind in die linker helfte, so laat ons noem dat die links, links. Beste koop / verkoop paar wat plaasvind in die regte helfte. Maar as ons net hierdie twee getalle in vergelyking, mis ons die geval waar ons hier iewers in die regte helfte koop en verkoop. Ons koop, verkoop in die linker helfte in die regte helfte. En die beste manier om die beste koop / verkoop paar wat strek oor beide helftes te bereken is die minimum om hier te bereken en bereken die maksimum hier en neem hulle verskil. Sodat die twee gevalle waar die koop / verkoop-paar kom net hier, net hier, of op beide helftes word gedefinieer deur hierdie drie getalle. Sodat ons algoritme ons oplossings vir terug saamsmelt, ons wil die beste koop / verkoop paar te bereken waar ons koop op die linker helfte en verkoop op die regter helfte. En die beste manier om dit te doen, is die laagste prys in die eerste helfte te bereken, die hoogste prys in die regte helfte, en hulle verskil. Die gevolglike drie winste, hierdie drie getalle, neem jy die maksimum van die drie, en dit is die beste wins wat jy kan maak oor hierdie eerste en end dae. Hier is die belangrike lyne is in die rooi. Dit is 'n rekursiewe oproep om die antwoord te bereken in die linker helfte. Dit is 'n rekursiewe oproep om die antwoord te bereken in die regte helfte. Hierdie twee vir loops bereken die min en die maksimum op die linker-en regter helfte, onderskeidelik. Nou het ek bereken die wins wat oor beide helftes, en die finale antwoord is die maksimum van hierdie drie. Okay. 

So, seker nie, ons het 'n algoritme, maar die groter vraag is, wat is die kompleksiteit van hierdie? En die rede waarom ek genoem merge soort is dat hierdie vorm van die antwoord verdeel in twee en dan die samesmelting van ons oplossings weer saam is presies die vorm van merge soort. So laat my gaan deur die duur. As ons 'n funksie gedefinieer t (n) die aantal stappe vir n dae, ons twee rekursiewe oproepe word elk gaan t (n / 2) kos, en daar is twee van hierdie oproepe. Nou moet ek die minimum van die linker helfte te bereken, wat ek kan doen in 'n / 2 tyd, plus die maksimum van die regter helfte. So dit is net n. En toe plus 'n konstante werk. En hierdie herhaling vergelyking is presies die herhaling vergelyking vir merge soort. En ons almal weet dat merge soort is n log n tyd. Daarom word ook ons ​​algoritme n log n tyd. Is hierdie iterasie sin maak? Net 'n kort herhaling van hierdie: T (n) is die aantal stappe om die maksimum wins te bereken oor die loop van n dae. Die manier waarop ons ons rekursiewe oproepe verdeel is deur die roeping van ons oplossing op die eerste n / 2 dae, so dit is 'n oproep, en dan noem ons weer op die tweede helfte. So dit is twee oproepe. En dan vind ons 'n minimum op die linker helfte, wat ons kan doen in lineêre tyd, die maksimum van die regter helfte, wat ons kan doen in lineêre tyd. So n / 2 + n / 2 is net n. Dan het ons 'n konstante werk, wat is soos die doen van rekenkunde. Hierdie herhaling vergelyking is presies die herhaling vergelyking vir merge soort. Dus, ons shuffle algoritme is ook 'n teken n. So hoeveel ruimte gebruik ons? Kom ons gaan terug na die kode. 

'N beter vraag is, hoeveel stapel rame wat ons ooit op enige gegewe oomblik? Aangesien ons met behulp van rekursie, die aantal van stapel rame bepaal ons ruimte gebruik. Kom ons kyk na n = 8. Ons doen 'n beroep shuffle op 8, wat shuffle sal 'n beroep op die eerste vier inskrywings, wat 'n shuffle op die eerste twee inskrywings sal roep. So ons stapel is - dit is ons stapel. En dan noem ons shuffle weer op 1, en dit is wat ons basis geval is, sodat ons onmiddellik terugkeer. Het ons ooit meer as dit baie stapel rame? No. Want elke keer wanneer ons 'n aanroeping, 'n rekursiewe aanroeping te skuif, deel ons ons grootte in die helfte. So het die maksimum aantal van stapel rame ons ooit sal hê op enige gegewe oomblik is op die einde van die log n stapel rame. Elke stapel raam het konstant ruimte, en daarom is die totale bedrag van die ruimte, die maksimum bedrag van die ruimte wat ons ooit gebruik is O (log n) ruimte waar n die aantal dae. 

Nou, altyd vra jouself, "Kan ons beter doen?" En in die besonder, kan ons verminder dit na 'n probleem wat ons het reeds opgelos? 'N wenk: ons net twee ander probleme bespreek voor dit, en dit is nie van plan om shuffle. Ons kan hierdie aandelemark probleem omskep in die maksimum subarray probleem. Hoe kan ons dit doen? Een van julle? Emmy? (Emmy, onverstaanbaar) [Yu] Presies. So die maksimum subarray probleem, ons is op soek vir 'n bedrag oor 'n deurlopende subarray. En Emmy se voorstel vir die voorraad probleem, Oorweeg die veranderinge, of die deltas. En 'n foto van hierdie is - dit is die prys van 'n voorraad, maar as ons het die verskil tussen elke opeenvolgende dag - So sien ons dat die maksimum prys maksimum wins kan maak is as ons hier koop en verkoop hier. Maar laat ons kyk na die voortdurende laat ons kyk by die subarray probleem. So hier is, kan ons gaan van hier tot hier, ons het 'n positiewe verandering, en dan gaan van hier tot hier het ons 'n negatiewe verandering. Maar dan gaan van hier tot hier het ons 'n groot positiewe verandering. En dit is die veranderinge wat ons wil op te som ons finale wins te kry. Dan het ons meer negatiewe veranderinge hier. Die sleutel tot die vermindering van ons voorraad probleem in ons maksimale subarray probleem is die deltas tussen dae te oorweeg. So skep ons 'n nuwe skikking met die naam deltas, inisialiseer die eerste toegang tot 0, en dan vir elke delta (i), wat die verskil wees van my insette array (i), en skikking (i - 1). Dan noem ons ons roetine prosedure vir 'n maksimale subarray wat in 'n delta se verskeidenheid. En omdat maksimale subarray is lineêr tyd, en hierdie vermindering, die proses van die skep van hierdie delta skikking, is ook 'n lineêre tyd, dan die finale oplossing vir die lêers is O (n) werk plus O (n) werk, is nog steeds O (n) werk. So ons het 'n lineêre tyd oplossing vir ons probleem. Verstaan ​​almal hierdie transformasie? 

In die algemeen, 'n goeie idee dat jy altyd moet is probeer om 'n nuwe probleem wat jy sien te verminder. As dit lyk bekend aan 'n ou probleem, probeer die vermindering van dit aan 'n ou probleem. En as jy kan gebruik maak van al die gereedskap wat jy gebruik het op die ou probleem die nuwe probleem op te los. So te draai, tegniese onderhoude uitdagend. Hierdie probleme is waarskynlik 'n paar van die meer moeilike probleme wat jy kan sien in 'n onderhoud, so as jy nie al die probleme wat ek net gedek verstaan, dis oukei. Dit is 'n paar van die meer uitdagende probleme. Oefen, oefen, oefen. Ek het 'n baie van die probleme in die opdragstuk, so beslis gaan diegene wat nie. En baie geluk op jou onderhoude. Al my hulpbronne gepos word by hierdie skakel, en een van my senior vriende het aangebied om spot tegniese onderhoude te doen, so as jy belangstel, e-pos sal Yao op daardie e-pos adres. As jy het 'n paar vrae, kan jy my vra. Moenie julle het spesifieke vrae wat verband hou met tegniese onderhoude of enige probleme wat ons tot dusver gesien het? Okay. Wel, baie geluk op jou onderhoude. [CS50.TV]