[Powered by Google Translate] [Seminè sou: Entèvyou teknik]
[Kenny Yu, Inivèsite Harvard]
[Sa a se CS50.] [CS50.TV]
Hi tout moun, mwen Kenny. Se mwen menm kounye a yon jinyò syans etidye òdinatè.
Mwen se yon ansyen CS tf, ak mwen swete mwen te gen sa a lè m 'te yon underclassman,
ak Se poutèt sa mwen bay sa a seminè.
Se konsa, mwen espere ou jwi li.
Sa a seminè se sou entèvyou teknik,
ak tout resous mwen ka jwenn nan lyen sa a,
lyen sa a dwa isit la, yon koup la resous.
Se konsa, mwen te fè yon lis de pwoblèm, aktyèlman, byen yon pwoblèm kèk.
Epitou yon jeneral resous paj kote nou ka jwenn konsèy
sou ki jan pou prepare pou yon entèvyou,
konsèy sou sa ou ta dwe fè pandan yon entèvyou reyèl,
kòm byen ke ki jan yo apwòch pwoblèm ak resous pou referans nan lavni.
Li nan tout sou entènèt.
Ak jis prefas sa a seminè-a, yon avètisman,
tankou sa a pa ta dwe - preparasyon pou antrevi ou
pa ta dwe limite a sa sèlman lis sa a.
Sa a se sèlman vle di ke yo gen yon gid,
epi ou ta dwe definitivman pran tout bagay sa m 'di ak yon grenn sèl,
men tou sèvi ak tout bagay mwen itilize yo ede w nan preparasyon entèvyou w la.
>> Mwen pral ale pi vit nan glisad kap vini yo
pou nou ka jwenn yo etid ka yo reyèl.
Estrikti a nan yon entèvyou pou yon postion jeni lojisyèl,
tipikman li se 30 a 45 minit,
jij miltip, depann sou konpayi an.
Souvan ou pral kodaj sou yon tablo blan.
Se konsa, yon tablo blan tankou sa a, men souvan sou yon echèl pi piti.
Si w ap gen yon entèvyou nan telefòn, ou pral pwobableman ap lè l sèvi avèk
swa collabedit oswa yon doc Google yo pou yo ka wè ou ap viv kodaj
pandan w ap yo te entèvyou nan telefòn.
Yon entèvyou li menm se tipikman 2 oubyen 3 pwoblèm
tès konesans syans òdinatè ou.
Epi li pral prèske definitivman gen pou wè ak kodaj.
Kalite kesyon ki ke ou pral wè yo anjeneral estrikti done ak algoritm.
Ak nan fè sa yo kalite pwoblèm,
yo pral mande ou, renmen, ki sa ki se tan a ak konpleksite espas, gwo O?
Souvan yo menm tou yo mande pi wo-nivo kesyon,
se konsa, desine yon sistèm,
ki jan ou ta kouche soti kòd ou a?
Ki sa ki interfaces, ki sa ki klas, ki sa ki modil ou gen nan sistèm ou a,
ak ki jan sa yo kominike ansanm?
Se konsa, done estrikti ak algoritm kòm byen ke sistèm desine.
>> Men kèk konsèy jeneral anvan nou plonje nan ka etid nou an.
Mwen panse ke règ ki pi enpòtan an se toujou dwe panse byen fò.
Se entèvyou a sipoze chans ou a montre nan pwosesis panse ou a.
Pwen nan entèvyou a se pou entèvyou a mezire
fason ou panse ak fason ou ale nan yon pwoblèm.
Bagay ki pi mal la ou ka fè se rete an silans pandan tout entèvyou a tout antye.
Se jis pa bon menm.
Lè w ap bay yon kesyon, ou vle asire tou ansòt ou konprann kesyon an.
Se konsa, repete kesyon an tounen nan pwòp mo ou
epi eseye fè travay bon jan yon kèk ka tès senp ki
asire w ke ou konprann kesyon an.
K ap travay nan yon ka tès kèk pral tou ba ou yon entwisyon an sou kòman yo rezoud pwoblèm sa a.
Ou ta ka menm dekouvri yon modèl kèk ede ou rezoud pwoblèm nan.
Pwent gwo yo se pa jwenn fristre.
pa jwenn fwistre.
Entèvyou yo se difisil, men bagay ki pi mal la ou ka fè,
nan adisyon a ke yo te an silans, se yo dwe wè fristre.
Ou pa vle bay enpresyon ke nan yon entèvyou.
Youn nan bagay ki ou - se konsa, anpil moun, lè yo ale nan yon entèvyou,
yo eseye eseye jwenn solisyon a pi bon an premye,
lè reyèlman, gen nan anjeneral yon solisyon furyezman evidan.
Li ta kapab dousman, li ta ka rezèvwa, men ou ta dwe jis deklare li,
jis pou ou gen yon pwen depa nan ki travay pi byen.
Epitou yo, montre yo solisyon an se ralanti, an tèm de
gwo O tan konpleksite oswa konpleksite espas,
yo ap montre entèvyou a ke ou konprann
pwoblèm sa yo lè li ap ekri kòd.
Se konsa, pa bezwen pè vini ak algoritm la ki pi senp premye
ak Lè sa a, travay pi byen apati de la.
Nenpòt kesyon byen lwen tèlman? Oke.
>> Se konsa, nan kite l 'plonje nan pwoblèm premye nou yo.
"Bay yon etalaj de n nonm antye yo, ekri yon fonksyon ki melanz etalaj la
nan plas sa yo ke tout pèrmutasyon nan nonm antye relatif yo n yo se menm chans. "
Ak asime ou gen disponib yon dèlko nonb antye relatif o aza
ki jenere yon nonb antye relatif nan yon seri ki ant 0 a mwen, ranje mwatye.
tout moun konprann kesyon sa a?
M 'ba ou yon etalaj de n nonm antye yo, ak mwen vle fè w chefeul li.
Nan anyè mwen, mwen te ekri yon pwogram kèk yo demontre sa m 'vle di.
Mwen pral chefeul yon etalaj de 20 eleman,
soti nan -10 +9,
e mwen vle ou nan pwodiksyon yon lis tankou sa a.
Se konsa, sa a se opinyon etalaj Ranje mwen an, epi mwen vle fè w chefeul li.
Nou pral fè l 'ankò.
tout moun konprann kesyon an? Oke.
Se konsa, li moute nan ou.
Ki sa ki yo se kèk ide? Èske ou ka fè li kòm n ^ 2, n boutèy demi lit n, n?
Yo admèt sijesyon.
Oke. Se konsa, yon sèl lide, te sijere ke pa Emmy,
se premye kalkile yon nimewo o aza, o aza nonb antye relatif, nan yon seri ki ant 0 a 20.
Se konsa, asime etalaj nou an ki gen yon longè 20.
Nan dyagram nou nan 20 eleman,
sa a se etalaj opinyon nou an.
Epi, koulye a, sijesyon l 'se kreye yon etalaj nouvo,
konsa sa a pral etalaj la randman.
Ak ki baze sou la mwen tounen pa rand -
Se konsa, si mwen te, kite la di, 17,
kopye eleman nan 17th nan pozisyon a an premye.
Koulye a, nou bezwen efase - nou bezwen chanjman tout eleman yo ki isit la
sou sa ke nou gen yon espas nan fen an ak pa gen twou nan mitan yo.
Epi, koulye a nou repete pwosesis la.
Koulye a, nou chwazi yon nouvo nonb antye relatif o aza ant 0 ak 19.
Nou gen yon nouvo mwen isit la, epi nou kopye sa a eleman nan pozisyon sa a.
Lè sa a, nou chanje atik sou yo ak nou repete pwosesis la jiskaske nou gen plen nou an nouvo etalaj.
Ki sa ki se tan an kouri nan sa a algorithm?
Oke, kite la konsidere enpak la nan sa a.
Nou ap déplacement chak eleman.
Lè nou retire sa a mwen, n ap déplacement tout eleman ki nan apre li fin a gòch la.
E ke se yon O (n) pri
paske sa si nou retire eleman nan an premye?
Se konsa, pou chak retire, nou retire -
chak ranvwa supports yon O (n) operasyon,
ak paske nou te fè n ranvwa, sa a mennen nan yon chefeul O (n ^ 2).
Oke. Se konsa, bon kòmanse. Bon kòmanse.
>> Yon lòt sijesyon se yo sèvi ak yon bagay ke yo rekonèt kòm chefeul a knu,
oswa chefeul a Fisher-Yates.
Epitou, se aktyèlman yon chefeul tan lineyè.
Ak lide nan trè sanblab.
Yon fwa ankò, nou genyen etalaj opinyon nou an,
men olye pou yo lè l sèvi avèk de ranje pou D 'nou an / pwodiksyon,
nou itilize pòsyon an premye nan etalaj la nan kenbe tras nan shuffled pòsyon nou an,
epi nou kenbe tras, ak Lè sa a, nou kite rès la nan etalaj nou an pou pòsyon ki unshuffled.
Se konsa, isit la nan sa m 'vle di. Nou kòmanse nan ak - nou chwazi yon mwen,
yon etalaj ki ant 0 a 20.
Konsèy aktyèl nou an, ap lonje dwèt endèks la an premye.
Nou chwazi kèk isit la mwen
e kounye a nou boukante.
Se konsa, si sa a, li te 5 sa a te 4,
etalaj la ki kapab lakòz ap gen 5 isit la ak 4 isit la.
Epi, koulye a nou sonje yon makè isit la.
Tout bagay sa yo bò gòch la ap shuffled,
epi li se tout bagay sa yo dwa pou unshuffled.
Epi, koulye a nou ka repete pwosesis la.
Nou chwazi yon endèks o aza ant 1 ak 20 kounye a.
Se konsa, ta kwè nou nouvo mwen se isit la.
Koulye a, nou boukante sa a mwen ak pozisyon nou an ki ajou nouvo isit la.
Se konsa, nou yon échanjé retounen ak lide tankou sa a.
Kite m 'pote yo moute kòd la fè li pi konkrè.
Nou kòmanse avèk chwa nou an mwen -
nou kòmanse ak mwen egal a 0, nou chwazi yon j kote o aza
nan pòsyon unshuffled nan etalaj la, mwen n 1-.
Se konsa, si mwen isit la, chwazi yon endèks o aza ant isit la ak rès la nan etalaj la,
epi nou boukante.
Sa a se tout kòd la nesesè yo chefeul etalaj ou a.
Nenpòt kesyon?
>> Oke, yon sèl bezwen kesyon ap, poukisa se sa a ki kòrèk?
Poukisa se chak pèmitasyon menm chans?
Apre sa, mwen pa pwal ale travèse prèv sa a,
men anpil pwoblèm nan syans òdinatè ou ka pwouve nan endiksyon.
Konbyen nan ou yo abitye avèk endiksyon?
Oke. Fre.
Se konsa, ou ka pwouve ekzaktitid sa a algorithm pa endiksyon ki senp,
kote ipotèz endiksyon ou ta dwe, asime ke
chefeul mwen retounen chak pèmitasyon menm chans
jiska eleman yo mwen an premye.
Koulye a, konsidere mwen + 1.
Ak nan chemen an, nou chwazi j endèks nou yo boukante,
sa a kondwi a - ak Lè sa a, ou ap travay sou detay yo
omwen yon prèv plen sou rezon ki fè sa a algorithm retounen
chak pèmitasyon ak pwobabilite menm chans.
>> Tout dwa, pwochen pwoblèm.
Se konsa, "yo bay yon seri nonm antye yo, postive, zewo, negatif,
ekri yon fonksyon ki kalkile sòm total la maksimòm
nan nenpòt ki subarray continueous nan etalaj la D '. "
Yon egzanp isit la se, nan ka a kote tout chif yo se pozitif,
Lè sa a, kounye a chwa ki pi bon se pran etalaj nan tout antye.
1, 2, 3, 4, egal 10.
Lè ou gen kèk negatif nan la,
nan ka sa a nou jis vle de a an premye
paske chwazi -1 ak / oswa -3 pral pote sòm nou desann.
Pafwa nou ka gen yo kòmanse nan mitan an nan etalaj la.
Pafwa nou ta vle chwazi pa gen anyen nan tout; li pi bon pa pran anyen.
E pafwa li pi bon yo pran otòn lan,
paske bagay la apre li fin se super gwo. Se konsa, nenpòt ide?
(Elèv yo, enkonpreansibl) >> Yeah.
Sipoze mwen pa pran -1.
Lè sa a, swa Mwen chwazi 1,000 ak 20,000,
oswa mwen jis chwazi 3 milya dola nan.
Oke, chwa ki pi bon se pran tout chif yo.
Sa a -1, malgre yo te negatif,
sòm total la antye se pi bon pase yo te Mwen pa pran -1.
Se konsa yonn nan konsèy yo mwen mansyone pi bonè te bay eta evidan an byen klè
ak solisyon an fòs brital premye.
Ki sa ki se solisyon an fòs brital nan pwoblèm sa a? Yeah?
[Jane] Oke, Mwen panse ke solisyon an fòs brital
ta dwe ajoute jiska tout konbinezon ki posib (enkonpreansibl).
[Yu] Okay. Se konsa, lide Jane nan se pran tout posib -
Mwen parafraze - se pran tout posib subarray kontinyèl,
kalkile sòm li yo, ak Lè sa a, pran maksimòm nan tout subarrays yo posib kontinyèl.
Ki sa ki inikman idantifye yon subarray nan etalaj opinyon mwen an?
Tankou, ki sa ki de bagay mwen bezwen? Yeah?
(Elèv yo, enkonpreansibl) >> Dwa.
Yon pi ba mare l 'sou endèks la ak yon anwo endèks mare
inikman detèmine yon subarray kontinyèl.
[Fi elèv] Èske nou estime li a yon etalaj nan nimewo inik?
[Yu] No Se konsa, kesyon li a, èske nou asepte etalaj nou yo -
se etalaj nou tout nimewo inik, e repons la se non.
>> Si nou itilize solisyon brital fòs nou an, Lè sa a, endis yo kòmanse / fen
inikman detèmine subarray kontinyèl nou an.
Se konsa, si nou répétèr pou tout antre kòmansman sa posib,
ak pou tout antre fen> oswa = kòmanse, ak <n,
ou kalkile sòm la, ak Lè sa a, nou pran sòm total la maksimòm nou te wè byen lwen tèlman.
Èske sa se klè?
Ki sa ki O nan gwo sa a solisyon?
Timewise.
Pa byen N ^ 2.
Remake byen ke nou répétèr ki ant 0 a n,
pou ki nan yon sèl pou riban.
Nou répétèr ankò soti nan prèske nan konmansman an nan fen a, yon lòt pou riban.
Epi, koulye a, nan sa, nou dwe rapò kantite moute chak antre,
pou ki nan yon lòt pou riban. Se konsa, nou gen twa pare solèy pou pasan, n ^ 3.
Oke. Sa a ale kòm yon pwen depa.
Solisyon nou se pa gen okenn pi mal pase n ^ 3.
tout moun konprann solisyon an fòs brital?
>> Oke. Yon solisyon pi bon an lè l sèvi avèk yon lide rele dinamik pwogramasyon.
Si ou pran CS124, ki se Algoritm ak Done Estrikti,
ou pral vin trè abitye ak teknik sa a.
Ak lide nan ki, eseye bati yon solisyon ak pwoblèm ki pi piti an premye.
Ki sa mwen vle di pa sa a se, nou kounye a gen enkyete sou de bagay: kòmansman ak yon fen.
Epi sa a, anmèdan. E si nou te ka debarase m de youn nan moun ki paramèt?
Youn nan lide se - we're bay pwoblèm orijinal nou an,
jwenn sòm total la maksimòm de nenpòt subarray nan yon seri [O, n-1].
Epi, koulye a nou gen yon subproblem nouvo, kote nou konnen, nan endèks nou an ki ajou mwen,
nou konnen nou dwe konkli la. Subarray nou an dwe fini nan endèks la ye kounye a.
Se konsa, pwoblèm nan rete a se, ki kote nou ta dwe kòmanse subarray nou an?
sa a fè sans? Oke.
Se konsa, mwen te kode sa a leve, epi kite pou yo gade nan ki sa sa a vle di.
Nan codirectory a, gen nan yon pwogram yo rele subarray,
epi li pran nimewo nan atik,
ak li retounen sòm total la subarray maksimòm nan shuffled lis mwen an.
Se konsa, nan ka sa a, subarray maksimòm nou an se 3.
E se te pran pa jis lè l sèvi avèk 2 ak 1.
Se pou nou kouri l 'ankò. Li la tou 3.
Men, tan sa a, sonje ki jan nou te resevwa 3 a.
Nou te pran an - nou jis pran 3 a li menm
paske li nan antoure pa negatif sou tou de bò,
ki pral pote yon sòm <3.
Se pou nou kouri sou 10 atik yo.
Fwa sa a, li nan 7, nou pran 3 nan dirijan ak 4.
Fwa sa a, li nan 8, epi nou jwenn ke lè yo pran 1, 4 ak 3.
Se konsa, nan ba ou yon entwisyon an sou ki jan nou ka rezoud pwoblèm sa a transfòme,
kite a pran yon gade nan sa a subarray.
Nou ap bay sa a etalaj D ', e nou konnen repons lan se 8.
Nou pran 1 an, 4, ak 3.
Men, se pou pou yo gade nan ki jan nou menm te rive ki repons lan.
Se pou yo gade nan subarray a maksimòm ki te fini nan chak nan sa yo endis.
Ki sa ki nan subarray a maksimòm ki gen nan fen nan pozisyon an premye?
[Elèv] Zewo. >> Zewo. Jis pa pran -5 la.
Isit la li pral yo dwe 0 kòm byen. Yeah?
(Elèv yo, enkonpreansibl)
[Yu] Oh, regrèt, li se yon -3.
Se konsa, sa a se yon 2, sa a se yon -3.
Oke. Se konsa, -4, sa ki nan subarray a maksimòm nan fen ki pozisyon
kote -4 se nan? Zewo.
Youn? 1, 5, 8.
Koulye a, mwen dwe fini nan kote a kote -2 se nan.
Se konsa, 6, 5, 7, ak yon nan dènye se 4.
Lè konnen ke sa yo, se antre mwen
pou pwoblèm nan transfòme kote mwen dwe fini nan chak nan sa yo endis yo,
Lè sa a, dènye repons mwen se jis, pran yon bale atravè tout,
epi pran kantite maksimòm.
Se konsa, nan ka sa a li nan 8.
Sa implique ke subarray a maksimòm fini nan sa a endèks,
e li te kòmanse yon kote anvan li.
tout moun konprann sa a subarray transfòme?
>> Oke. Oke, kite la konpwan ankò la pou sa a.
Se pou nou konsidere jis premye antre yo kèk.
Se konsa, isit la li te 0, 0, 0, 1, 5, 8.
Lè sa a, te gen yon -2 isit la, ak ki te fè li desann nan 6.
Se konsa, si mwen rele antre a nan pozisyon mwen subproblem (mwen),
kouman mwen ka itilize repons lan nan yon subproblem anvan
reponn sa a subproblem?
Si m 'gade nan, kite la di, sa a antre.
Kouman mwen ka kalkile repons lan 6 pa gade
yon konbinezon de sa a etalaj ak repons yo nan subproblems anvan nan sa a etalaj? Wi?
[Fi elèv] Ou pran etalaj la nan sòm total
nan yon pozisyon nan dwa anvan li, se konsa 8 la,
ak Lè sa a, ou ajoute subproblem aktyèl la.
[Yu] Se konsa, sijesyon li se fè yon gade nan de nimewo sa yo,
nimewo sa a ak nimewo sa a.
Se konsa, sa a 8 refere a repons lan pou subproblem a (mwen - 1).
Li kite yo rele A. D 'etalaj mwen
Yo nan lòd yo jwenn yon subarray maksimòm ki fini nan pozisyon mwen,
Mwen gen de chwa: Mwen ka swa kontinye subarray la
ki te fini nan endèks la anvan, oswa kòmanse yon etalaj nouvo.
Si m 'te kontinye subarray a ki te kòmanse nan endèks la anvan,
Lè sa a, sòm total la maksimòm mwen kapab reyalize se repons lan nan subproblem a anvan
plis antre nan etalaj aktyèl.
Men, mwen menm tou nou gen chwa pou yo kòmanse yon subarray nouvo,
nan ka sa a sòm total la se 0.
Se konsa, repons lan se max nan 0, subproblem mwen - 1, plis antre nan etalaj aktyèl.
sa a ankò fè sans?
Ankò nou an, jan nou jis dekouvri, se subproblem mwen
ki egal a maksimòm la nan subproblem a anvan plis antre aktyèl etalaj m 'yo,
ki vle di kontinye subarray anvan an,
oswa 0, kòmanse yon nouvo subarray nan endèks mwen ye kounye a.
E yon fwa nou te bati moute tablo sa a nan solisyon, Lè sa a, dènye repons nou an,
jis fè yon bale lineyè atravè etalaj la subproblem
epi pran kantite maksimòm.
Sa a se yon aplikasyon egzak nan sa mwen jis te di.
Se konsa, nou kreye yon etalaj subproblem nouvo, subproblems.
Antre an premye se swa 0 oswa antre a an premye, maksimòm tout moun sa yo de.
Ak pou tout rès subproblems yo
nou itilize ankò an egzak nou jis dekouvri.
Koulye a, nou kalkile maksimòm la nan etalaj subproblems nou an, epi ki nan dènye repons nou yo.
>> Se konsa, kouman kantite espas yo nou lè l sèvi avèk sa a nan algorithm?
Si ou te sèlman pran CS50, lè sa a ou pa ta ka mwen te diskite espas anpil.
Oke, yon sèl bagay a nòt la ki mwen te rele malok isit la ak n gwosè.
Ki sa ki ki te sijere nou sou sa?
Sa a algorithm itilize espas lineyè.
Nou ka fè pi byen?
Eske gen yon bagay ke ou avi ke se nesesè kalkile repons final la?
Mwen devine yon kesyon pi bon se, ki sa ki enfòmasyon
nou pa bezwen pote tout wout la a la fen?
Koulye a, si nou gade nan de liy sa yo,
nou sèlman pran swen sou subproblem anvan an,
epi nou sèlman pran swen sou maksimòm an nou te janm wè byen lwen tèlman.
Kalkile repons final nou an, nou pa bezwen etalaj a tout antye.
Nou bezwen sèlman nimewo nan dènye, dènye de nonb.
Denye nimewo pou etalaj la subproblem, ak nimewo dènye pou maksimòm la.
Se konsa, an reyalite, nou ka Fuse sa yo pasan ansanm
epi ale nan lineyè espas nan espas konstan.
Kouran sòm twò lwen, isit la, ranplase wòl nan subproblem, etalaj subproblem nou an.
Sòm Se konsa, kounye a, twò lwen, se repons lan nan subproblem a anvan yo.
E ke sòm, se konsa, lwen, pran plas nan max nou an.
Nou kalkile maksimòm a jan nou ale ansanm.
Se konsa, nou ale nan espas lineyè nan espas konstan,
ak nou menm tou nou gen yon solisyon lineyè nan pwoblèm subarray nou an.
>> Sa yo kalite kesyon ki ou pral jwenn pandan yon entèvyou.
Ki sa ki konpleksite nan tan; sa ki konpleksite nan espas?
Èske ou ka fè pi byen? Èske gen bagay ki nesesè kenbe nan jiwon l?
Mwen te fè sa a mete aksan sou analyses ki ou ta dwe pran sou pwòp ou a
kòm w ap travay nan pwoblèm sa yo.
Toujou dwe mande tèt ou, "Èske mwen ka fè pi byen?"
An reyalite, nou ka fè pi bon pase sa a?
Triye nan yon kesyon Trick. Ou pa kapab, paske ou bezwen
omwen li D 'a pwoblèm nan.
Se konsa, reyalite a ke ou bezwen omwen li D 'a nan pwoblèm nan
vle di ke ou pa kapab fè pi bon pase tan lineyè,
ak ou pa kapab fè pi bon pase espas konstan.
Se konsa, sa a se, an reyalite, solisyon an pi byen pwoblèm sa a.
Kesyon? Oke.
>> Stock mache pwoblèm:
"Bay yon etalaj de n nonm antye yo, pozitif, zewo, oswa negatif,
ki reprezante pri a nan yon estòk sou n jou,
ekri yon fonksyon kalkile pwofi a maksimòm ou ka fè
bay sa ou achte ak vann egzakteman 1 stock nan jou sa yo n. "
Esansyèlman, nou vle achte ki ba, vann segondè.
E nou vle konnen ki Peye a pi bon nou ka fè.
Ale tounen nan pwent m 'yo, sa ki se imedyatman klè, repons lan ki pi senp, men li la dousman?
Wi? (Elèv yo, enkonpreansibl) >> Wi.
>> Se konsa, ou ta jis ale menm si ak gade nan pri yo stock
nan chak pwen nan tan, (enkonpreansibl).
[Yu] Oke, kidonk solisyon li - sijesyon li nan informatique
pi ba a ak kalkile pi wo a pa nesesèman travay
paske pi wo a kapab rive anvan ki pi ba a.
Se konsa, sa se solisyon an fòs brital sa a pwoblèm?
Ki sa ki yo se bagay ki de ke mwen bezwen inikman detèmine pwofi a mwen fè? Dwat.
Solisyon an fòs brital se - oh, se konsa, sijesyon George a se nou bezwen wè sèlman de jou
inikman detèmine pwofi a nan de jou sa yo.
Se konsa, nou kalkile chak pè, renmen achte / vann,
kalkile pwofi a, ki ta ka negatif oswa pozitif oswa zewo.
Kalkile pwofi a maksimòm ke nou fè apwè yo fin iteration sou tout pè jou.
Ki pral dènye repons nou yo.
E ke solisyon yo pral O (n ^ 2), paske gen n chwazi de pè -
nan jou ke ou ka chwazi nan mitan jou fen.
Oke, kidonk mwen pa pwal ale sou solisyon an fòs brital isit la.
Mwen pral di ou ke gen nan yon boutèy demi lit n n solisyon an.
Ki sa ki algorithm ou kounye a konnen se n boutèy demi lit n?
Li pa yon kesyon Trick.
>> Rantre zèl. Rantre sòt se n boutèy demi lit n,
ak an reyalite, yon fason pou rezoud pwoblèm sa a se sèvi ak
yon kalite sòt unifye nan lide rele, an jeneral, separe ak konkeri.
Ak lide a se jan sa a.
Ou vle kalkile achte a pi byen / vann pè nan mwatye gòch la.
Jwenn Peye nan pi bon ou ka fè, jis ak n nan premye sou de jou.
Lè sa a, ou vle oompute achte a pi byen / vann pè sou mwatye a dwat,
se konsa n an dènye sou de jou.
Epi, koulye a kesyon an se, ki jan nou rantre sa yo solisyon tounen ansanm?
Wi? (Elèv yo, enkonpreansibl)
>> Okay. Se konsa, kite m 'desine yon foto.
Wi? (George, enkonpreansibl)
>> Egzakteman. Solisyon George a se egzakteman dwa.
Se konsa, sijesyon li ye, se premye kalkile pi byen achte / vann pè a,
ak ki fèt nan mwatye a gòch, kidonk kite a rele ki bò gòch, yo kite.
Pi bon achte / vann pè ki fèt nan mwatye a dwat.
Men, si nou sèlman konpare nimewo sa yo de, nou ap manke ka a
kote nou achte isit la ak vann yon kote nan mwatye a dwat.
Nou achte nan mwatye gòch la, vann nan mwatye a dwat.
Ak pi bon fason yo kalkile pi byen achte / vann pè a ki porte tou de mwatye
se kalkile minimòm la isit la ak kalkile maksimòm an isit la
epi pran diferans yo.
Se konsa, de ka yo kote pè a achte / vann fèt sèlman isit la,
sèlman isit la, oswa sou tou de mwatye yo defini pa twa nimewo sa yo.
Se konsa, algorithm nou yo rantre solisyon nou an tounen ansanm,
nou vle kalkile pi byen achte / vann pè a
kote nou achte sou mwatye nan bò gòch ak vann sou mwatye a dwat.
Ak pi bon fason yo fè sa se kalkile pri ki pi ba a nan mwatye a an premye,
pri ki pi wo nan mwatye nan dwa, epi pran diferans yo.
Rézilta twa pwofi yo, chif sa yo twa, ou pran maksimòm a nan twa a,
ak sa a, se pwofi nan pi bon ou ka fè sou jou sa yo premye ak yon fen.
Isit la liy ki enpòtan yo se nan wouj.
Sa a se yon apèl repetitif kalkile repons lan nan mwatye a gòch.
Sa a se yon apèl repetitif kalkile repons lan nan mwatye a dwat.
Sa yo de pou pasan kalkile min a ak max la sou mwatye nan kite la ak dwa, respektivman.
Koulye a, mwen kalkile pwofi a ki porte tou de mwatye,
ak repons lan final la maksimòm la nan sa yo twa.
Oke.
>> Se konsa, asire w, nou gen yon algorithm, men kesyon an pi gwo se,
ki sa ki konpleksite nan tan sa a?
Ak rezon an poukisa mwen mansyone unifye sòt se ke fòm sa a nan divize repons lan
an de ak Lè sa a, Fusion solisyon nou an tounen ansanm
se egzakteman fòm lan nan sòt unifye.
Se konsa, kite m 'ale nan dire a.
Si nou defini yon t fonksyon (n) yo dwe nimewo a nan etap
pou jou n,
apèl de nou repetitif
yo chak pral koute t (n / 2),
ak gen nan de nan sa yo apèl.
Koulye a, mwen bezwen kalkile minimòm lan nan mwatye a gòch,
ki mwen ka fè nan n / tan 2, plis maksimòm a nan mwatye a dwat.
Se konsa, sa a se jis n.
Lè sa a, plis kèk travay konstan.
Lè sa a ankò ekwasyon
se egzakteman ekwasyon an ankò pou sòt unifye.
Ak nou tout konnen ke unifye sòt se n boutèy demi lit n tan.
Se poutèt sa, se algorithm nou an tou n boutèy demi lit n tan.
sa a iterasyon fè sans?
Jis yon rapèl tou kout sou sa a:
T (n) se nimewo a nan etap sa yo kalkile pwofi a maksimòm
sou kou nan n jou.
Wout la nou fann moute apèl repetitif nou
se lè w rele solisyon nou an sou premye jou yo n / 2,
pou ki nan yon sèl rele,
ak Lè sa a, nou rele ankò sou dezyèm mwatye a.
Se konsa, sa a, se de apèl.
Lè sa a, nou jwenn yon minimòm sou mwatye nan bò gòch, ki nou ka fè nan tan lineyè,
jwenn maksimòm a nan mwatye nan dwa, ki nou ka fè nan tan lineyè.
Se konsa, n / 2 + n / 2 se jis n.
Lè sa a, nou gen kèk travay konstan, ki se tankou fè aritmetik.
Ekwasyon sa a ankò se egzakteman ekwasyon an ankò pou sòt unifye.
Pakonsekan, algorithm chefeul nou an se tou n ale n.
Se konsa, kouman kantite espas yo nou lè l sèvi avèk?
Se pou nou tounen nan kòd la.
>> Yon kesyon pi bon se, konbyen ankadreman chemine nou janm genyen nan nenpòt moman?
Depi nou ap sèvi ak rkursyon,
ki kantite ankadreman chemine detèmine itilizasyon espas nou yo.
Se pou nou konsidere n = 8.
Nou rele chefeul sou 8,
ki pral rele chefeul sou kat antre yo an premye,
ki pral rele yon chefeul sou de antre yo an premye.
Se konsa, chemine nou an, se - sa a se pil nou an.
Lè sa a, nou rele chefeul ankò sou 1,
ak se sa ki ka baz nou an se, konsa nou retounen imedyatman.
Èske nou janm gen plis pase sa a ankadreman chemine anpil?
No Paske chak fwa nou fè yon invoké,
yon invoké repetitif chefeul,
nou divize gwosè nou yo nan mwatye.
Se konsa, la pou maksimòm kantite ankadreman chemine nou janm genyen nan nenpòt moman
se sou lòd la nan boutèy n chemine ankadreman.
Chak ankadreman chemine ki gen yon plas konstan,
ak Se poutèt sa kantite total espas,
kantite lajan maksimòm nan espas nou janm sèvi ak se O (boutèy demi lit n) espas
kote n se kantite jou.
>> Koulye a, toujou mande tèt ou, "Èske nou ka fè pi byen?"
Ak nan patikilye, nou ka diminye sa a nan yon pwoblèm nou te deja rezoud?
Yon allusion: nou sèlman diskite de pwoblèm lòt anvan sa a, e li pa k ap pase yo dwe chefeul.
Nou ka konvèti pwoblèm sa a mache dechanj nan pwoblèm nan subarray maksimòm.
Ki jan nou ka fè sa?
Youn nan ou? Emmy?
(Emmy, enkonpreansibl)
[Yu] Egzakteman.
Se konsa, pwoblèm nan subarray maksimòm,
nou ap chèche pou yon sòm sou yon subarray kontinyèl.
Ak sijesyon Emmy a pou pwoblèm nan aksyon,
konsidere chanjman yo, oswa dèlta yo.
Ak yon foto nan sa a se - sa a se pri a nan yon estòk,
Men, si nou te pran diferans ki genyen ant chak jou youn apre lòt -
se konsa nou wè ke pri a maksimòm, maksimòm pwofi nou te ka fè
se si nou achte isit la ak vann isit la.
Men, se pou pou yo gade nan kontinyèl la - kite pou yo gade nan pwoblèm nan subarray.
Se konsa, isit la, nou ka fè - pral soti isit la isit la,
nou gen yon chanjman pozitif, ak Lè sa a, pral soti nan isit la yo isit la nou gen yon chanjman negatif.
Men, lè sa a, pral soti nan isit la yo isit la nou gen yon gwo chanjman pozitif.
Ak sa yo, se chanjman sa yo ke nou vle rapò kantite jiska jwenn pwofi final nou an.
Lè sa a, nou gen plis negatif chanjman isit la.
Kle a ou diminye nan kantite pwoblèm stock nou an, nan pwoblèm maksimòm subarray nou
se konsidere delta ki genyen ant jou.
Se konsa, nou kreye yon etalaj nouvo rele dèlta,
inisyalize antre nan premye yo dwe 0,
ak Lè sa a, pou chak dèlta (mwen), kite sa dwe diferans lan
nan etalaj opinyon mwen an (mwen), ak etalaj (mwen - 1).
Lè sa a, nou rele pwosedi woutin nou an pou yon maksimòm subarray
pase nan etalaj yon Delta la.
Epi paske subarray maksimòm a se tan lineyè,
ak sa a rediksyon, pwosesis sa a pou kreye sa a etalaj delta,
se tou tan lineyè,
Lè sa a, solisyon an final pou aksyon se O (n) travay plis O (n) travay, se toujou O (n) travay.
Se konsa, nou gen yon solisyon tan lineyè nan pwoblèm nou yo.
tout moun konprann sa a transfòmasyon?
>> An jeneral, yon bon lide ke ou ta dwe toujou gen
se eseye diminye yon pwoblèm nouvo ki w ap wè.
Si li sanble abitye nan yon pwoblèm fin vye granmoun,
eseye diminye li nan yon pwoblèm fin vye granmoun.
Men, si ou ka sèvi ak tout zouti sa yo ke ou te itilize sou pwoblèm nan fin vye granmoun
rezoud pwoblèm nan nouvo.
Se konsa, vlope moute, entèvyou teknik ki difisil.
Pwoblèm sa yo yo se pwobableman kèk nan pwoblèm ki pi difisil
ke ou ta ka wè nan yon entèvyou,
Se konsa, si ou pa konprann tout pwoblèm sa yo ke mwen jis kouvri, li nan oke.
Sa yo se kèk nan pwoblèm yo plis enteresan.
Pratike, pratike, pratike.
Mwen te bay yon anpil nan pwoblèm nan feyè a, se konsa definitivman tcheke sa yo deyò.
Ak bon chans sou entèvyou ou an. Tout resous m 'yo ap afiche nan lyen sa a,
ak youn nan zanmi ansyen mwen te ofri fè Metye entèvyou teknik,
Se konsa, si w ap enterese, imel Will Yao nan ki adrès imel.
Si ou gen kèk kesyon, ou kapab mande m '.
ou nèg gen kesyon espesifik ki gen rapò ak entèvyou teknik
oswa nenpòt ki pwoblèm nou te wè byen lwen tèlman?
Oke. Oke, bon chans sou entèvyou ou an.
[CS50.TV]