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.