Të gjithë të drejtë, kështu që, kompleksiteti kompjuterike. Vetëm pak e një paralajmërim para se të zhyten në diskutim edhe far-- kjo ndoshta do të jetë në mesin e më të matematikës, të rënda gjëra ne flasim për në CS50. Shpresojmë se nuk do të jetë shumë e madhe dhe ne do të përpiqemi dhe të ju udhëzojë nëpërmjet procesit, por vetëm një grimë e një paralajmërim të drejtë. Ka pak i matematikës të përfshira këtu. Të gjithë të drejtë, kështu që në mënyrë për të bërë përdorimi i burimeve tona kompjuterike në world-- e vërtetë është e vërtetë e rëndësishme për të kuptuar algoritme dhe se si ata përpunojnë të dhëna. Në qoftë se ne kemi një të vërtetë algoritmi efikas, ne mund të minimizuar shumën e burimeve ne kemi në dispozicion për t'u marrë me të. Në qoftë se ne kemi një algoritëm që do të marrë një shumë punë për të përpunuar një të vërtetë grup i madh i të dhënave, kjo është do të kërkojë më shumë dhe më shumë burime, të cilat është e para, RAM, të gjitha atë lloj stuff. 

Pra, duke qenë në gjendje për të analizuar një algorithm përdorur këtë set mjet, në thelb, kërkon question-- si e bën këtë shkallë algorithm si ne hedhin të dhënat e më shumë në atë? Në CS50, sasinë e të dhënave që ne jemi duke punuar me është shumë i vogël. Në përgjithësi, programet tona janë duke shkuar për të kandiduar në një të dytë apo less-- ndoshta shumë më pak veçanërisht në fillim. 

Por mendoni për një kompani që merret me qindra e miliona konsumatorëve. Dhe ata kanë nevojë për një proces se të dhënat e konsumatorëve. Ndërsa numri i klientëve që ata kanë merr më të mëdha, ajo do të kërkojë gjithnjë e më shumë burime. Sa më tepër burime? E pra, kjo varet se si ne analizuar algoritmin, duke përdorur mjetet në këtë Toolbox. Kur ne flasim për kompleksitetin e një algorithm-- që ndonjëherë ju do të dëgjojë atë referuara si kohë Kompleksiteti ose hapësirë ​​kompleksitetin por ne jemi vetëm duke shkuar për të thirrur complexity-- ne jemi përgjithësisht duke folur për skenari më i keq-rast. Duke pasur parasysh grumbull absolute më e keqe e të dhëna që ne mund të jetë hedhur në të, si është ky algoritëm do të përpunojnë ose merren me këto të dhëna? Ne në përgjithësi e quajmë më të keq Runtime e një algoritmi të mëdha-O. Pra, një algoritmi mund të thuhet se drejtuar në O e n ose o të n katror. Dhe më shumë në lidhje me atë ata që do të thotë në një të dytë. 

Ndonjëherë, edhe pse, ne bëjmë kujdes në lidhje me rastin më të mirë. Nëse të dhënat është çdo gjë ne kemi kërkuar ajo të jetë dhe kjo ishte absolutisht e përsosur dhe ne kemi qenë të dërguar këtë të përsosur të vendosur e të dhënave përmes algorithm tonë. Si do të trajtojë në atë situatë? Ne nganjëherë referohen se si madh-Omega, kështu që në kontrast me të madhe-O, ne kemi big-Omega. Big-Omega për rastin më të mirë. Big-O për skenarin më të keq. Në përgjithësi, kur flasim për kompleksiteti i një algoritmi, ne jemi duke folur për rastin më të keq skenari. Pra, mbani në mend. 

Dhe në këtë klasë, ne jemi duke shkuar në përgjithësi për të lënë analizë rigoroze mënjanë. Nuk janë shkencat dhe fusha përkushtuar për këtë lloj stuff. Kur ne flasim për arsyetim përmes algoritme, që ne do të bëjmë copë-nga-pjesë për shumë Algoritme flasim për në klasë. Ne jemi me të vërtetë vetëm duke folur për arsyetuar nëpërmjet saj me sens të përbashkët, jo me formula, apo provave, apo diçka të tillë. Pra, mos u bëni merak, ne nuk do të jetë duke u kthyer në një klasë të madhe të matematikës. 

Kështu që unë tha se ne kujdesemi për kompleksitetin sepse ai bën pyetjen, se si e algoritme tonë të trajtojë më të mëdha dhe dhënave grupe të mëdha duke u hedhur në to. E pra, ajo që është një grup të dhënat? Çfarë dua të them kur kam thënë se? Kjo do të thotë çfarëdo që e bën më kuptim në kontekst, të jetë i sinqertë. Në qoftë se ne kemi një algoritëm, i Proceset Strings-- ne jemi me siguri duke folur në lidhje me madhësinë e vargut. Kjo është të dhënat set-- madhësia, numri e karaktereve që përbëjnë vargun. Në qoftë se ne jemi duke folur për një algorithm se proceset fotografi, ne mund të flasim për mënyrën se si shumë kilobytes e përbëjnë këtë dosje. Dhe kjo është tërësia e të dhënave. Në qoftë se ne jemi duke folur për një algoritmi që trajton vargjeve më në përgjithësi, të tilla si algoritme sorting ose të kërkoni algoritme, ne jemi ndoshta duke folur për numrin e elementeve që përbëjnë një koleksion. 

Tani, ne mund të masë një algorithm-- në mënyrë të veçantë, kur unë them që ne mund të të matur një algoritëm, unë thotë që ne mund të masë se sa shumë burime ajo merr. Nëse këto burime janë, sa bytes RAM-- ose MB RAM ajo përdor. Apo se sa kohë duhet për të drejtuar. Dhe ne mund ta quajmë këtë matur, në mënyrë arbitrare, f e n. Ku n është numri i elementet në grupin e të dhënave. Dhe f e n është se si shumë ca. Sa njësitë e burimeve të bën ajo kërkon për të përpunuar këto të dhëna. 

Tani, ne fakt nuk e kujdesit për atë f e n është pikërisht. Në fakt, ne shumë rrallë will-- sigurisht do të kurrë në këtë unë class-- zhyten në ndonjë të vërtetë të thellë Analiza e asaj f e n është. Ne jemi vetëm do të flasim për atë që f të n është rreth, ose çfarë ajo tenton për të. Dhe tendenca e një algoritmi është diktuar nga urdhër mandatit të tij më të lartë. Dhe ne mund të shohim se çfarë unë të them me këtë, duke marrë një vështrim në një shembull më konkret. 

Pra, le të themi se ne kemi tre algoritme të ndryshme. E para e cila merr n Cubed, disa njësi të burimeve për të përpunuar një sërë të dhënash me madhësi n. Ne kemi një algoritëm të dytë që merr n cubed plus burimet forme katrore n për të përpunuar një sërë të dhënash me madhësi n. Dhe ne kemi një të tretë algorithm që shkon in-- se merr n minus cubed 8n katror plus 20 n njësitë e burimeve të procesit të një algoritmi me të dhënat e përcaktuara me madhësi n. 

Tani përsëri, ne me të vërtetë nuk do për të marrë në këtë nivel të detajuar. Unë jam me të vërtetë vetëm kanë këto deri këtu si një ilustrim i një pikë që unë jam do të jetë bërë në një të dytë, i cili është se ne vetëm me të vërtetë intereson për tendencën e gjërave si të dhënat grupe merrni më të mëdha. Pra, nëse tërësia e të dhënave është i vogël, nuk ka në fakt një ndryshim goxha i madh në këto algoritme. Algoritmi i tretë ka merr 13 herë më shumë, 13 herë shuma e burimeve për të kandiduar në lidhje me një të parë. 

Nëse set dhënat ynë është madhësia e 10, e cila është më e madhe, por jo domosdoshmërisht i madh, ne mund të shohim se ka në fakt pak e një ndryshim. Algoritmi i tretë bëhet më efikase. Kjo është për të vërtetë 40% - ose 60% më të efektshme. Ajo merr 40% sasinë e kohës. Ajo mund të run-- ajo mund të marrë 400 njësitë e burimeve për të përpunuar një sërë të dhënash të madhësisë 10. Ndërsa i pari algorithm, nga ana tjetër, merr 1000 njësi të burimeve për të përpunuar një sërë të dhënash të madhësisë 10. Por shikoni se çfarë ndodh si numrat tanë të merrni edhe më të mëdha. 

Tani, ndryshimi në mes të këtyre algoritmeve të fillojë të bëhet më pak i dukshëm. Dhe fakti se ka ulët rendit terms-- ose më mirë, Termat me exponents-- ulët fillojnë të bëhen të parëndësishme. Në qoftë se një grup të dhënave është e madhësisë 1000 dhe algorithm parë shkon në një miliard hapa. Dhe algoritmi i dytë shkon në një miliard e një milion hapa. Dhe algorithm tretë shkon në vetëm turpërohet prej një miliard hapa. Kjo është shumë e shumë një miliardë hapa. Ato Termat ulët rendit të fillojë për t'u bërë me të vërtetë e parëndësishme. Dhe vetëm për të vërtetë çekiç Shtëpi point-- në qoftë se input të dhënave është i Madhësi A million-- të gjitha tre prej tyre shumë e shumë të marrë një quintillion-- nëse matematikë im është hapa correct-- për të përpunuar një kontribut të dhënave të madhësisë së një milion. Kjo është një shumë e hapa. Dhe fakti se njëri prej tyre mund të marrë një çift 100.000, ose një çift 100 milion edhe më pak kur ne jemi duke folur për një numër se big-- kjo është lloj i parëndësishme. Ata të gjithë kanë tendencë për të marrë përafërsisht n cubed, dhe kështu ne fakt do i referohemi të gjitha këto algoritme si me urdhër të n Cubed ose i madh-o i n kub. 

Këtu është një listë e disa prej më të klasa të zakonshme kompjuterike kompleksiteti se ne do të hasni në algoritme, në përgjithësi. Dhe gjithashtu në mënyrë specifike në CS50. Këto janë urdhëruar nga përgjithësisht më të shpejtë në krye, në përgjithësi slowest në fund. Pra, algoritme kohë konstante tentojnë të jetë më e shpejtë, pa marrë parasysh i madhësisë e Futja e të dhënave ju të kalojë në. Ata gjithmonë të marrë një operacion ose një njësi e burimeve për t'u marrë me të. Ajo mund të jetë 2, ajo mund të jetë 3, mund të jetë 4. Por kjo është një numër konstant. Ajo nuk ndryshon. 

Algoritme kohë logaritmike janë pak më të mirë. Dhe një shembull të vërtetë të mirë të një algoritmi logaritmike kohë ju keni parë me siguri deri tani është vrullshëm përveç i librit telefonit për të gjetur Mike Smith në librin e telefonit. Ne prerë problemin në gjysmë. Dhe kështu si n merr më të mëdha dhe më të mëdha dhe larger-- në fakt, çdo herë që të dyfishtë n, ajo merr vetëm një hap më shumë. Pra, kjo është shumë më mirë se, të themi, koha lineare. E cila është në qoftë se ju të dyfishtë n, ajo merr dyfishin e numrit të hapave. Nëse ju trefishojë n, ajo merr trefishojë numrin e hapave. Një hap për njësi. 

Atëherë gjërat merrni një more-- vogël më pak e madhe nga atje. Ju keni kohë linear ritmike, nganjëherë quajtur log herë linear ose vetëm n log n. Dhe ne do një shembull e një algoritmi që shkon në n log n, e cila është ende më mirë se time-- n katror katror. Ose kohë polinom, n dy çdo numër i madh se dy. Ose kohë eksponenciale, e cila edhe worse-- C me n. Pra, disa numër konstante ngritur në fuqia e madhësisë së kontributit. Pra, nëse nuk ka 1,000-- nëse Futja e të dhënave është e madhësisë 1.000, ajo do të marrë C fuqisë 1,000th. Kjo është një shumë më keq se sa kohë polinomit. 

Ora faktorial është edhe më keq. Dhe në fakt, ka të vërtetë të bëjë ekzistojnë algoritme kohë pafund, të tilla si, e ashtuquajtura sort-- budalla të cilit Detyra është që rastësisht riorganizimi një grup dhe pastaj kontrolloni për të parë nëse është e renditura. Dhe në qoftë se kjo nuk është, rastësisht riorganizimi array përsëri dhe kontrolloni për të parë nëse është e renditura. Dhe si ju ndoshta mund të imagine-- ju mund të imagjinoni një situatë ku në më të keq, që vullneti i kurrë nuk të vërtetë të fillojë me rrjet. Kjo algorithm do të kandidojë përgjithmonë. Dhe kështu që do të jetë një algorithm kohë pafund. Shpresojmë se ju nuk do të jetë me shkrim çdo kohë faktorial ose i pafund Algoritme në CS50. 

Pra, le të marrin një pak më shumë vështrim konkrete në disa thjeshtë Klasat kompjuterike kompleksitetit. Pra, ne kemi një example-- ose dy shembuj here-- e algoritme kohë të vazhdueshme, që gjithmonë të marrë një operacion të vetëm në më të keq. Pra, të example-- parë ne kemi një funksion 4 thirrje për ju, që merr një grup të madhësisë 1,000. Por pastaj me sa duket ka të vërtetë nuk duket në it-- nuk ka të vërtetë kujdes se çfarë është në brendësi të saj, e atij grup. Gjithmonë vetëm kthehet katër. Pra, kjo algorithm, pavarësisht nga fakti se ajo merr 1000 elemente nuk të bëjë asgjë me ta. Vetëm kthehet katër. Kjo është gjithmonë një hap të vetëm. 

Në fakt, shtoni 2 nums-- që ne kemi parë më parë si well-- vetëm proceset dy integers. Kjo nuk është një hap të vetëm. Është në fakt hapa një çift. Ju merrni një, ju merrni b, ju shtoni ato së bashku, dhe ju prodhimit rezultatet. Pra, kjo është 84 hapa. Por është gjithmonë konstante, pavarësisht nga një ose b. Ju duhet të merrni një, të merrni b, shtoni ata së bashku, prodhimi rezultati. Pra, kjo është një algoritëm konstante kohë. 

Ja një shembull i një algorithm-- kohë lineare një algoritmi që gets-- që merr një hap tjetër, ndoshta, si input juaj rritet me 1. Pra, le të thonë se ne jemi duke kërkuar për numri 5 brenda një grup. Ju mund të keni një situatë ku ju mund të gjeni atë mjaft herët. Por ju gjithashtu mund të ketë një situatë ku ajo mund të jetë element i fundit i vektorit. Në një rrjet të madhësisë 5, në qoftë ne jemi duke kërkuar për numrin 5. Ajo do të marrë 5 hapa. Dhe në fakt, imagjinoni se ka jo 5 kudo në këtë grup. Ne ende të vërtetë duhet të shikojmë në çdo element i vetëm i vektorit në mënyrë të përcaktuar nëse janë apo jo 5 është atje. 

Pra, në rastin më të keq, i cili është se element është i fundit në grup apo nuk ekziston fare. Ne ende duhet të shikoni në të gjithë elementet n. Dhe kështu kjo algoritëm shkon në kohë lineare. Ju mund të konfirmojë se nga nxjerrjen pak duke thënë: në qoftë se kemi pasur një koleksion të 6-element dhe ne kemi qenë në kërkim për numrin 5, ajo mund të marrë 6 hapa. Në qoftë se ne kemi një rrjet të 7-element dhe ne jemi duke kërkuar për numrin 5. Ajo mund të marrë 7 hapa. Si ne shtoni një element më shumë për tonë grup, ajo merr një hap më shumë. Kjo është një algoritmi linear në rastin më të keq. 

Çifti pyetje të shpejtë për ju. Çfarë është runtime-- çfarë është më të keq-rast runtime e këtij copë të veçantë të kodit? Kështu që unë kam një lak 4 këtu që shkon nga j barabartë me 0, gjatë gjithë rrugës deri në m. Dhe ajo që unë jam duke parë këtu, është se trupi i lak shkon në kohë të vazhdueshëm. Pra, duke përdorur terminologjinë që ne kemi folur tashmë? Për çfarë do të ishte më i keq i rastit Runtime e këtij algoritmi? Merrni një të dytë. Pjesa e brendshme e lak shkon në kohë të vazhdueshme. Dhe pjesa e jashtme e lak do të kandidojë m herë. Pra, çfarë është më të keq rast runtime këtu? A ju me mend të madhe-O i m? Ju do të jetë e drejtë. 

Si në lidhje me një tjetër? Këtë herë ne kemi një lak brenda një lak. Ne kemi një lak e jashtme që shkon nga zero deri f. Dhe ne kemi një lak të brendshme që shkon nga zero në p, dhe brenda kësaj, Unë pohojnë se trupi lak shkon në kohë të vazhdueshme. Pra, çfarë është më të keq rast runtime e këtij copë të veçantë të kodit? E pra, përsëri, ne kemi një lak e jashtme që shkon herë fq. Dhe çdo përsëritje time-- e atij lak, në vend. Ne kemi një lak të brendshme që gjithashtu shkon herë fq. Dhe pastaj brenda se, nuk ka copë konstante time-- pak atje. 

Pra, nëse ne kemi një lak e jashtme që shkon herë p brenda e cila është një lak i brendshëm që shkon p Times-- çfarë është më të keq-rast runtime e këtij copë të kodit? A ju me mend i madh-o i p katror? 

Unë jam Doug Lloyd. Kjo është CS50.