>> Doug LLOYD: Allura fil CS50 aħna tgħallmu dwar varjetà ta 'għażla u tiftix
algoritmi.
U xi kultant jista 'jkun ftit delikata biex iżommu
rekord ta 'dak algoritmu ma dak.
Imxejna verament biss xkumat-wiċċ wisq,
hemm tiftix oħra ħafna u l-għażla algoritmi.
Allura f'dan il-video ejja ħu ftit minuti
li tipprova jiddistillaw kull algoritmu l isfel għall-elementi ewlenin tagħha
sabiex inti tista 'tiftakar l-aktar informazzjoni importanti dwarhom
u jkunu kapaċi li tartikula l- differenzi, jekk ikun hemm bżonn.
>> L-ewwel huwa tip ta 'għażla.
L-idea bażika wara sort għażla hu li jinstabu l-iżgħar element mhux magħżul
fil-firxa u tpartit ma 'l- ewwel element mhux magħżul ta 'dak array.
Aħna qal li l-agħar każ ħin run ta 'li kien n kwadrat.
U jekk inti tixtieq li tfakkar għaliex, jieħdu Ħarsa lejn il-video tip għażla.
L-aħjar każ run time huwa wkoll n kwadrat.
>> Sort Bubble, l-idea wara li wieħed huwa li tpartit pari li jmissu magħhom.
Allura dak l-ewlenin li jgħinek ftakar id-differenza hawn.
Għażla sort jiġifieri, s'issa, isibu l-bużżieqa smallest--
sort jiġifieri swap pari li jmissu magħhom.
Aħna tpartit pari li jmissu magħhom ta 'elementi jekk
huma out of order, li effettivament bżieżaq elementi akbar għad-dritt,
u fl-istess ħin li jibda wkoll li jiċċaqalqu elementi iżgħar lejn ix-xellug.
L-agħar każ time każ jibqa 'jiddekorri tal sort bużżieqa huwa n kwadrat.
L-aħjar każ run time ta 'bużżieqa tip huwa n.
Minħabba f'dik is-sitwazzjoni aħna ma actually--
aħna ma jista 'jeħtieġ li tagħmel xi swaps fil-livelli kollha.
Aħna biss għandek tagħmel waħda jgħaddu fl-elementi kollha n.
>> Fil sort inserzjoni, il- idea bażika hawnhekk qed tiċċaqlaq.
Dik hija l-keyword għall tip inserzjoni.
Aħna ser pass darba permezz l-array mix-xellug għal-lemin.
U kif nagħmlu, aħna qed se ċċaqlaq elementi
konna diġà raw biex tagħmel spazju għall dawk iżgħar li jeħtieġ li jitwaħħal x'imkien
lura b'dik il-porzjon magħżula.
Allura aħna nibnu l-array Issortjat wieħed element fi żmien, xellug għal-lemin,
u aħna bidla affarijiet li jagħmlu kamra.
L-agħar każ run time ta sort inserzjoni huwa n kwadrat.
L-aħjar każ run time huwa n.
>> Jingħaqdu sort---keyword hawn huwa maqsum u jingħaqdu.
Aħna maqsuma l-firxa sħiħa, kemm jekk huwa sitt elementi, tmien elementi,
10000 elements-- aħna qasmitha stabbiliti bin-nofs, bin-nofs, bin-nofs,
sakemm ikollna taħt firxa tal arrays element n wieħed.
Sett ta 'arrays element n wieħed.
Allura bdejna ma 'wieħed Firxa 1,000 element,
u aħna jasal sal-punt fejn aħna jkollhom 1,000 arrays one-element.
Imbagħad aħna jibdew jingħaqdu f'dawk is arrays lura flimkien fl-ordni korretta.
Allura aħna jieħdu żewġ arrays one-element u joħolqu firxa żewġ element.
Nieħdu żewġ arrays two-element u joħolqu firxa ta 'erba' element
u hekk u hekk sakemm konna għal darb'oħra inbniet wieħed array element n.
>> L-agħar każ run time ta jingħaqdu sort jiġifieri n żminijiet log n.
Għandna elementi n, iżda dan il-proċess jiżżewweġ
jieħu log n-passi biex tikseb lura għal firxa sħiħa.
L-aħjar każ ħin run hija wkoll log n n għaliex dan il-proċess ma verament
kura jekk l-firxa kienet magħżula jew le biex jibdew bihom.
Il-proċess huwa l-istess, hemm ebda mod biex l-affarijiet ċirkwit qasir.
Allura n log n fl-agħar każ, n log n fl-aħjar każ.
>> Aħna tkellimna dwar żewġ tiftix algoritmi.
Allura tfittxija lineari hija ta 'madwar mtennija.
Aħna tipproċedi madwar l-firxa darba, mix-xellug għal-lemin,
tipprova ssib l-għadd li aħna qed tfittex.
Il-ħin agħar każ run hija O kbir ta 'n.
Jista 'jieħu us mtennija madwar kull element wieħed
biex isibu l-element aħna qed tfittex għal, jew fl-aħħar pożizzjoni,
jew xejn affattu.
Iżda aħna ma tista 'tikkonferma li sakemm konna ħares lejn kollox.
m-aħjar każ, insibu immedjatament.
L-aħjar każ run time ta tfittxija lineari huwa omega-1 ta '.
>> Fl-aħħar nett, kien hemm tfittxija binarju, li teħtieġ firxa assortiti.
Ftakar li l-ħafna konsiderazzjoni importanti
meta jaħdmu mal-tfittxija binarja.
Huwa prerekwiżit għall-użu it-- l-array li qed tfittex permezz
għandhom jiġu magħżula.
Inkella, il-keyword huwa qasma u conquer.
Taqsam il-firxa fil nofs u jelimina nofs mill-elementi
kull darba kif inti tipproċedi permezz.
Minħabba dan firda u conquer u affarijiet qsim fil nofs approċċ,
l-agħar każ run time ta 'tfittxija binarja huwa
log n, li hija sostanzjalment aħjar minn n tfittxija lineari.
L-aħjar każ run time għadu wieħed.
>> Aħna jistgħu jsibuha immedjatament l- ewwel darba nagħmlu diviżjoni, iżda,
għal darb'oħra, ftakar li għalkemm tfittxija binarja huwa
sostanzjalment aħjar minn tfittxija lineari minħabba li jkunu qegħdin log n versus n,
inti jista 'jkollok tmur permezz tax-xogħol tal issortjar array tiegħek ewwel, li
jista 'jagħmilha inqas effettiv jiddependi fuq id-daqs tal-mtennija magħżula.
>> Jien Doug Lloyd, dan huwa CS50.