>> DOUG Lloyd: Pra, në CS50 kemi mësuar për një shumëllojshmëri të klasifikim dhe kërkim
algoritme.
Dhe nganjëherë kjo mund të jetë pak e ndërlikuar për të mbajtur
gjurmët e asaj që algorithm bën çfarë.
Ne kemi me të vërtetë vetëm skremuar sipërfaqen shumë,
ka shumë të tjera kërkim dhe klasifikim algoritme.
Pra, në këtë video, le të të marrë vetëm disa minuta
të përpiqen dhe të gjej çdo algorithm deri në elementet e saj themelore
kështu që ju mund të mbani mend më shumë informacione të rëndësishme rreth tyre
dhe të jenë në gjendje të artikulojnë dallimet, nëse është e nevojshme.
>> E para është zgjedhja lloj.
Ideja themelore prapa përzgjedhjes lloj është gjetur elementin më të vogël Unsorted
në një grup dhe të bie në ujdi atë me Elementi i parë unsorted e atij grup.
Kemi thënë se më e keqja, rasti kohë të drejtuar nga që ishte katror n.
Dhe në qoftë se ju doni të kujtojnë pse, të marrë Një vështrim në video përzgjedhjes renditjes.
Më të mirë-Rasti kohë të drejtuar është gjithashtu katror n.
>> Lloj flluskë, ideja që një është që të bie në ujdi çifte ngjitur.
Pra, kjo është çelësi që ju ndihmon mos harroni dallimin këtu.
Përzgjedhja lloj është, deri tani, gjeni flluskë smallest--
lloji është shkëmbim palë ngjitur.
Ne swap palë ngjitur e elementeve në qoftë se ata
janë jashtë funksionit, e cila në mënyrë efektive bubbles elemente më të mëdha në të djathtë,
dhe në të njëjtën kohë ajo gjithashtu fillon për të lëvizur elementet më të vogla në të majtë.
Më e keqja-Rasti kohë drejtuar rasti i flluskë lloji është katror n.
Më të mirë-Rasti kohë të drejtuar i flluskë lloj është n.
Sepse në këtë situatë ne nuk actually--
ne nuk mund të kenë nevojë për të bëjë ndonjë këmbime në të gjitha.
Ne vetëm duhet të bëjë një kalojnë nëpër të gjitha elementet n.
>> Në futje lloj, The Ideja themelore këtu është zhvendosur.
Kjo është fjalen për futje lloj.
Ne jemi duke shkuar për të rritur një herë përmes array nga e majta në të djathtë.
Dhe si ne të bëjmë, ne jemi do të zhvendoset elementet
ne kemi parë tashmë për të bërë vend për ato më të vogla që duhet të përshtaten diku
përsëri në atë pjesë renditura.
Kështu që ne ndërtojmë array renditura një element në një kohë, majta në të djathtë,
dhe ne ndryshim gjëra për të bërë dhomë.
Më e keqja-Rasti kohë të drejtuar nga futje lloj është katror n.
Më të mirë-Rasti drejtuar kohë është n.
>> Merge sort-- fjalen këtu është e ndarë dhe të shkrihej.
Ne të ndarë koleksion të plotë, nëse është gjashtë elemente, tetë elemente,
10.000 elements-- ne ndarë atë poshtë nga gjysma, përgjysmë, përgjysmë,
derisa të kemi nën grup e n një vargjeve element.
Një grup i n një vargjeve element.
Pra, kemi filluar me një 1000-element array,
dhe ne të merrni në pikën ku ne kanë 1.000 vargjeve një element.
Atëherë ne fillojmë të bashkojë këto vargjeve nën përsëri së bashku në mënyrë korrekte.
Pra, ne marrim dy vargjeve një element dhe për të krijuar një grup të dy element.
Ne kemi marrë dy vargjeve dy-element dhe për të krijuar një grup të katër element
dhe kështu me radhë e kështu me radhë derisa ne kemi përsëri rindërtuar një koleksion element n.
>> Më e keqja-Rasti kohë të drejtuar nga bashkojë lloj N herë log n.
Ne kemi elemente n, por ky proces recombining
merr log n hapa për të marrë mbështetur në një koleksion të plotë.
Rasti më i mirë drejtuar kohë është edhe log n n për shkak se ky proces nuk ka të vërtetë
intereson nëse array ishte renditura apo jo për të filluar me.
Procesi është i njëjtë, nuk ka asnjë mënyrë për gjëra qark të shkurtër.
Pra, n log n në rastin më të keq, n log n në rastin më të mirë.
>> Ne folëm për dy kërkim algoritme.
Pra Kërkimi linear është rreth iterating.
Ne të vazhdojë nëpër rrjet një herë, nga e majta në të djathtë,
duke u përpjekur për të gjetur numrin se ne jemi duke kërkuar për të.
Më e keqja-Rasti drejtuar kohë është O e madhe e n.
Ajo mund të na iterating nëpër çdo element të vetme
për të gjetur elementin ne jemi duke kërkuar për, ose në pozitën e fundit,
ose aspak.
Por ne nuk mund të konfirmojë se deri ne kemi shikuar në çdo gjë.
m të mirë-rasti, ne gjejmë menjëherë.
Më të mirë-Rasti kohë të drejtuar nga Kërkimi linear është omega e 1.
>> Së fundi, ka pasur kërko binar, e cila kërkon array ndryshme.
Mos harroni se është një shumë konsideratë e rëndësishme
kur punojnë me kërkimin binar.
Është një parakusht për të përdorur it-- array që ju jeni në kërkim përmes
duhet të ndahen.
Përndryshe, fjalen është Përça dhe sundo.
Split array në gjysmë dhe eliminuar gjysma e elementeve
çdo herë si ju të vazhdojë përmes.
Për shkak të kësaj përça dhe sundo dhe ndarjen gjëra në gjysmën qasje,
rastin më të keq koha kandidojë i kërko binar është
log n, e cila eshte substancialisht më mirë se n kërkim linear së.
Më të mirë-Rasti drejtuar kohë është ende një.
>> Ne mund të gjeni atë menjëherë hera e parë që ne kemi bërë një ndarje, por,
përsëri, mos harroni se megjithëse kërko binar është
dukshëm më mirë se kërkim lineare duke u mbështetur në të qenit log n kundrejt n,
ju mund të keni për të shkuar nëpërmjet punës i sorting rrjet tuaj të parë, e cila
mund të bëjë atë më pak efektive në varësi në madhësinë e iterating renditura.
>> Unë jam Doug Lloyd, kjo është CS50.