[Powered by Google Translate] [Merge Triye] [Rob Bowden - Inivèsite Harvard] [Sa a se CS50. - CS50.TV] Se pou nou pale sou sòt unifye. Se konsa, lwen ou te wè sòt bil, sòt ensèsyon, ak sòt seleksyon. Malgre ke m'a kalite vag men m 'nan sa ki mwen vle di yo pa pi bon, rantre sòt jeneralman fè pi bon pase nenpòt nan 3 sa yo kalite. 

Men, anvan ap pale de sòt fizyone, kite nan pale sou Fusion 2 Ranje lis. Nou pral rele pwosesis la nan pran 2 Ranje lis, tankou sa yo, ak fè yon sèl lis Ranje soti nan yo - Fusion bay lis yo. Ki jan nou ka fè sa? Oke, yon sèl lide se jis bwa yon sèl lis sou nan fen lis la lòt ak Lè sa a, klase lis la ki kapab lakòz. 

Pandan ke sa a ap travay, li nan yon anpil nan travay nesesè. Nou ka fè li pi vit pase jis Fouye. Remake yon ide sa ki mal se jis pran altène tas ki soti nan chak lis. Pandan ke sa ka parèt tankou yon ki travay an premye, fè ke nou fini ak 4, 8, 15, 23, 16 - avi ke 16 ak 23 yo soti nan plas li. Sa a se paske 2 eleman ki ta dwe parèt youn apre lòt nan lis la uni yo se nan lis la menm inisyal. Tou de 15 ak 16 yo nan lis la sou bò gòch la. Jwe fent la se pran avantaj de lefèt ke tou de lis yo deja klase. Sa vle di ke si nou jis gade nan eleman yo an premye nan tou de bay lis - isit la, 4 ak 8 - youn nan yo dwe tou pou eleman an premye nan lis la uni. Byen, poukisa se sa? Tou de sa yo bay lis yo deja klase, ak sa swa 4 oswa 8 dwe eleman ki pi piti a, lè nou konbine lis la 2. Nan ka sa a, pi piti a se 4, pou nou ka pran soti 4, epi fè li eleman an premye nan lis uni nou an. Koulye a, nou kontinye Fusion rès 3 eleman ki nan lis nan premye ak 4 eleman nan lis la dezyèm fwa. 

Yon fwa ankò, nou sèlman bezwen gade eleman an premye nan tou de lis. Ki pi piti a nan 2 a dwe eleman an dezyèm nan lis uni nou an. Tan sa a, ant 8 ak 15 pi piti a se 8, epi pou nou insert ki kòm eleman an dezyèm nan Ranje lis nou an. Nou ka kontinye konpare eleman yo an premye nan tou de lis epi yo retire pi piti a nan 2 a. Konparezon 15 ak 23, 15 se pi piti ak pou ke nan eleman twazyèm nou an. Koulye a, konpare 16 ak 23, 16 se pi piti. Se konsa, sa a, se eleman nan katriyèm. 

Remake 2 eleman te soti nan lis la menm nan yon ranje. Sa a se poukisa lis la uni pa kapab jis eleman altène soti nan 2 bay lis yo. Konparezon 50 ak 23, 23 se pi piti, se konsa nou chwazi sa. Ant 50 ak 42, 42 se pi piti. Ant 50 ak 108, 50 se pi piti. Epi, finalman, nou jis gen 108, se konsa li dwe ale sou fen a nan lis nou an. Remake ke nou gen yon bèl, Ranje lis la. Chak fwa nou konpare premye 2 eleman ki nan lis nan 2 nou te kapab detèmine eleman nan pwochen nan lis la uni. Sa vle di ke si lis la final gen nimewo n, kote n isit la se 8, Lè sa a, nou bezwen nan pifò konparezon n jwenn tout moun ki nimewo nan plas la dwat. Tankou yon algorithm te di se kouri nan tan lineyè, men pa enkyete w sou sa isit la. 

Lè l sèvi avèk algorithm nou an pou Fusion, nou ka fè yon sèvis jèn algorithm sòt unifye. Se konsa, kite a Reyajiste lis nou an. Gen 2 gwo etap nan pwosesis pou yo sòt unifye. Premyèman, kontinyèlman fann lis la nan tas nan mwatye jiskaske nou gen yon pakèt moun sou lis ak jis tas 1 nan yo. Pa enkyete w si yon lis gen yon nimewo enpè epi ou pa kapab fè yon koupe parfe pwòp ant yo. Jis abitrèman chwazi ki lis yo mete gode a siplemantè pous Se konsa, kite a fann sa yo lis. Koulye a, nou gen 2 lis. Koulye a, nou gen 4 lis. 

Epi, koulye a nou gen 8 lis ak yon tas sèl nan chak lis. Se konsa, sa a, se li pou etap 1. Pou etap 2, nou repete rantre pè lis lè l sèvi avèk algoritm la unifye nou te aprann anvan. Machin rantre 108 ak 15, nou fini ak lis la 15, 108. Machin rantre 50 ak 4, nou fini ak 4 50,. Machin rantre 8 ak 42, nou fini ak 8, 42. Ak fusion 23 ak 16, nou fini ak 16, 23. Koulye a, tout lis nou yo se nan gwosè 2. Remake chak nan 4 lis la se Klase. 

Se konsa, nou kapab kòmanse Fusion pè lis ankò. Machin rantre 15 ak 108 ak 4 ak 50 - premye pran 4 a, Lè sa a, 15 an, Lè sa a, 50 an, Lè sa a, 108 la. Machin rantre 8, 42 ak 16, 23, nou premye pran 8 a, Lè sa a, 16 an, Lè sa a, 23 an, Lè sa a, 42 la. Se konsa, kounye a nou gen jis 2 bay lis gwosè 4, chak nan yo ki se Klase. Se konsa, kounye a nou rantre sa yo bay lis 2. Premye nou pran 4 a. Lè sa a, nou pran 8 la. Lè sa a, nou pran 15 an ak 16 an, Lè sa a, 23, Lè sa a, 42, Lè sa a, 50, Lè sa a, 108. Ak nou ap fè. Nou kounye a gen yon lis Ranje. Se konsa, kouman vit te sa a, egzakteman? An tèm teknik, rantre sòt se O (n boutèy demi lit n), Lè nou konsidere ke tout sòt bil, sòt ensèsyon, ak sòt seleksyon yo se O (n ²). An reyalite, kòm ou pral aprann vit, ou pa yo pral kapab vini ak yon sòt ki fè pi bon pase O (n boutèy demi lit n) nan ka jeneral la. Yon fwa ankò, pa enkyete sou sa a notasyon gwo O, si ou pa fin wè li ankò. 

Jis konnen ke sa a vle di si nou te vle sòt yon lis reyèlman gwo sòt bil, sòt ensèsyon, ak seleksyon sòt te kapab potansyèlman pran siyifikativman pi long pase rantre zèl. Li pa vle di ke unifye sòt yo ap pi vit pou tout lis oswa menm pou nenpòt ki lis sèl anba yon gwosè a sèten. Pou egzanp, sòt ensèsyon ta ka sòt nan pi rapid pou tout lis ki pi piti pase 5 eleman. Nan pratik, rantre sòt se nòmalman pi vit pou bay lis tankou ti jan 50 eleman. 

Men, sa a vitès siplemantè pa vini san yon pri. Kontrèman ak kalite lòt nou an, ki pran yon lis epi modifye lis la nan plas jiskaske nou jwenn yon lis Ranje, rantre sòt bezwen kèk espas anplis rantre 2 bay lis yo ansanm. Nou pa kapab imedyatman sèvi ak lis la sa ki te fizyone nan magazen lis la uni depi nou ta ka pase sou desizyon eleman ki toujou bezwen yo dwe fizyone. Espas sa a se yon ti jan nan yon pri, men li anjeneral se pa rezonab. Epi sa a, li pou sòt unifye. 

Non mwen se Rob Bowden, ak sa a se CS50. [CS50.TV] - Ak seleksyon zèl. [Ri] Oh, te rive nan pran ki soti tou paske mwen chanje ki jan mwen te prezante li. Lis sou bò gòch la. Sa se te yon Typo. [Misspoke] mwen vise moute - [Ri] Mwen pa konnen sa -