[Powered by Google Translate] [Mintegia: Elkarrizketak teknikoak]
[Kenny Yu, Harvard Unibertsitatea]
[Hau da CS50.] [CS50.TV]
Kaixo guztioi, Kenny naiz. Gaur egun, I am ikasten informatika junior.
CS TF ohia naiz, eta hau izan nuen, underclassman bat izan dut nahi dut,
eta hori zergatik mintegi hau ematen dut.
Beraz, gozatzeko aukera izatea espero dut.
Mintegia hau tekniko buruzko elkarrizketak da,
eta nire baliabide guztiak esteka honetan aurki daitezke,
eskubide hau hemen baliabide pare bat.
Beraz, arazoak zerrenda bat egin dut, egia esan, nahiko arazo gutxi.
Halaber, oro har, baliabide orrialdean non aholku aurki ditzakegu
nola prestatu elkarrizketa bat,
zer egin behar duzu benetako elkarrizketa zehar aholkuak,
eta baita nola arazoak eta baliabideak etorkizunean erreferentzia hurbiltzeko.
Da online.
Eta, besterik ez, mintegi honetan, lege oharra Prólogo,
atsegin dute hau egin beharko lukete ez - zure elkarrizketa prestatzeko
ez litzateke zerrenda honetan mugatuta dago.
Hori bakarrik esan nahi du gida bat izan nahi,
eta behin betiko hartu behar duzu, gatz ale bat esaten dut dena,
baina ere erabili guztia lagunduko dizu zure elkarrizketa prestatzeko erabiltzen dut.
>> Abiadura noa datozen diapositiba bidez
beraz, benetako kasu praktikoak eskuratu ahal izango dugu.
Software ingeniaritza postion elkarrizketa baten egitura,
normalean, 30 eta 45 minutu da.
erronda bat baino gehiago, enpresaren arabera.
Askotan zuri-taula duzu kodifikazioa.
Hau atsegin dute, baina askotan, neurri txikiagoan taula zuri bat, beraz.
Ari zaren telefono-elkarrizketa bat izanez gero, ziurrenik duzu erabiliz
bai collabedit edo Google Doc ikus daitezke kodeketa bizi zaren
zu ari den bitartean, telefonoz elkarrizketatu.
Elkarrizketa bat bera da, normalean 2 edo 3 arazo
zure informatika ezagutza probatzeko.
Eta ia behin betiko izango da inplikatzeko kodifikazioa.
Galdera mota egingo ikusten izan ohi dira Datu-egitura eta algoritmoak.
Eta mota horiek egiteko arazoak,
eskatuko dizu dute, bezala, denbora eta espazioaren konplexutasuna, big O zer da?
Sarritan eskatu ere, goi-maila galderak,
beraz, sistema bat diseinatu,
nola arautuko zure kodea?
Zer interfaces, zer klaseak, zer modulu egin behar zure sisteman,
eta nola horiek elkarreragin elkarrekin?
Beraz, datu egiturak eta algoritmoak diseinatzeko sistemak, baita.
>> Aholku batzuk gure kasuan ikasketak murgiltze aurretik.
Arau garrantzitsuena da beti pentsatzen ozen uste dut.
Zure pentsamendu-prozesu off erakusteko aukera izango da, ustezko elkarrizketa.
Erreportajearen puntua da elkarrizketatzaileak neurtzeko
nola pentsatzen duzun eta nola arazo baten bitartez.
Egin ahal izango duzu gauza txarrena da isila elkarrizketa osoan zehar.
Hori besterik ez da ez ona.
Duzunean galdera bat eman ere, nahi duzun galdera ulertzen ziur egiteko.
Beraz, galdera errepikatu zure hitzetan
eta saiakera sakon bat erraz batzuk test kasu lan egiteko
Ziur galdera ulertzen.
Test batzuk kasu bidez lan egiten du, halaber, arazo hau nola konpondu intuizio bat emango dizu.
Batzuk eredu bat ere aurkituko dezakezu arazoa konpontzeko laguntzeko.
Bere big tip ez da zapuztu.
Ez zaitez zapuztu.
Elkarrizketak zaila, baina egin dezakezu gauzarik txarrena,
isila izateaz gain, nabarmen behar zapuztuta.
Ez duzu nahi inpresioa ematen dioten elkarrizketa bat.
Gauza bat - beraz, jende askok eta askok, joan elkarrizketa bat sartzen dira,
konponbide onena aurkitzeko lehen saiatu saiatzen dira,
denean, benetan, ez da normalean glaringly bistako irtenbide bat.
Motela izango da agian, eraginkorra izan daiteke, baina besterik ez behar duzu aipatu,
beraz, hobeto lan egiteko abiapuntua besterik ez duzu.
Era berean, konponbidea seinalatuz motela da, termino
big O denbora konplexutasuna edo espazio konplexutasuna,
ulertzen duzu elkarrizketatzaileak erakusteko
gai horiek kodea idatziz.
Beraz, ez izan beldurrik errazena algoritmoa lehen
eta, ondoren, lan hobea bertatik.
Edozein galdera, beraz, orain arte? Ongi da.
>> Hargatik gure arazoa lehen murgiltzea.
"N zenbaki osoen array bat, array shuffles funtzio bat idatzi
lekua, hala nola, n osoko zenbakien permutazio guztiak dira berdin litekeena. "
Eta bere gain hartzen duzu eskuragarri zenbaki bat ausazko generator
barruti bat zenbaki oso bat sortzen 0-tik i, erdi-sorta.
Denek ulertzen ez du galdera hau?
N zenbaki osoen array bat ematen dizut, eta nahastu du nahi dut.
Nire direktorioa, zer esan nahi dut erakusteko programa bat gutxi idatzi nuen.
20 elementu array bat nahastu noa,
-10 tik +9,
eta hau atsegin zerrenda bat bistaratu nahi dut.
Beraz, hau da nire sarrera array ordenatuko da, eta nahastu du nahi dut.
Egin dugu berriro.
Denek ulertu galdera? Ongi da.
Beraz, sortu da.
Zer dira ideia batzuk? Ezin da egin n ^ 2, n log n, n?
Iradokizunak Ireki.
Ongi da. Beraz, ideia, Emmy iradokitako
da lehen compute ausazko zenbaki bat, ausazko zenbaki oso, tarte bat 0-tik 20.
Beraz gure array 20 luzera du.
Gure 20 elementu diagrama,
hau da, gure sarrera array da.
Eta orain, bere iradokizun array berri bat sortzeko,
beraz, hau izango da irteera array.
Eta itzuli aus i oinarritutako
beraz, izan zen i, demagun, 17,
lehen posizioan sartu kopiatu elementu 17an.
Orain ezabatu behar dugu, elementu guztiak mugitzeko behar dugu hemen
beraz gainean amaieran hutsune bat eta erdian zulo ez dugula.
Eta orain, prozesua errepikatu dugu.
Ausazko zenbaki oso berri bat 0 eta 19 artean hautatzeko orain dugu.
I berri bat izan dugu hemen, eta elementu hau kopiatu dugu jarrera hori.
Ondoren, elementu filmea dugu eta gehiagoko prozesua errepikatu ditugu gure berri array arte.
Zer da algoritmo hau denbora run?
Beno, dezagun honen eragina kontuan hartu.
Elementu aldatzearen behin ari gara.
Hori kendu dugu i, elementu guztiak ari gara aldatzearen ondoren ezkerrera.
Eta hori O (n) kostua
zer delako lehenengo elementu ezabatu badugu?
Beraz kentzea bakoitzean, kendu
kentzea bakoitzean bat O (n) eragiketa incurs
dugu eta kentzeko n geroztik, hau bat O (n ^ 2) nahastu eramaten du.
Ongi da. Irteeran onak. Good Irteeran.
>> Iradokizun bat da, zerbait Knuth nahastu bezala ezagutzen erabili,
edo Fisher-Yates nahastu.
Eta benetan lineal bat da, denbora nahastu.
Eta ideia oso antzekoa da.
Berriz ere, gure sarrera array dugu,
baina bi array erabiliz gure sarrera / irteera ordez,
array lehen zati erabiltzen ditugu gure zati nahastu segimendua egiteko,
eta jarraipena dugu, eta, ondoren, gure array gainerako utziko dugu unshuffled zati.
Hortaz, hona hemen zer esan nahi dut. Hasiko gara - i bat aukeratu dugu,
0-tik 20 array bat.
Gure gaur egungo erakuslea da lehenengo indizea seinalatuz.
I hemen batzuk aukeratzen ditugu
eta gaur egun trukatzeko.
Beraz, bada, 5 izan zen, eta hau izan zen 4.
ondorioz array 4 5 Hemen eta hemen izango dute.
Eta orain, markatzaile bat kontutan izan dugu hemen.
Ezkerraldean Dena nahastu,
eta eskubidea dena unshuffled.
Eta orain, prozesua errepikatu ahal izango dugu.
1 eta 20 arteko indizea ausazko gaur egun bat aukeratzen dugu.
Beraz, demagun gure berri hemen da i.
Orain i hau swap dugu gure gaur egungo egoera berria hemen.
Beraz, ez dugu atzera eta aurrera aldaketa hau atsegin dute.
Dezagun ekarri me kodea hormigoizko gehiago egin.
Hasten dugu gure i aukeratu -
0 i berdinak hasten gara, ausazko kokaleku j jaso dugu
array unshuffled zatia, n-1 i.
Hemen nago, aukeratu hemen eta gainerako array arteko indize ausazko
eta trukatzeko.
Kodea zure array Nahastu beharrezkoa da.
Edozein galdera?
>> Beno, galdera behar bat da, zergatik zuzena hau da?
Zergatik da permutazio bakoitzean bereko?
Eta ez dut horren froga bidez,
baina informatika arazo ugari indukzio frogatu daiteke.
Nola asko dira indukzio ezagutzen?
Ongi da. Cool.
Algoritmo honen zuzentasuna indukzio simple Beraz, frogatu ahal izango duzu,
non zure indukzio-hipotesia litzateke, bere gain hartzen duten
nire nahastu itzultzen behin permutazio bereko
lehen i elementuak.
Orain, kontuan hartu i + 1.
Eta gure indizea j swap aukeratu dugu,
hau dakar, eta, ondoren, lan xehetasunak
gutxienez, algoritmo hau zergatik itzultzen froga osoa
probabilitate bereko permutazio bakoitzean.
>> Guztiak eskubidea, hurrengo arazoa.
Beraz, "Emandako zenbaki osoen array, postive, zero, negatiboa,
gehienez batura kalkulatzen duen funtzio bat idatzi
sarrera array continueous subarray edozein ".
Adibide bat hemen da, non zenbaki guztiak positiboak dira kasuan,
ondoren, gaur egun, aukerarik onena da array osoa hartzeko.
1, 2, 3, 4, berdin 10.
Negatibo batzuk bertan,
Kasu honetan, nahi dugu lehen bi
-1 eta / edo -3 aukeratzeagatik duelako gure batura jarriko du behera.
Batzuetan, array-erdian hasten gara dezake.
Batzuetan, ezer ez guztietan aukeratu nahi dugu, hobe da ezer ez dute.
Eta batzuetan, hobe da jaitsiera,
ondoren gauza super handi delako. Ideiak edozein Beraz?
(Ikaslea, ulertezina) >> Bai.
Demagun ez dut hartu -1.
Gero bai, 1.000 eta 20.000 aukeratu dut,
edo hautatu dut 3 milioi.
Beno, aukerarik onena da zenbaki guztiak hartu.
-1, Negatiboak izan arren,
batura osoa da hobea baino ez dut -1 hartzeko.
Beraz, aholkuak lehenago aipatu dut bat izan zen argi eta garbi bistako adieraziko
eta brute indarrean aurreneko irtenbidea.
Zer da arazo hau indarrean brute irtenbidea? Bai?
[Jane] Beno, uste dut brute indarrean irtenbide
gehitu konbinazio posible guztiak (ulertezina) izango litzateke.
[Yu] Larreina. Beraz, Jane ideia da posible guztiak hartzeko
Parafraseatuz naiz da eta ahalik eta etengabeko subarray bakoitzean hartu,
konputatzeko bere batura, eta gero, etengabeko posible guztiak subarrays gehienezko hartu.
Zer bakarrean subarray bat identifikatzen nire sarrerako array?
Bezala, zer bi gauza egin behar dut? Bai?
(Ikaslea, ulertezina) >> eskubidea.
A txikiagoa indize eta goi-koadernatuta indizea lotuak
bakarrean etengabeko subarray bat zehazten du.
[Emakumezkoak ikaslea] estimatzea zenbaki berezia da array bat da?
[Yu] N º Beraz, bere galdera da, ari suposatuz gure array dugu
gure array berezia zenbakiak da, eta erantzuna ez da.
>> Erabili dugu gure brute indarrean konponbidea, ondoren, hasiera / amaiera indizeak
bakarrean, gure etengabeko subarray zehazten du.
Beraz, batetik bestera joateko Irteeran posible sarrerak dugu,
eta azken sarrera guztiak> edo =, hasteko eta <n
batura kalkulatzeko, eta, ondoren, ikusi dugu, orain arte, gehienez batura hartuko dugu.
Hau argi eta garbi?
Zer da O big irtenbide hau?
Timewise.
Ez da nahiko n ^ 2.
Kontuan 0-tik n batetik bestera joateko,
beraz, loop bat da.
Batetik bestera joateko dugu berriro ia hasieratik amaierara arte, beste begizta.
Eta gaur egun, horren barruan, sarrera bakoitzean laburbildu dugu,
beraz, beste begizta. Beraz, hiru begiztak for habiaratuak, n ^ 3 dugu.
Ongi da. Abiapuntu gisa doa.
Gure soluzioa ez n ^ 3 baino okerrago.
Denek ulertu brute indarrean irtenbidea?
>> Ongi da. Konponbide bat hobea dinamikoa programazio izeneko ideia bat erabiltzen ari da.
Hartu duzu CS124 bada, eta Algoritmoak eta Datu Egiturak
teknika hau oso ezaguna bihurtu ahal izango duzu.
Eta ideia da, eta saiatu konponbideak eraikitzeko txikiagoa arazoak lehen aldiz.
Zer esan nahi dut, hau da, gaur egun dugun bi gauza kezkatu: hasieran eta amaieran.
Eta hori da gogaikarriak. Zer parametro horietako bat kentzeko bada ezin izan gara?
We're gure jatorrizko arazoa kontuan hartuta, - ideia bat da.
gehienezko barruti bat edozein subarray batura [O, n-1].
Eta orain berri bat subproblem, non gauden jakin behar dugu, gaur egungo gure indizea i,
badakigu ez ondorioztatu behar dugu. Uneko indizea Gure subarray behar amaituko da.
Gainerako arazoa da Beraz, non behar gure subarray hasteko dugu?
Ba al du zentzurik? Ongi da.
Beraz, kodetu Nik, hau, eta dezagun zer esan nahi hau begiratu.
: Codirectory da, ez dago subarray izeneko programa bat da,
eta elementu kopurua hartzen du,
eta subarray batura maximoa itzultzen du nire zerrenda nahastu.
Beraz, kasu honetan, gure subarray maximoa 3.
Eta hori besterik ez, 2 eta 1 erabiliz hartu.
Dezagun exekutatu berriro. Gainera, 3.
Baina une honetan, kontutan izan nola 3 genuen.
Hartu genuen hartu besterik ez dugu 3 bera
eta negatiboak delako inguratuta bi aldeetan,
batura bat ekarriko du, <3.
Dezagun 10 elementuak exekutatzeko.
Oraingo honetan 7 da, liderra 3 eta 4. Hartuko dugu.
Oraingo honetan 8 da, eta 1, 4 eta 3 hartu lortuko dugu.
Beraz, nola intuizioa emateko eraldatu arazo hau konpondu ahal izango dugu,
dezagun subarray honetan begirada bat.
Emandako sarrera array hau gara, eta badakigu erantzuna 8.
1, 4, eta 3 hartuko dugu.
Baina nola lortu benetan erantzuna begiratu.
Maximoa duen indize horietako bakoitzean subarray amaitu.
Zer da maximoa subarray duen lehen posizioan bukatzen da?
[Student] Zero. >> Zero. Just ez hartu -5.
0 izango baita egingo. Bai?
(Ikaslea, ulertezina)
[Yu] Oh, barkatu, -3 da.
2 Beraz, -3 da.
Ongi da. Beraz, -4, zer maximoa subarray posizio hori amaitzeko
non -4 da? Zero.
One? 1, 5, 8.
Orain, non -2 da behar dut amaituko da.
6 Beraz, 5, 7, eta azkena 4.
Horiek dira nire sarrerak ezagutzea
arazoa eraldatu non indize horietako bakoitzean amaitzeko behar dut,
gero, nire final erantzuna besterik ez da, hartu Ekorketa baten zehar,
eta gehienezko hartu.
Beraz, kasu honetan, 8.
Horrek esan nahi du maximoa subarray indize honetan amaitzen da,
eta nonbait hasi aurretik.
Denek ulertu eraldatu subarray hau?
>> Ongi da. Beno, dezagun hau errepikatze irudikatu.
Dezagun kontuan hartu lehen sarrera batzuk bakarrik.
Hortaz, hona hemen 0, 0, 0, 1, 5, 8.
Eta gero bat -2 izan zen hemen, eta ekarri behera 6.
Beraz, bada posizioan sarrera deitzen I i subproblem (i),
nola egin dezaket erantzuna erabili dut aurreko subproblem
subproblem honi erantzuteko?
Begiratzen dut bada, demagun, baina sarrera hau.
Nola egin dezaket erantzun 6 konputatu I begira
array eta array honetan subproblems aurreko erantzun konbinazio bat? Bai?
[Emakumezkoak ikaslea] batuketa array hartuko duzu
posizio eskuinera aurretik, 8, beraz,
eta, ondoren, gaur egungo subproblem gehitu duzu.
[Yu] bere iradokizuna da, bi zenbaki horiek begiratu,
Zenbaki hau, eta zenbaki hau.
Beraz, hau 8 erantzun subproblem kodea (1 - i) egiten dio erreferentzia.
Eta dezagun nire sarrera array A. deitu
Ordena maximoa subarray posizioa i amaitzen da,
Bi aukera daukat: bai dut jarraitu subarray
aurreko indizea amaitu zen, edo array berri bat hasteko.
Ziren I subarray aurreko indizea hasi, jarraitu nahi izanez gero,
gero gehienezko batura lor daiteke I, aurreko subproblem erantzun
plus egungo array sarrera.
Baina, izan ere berri subarray hasierako aukeratu dut,
Kasu horretan, batura 0 da.
1, gehi uneko array sarrera - Beraz, erantzuna 0 max, subproblem i.
Errepikatze horrek ez du zentzurik?
Gure errepikatze, besterik ez dugu aurkitu, subproblem i
gehienez aurreko subproblem plus, nire uneko array sarrera berdina da,
horrek esan nahi du jarraitu aurreko subarray,
edo 0, nire uneko indizea subarray berri bat hasteko.
Eta behin eraiki dugu, irtenbideak taula honetan, eta ondoren gure behin betiko erantzuna,
Ekorketa lineala egin bat subproblem array zehar
eta gehienezko hartu.
Inplementazio zehatza da zer esan besterik ez dut.
Beraz, subproblems array berri bat subproblem sortu dugu.
0 edo lehen sarrera, gehienez bi horien lehen sarrera da.
Eta subproblems, gainerako
aurkitu besterik ez dugu zehatza errepikatze erabiltzen dugu.
Orain gure subproblems array gehienez konputatu dugu, eta, gure behin betiko erantzuna.
>> Beraz, zenbat espazio algoritmo hau erabiltzen ari gara?
Dituzun hartu baino ez bada CS50, eta gero, agian ez duzu eztabaidatu espazio asko.
Beno, gauza bat kontutan izan da malloc deitu dut hemen tamaina n.
Zer esan gomendatzen?
Algoritmo honek espazio lineala erabiltzen du.
Ezin hobeto egiten dugu?
Ba al dago ezer ez da beharrezkoa azken erantzuna kalkulatzeko nabarituko duzula?
I guess galdera bat hobea da, zein informazio
egin behar, ez dugu modu guztiak aurrera eraman ahal izateko amaieran?
Orain, bi lerro hauek kontuan hartuz gero,
, aurreko subproblem buruz baino ez dugu nahi,
eta inoiz ikusi dugu, orain arte, gehienez buruz baino ez dugu zaindu.
Gure azken erantzuna kalkulatzeko, ez dugu behar array osoa.
Azken zenbakia, azken bi zenbakiak bakarrik behar dugu.
Azken zenbakia subproblem array, eta azken gehienezko kopurua.
Beraz, hain zuzen ere, loops horiek Fuse ahal izango dugu elkarrekin
eta espazio lineal espazio etengabeko joan.
Oraingo batura beraz, orain arte, hemen, subproblem, gure subproblem array rola ordezkatzen du.
Beraz, gaur egungo batura, eta, beraz, orain arte,, aurreko subproblem erantzuna da.
Eta batura hori, eta, beraz, orain arte, gure max lekua hartzen du.
Gehienez konputatu dugu, joan gara.
Eta, beraz, espazio lineal joan gara etengabe espazioa
dugu gure subarray arazoa konpontzeko lineal bat.
>> Elkarrizketa batean galdera-mota hauek izango duzu.
Zer da denbora konplexutasuna da; espazioaren konplexutasuna zer da?
Ezin hobeto egin nahi duzu? Ba al dago alferrikako mantendu diren gauzak?
Hau nik egin dut zure hartu behar aztertzen nabarmendu
ari zaren arazoak horien bidez lan.
Beti zeure buruari galdetuz, "Ezin hobeto egin dut?"
Izan ere, hori baino hobeto egin dugu?
Ordena trikimailu galdera bat. Ezin duzu, behar duzu delako
gutxienez, arazo sarrera irakurri.
Izan ere, behar duzu, eta, gutxienez, irakurri Beraz, sarrerako arazoa
esan nahi du ezin duzula egin denbora lineala baino hobea da,
eta ezin duzu etengabeko espazioa baino hobeto.
Beraz, hau da, hain zuzen ere, arazo hau konponbide onena.
Zalantzak dituzu? Ongi da.
>> Burtsa arazoa:
"N zenbaki osoko, positiboa, zero, edo negatiboa array bat,
stock baten prezioa n egunetan zehar,
funtzio bat idatzi gehienezko irabazien kalkulatzeko egin dezakezu
ematen, erosi eta saldu zehazki 1 stock eguneko epean n horiek ".
Funtsean, baxua erosi, saldu handiko nahi dugu.
Eta egin ahal ditugu irabazien onena irudikatu nahi dugu.
Atzera eginez, nire tip, zer berehala argi eta garbi, erantzun sinpleena da, baina motela da?
Bai? (Ikaslea, ulertezina) >> Bai.
>> Beraz, nahi duzun joan nahiz eta stock prezioak begiratu
une bakoitzean, (ulertezina).
[Yu] Ados, eta, beraz, bere irtenbide - bere informatika gomendioa
txikiena eta handiena kalkulatzeko, ez du zertan lan
altuena, baxuena aurretik ere gerta liteke.
Beraz, zer brute indarrean Arazo honen konponbidea da?
Zer dira bi gauza bakarra irabazi egin zehaztu behar dut? Eskuin.
Brute indarrean soluzioa - oh, beraz, George iradokizuna da, bi egun besterik ez dugu behar.
bi egun horietan irabazi bakarrean zehazteko.
Beraz, bikote bakoitzak konputatu dugu, nahi erosi / saldu,
konputatzeko irabazi, negatiboa edo positiboa edo zero izan daiteke.
Kontatu gehienezko irabazien egun bikote guztiak baino gehiago errepikatzean ondoren egiten dugu.
Hori da gure erantzuna behin betiko izango da.
Eta konponbide O (n ^ 2) izango da, ez dagoelako n bi bikote aukeratu -
egun, azken egun artean aukeratu ahal izango dituzu.
Ados, beraz, ez naiz hemen indarrean brute irtenbide baino gehiago joan behar.
Esango dizut ez dagoela log n irtenbide bat n noa.
Zer algoritmoa ez gaur egun ezagutzen duzun n log n?
Ez da trikimailu galdera bat.
>> Batu sort. Batu sort-n log-n da,
eta hain zuzen ere, arazo hau konpontzeko modu bat da erabili
merge sort ideia mota deitzen zaio, oro har, zatitzea eta konkistatzeko.
Eta ideia da honela.
Best buy konputatu / bikotea saldu ezkerreko erdia nahi duzu.
Aurkitu eta irabazien onena egin dezakezu, bi egunetan zehar lehen n.
Orduan, onena erosi oompute / bikotea eskuineko erdia saldu nahi baduzu,
beraz, azken bi egunetan zehar n.
Eta orain, galdera da, nola irtenbide hauek batu ditugu atzera elkarrekin?
Bai? (Ikaslea, ulertezina)
>> Ados. Beraz, let irudi bat marraztu me.
Bai? (George, ulertezina)
>> Zehazki. George irtenbide zehazki eskubidea da.
Bere iradokizun Beraz, lehenik eta behin, konputatu buy / Saldu bikote onena,
eta ezkerreko zatian gertatzen da, beraz, dezagun dei ezker, ezkerretik.
Best erosi / saldu eskuineko erdia gertatzen den bikotea.
Baina besterik ez dugu aldean bada, bi zenbaki horiek, kasu ari gara falta
non hemen erosi eta saldu nonbait eskuineko erdia.
Ezkerreko erdia erosi dugu, eskuineko erdia saltzen.
Eta onena buy / Saldu bikotea halves bi luzeago kalkulatzeko modurik onena
gutxieneko konputatu da hemen eta gehienez kalkulatzeko hemen
eta dute aldea.
Buy / Saldu bikotea gertatzen da bi kasuetan bakarrik hemen, beraz,
bakarrik, edo halves bi hiru zenbaki horiek definitzen da.
Gure algoritmoa Beraz, gure irtenbideak batu itzuli batera,
buy / Saldu bikote onena konputatu nahi dugu
ezkerreko erdia non erosi eta eskuineko erdia saldu dugu.
Eta hori egiteko modurik onena da txikiena prezioa kalkulatzeko, lehenengo seihilekoan,
eskuineko erdia prezio handiena, eta aldea hartu.
Emaitzeko hiru irabaziak, hiru zenbaki horiek, gehienez, hiru hartzen duzu,
eta horiek lehen eta bukaera egunetan zehar mozkin egin dezakezu hori.
Here garrantzitsua lerro gorri dira.
Ezkerreko erdia erantzuna kalkulatzeko dei errekurtsiboa da.
Dei errekurtsiboa erantzuna kalkulatzeko eskuineko zatia da.
Hauek bi begiztak konputatzeko min eta max ezkerreko eta eskuineko erdia, hurrenez hurren.
Orain halves bi irabazi luzeago konputatu I,
eta azken erantzun horiek hiru gehienez.
Ongi da.
>> Beraz, ziur aski, algoritmo bat dugu, baina handiagoa da galdera,
zer da hau konplexutasuna denbora?
Eta zergatik aipatu dut merge sort formulario hau zatitzen erantzuna
bi sartu eta, ondoren, gure irtenbideak batuz itzuli batera
zehazki merge sort.
Hargatik joan iraupena bidez.
Definitu dugu funtzioa t (n) bada urratsen kopurua izango
n egun,
gure bi dei errekurtsiboak
bakoitzeko kostua t (n / 2),
eta ez da bi dei horiek.
Orain ezker erdia gutxienez konputatu behar dut,
n / 2 denbora, gehi eskuineko erdia gehienez egin ahal izango dut.
Beraz, hori besterik ez da, n.
Eta gero, etengabeko lan batzuk gehi.
Eta errepikatze ekuazio honen
hain zuzen ere, errepikatze merge sort ekuazioa.
Eta denok dakigu, merge sort n log n denbora da.
Hori dela eta, gure algoritmoa da, baita ere n log n denbora.
Iterazio honetan ez du zentzurik?
Just honen laburpena txiki bat:
Gehienezko irabazien urratsen kopurua kalkulatzeko T (n)
n egun osoan zehar.
Zatitu dugu gure dei errekurtsiboak
n / 2 lehen egunetan gure irtenbide deituz da,
beraz, dei bat da,
eta, ondoren, berriro deitzen diogu bigarren erdian.
Beraz, bi deiak.
Eta gero, gutxienez bat aurkituko dugu ezkerreko erdia, denbora lineala egin ahal izango dugu,
aurkitu eskuineko erdia, gehienez, denbora lineala egin ahal izango dugu.
Beraz, n / 2 + n / 2 besterik ez da n.
Ondoren, etengabeko lan batzuk ditugu, aritmetika egiten bezalakoa da.
Errepikatze-ekuazioa hau da, hain zuzen ere errepikatze merge sort ekuazioa.
Hori dela eta, gure nahastu algoritmoa ere n n saioa.
Beraz, zenbat espazio erabiltzen ari gara?
Dezagun itzuli kodea.
>> Galdera bat hobea da, zenbat pila markoak edozein une jakin dugu inoiz izan?
Ari gara errekurtsio erabiliz geroztik,
gure erabilera espazio pila fotograma kopurua zehazten du.
Dezagun kontuan hartu n = 8.
Nahastu deitzen diogu, 8,
nahastu deituko lehen lau sarrerak,
lehen bi sarrerak nahastu deituko.
Beraz, gure pila da, hau da, gure pila da.
Eta ondoren, nahastu berriro deitzen diogu 1,
eta horrek zer da gure oinarria kasuan, eta, beraz, berehala itzuliko gara.
Dugu inoiz hau pila asko fotograma baino gehiago?
Aldi bakoitzean deitzeko bat egiten dugu delako,
Nahastu deitzeko recursive,
gure tamaina erdia zatitzen dugu.
Pila fotograma kopurua gehienez Beraz, edozein une jakin dugu inoiz
log n pila fotograma ordena da.
Pila marko bakoitzak etengabeko espazioa du,
eta, beraz, espazioaren zenbatekoa, guztira,
espazioaren zenbatekoa, gehienez erabili dugu inoiz O (log n) espazioa da
non n egun kopurua da.
>> Orain, beti galdetu zeure burua, "Ezin hobeto egiten dugu?"
Eta, batez ere, ezin hori murrizteko dugu dagoeneko konpondu arazo bat?
Aholkua: beste bi arazo eztabaidatu besterik ez dugu aurretik, eta ez da nahastu izango.
Burtsa hau arazo bihurtu ahal izango dugu subarray maximoa arazoa.
Nola egin dezakegu hori?
Duzu bat? Emmy?
(Emmy, ulertezina)
[Yu] Zehazki.
Maximoa arazoa Beraz subarray
batura bat bilatzen ari gara etengabeko subarray zehar.
Eta Emmy stock arazoa iradokizun,
iritziz, aldaketa, edo deltak.
Eta argazki bat da, hau da stock baten prezioa,
baina egun bakoitzean partiduko arteko aldea hartu badugu -
beraz, gehienezko prezioa, gehienezko irabazien egin izan dugu ikusiko dugu
erosi dugu hemen, eta hemen saltzeko.
Baina etengabe begiratu dezagun subarray arazoa begiratu.
Hortaz, hona hemen, egin ahal izango dugu, hemendik aurrera hemen joan,
positiboa aldaketa bat dugu, eta, ondoren, hemendik aurrera hemen negatiboa aldaketa bat dugu.
Baina orduan, hemendik aurrera hemen positiboa aldaketa handi bat izan dugu.
Eta aldaketa horiek laburbildu nahi dugun gure azken irabazien iritsi dira.
Ondoren, aldaketa gehiago negatiboa izan dugu hemen.
, Gure stock arazoa murrizteko gure subarray maximoa arazoa gakoa
egun arteko deltak kontuan hartu behar da.
Beraz izeneko deltak array berri bat sortu dugu,
hasieratu 0 izango lehen sarrera,
eta, ondoren, delta bakoitzean (i), utzi aldea
nire sarrera array (i), eta array (i - 1).
Ondoren, gure maximoa subarray prozedura errutina deitzen dugun
delta baten array igaroz.
Lineal denbora maximoa subarray delako,
eta murrizketa hori, delta array hau sortzeko prozesu honetan,
da ere denbora lineala,
ondoren stock behin betiko irtenbidea O (n) lan-plus O (n) lana da, oraindik O (n) lana.
Beraz, lineal bat denbora gure arazoa konpontzeko behar dugu.
Denek ulertzen ez du eraldaketa hau?
>> Oro har, ideia ona da beti izan behar duzula
ari zaren arazo berri bat ikusteko murrizten saiatuko da.
Badirudi arazo zahar bat ezagutzen baduzu,
saiatuko da arazo zahar murrizteko.
Eta arazo zaharrak erabiltzen duzun tresna erabiltzen baduzu
arazoa konpontzeko.
Beraz, itzulbiratu, tekniko elkarrizketak dira erronka.
Arazo horiek dira ziurrenik arazo zailagoa batzuk
elkarrizketa bat ikusi liteke,
beraz, arazo besterik ez dut estaltzen ez baduzu ulertzen, ados.
Hauek arazo gehiago Challenging batzuk dira.
Praktika, praktikan, praktikan.
Esku-en arazo asko eman dut, eta, beraz, behin betiko egiaztatu duten.
Eta sorte on zure elkarrizketak. Nire baliabide guztiak esteka honetan etan
eta nire lagunak senior bat eskaini du mock tekniko elkarrizketak egin,
hala badagokio interesatuta bazaude, email Will Yao duten e-posta helbidea.
Zalantzaren bat izanez gero, galdetu ahal izango duzu.
Do you guys tekniko elkarrizketak lotutako galdera zehatzei
edo ikusi dugu, orain arte, inolako arazorik?
Ongi da. Beno, sorte on zure elkarrizketak.
[CS50.TV]