[Powered by Google Translate] [Seimineár: Agallaimh Teicniúil] [Kenny Yu, Ollscoil Harvard] [Tá sé seo CS50.] [CS50.TV] Dia duit gach duine, tá mé Kenny. Tá mé faoi láthair ag déanamh staidéir ar eolaíocht ríomhaireachta sóisearach. Tá mé iar-CS TF, agus is mian liom go raibh mé seo nuair a bhí mé underclassman, agus sin an fáth a bhfuil mé ag tabhairt an seimineár seo. Mar sin, tá súil agam go mbainfidh tú taitneamh as é. Is é an seimineár seo faoi agallaimh teicniúla, agus is féidir gach mo acmhainní a fháil ag an nasc seo, an nasc seo ar dheis anseo, cúpla na n-acmhainní. Mar sin, rinne mé liosta de na fadhbanna, i ndáiríre, go leor le roinnt fadhbanna. Chomh maith leis sin ginearálta acmhainní leathanach áit ar féidir linn a leideanna a fháil maidir le conas a ullmhú le haghaidh agallaimh, leideanna maidir le cad ba cheart duit a dhéanamh le linn agallaimh iarbhír, chomh maith le conas a chur chuige fadhbanna agus acmhainní le haghaidh tagartha sa todhchaí. Tá sé ar fad ar líne. Agus díreach chun réamhrá ar an seimineár seo, séanadh, Níor chóir mar seo - a ullmhú do agallamh Níor chóir a bheith teoranta do liosta seo. Tá sé seo i gceist ach amháin a bheith ina threoir, agus ba chóir duit a ghlacadh cinnte gach rud a rá liom le gráin salainn, ach úsáid a bhaint freisin gach rud a úsáid mé chun cabhrú leat i do ullmhú agallamh. 

Tá mé ag dul chun dlús a chur tríd an sleamhnán amach romhainn ionas gur féidir linn a fháil chun an cás-staidéir iarbhír. Struchtúr ar agallamh do postion innealtóireacht bogearraí, de ghnáth go bhfuil sé 30 go 45 nóiméad, babhtaí il, ag brath ar an gcuideachta. Is minic go mbainfidh tú a códú ar bord bán. Mar sin gclár bán mar seo, ach is minic ar scála níos lú. Má tá tú tar éis agallamh teileafóin, beidh tú is dócha a bheith ag baint úsáide as ceachtar collabedit nó Doc Google ionas gur féidir leo a fheiceann tú beo códaithe agus tú á agallamh ar an teileafón. Tá agallamh féin de ghnáth 2 nó 3 fadhbanna tástáil do chuid eolais eolaíocht ríomhaireachta. Agus beidh sé beagnach cinnte i gceist códaithe. Is iad na cineálacha ceisteanna a mbainfidh tú a fheiceáil de ghnáth struchtúir sonraí agus halgartaim. Agus a dhéanamh ar na cineálacha fadhbanna, beidh siad a iarraidh ort, cosúil le, cad é an t-am agus castacht spás, mór O? Is minic a iarrann siad freisin ar leibhéal níos airde ceisteanna, mar sin, a dhearadh córas, conas a leagan amach do chód? Cad iad na Comhéadain, cad ranganna, cad modúil bhfuil tú i do chóras, agus conas a idirghníomhaíonn na chéile? Mar sin, struchtúir sonraí agus halgartaim chomh maith le córais a dhearadh. 

Roinnt leideanna ginearálta sula Léim in ár cás-staidéir. Sílim go bhfuil an riail is tábhachtaí i gcónaí a bheith ag smaoineamh amach os ard. Is é an t-agallamh ceaptha a bheith do dheis a thaispeáint as do phróiseas smaoineamh. Is é an pointe an t-agallamh le haghaidh an t-agallóir a mheas conas a cheapann tú, agus conas a théann tú trí fhadhb. Is é an rud is measa féidir leat a dhéanamh a bheith ciúin ar fud an agallamh ar fad. Sin díreach chomh maith uimh. Nuair a bheidh tú a thugtar ceist, ba mhaith leat freisin chun a dhéanamh cinnte go dtuigeann tú an cheist. Mar sin, arís an cheist ar ais i do chuid focal féin agus iarracht a bheith ag obair chríochnúil cásanna tástála cúpla simplí a dhéanamh cinnte go dtuigeann tú an cheist. Beidh Ag obair trí chásanna tástála cúpla a thabhairt duit freisin ar intuition ar an gcaoi a fhadhb seo a réiteach. D'fhéadfá a fháil amach fiú patrúin cúpla chun cabhrú leat an fhadhb a réiteach. Is é an tip mór chun nach fháil frustrated. Ná fháil frustrated. Agallaimh Tá dúshlánach, ach an rud is measa féidir leat a dhéanamh, chomh maith le bheith ciúin, is é a bheidh frustrated go feiceálach. Ní mian leat leis an tuiscint a thabhairt do agallóir. Rud amháin go bhfuil tú - mar sin, go leor daoine, nuair a théann siad isteach i agallamh, iad ag iarraidh chun iarracht a dhéanamh teacht ar an réiteach is fearr ar dtús, nuair i ndáiríre, níl de ghnáth réiteach glaringly soiléir. D'fhéadfadh sé a bheith mall, d'fhéadfadh sé a bheith mí-éifeachtach, ach ba chóir duit a lua sé ach, ach ionas go mbeidh tú phointe tosaigh as a bheith ag obair níos fearr. Chomh maith leis sin, is é ag cur in iúl an réiteach mall, i dtéarmaí castacht am mór O nó castacht spáis, Beidh léiriú don agallóir go dtuigeann tú na ceisteanna seo nuair a scríobh cód. Ní sin a dhéanamh a bheith eaglach chun teacht suas leis an algartam is simplí ar dtús agus ag obair ansin níos fearr ó ann. Ceisteanna ar bith go dtí seo? Maith go leor. 

Mar sin a ligean ar Léim isteach inár chéad fhadhb. "Mar gheall ar sraith de slánuimhreacha n, scríobh feidhm a Shuffle an eagar san áit sin go bhfuil gach permutations de na slánuimhreacha n seans céanna. " Agus glacadh leis go bhfuil tú ar fáil gineadóir slánuimhir randamach a ghineann slánuimhir i raon ó 0 go dtí mé, raon leath. An bhfuil gach duine a thuiscint cheist seo? Mé a thabhairt duit le sraith de slánuimhreacha n, agus ba mhaith liom a thabhairt duit Suaitheadh ​​é. I mo eolaire, scríobh mé cláir cúpla a thaispeáint cad is ciall agam. Tá mé ag dul Suaitheadh ​​le sraith de 20 eilimintí, ó -10 go 9, agus ba mhaith liom tú a aschur liosta mar seo. Mar sin, is é seo mo sraith ionchur sórtáilte, agus ba mhaith liom a thabhairt duit Suaitheadh ​​é. Beidh muid é a dhéanamh arís. An bhfuil gach duine a thuiscint an cheist? Maith go leor. Mar sin tá sé suas chun tú. Cad iad roinnt smaointe? An féidir leat é a dhéanamh mar n ^ 2, n logáil n, n? Oscailte do mholtaí. Maith go leor. Mar sin, aon smaoineamh, mhol Emmy, Is é an chéad uimhir randamach, slánuimhir randamach, i réimse a ríomh 0-20. Mar sin, glacadh leis go bhfuil ár sraith ar fad de 20. I ár léaráid de 20 eilimintí, is é seo ár sraith ionchur. Agus anois, tá a moladh a chruthú sraith nua, mar sin beidh sé seo an raon aschur. Agus atá bunaithe ar an ais i ag Rand - mar sin má bhí mé, a ligean ar rá, 17, cóip an eilimint an 17ú isteach an chéad staid. Anois, ní mór dúinn a scriosadh - is gá dúinn a athrú ar fad na gnéithe anseo níos mó ná sin go bhfuil bearna ag an deireadh agus ní poill sa lár. Agus anois táimid arís ar an bpróiseas. Anois táimid ag Pioc slánuimhir nua randamach idir 0 agus 19. Tá mé nua anseo, agus cóip muid ngné seo sa phost seo. Ansin againn míreanna athrú thar agus arís againn ar an bpróiseas go dtí go bhfuil muid ár sraith nua go hiomlán. Cad é an t-am a reáchtáil ar an algartam? Bhuel, a ligean ar breathnú ar an tionchar seo. Táimid ag aistriú gach eilimint. Nuair seo a bhaint i, táimid ag aistriú na heilimintí go léir tar éis é a ar an taobh clé. Agus is é sin an (n) O costas mar gheall ar cad má táimid réidh leis an chéad eilimint? Mar sin, le haghaidh gach aistriú, ní mór dúinn a bhaint - dtabhóidh gach aistriú a (n) O oibriú, agus ós rud é tá muid removals n, a thugann sé sin le (n ^ 2) Suaitheadh ​​O. Maith go leor. Mar sin tús maith. Tús maith. 

Tá moladh eile a úsáid rud éigin ar a dtugtar an Suaitheadh ​​Knuth, nó an Suaitheadh ​​Fisher-Yates. Agus tá sé i ndáiríre Suaitheadh ​​am líneach. Agus is é an smaoineamh an-chosúil. Arís, ní mór dúinn ár raon ionchur, ach seachas úsáid a bhaint dhá arrays le haghaidh ár n-ionchur / aschur, úsáidimid an chuid chéad an sraith súil a choinneáil ar ár sciar shuffled, agus táimid ag súil a choinneáil ar, agus ansin fág an chuid eile den ár sraith againn don chuid unshuffled. Mar sin, tá anseo cad is ciall agam. Tús a chur againn amach le - a roghnú againn i, le sraith 0-20. Is é ár pointeoir atá ann faoi láthair atá dírithe ar an innéacs ar dtús. Roghnú muid roinnt anseo i agus anois táimid ag babhtála. Mar sin, má ba é seo 5 agus bhí sé seo 4, Beidh an sraith de thoradh a bheith 5 anseo agus 4 anseo. Agus anois faoi deara againn marcóir anseo. Tá gach rud ar an taobh clé shuffled, agus tá gach rud ar dheis unshuffled. Agus anois is féidir linn arís ar an bpróiseas. Roghnú againn innéacs randamach idir 1 agus 20 anois. Mar sin, is dócha ár nua atá i anseo. Anois táimid ag babhtáil seo i lenár phost nua atá ann faoi láthair anseo. Mar sin, is féidir linn a mhalartú ar ais agus amach é seo. Lig dom a thabhairt suas an cód chun é a dhéanamh níos nithiúla. Tús a chur againn lenár rogha i - tús a chur againn le cothrom liom a 0, ní mór dúinn a roghnú j suíomh randamach sa chuid unshuffled an eagar, a i n-1. Mar sin má tá mé anseo, a roghnú innéacs randamach idir anseo agus an chuid eile den eagar, agus táimid mhalartú. Is é seo go léir ar an gcód is gá chun Suaitheadh ​​do eagar. Ceisteanna ar bith? 

Bhuel, is gá ceist amháin go bhfuil, cén fáth seo ceart? Cén fáth go bhfuil gach permutation chomh dóchúil? Agus ní bheidh mé ag dul tríd an cruthúnas ar seo, ach is féidir go leor fadhbanna san eolaíocht ríomhaireachta a chruthú trí ionduchtú. Cé mhéad de tú eolach ar ionduchtaithe? Maith go leor. Cool. Mar sin, is féidir leat a chruthú ar an cruinneas an algartam trí ionduchtú simplí, i gcás ina mbeadh do hipitéis ionduchtaithe a bheith, glacadh leis go ar ais ar mo Suaitheadh ​​gach seans go cothrom permutation suas go dtí na heilimintí i dtús. Anois, a mheas i + 1. Agus ag an mbealach a roghnaímid ár j innéacs a mhalartú, seo mar thoradh ar - agus ansin tú ag obair amach na sonraí, ar a laghad cruthúnas iomlán cén fáth ar ais an algartam gach permutation le dóchúlacht chomh dócha. 

Gach ceart, fadhb eile. "Mar sin, tugadh le sraith de slánuimhreacha, postive, náid, diúltach, scríobh feidhm a ríomh, ríomhann an tsuim uasta d'aon subarray continueous an eagar ionchuir. " Is sampla anseo, i gcás ina bhfuil gach uimhreacha deimhneacha, ansin faoi láthair ar an rogha is fearr a chur ar an eagar ar fad. 1, 2, 3, 4, is ionann 10. Nuair a bheidh tú roinnt negatives in ann, sa chás seo ba mhaith linn ach an chéad dá mar go mbeidh a roghnú -1 agus / nó -3 thabhairt ar ár suim síos. Uaireanta, d'fhéadfadh muid a bheith chun tús a chur i lár an eagar. Uaireanta, ba mhaith linn a roghnú aon rud ar chor ar bith; tá sé is fearr chun a ghlacadh rud ar bith. Agus uaireanta tá sé níos fearr a chur ar an titim, toisc go bhfuil an rud tar éis é a Super mór. Mar sin, aon smaointe? (Mac léinn, dothuigthe) >> Yeah. Cuir Ní féidir liom a ghlacadh -1. Ansin, ceachtar roghnaigh mé 1,000 agus 20,000, nó I roghnú ach an 3 billiún. Bhuel, tá an rogha is fearr a ghlacadh na huimhreacha go léir. Seo -1, in ainneoin a bheith diúltach, Is é an tsuim iomlán níos fearr ná mar a bhí mé a ghlacadh -1. Mar sin, bhí ar cheann de na leideanna luaigh mé níos luaithe a lua soiléir go soiléir agus ar an réiteach bhfeidhm brute ar dtús. Cad é an réiteach bhfeidhm brute sa fhadhb seo? Yeah? [Jane] Bhuel, Sílim go bhfuil an réiteach bhfeidhm brute Bheadh ​​a chur suas go léir na teaglamaí féideartha (dothuigthe). [Yu] Maith go leor. Dá bhrí sin tá smaoineamh Jane a thógáil gach is féidir - Tá mé paraphrasing - Is é a thógáil gach subarray is féidir leanúnach, ríomh a suim, agus ansin an t-uasmhéid de na subarrays féidir leanúnach a ghlacadh. Cad a aithníonn uathúil a subarray i mo sraith ionchur? Cosúil, cad dhá rud atá de dhíth orm? Yeah? (Mac léinn, dothuigthe) An ceart. >> A níos ísle cheangal ar an innéacs agus innéacs uachtair faoi cheangal uathúil chinneann subarray leanúnach. [Mac léinn Mná] An bhfuil meastachán a dhéanamh ar againn tá sé le sraith de uimhreacha ar leith? [Yu] Uimh Tá Mar sin, a cheist, ag glacadh leis muid ár sraith - Is é ár n-eagar gach uimhir ar leith, agus is é an freagra ar bith. 

Má úsáidimid ár réiteach bhfeidhm brute, ansin na hinnéacsanna tús / deireadh uathúil Cinneann ár subarray leanúnach. Mar sin, má táimid iterate do gach iontráil tús is féidir, agus le haghaidh gach iontráil deireadh> nó = a thosú, agus <n, ríomh tú an tsuim, agus ansin dúinn a chur ar an tsuim uasta againn le feiceáil go dtí seo. An bhfuil sé seo soiléir? Cad é an O mór an réiteach? Timewise. Ní leor n ^ 2. Tabhair faoi deara go bhfuil muid iterate ó 0 go n, mar sin go ceann amháin le haghaidh lúb. Táimid iterate arís ó thús beagnach go deireadh, ceann eile le haghaidh lúb. Agus anois, ina theannta sin, ní mór dúinn a suim suas gach iontráil, mar sin tá go ceann eile le haghaidh lúb. Mar sin, ní mór dúinn trí neadaithe do lúb, n ^ 3. Maith go leor. Téann sé seo mar phointe tosaigh. Is é ár réiteach aon níos measa ná n ^ 3. An bhfuil gach duine a thuiscint an réiteach bhfeidhm brute? 

Maith go leor. Tá réiteach níos fearr ag baint úsáide as smaoineamh ar a dtugtar cláir dinimiciúil. Má tá tú CS124, a bhfuil halgartaim agus Struchtúir Sonraí, beidh tú a bheith an-eolach ar an teicníc. Agus is é an smaoineamh, déan iarracht a thógáil suas ar réitigh ar fhadhbanna níos lú ar dtús. Cad a chiallaíonn mé ag an bhfuil sé seo, atá againn faoi láthair a bheith buartha faoi dhá rud: tús agus deireadh. Agus sin annoying. Cad a tharlaíonn má d'fhéadfadh muid a fháil haitheantas coibhneasta de cheann amháin de na paraiméadair? Tá smaoineamh amháin go - we're tugadh ár fhadhb bunaidh, teacht ar an tsuim uasta aon subarray i raon [O, n-1]. Agus anois táimid tar éis subproblem nua, nuair a fhios againn, inár innéacs reatha i, tá a fhios againn ní mór dúinn i gcrích ann. Ní mór ár subarray deireadh ag an t-innéacs reatha. Dá bhrí sin tá an fhadhb atá fágtha, ba chóir áit linn tús ár subarray? An bhfuil an ciall a bhaint as? Maith go leor. Mar sin, tá mé códaithe seo suas, agus a ligean ar breathnú ar cad a chiallaíonn sé. Sa codirectory, níl clár ar a dtugtar subarray, agus tógann sé líon na míreanna, agus tugann sé an tsuim subarray uasta i mo liosta shuffled. Mar sin, sa chás seo, is é ár subarray uasta 3. Agus tá a tógadh ag díreach ag baint úsáide as 2 agus 1. A ligean ar siúl arís. Tá sé freisin 3. Ach an uair seo, faoi deara conas a fuair muid an 3. Chuir muid an - táimid a ghlacadh ach na 3 féin toisc go bhfuil sé timpeallaithe ag negatives ar an dá thaobh, a thabharfaidh suim <3. A ligean ar siúl ar 10 míreanna. An uair seo tá sé 7, a chur orainn an 3 rá agus 4. An uair seo tá sé 8, agus muid a fháil go trí 1, 4 agus 3. Mar sin, a thabhairt duit ar intuition ar conas is féidir linn a fhadhb seo a réiteach a chlaochlú, a ligean ar ghlacadh le breathnú ar an subarray. Táimid tugtha seo sraith ionchur, agus tá a fhios againn go bhfuil an freagra 8. Glacann muid ar an 1, 4, agus 3. Ach a ligean ar breathnú ar conas a fuair muid i ndáiríre go fhreagra. A ligean ar breathnú ar an subarray uasta a chríochnaigh ag gach ceann de na innéacsanna. Cad é an subarray uasta go bhfuil deireadh ag ionad an chéad? [Mac Léinn] nialais. >> Nialais. Ní Just a dhéanamh a chur ar an -5. Anseo tá sé ag dul a bheith 0 chomh maith. Yeah? (Do mhic léinn, dothuigthe) [Yu] Oh, tá brón orainn, tá sé -3. Mar sin, tá sé seo le 2, tá sé seo -3. Maith go leor. Mar sin, -4 tá, cad é an subarray uasta chun deireadh a phost sin áit a bhfuil -4 ag? Zero. Ceann? 1, 5, 8. Anois, caithfidh mé deireadh ag an suíomh ina bhfuil -2 ag. Mar sin 6, 5, 7, agus an ceann deireanach 4. A fhios agam go bhfuil na mo iontrálacha chun an fhadhb a chlaochlú ina Caithfidh mé deireadh ag gach ceann de na innéacsanna, ansin tá mo freagra deiridh ach, a chur le sweep ar fud, agus a chur ar an líon uasta. Mar sin, sa chás seo tá sé 8. Ciallaíonn sé seo go deireadh an subarray uasta ag an innéacs, agus thosaigh sé áit éigin os a chomhair. An bhfuil gach duine a thuiscint seo subarray chlaochlú? 

Maith go leor. Bhuel, a ligean ar an figiúr amach an atarlú seo. Ligean ar a mheas ach an chéad chúpla iontrálacha. Mar sin anseo a bhí sé 0, 0, 0, 1, 5, 8. Agus ansin bhí -2 anseo, agus a thug sé síos go dtí 6. Mar sin, má ghlaonn mé an iontráil ag seasamh i subproblem (i), conas is féidir liom an freagra a úsáid chun a subproblem roimhe seo chun an cheist seo subproblem? Má mé ag amharc ar, a ligean le rá, an iontráil seo. Conas is féidir liom a ríomh an freagra 6 trí bhreathnú ar meascán de seo, eagar agus na freagraí ar subproblems roimhe seo eagar? Tá? [Mac léinn Mná] a ghlacadh tú an sraith de shuimeanna sa suíomh ceart os a comhair, mar sin na 8, agus ansin cuir tú ar an subproblem reatha. [Yu] Mar sin, tá sí moladh ag féachaint ar na dhá uimhir, an uimhir seo agus an líon sin. Mar sin, tagraíonn sé seo 8 an freagra don subproblem (i - 1). Agus a ligean ar glaoch ar mo A. sraith ionchur D'fhonn a fháil ar subarray uasta a chríochnaíonn ag seasamh i, Tá mé dhá rogha: Is féidir liom leanúint ar aghaidh ceachtar an subarray a chríochnaigh ar an t-innéacs roimhe sin, nó tús a chur le sraith nua. Má bhí mé a leanúint ar an subarray a thosaigh ag an t-innéacs roimhe sin, ansin tá an tsuim uasta is féidir liom a bhaint amach freagra na subproblem roimhe seo móide an iontráil eagar atá ann faoi láthair. Ach, tá mé freisin an rogha a thosú subarray nua, agus sa chás sin an tsuim 0. Mar sin, tá an freagra uasta de 0, subproblem i - 1, móide an iontráil eagar atá ann faoi láthair. An bhfuil an atarlú ciall? Ár atarlú, mar a fuair sé amach againn ach tá subproblem i is comhionann leis an t-uasmhéid an subproblem roimhe móide mo iontráil eagar atá ann faoi láthair, rud a chiallaíonn leanúint ar aghaidh leis subarray roimhe sin, nó 0, tús a chur le subarray nua ar mo innéacs reatha. Agus nuair a ní mór dúinn tógtha suas an tábla seo na réitigh, ansin is é ár freagra deiridh, ach a dhéanamh ar sweep líneach ar fud an raon subproblem agus a chur ar an líon uasta. Is é seo an cur i bhfeidhm beacht cad a dúirt mé díreach. Mar sin, táimid a chruthú sraith subproblem nua, subproblems. Is é an chéad iontráil ceachtar 0 nó an chéad iontráil, an t-uasmhéid den dá. Agus don chuid eile de na subproblems úsáidimid an atarlú cruinn amach againn ach. Anois táimid ag ríomh an t-uasmhéid ar ár sraith subproblems, agus gur ar ár freagra deiridh. 

Mar sin, cé mhéad spás atá in úsáid againn sa algartam? Má tá tú ag glacadh ach CS50, ansin ní bheadh ​​agat a phlé spás mór. Bhuel, tá rud amháin a thabhairt faoi deara gur iarr mé malloc anseo le n méid. Cad a dhéanann a mholadh a thabhairt duit? Úsáideann an algartam spás líneach. An féidir linn a dhéanamh níos fearr? An bhfuil aon rud go tú faoi deara go bhfuil gá a ríomh an freagra deiridh? Buille faoi thuairim mé go bhfuil ceist níos fearr, cén t-eolas ní mór dúinn a dhéanamh an bealach ar fad tríd go dtí an deireadh? Anois, má táimid ar an dá línte seo, linn cúram ach thart ar an subproblem roimhe sin, agus muid cúram ach thart ar an t-uasmhéid againn atá feicthe riamh go dtí seo. A ríomh ar ár freagra deiridh, ní mór dúinn an eagar ar fad. Againn ach is gá an líon seo caite, anuas dhá uimhir. Uimhir seo caite le haghaidh an sraith subproblem, agus uimhir caite le haghaidh an t-uasmhéid. Mar sin, i ndáiríre, is féidir linn a fuse na lúb le chéile agus dul ó spás líneach le spás leanúnach. Tsuim atá ann faoi láthair go dtí seo, anseo in ionad an ról subproblem, ár eagar subproblem. Tsuim sin atá ann faoi láthair, a mhéid, is é an freagra ar an subproblem roimhe sin. Agus an tsuim sin, go dtí seo, glacann an áit a bhí ár max. Ríomh againn an t-uasmhéid mar a théann muid chomh maith. Agus mar sin a théann muid ó spás líneach spás leanúnach, agus ní mór dúinn freisin ar réiteach líneach ar ár fhadhb subarray. 

Tá na cineálacha ceisteanna a gheobhaidh tú le linn agallaimh. Cad é an chastacht am; cad é an chastacht spáis? An féidir leat a dhéanamh níos fearr? An bhfuil rudaí a bhfuil gá leo a choinneáil ar fud? Rinne mé seo aird a tharraingt ar anailísí gur chóir duit a chur ar do chuid féin mar a tá tú ag obair trí mheán na fadhbanna seo. I gcónaí a iarraidh ort féin, "An féidir liom a dhéanamh níos fearr?" Go deimhin is féidir, ní mór dúinn a dhéanamh níos fearr ná é seo? Sórtáil de cheist trick. Ní féidir leat, mar is gá duit ar a laghad, a léamh an t-ionchur ar an bhfadhb. Mar sin, ar an bhfíric gur gá duit ar a laghad an t-ionchur a léamh ar an bhfadhb Ciallaíonn sé seo nach féidir leat a dhéanamh níos fearr ná am líneach, agus ní féidir leat a dhéanamh níos fearr ná spás leanúnach. Mar sin, tá sé seo, i ndáiríre, an réiteach is fearr chun an fhadhb seo. Ceisteanna? Maith go leor. 

Fhadhb margadh stoc: "Mar gheall ar sraith de slánuimhreacha n, dearfach, náid, nó diúltach, a léiríonn an praghas ar stoc thar laethanta n, scríobh feidhm a ríomh ar an brabús mó is féidir leat a dhéanamh ós rud é go leat a cheannach agus a dhíol go díreach 1 stoc laistigh de na laethanta n. " Go bunúsach, ba mhaith linn a cheannach íseal, a dhíol ard. Agus ba mhaith linn a figiúr amach an brabús is fearr is féidir linn a dhéanamh. Ag dul ar ais go dtí mo tip, cad é an soiléir láithreach, freagra simplí, ach tá sé mall? Tá? (Mac léinn, dothuigthe) >> Tá. >> Mar sin, bheadh ​​tú ag dul díreach cé agus breathnú ar na praghsanna stoc ag gach pointe in am, (dothuigthe). [Yu] Maith go leor, mar sin a réiteach - a mholadh na ríomhaireachta nach bhfuil an ísle agus ríomh an líon is airde obair gá mar a d'fhéadfadh an líon is airde a tharlaíonn roimh an ráta is ísle. Mar sin, cad é an réiteach bhfeidhm brute ar an bhfadhb seo? Cad iad an dá rudaí a bhfuil gá dom a chinneadh uathúil an brabús a dhéanamh liom? Ceart. Is é an réiteach bhfeidhm brute - ó, mar sin, moladh Sheoirse is gá dúinn ach dhá lá a chinneadh uathúil an brabús de na dhá lá. Mar sin, táimid ríomh gach péire, cosúil le cheannach / a dhíol, ríomh brabús, d'fhéadfadh a bheith diúltach nó dearfach nó nialas. Ríomh an brabús uasta a dhéanamh linn tar éis iterating thar gach péirí lá. Beidh go bhfuil ár freagra deiridh. Agus beidh go réiteach O (n ^ 2), toisc go bhfuil n dhá phéire a roghnú - na laethanta gur féidir leat a roghnú i measc laethanta deiridh. Maith go leor, mar sin ní mé ag dul chun dul thar an réiteach bhfeidhm brute anseo. Tá mé ag dul a insint duit go bhfuil an log n réiteach. Cén algartam bhfuil a fhios agat faoi láthair go bhfuil n log n? Níl sé ceist trick. 

Cumaisc saghas. Is Cumaisc saghas n log n, agus i ndáiríre, tá bealach amháin a réiteach an fhadhb seo a úsáid chineál saghas merge de smaoineamh ar a dtugtar, i gcoitinne, roinnt agus conquer. Agus is é an smaoineamh mar seo a leanas. Ba mhaith leat a ríomh ar an cheannach is fearr / péire a dhíol sa leath chlé. Faigh an brabús is fearr is féidir leat a dhéanamh, ach leis an chéad n ar feadh dhá lá. Ansin mian leat a oompute an cheannach is fearr / péire a dhíol ar an leath ceart, mar sin n deireanach ar feadh dhá lá. Agus anois tá an cheist, conas is féidir linn a chumasc leis na réitigh ar ais le chéile? Tá? (Do mhic léinn, dothuigthe) >> Maith go leor. Mar sin, lig dom a tharraingt pictiúr. Tá? (George, dothuigthe) >> Go díreach. Tá réiteach Sheoirse go díreach ceart. Mar sin, tá a moladh, a ríomh ar dtús leis an is fearr a cheannach / a dhíol péire, agus a tharlaíonn sa leath chlé, mar sin a ligean glaoch go clé, ar chlé. Fearr a cheannach / a dhíol péire a tharlaíonn i leath ceart. Ach má gcomparáid againn ach an dá uimhir, tá muid ag iarraidh an cás nuair linn a cheannach agus a dhíol anseo áit éigin sa leath ceart. Cheannach muid sa leath chlé, a dhíol sa leath ceart. Agus an bealach is fearr a ríomh is fearr a cheannach / a dhíol péire a théann trasna an dá leath Is é a ríomh an t-íosmhéid anseo agus an t-uasmhéid a ríomh anseo agus a gcuid difríocht. Mar sin, an dá gcásanna ina dtarlaíonn an péire a cheannach / a dhíol ach amháin anseo, ach anseo, nó ar an dá leath sainithe ag na trí uimhreacha. Mar sin, ár n-algartam a chumasadh ár n-réitigh ar ais le chéile, ba mhaith linn a ríomh is fearr a cheannach / a dhíol péire nuair linn a cheannach ar an leath clé agus a dhíol ar an leath ceart. Agus is é an bealach is fearr chun é sin a dhéanamh a ríomh an praghas is ísle sa chéad leath, an praghas is airde sa leath ceart, agus a ghlacadh a difríocht. Is iad na trí bharr sin brabúis, na trí uimhreacha, go dtógfaidh tú an t-uasmhéid de na trí, agus sin é an brabús is fearr is féidir leat a dhéanamh thar na laethanta seo an chéad agus deiridh. Seo iad na línte tábhachtacha i dearg. Is é seo an glao athchúrsach a ríomh an freagra sa leath chlé. Is é seo an glao athchúrsach a ríomh an freagra sa leath ceart. Tá an dá le haghaidh lúb ríomh min agus an uas ar an leath chlé agus ar dheis, faoi seach. Anois liom a ríomh brabús a théann trasna an dá leath, agus is é an freagra deiridh an t-uasmhéid de na trí. Maith go leor. 

Mar sin, cinnte, ní mór dúinn algartam, ach tá an cheist níos mó, cad é an chastacht am seo? Agus is é an fáth a luaigh mé merge sórtáil go roinneann an fhoirm seo an freagra i dhá agus ansin chumasc ár n-réitigh ar ais le chéile é go díreach an cineál saghas chumaiscthe. Mar sin, lig dom dul tríd an tréimhse. Má shainmhínítear muid feidhm t (n) a bheith ar líon na céimeanna le haghaidh laethanta n, ár dhá glaonna recursive Tá gach dul chun costas t (n / 2), agus tá dhá cheann de na glaonna. Anois, is gá dom a ríomh an t-íosmhéid de leath chlé, inar féidir liom a dhéanamh i n / 2 am, móide an t-uasmhéid leath ceart. Mar sin, tá sé seo n go díreach. Agus ansin chomh maith le roinnt oibre i gcónaí. Agus an chothromóid atarlú é go díreach an chothromóid arís le haghaidh saghas chumaiscthe. Agus tá a fhios againn go léir go bhfuil merge sórtáil n logáil n am. Dá bhrí sin, is é ár n-algartam freisin log n am. An bhfuil an leagan ciall? Just a recap gairid seo: Is é T (n) líon na céimeanna a ríomh ar an brabús uasta le linn na laethanta n. An bealach scoilt muid suas ár glaonna recursive Is trí ghlaoch ar ár réiteach ar na laethanta n / 2 an chéad, ionas go bhfuil ceann glaoch, agus ansin tugaimid arís ar an dara leath. Mar sin, go dhá ghlaoch. Agus ansin a fháil againn ar a laghad ar an leath chlé, is féidir linn a dhéanamh in am líneach, teacht ar an uasmhéid an leath ceart, is féidir linn a dhéanamh in am líneach. Mar sin, n / 2 Is é + n / 2 ach n. Ansin tá roinnt oibre leanúnach, atá cosúil a dhéanamh uimhríocht. Is é seo an chothromóid atarlú go díreach ar an chothromóid arís le haghaidh saghas chumaiscthe. Dá réir sin, is é ár algartam Suaitheadh ​​freisin n logáil n. Mar sin, cé mhéad spás atá in úsáid againn? A ligean ar dul ar ais chuig an gcód. 

Tá ceist níos fearr, cé mhéad frámaí Stack bhfuil againn riamh ag aon am ar leith? Ós rud é go bhfuil muid ag baint úsáide as athchúrsáil, chinneann líon na frámaí chairn ár úsáid spáis. Ligean ar a mheas n = 8. Glaoch orainn Suaitheadh ​​ar 8, a ghlaoch Suaitheadh ​​ar na ceithre hiontrálacha, a glaoch ar Suaitheadh ​​ar an dá iontráil ar dtús. Mar sin, is é ár Stack - is é seo ár n-chairn. Agus ansin tugaimid Suaitheadh ​​arís ar 1, agus go cad é ár gcás bonn, mar sin againn ar ais láithreach. An bhfuil muid riamh níos mó ná seo frámaí Stack go leor? Uimh Mar gheall ar gach uair a dhéanann muid ar agairt, a agairt athchúrsach le Suaitheadh, roinnimid ár méid ina dhá leath. Mar sin, an líon is mó de fhrámaí chairn atá againn riamh ag aon am ar leith Is ar an ord frámaí log n chairn. Tá gach fráma Stack spás leanúnach, agus dá bhrí sin an méid iomlán de spás, Is é an t-uasmhéid spáis linn a úsáid riamh O (log n) spás áit a bhfuil n líon na laethanta. 

Anois, i gcónaí a iarraidh ort féin, "An féidir linn a dhéanamh níos fearr?" Agus go háirithe, an féidir linn é seo a laghdú go bhfuil fadhb againn réiteach cheana féin? A leid: plé againn ach dhá fhadhb eile roimhe seo, agus níl sé ag dul a bheith Suaitheadh. Is féidir linn a thiontú ar an bhfadhb margadh stoc isteach an bhfadhb subarray uasta. Conas is féidir linn seo a dhéanamh? Ceann de tú? Emmy? (Emmy, dothuigthe) [Yu] díreach. Mar sin, an fhadhb subarray uasta, táimid ag lorg suim thar subarray leanúnach. Agus moladh Emmy don fhadhb stoic, bhreithniú na n-athruithe, nó deilteanna. Agus is é an pictiúr seo - is é seo an praghas de stoc, ach má bhí muid an difríocht idir gach lá as a chéile - mar sin againn a fheiceáil go bhfuil an praghas uasta, brabús uasta d'fhéadfaí linn a dhéanamh Is é má táimid a cheannach anseo agus a dhíol anseo. Ach a ligean ar breathnú ar an leanúnach - ligean ar breathnú ar an bhfadhb subarray. Mar sin anseo, is féidir linn a dhéanamh - ag dul ó anseo chun anseo, ní mór dúinn a athrú dearfach, agus ansin dul ó anseo chun anseo ní mór dúinn a athrú diúltach. Ach ansin, ag dul ó anseo chun anseo ní mór dúinn a athrú ollmhór dearfach. Agus iad seo na hathruithe a theastaíonn uainn chun achoimre a fháil ar ár brabús deiridh. Ansin tá athruithe níos diúltaí anseo. An eochair chun a laghdú ár fhadhb stoc isteach inár fhadhb subarray uasta Is é a bhreithniú deilteanna idir lá. Mar sin, táimid a chruthú sraith nua ar a dtugtar deilteanna, thúsú an chéad iontráil a bheith 0, agus ansin do gach deilt (i), a ligean ar a bheith ar an difríocht mo eagar ionchur (i), agus eagar (i - 1). Ansin tugaimid ár nós imeachta gnáthamh le haghaidh subarray uasta dul i sraith a deilt ar. Agus toisc go bhfuil subarray uasta am líneach, agus an laghdú seo, an próiseas seo a chruthú eagar deilte, Tá freisin am líneach, ansin tá an réiteach deiridh le haghaidh stoc O (n) obair móide O (n) obair, fós O (n) obair. Mar sin, ní mór dúinn a réiteach am líneach ar ár fhadhb. An bhfuil gach duine a thuiscint athrú seo? 

Go ginearálta, is smaoineamh maith gur chóir duit a bheith i gcónaí Tá iarracht a laghdú fadhb nua go bhfuil tú ag féachaint ar. Má tá sé ar an eolas ar fhadhb d'aois, déan iarracht a laghdú sé le fadhb d'aois. Agus más féidir leat é a úsáid go léir na huirlisí go bhfuil tú a úsáidtear ar an bhfadhb d'aois an fhadhb a réiteach nua. Mar sin, chun wrap suas, tá agallaimh teicniúla dúshlánach. Tá na fadhbanna is dócha roinnt de na fadhbanna níos deacra go mb'fhéidir go mbeadh tú a fheiceáil in agallamh, mar sin más rud é nach dtuigeann tú na fadhbanna a chlúdaítear mé díreach tar éis, tá sé ceart go leor. Seo iad roinnt de na fadhbanna níos dúshlánaí. Cleachtais, cleachtais, cleachtas. Thug mé a lán de na fadhbanna sa bhileog, mar sin cinnte a sheiceáil amach na. Agus dea-luck ar do agallaimh. Gach mo acmhainní sa phost ag an nasc seo, agus tá ceann de mo chairde sinsearach ar fáil a dhéanamh agallaimh teicniúla bréag, mar sin má tá suim agat, Will r-phost Yao ag an seoladh r-phoist. Má tá tú roinnt ceisteanna, is féidir leat a iarraidh orm. An bhfuil tú guys ceisteanna sonracha a bhaineann le hagallaimh teicniúla nó fadhbanna ar bith againn le feiceáil go dtí seo? Maith go leor. Bhuel, luck maith ar do agallaimh. [CS50.TV]