Doug LLOYD: Taigi CS50 mes suÅ¾inojome apie iÅ¡ rÅ«Å¡iavimo ir paieÅ¡kos Ä¯vairovÄ algoritmai. Ir kartais ji gali bÅ«ti Å¡iek tiek sudÄtinga iÅ¡laikyti stebÄti, kas algoritmas kÄ daro. Mes tikrai tik nugriebto pavirÅ¡iÅ³ taip pat, yra daug kitÅ³ paieÅ¡ka ir rÅ«Å¡iavimo algoritmÅ³. Taigi Å¡io vaizdo tegul tiesiog uÅ¾trukti keletÄ minuÄiÅ³ iÅ¡bandyti ir distiliuoti kiekvienÄ algoritmÄ iki jos pagrindiniÅ³ elementÅ³ todÄl jÅ«s galite prisiminti, labiausiai Svarbi informacija apie juos ir gebÄti formuluoti skirtumai, jei reikia. 

Pirmasis pasirinkimas rÅ«Å¡iuoti. PagrindinÄ idÄja atrankos rÅ«Å¡iuoti yra rasti maÅ¾iausiÄ nerÅ«Å¡iuotas elementÄ masyve ir sukeisti su Pirmasis nerÅ«Å¡iuotos elementas toje masyvo. Mes sakÄ, kad blogiausio atvejo buvo n kvadratu paleisti laikas, kad. Ir jei norite atÅ¡aukti, kodÄl imtis Å½vilgsnis atrankos rÅ«Å¡iavimo vaizdo. Geriausiu atveju vykdymo metu taip pat n kvadrato. 

Burbulas rÅ«Å¡iuoti, uÅ¾ idÄja, kad viena yra apsikeitimo gretimÅ³ porÅ³. Å tai raktas, kuris padeda jums prisiminti skirtumÄ Äia. Atrankos RÅ«Å¡iuoti tai yra, kiek, rasti smallest-- burbulas RÅ«Å¡iuoti yra apsikeitimo gretimÅ³ porÅ³. Mes apsikeitimo gretimÅ³ porÅ³ elementÅ³, jeigu jie yra iÅ¡ tam, kuris efektyviai bubbles didesnius elementus Ä¯ deÅ¡inÄ, ir tuo paÄiu metu ji taip pat pradeda judÄti maÅ¾esnius elementus Ä¯ kairÄ. Blogiausias atvejis atvejis vykdymo metu burbuliukÅ³ rÅ«Å¡iuoti yra N kvadratu. Geriausiu atveju vykdymo metu Bubble RÅ«Å¡iuoti yra n. Kadangi tokioje situacijoje mes neturime actually-- mes galime nereikia jokiÅ³ apsikeitimo ne visiems. Mes tik turime padaryti vienÄ perduoti visoms n elementÅ³. 

Be Ä¯terpimo rÅ«Å¡iuoti, The PagrindinÄ idÄja Äia keiÄiasi. Å tai dÄl Ä¯terpimo rÅ«Å¡iuoti raktinÄ¯ Å¾odÄ¯. Mes ketiname dÄti vienÄ kartÄ per iÅ¡ masyvo kairÄs Ä¯ deÅ¡inÄ. Ir kaip mes darome, mes ketina perkelti elementus mes jau matÄme, kad paliktume maÅ¾esni, kad reikia, kad tilptÅ³ kaÅ¾kur atgal Ä¯ tÄ surÅ«Å¡iuoti dalÄ¯. Taigi mes statome surÅ«Å¡iuoti masyvo vienas elementas vienu metu, iÅ¡ kairÄs Ä¯ deÅ¡inÄ, ir mes pereiti dalykÅ³ padaryti kambarÄ¯. Blogiausias atvejis paleisti laikas Ä¯terpimo RÅ«Å¡iuoti yra N kvadratu. Geriausiu atveju paleisti laikas yra n. 

Sujungti sort-- raktaÅ¾odÄ¯ Äia yra padalyti ir sujungti. Mes padalinti visÄ masyvÄ, ar tai Å¡eÅ¡is elementus, aÅ¡tuoni elementai, 10000 elements-- mes padalinti jÄ Å¾emyn per pusÄ, per pusÄ, per pusÄ, kol mes turime pagal masyvo n vieno elemento matricos. A n vieno elemento masyvÅ³ rinkinys. Taigi mes pradÄjome su vienu 1000-elementas masyvas, ir mes gauti iki taÅ¡ko, kur mes turi 1000 vieno elemento masyvus. Tada mes pradedame sujungti tuos sub masyvai atgal kartu teisinga tvarka. Taigi mes dvi vieno elemento masyvai ir sukurti dviejÅ³ elementÅ³ masyvas. Mes du dviejÅ³ elementÅ³ masyvai ir sukurti keturiÅ³ elementÅ³ masyvas ir taip toliau ir taip toliau, kol mes vÄl atstatyta vienÄ n elementÅ³ masyvas. 

Blogiausias atvejis paleisti laikas sujungti rÅ«Å¡iuoti yra n kartÅ³ log n. Mes turime n elementÅ³, taÄiau tai apsauginio apvalkalo procesas priima log n Å¾ingsniai gauti atgal Ä¯ visu masyvo. Geriausiu atveju paleisti laikÄ taip pat n Prisijungti n, nes Å¡is procesas tikrai ne nesvarbu, ar masyvas buvo rÅ«Å¡iuojamos ar ne pradÄti. Å is procesas yra tas pats, ten jokiu bÅ«du trumpo jungimo dalykÅ³. Taigi n log n, blogiausiu atveju, N log N geriausiu atveju. 

Mes kalbÄjome apie dviejÅ³ ieÅ¡koti algoritmai. Taigi linijinis paieÅ¡ka yra apie Iteracja. Mes toliau visoje masyvo vienÄ kartÄ, iÅ¡ kairÄs Ä¯ deÅ¡inÄ, bando surasti skaiÄiÅ³ kad mes ieÅ¡kome. Blogiausias atvejis paleisti laikas yra didelis O n. Tai gali uÅ¾trukti mus Iteracja visoje kiekvieno elemento rasti elementÄ Mes ieÅ¡kome uÅ¾, arba paskutinÄje vietoje, arba ne visi. Bet mes negalime patvirtinti, kad iki mes paÅ¾velgÄ viskas. M geriausiu atveju, mes iÅ¡ karto. Geriausiu atveju paleisti laikas linijinis paieÅ¡ka omega 1 d. 

Galiausiai, buvo dvejetainis paieÅ¡kos, kuris reikalauja asorti masyvo. Atminkite, kad tai labai svarbu atsiÅ¾velgti Dirbdami su dvejetainiu paieÅ¡kÄ. Tai bÅ«tina sÄlyga siekiant naudojant it-- masyvo, kad jÅ«s ieÅ¡kote per turi bÅ«ti rÅ«Å¡iuojami. PrieÅ¡ingu atveju, raktinis Å¾odis yra skaldyk ir valdyk. Splitas masyvo Ä¯ pusÄ ir paÅ¡alinti pusÄ elementÅ³ kiekvienÄ kartÄ, kaip jums pereiti per. DÄl Å¡ios Skaldyk ir valdyk ir trupinimo dalykÅ³ pusÄ poÅ¾iÅ«rio, blogiausiu atveju vykdymo metu dvejetainiai paieÅ¡ka log n, kuris yra iÅ¡ esmÄs geriau nei Linijinio PaieÅ¡ka anketa n. Geriausiu atveju vykdymo metu yra ir dar vienas. 

Mes galime rasti jÄ¯ nedelsiant PirmÄ kartÄ mes dalybÄ, bet vÄl prisiminti, kad nors dvejetainis paieÅ¡ka iÅ¡ esmÄs geriau nei tiesinÄs paieÅ¡kos pagal bÅ«ties Å¾urnalas n palyginti n, jums gali tekti eiti per darbo rÅ«Å¡iavimo jÅ«sÅ³ masyvo pirmas, kuris gali padaryti jÄ¯ maÅ¾iau veiksmingas, priklausomai nuo ant Iteracja surÅ«Å¡iuoti dydÅ¾io. 

AÅ¡ Doug Lloyd, tai CS50.