>> 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.