DOUG LLOYD: Do en CS50 ni lernis pri vario de ordigado kaj serĉado algoritmoj. Kaj kelkfoje ĝi povas esti iom malfacila teni trako de kio algoritmo faras kion. Ni vere nur senkremigita la surfaco tro, ekzistas multaj aliaj traserĉado kaj ordigado algoritmoj. Do en ĉi tiu video ni nur preni kelkajn minutojn provi kaj distili ĉiu algoritmo malsupren al sia kerno elementoj do vi povas memori la plej grava informo pri ili kaj povos artiki la diferencoj, se necese. 

La unua estas selektado varon. La baza ideo malantaŭ selektado speco estas trovi la plej malgrandan elementon unsorted en tabelo kaj interŝanĝi ĝin kun la unua unsorted elemento de tiu tabelo. Ni diris ke la plej malbona-kazo kuri tempo de kiu n kvadratoj. Kaj se vi volas memori kial, prenu Rigardu la selektado speco vídeo. La plej kazo tempo de ekzekuto ankaŭ n kvadratoj. 

Bobelo varo, la ideo malantaŭ tiu unu estas interŝanĝi apudajn parojn. Do jen la ŝlosilo kiu helpas vin memori la diferenco ĉi tie. Selektado varo estas, ĝis nun, trovi la smallest-- bobelo varo interŝanĝi apudajn parojn. Ni interŝanĝu najbaraj paroj de elementoj se ili estas el ordo, kiu efike bobelas grandaj elementoj dekstren, kaj samtempe ĝi ankaŭ komencas moviĝi malgrandaj elementoj maldekstren. La plej malbona-kazo kazo tempo de ekzekuto de bobelo varo estas n kvadratoj. La plej kazo tempo de ekzekuto de bobelo varo estas n. Ĉar en tiu situacio ni ne actually-- ni ne bezonas fari ajnan svopoj ajn. Ni nur devas fari unu pasas tra ĉiuj n elementoj. 

En inserción varon, la baza ideo tie estas movanta. Tio estas la ŝlosilvorto por inserción varon. Ni tuj paŝi iam tra la tabelo de maldekstre al dekstre. Kaj kiel ni faras, ni estas tuj movi elementojn Ni jam vidis por fari lokon por malgrandaj ke bezonas persvadi ie reen en tiu ordo parton. Do ni konstruas la ordo tabelo unu elementon je fojo, maldekstre dekstren, kaj ni ŝanĝi aferojn por fari lokon. La plej malbona-kazo tempo de ekzekuto de inserción varo estas n kvadratoj. La plej kazo tempo de ekzekuto estas n. 

Kunfandi sort-- la ŝlosilvorto tie estas fendita kaj kunfandi. Ni disiĝis la plena tabelo, ĉu ĝi estas ses elementoj, ok elementojn, 10.000 elements-- ni fendi ĝin malsupren por la duono, de la duono, de la duono, ĝis ni havas sub tabelo de n unu elemento tabeloj. Aro de n unu elemento tabeloj. Do ni komencis kun unu 1.000-era tabelo, kaj ni atingos la punkto kie ni havas 1,000 unu-era tabeloj. Tiam ni komencas kunfandi tiuj sub tabeloj reen kune en la ĝusta ordo. Do ni prenu du unu-era tabeloj kaj krei du-era tabelo. Ni prenu du du-eraj aroj kaj krei kvar-era tabelo kaj tiel plu kaj tiel plu ĝis ni havas denove rekonstruis unu n elemento tabelo. 

La plej malbona-kazo tempo de ekzekuto de kunfandi varo estas n fojoj logo n. Ni havas n erojn, sed ĉi rekombini procezo prenas log n paŝoj akiri malantaŭo al plena tabelo. La plej bona kazo kuri tempo estas ankaŭ n log n ĉar tiu procezo ne vere gravis ĉu la tabelo estis ordo aŭ ne komence. La procezo estas la sama, estas neniu vojo fuŝkontakto aferojn. Do n log n en la plej malbona kazo, n log n en la plej bona kazo. 

Ni parolis pri du serĉanta algoritmoj. Do lineara serĉo estas pri ripetanta. Ni procedi trans la tabelo unufoje, de maldekstra al dekstra, provante trovi la nombron ke ni serĉas. La plej malbona-kazo tempo de ekzekuto estas granda a de n. Ĝi povus preni nin ripetanta trans ĉiu unuopa elemento trovi la elemento ni serĉas por, ĉu en la lasta pozicio, aŭ tute ne. Sed ni ne povas konfirmi ke ĝis ni rigardis ĉion. m la plej kazo, ni trovas tuj. La plej kazo tempo de ekzekuto de lineara serĉo estas omega de 1. 

Finfine, ekzistis duuma serĉo, kiu postulas diversspeca tabelo. Memoru ke estas tre grava konsidero kiam laborante kun duuma serĉo. Ĝi estas antaŭkondiĉo por uzanta it-- la tabelo kiun vi serĉas tra devas esti ordo. Alie, la ŝlosilvorto estas dividi kaj venki. Fendi la tabelo en duono kaj forigi duonon de la elementoj ĉiufoje kiam vi procedi tra. Pro tiu dividu kaj regu kaj forkiĝanta aferoj en duono alproksimiĝo, la plej malbona-kazo tempo de ekzekuto de duuma serĉo estas logo n, kiu estas substance bona ol lineara serĉo de n. La plej kazo kuri horo estas ankoraŭ unu. 

Ni povus trovi ĝin tuj la unuafoje ni faras dividon, sed, denove, memoru ke kvankam duuma serĉo estas substance bona ol lineara serĉo pro esti log n kontre n, vi eble devas iri tra la verkon de ordiga via tabelo unuaj, kiuj povus fari ĝin malpli efika depende sur la grandeco de la ripetanta ordo. 

Mi Doug Lloyd, tiu estas CS50.