Ondo da, beraz, konplexutasun konputazionala. Just abisu bat pixka bat murgiltze dugu gehiegi far-- aurretik hau zihurrenik artean izango gehien matematika-heavy gauzak CS50 buruz hitz egin dugu. Zorionez, ez da gehiegi erabatekoa izan eta saiatu eta gidatuko zaitugu prozesuan zehar, baina azoka abisu bat apur bat besterik ez. Ez da, pixka bat matematika inplikatutako hemen. Ondo da, ordenan hain egiteko gure baliabide konputazional erabilera benetako world-- in da benetan algoritmoak ulertzeko garrantzitsua eta nola datuak prozesatu dute. Badugu benetan bat algoritmo eraginkor, dugu baliabideen zenbatekoa murriztu dezake horri aurre egiteko, eskuragarri dugu. Algoritmo bat dugu bada hori da lan asko hartzen joan Benetan prozesatu Datu multzo handia, da gehiago behar da eta baliabide gehiago, eta horrek dirua, RAM, gauza mota hori guztia. 

Beraz, gai izatea bat aztertzeko Algoritmo tresna multzo hau erabiliz, Funtsean, galdetzen du question-- du Algoritmo eskala, nola ez du Gero eta gehiago egiten datuen bota dugu? CS50, datuen kopurua gaude lan egitea nahiko txikia da. Oro har, gure programa joan bigarren edo less-- ere exekutatu seguruenik askoz gutxiago batez ere goiz. 

Baina hori jorratzen duen enpresa bat pentsatzen bezeroen milioika ehunka. Eta prozesatu behar dute bezeroen datu hori. Bezeroen kopurua ahala dute handiagoa eta handiagoa lortzen, nik eskatzen joan baliabideak gero eta gehiago. Zenbat gehiago baliabideak? Beno, hori nola araberakoa Algoritmoaren aztertuko ditugu, honetan laukitik tresna erabiliz. When konplexutasuna buruz hitz egiten dugu algoritmo baten zenbaitetan dituzu entzuteko denbora gisa aipatzen da konplexutasuna edo espazio konplexutasuna baina besterik ez gara joan complexity-- deitzeko oro har ari gara buruz hitz egiten Kasurik txarrenean du. Pila txarrena absolutuaren emanda Datu ditugula litezke bota, nola da algoritmo hau joan prozesatu edo datu horiek aurre egiteko? Oro har, dei egiten diegu kasurik txarrenaren Algoritmo big-O baten exekuzio. Beraz, algoritmo bat esan behar ditzake n edo n O O abian egongo karratu. Eta zer gehiago horiek bigarren bat ere esan nahi. 

Batzuetan, ordea, arreta egiten dugu best-kasuan agertokia buruz. Datuen guztia bada nahi dugu eta izango da erabat perfektua izan zen eta hau ezin hobea bidaltzen ari ginen Datu multzo gure algoritmoaren bidez. Nola litzateke kudeatuko du egoera horretan? Batzuetan erreferentzia dugun bezala big-Omega, big-O alderatuta beraz, big-Omega ditugu. Big-Omega best-kasu eszenatokia da. Kasurik txarrenean du Big-O. Oro har, buruz hitz egiten dugu algoritmo bat konplexutasuna, dugu buruz hitz egiten ari Kasurik txarrenean. Beraz, kontuan izan hori. 

Eta klase honetan, oro har ari gara joan du azterketa zorrotza alde batera utzi nahi. Badira zientziak eta eremuak Gauza mota hau eskainita. When arrazoibide buruz hitz egiten dugu algoritmoen bidez, bertan egin dugu pieza-ek pieza askorentzat algoritmoak buruz hitz egiten dugu klasea. Benetan ari gara buruz hitz egiten Bidez pensatzen sen, Ez formulak, edo frogak batera, edo horrelako zerbait. Beraz, ez kezkatu, ez gara gai izan matematika klase handi bat bihurtzen da. 

Beraz konplexutasuna buruz baino ez dugu esan dut galderari, nola eskatu dio delako ez gure algoritmoak kudeatzeko handiago eta ari haiek bota datuak multzo handiago. Beno, zer datu multzo bat da? Zer egin zuen hura esan dut esan nahi dut? Edozein izanda ere egiten gehienak esan nahi du Testuinguru zentzurik, egia esateko. Algoritmo bat, daukagu ​​bada Prozesuak Strings-- ziurrenik gaude katea tamaina buruz hitz egiten. Hori datuen da set-- tamaina, kopurua, egiteko katea osatzen duten pertsonaien. Dugu bati buruz hitz egiten ari bada Algoritmo fitxategiak prozesatzen duen, dugu nola buruz liteke hizketan kilobyteko fitxategi hori osatzen. Eta hori datu-sorta da. Dugu algoritmo bat buruz hitz egiten bada Hori arrayak maneiatzen orokorrago, hala nola algoritmoak bezala algoritmorikerabiltzen bilatuz, ziurrenik ari gara zenbaki buruz hitz egiten array bat osatzen duten elementuen. 

Orain, bat neurtu ahal izango dugu algoritmo bereziki, nuenean, esan dezakegu algoritmo bat neurtzeko, I Esan nahi neurtu ahal izango dugu nola baliabide asko hartzen du. Baliabide horiek diren ala ez, zenbat RAM byte edo megabyte RAM Erabiltzen. Edo zenbat denbora exekutatu hartzen du. Eta hau esan genezake neurtzeko, edonola, n f. Non n kopurua da Datu multzo elementu. Eta n f Somethings zenbat da. Zenbat baliabide unitateak egiten Datu hori prozesatu behar da. 

Orain, egia esan, ez zaintzeko zer n f da, hain zuzen ere. Izan ere, oso gutxitan Borondate dugu Zalantzarik gabe, izango klase dut hau sekula ere Edozein benetan sakon murgiltzea zer f n da azterketa. Besterik ez gara zer f buruz hitz egingo n, gutxi gorabehera, edo zer joera da. Algoritmo bat joera da bere ordena epe altuena aginduei. Eta zer ikusi ahal izango dugu I esan nahi hartuz a Zehatzagoak adibide bat begiratu. 

Beraz, demagun dugun hiru algoritmo ezberdinak. Horietatik lehena hartzen n Baliabide cubed, unitate batzuk Datu tamaina n multzo bat lantzeko. Garamatzan bigarren bildu bat daukagu n cubed plus n karratu baliabideak Datu tamaina n multzo bat lantzeko. Eta hirugarren bat dugu Hori dela in-- exekutatzen algoritmo hartzen n cubed ken 8n karratu Baliabide plus 20 n unitateak algoritmo bat prozesatu tamaina n ezarri datuekin. 

Orain, berriz ere, ez dugu benetan ez dira joan den xehetasun maila honetan sartu. Ziur nago besterik ez dute horiek eman Hemen puntu baten adibide gisa naiz duten I izango da joan bigarren bat egiten da, eta horrek da dugun bakarra benetan axola duten Gauzak joeraren inguruko Datu multzo handiagoa lortu zuen. Beraz, datu multzo txikia da, bada, ez dago benetan aldea nahiko handia algoritmo horietan. Hirugarren Algoritmoa ez hartzen 13 aldiz gehiago, Baliabideen zenbatekoa 13 aldiz handiagoa lehenengoa erlatiboa exekutatu. 

Gure datu-sorta tamaina 10, badago bertan handiagoa da, baina ez du zertan oso handia da, ikusi ahal izango dugu, ez dagoela Egia esan, diferentzia bat pixka bat. Hirugarren Algoritmoa eraginkorragoa bihurtzen. Egia esan, 40% inguru ditu - edo% 60 eraginkorragoa. % 40 zenbat denbora behar izaten ditu. Run daiteke hartu ahal izango du 400 baliabideak unitateak Datu tamaina 10 multzo bat lantzeko. Lehenengo Kontuan izanik bildu, aitzitik, 1.000 baliabideak unitateak hartzen Datu tamaina 10 multzo bat lantzeko. Baina begira zer gertatzen Gure zenbakiak are handiagoa lortzeko. 

Orain, aldea Algoritmo horien arteko hasteko apur bat gutxiago agerian gera dadin. Eta, hain zuzen, ez direla behe-ordena terms-- edo, hobeto esanda, txikiagoa exponents-- termino hasteko garrantzirik bihurtu. Datu multzo baten tamaina bera bada 1.000 eta lehen bildu bilioi bat urrats exekutatzen. Eta bigarren bildu exekutatzen milioi eta milioi bat urrats. Eta hirugarren algoritmoa exekutatzen besterik mila milioi urrats lotsati ere. It bat milioi urrats nahiko askoz. Behe-ordena termino horiek hasteko benetan garrantzirik bihurtu. Eta besterik gabe, benetan behar Mailu etxean point-- du Datu-sarrerarekin tamaina bat baldin bada million-- guztiak horiek hiru pretty much quintillion-- bat bada hartu Nire math correct-- pausoak da Sarrera datu bat prozesatu tamaina milioi bat. Hori urrats asko da. Eta hain zuzen, horietako bat gerta daiteke Pare bat 100.000 edo pare bat hartuko 100 milioi are gutxiago dugu zenbaki bati buruz hitz egiten ari Hori big-- motatako inolako garrantzirik. Hartu ohi dute, guztiak gutxi gorabehera n cubed, eta, beraz, benetan genuke erreferentzia algoritmo horiek guztiak n ordena izateaz gain cubed edo n cubed of big-O. 

Hemen gehiago batzuen zerrenda bat da komun konplexutasun konputazionala klaseak dugula topo egingo in algoritmoak, oro har. Eta, era berean, zehazki, CS50. Hauek dira agindu Oro har, goialdean azkarrena, Oro har, motelena behealdean. Beraz, denbora etengabe algoritmoak joera azkarrena izan da, kontuan hartu gabe tamaina du Sarrera datu pasatzen duzu. Beti eragiketa bat hartzen dute, edo baliabideak unitate bat landu. Baliteke 2, izango da, agian izan 3, agian 4, izango da. Baina kopurua konstante bat da. Ez du aldatzen dira. 

Logaritmikoa denbora algoritmoak zertxobait hobeak dira. Eta adibide benetan ona logaritmikoa denbora algoritmoa duzun bada, ziur aski, dirudienez, orain da urraketaren telefono liburuaren aparte Mike Smith aurkitu telefono-liburuan. Arazoa moztu dugu erditik. Eta beraz, n lortzen handiago gisa eta handiago eta larger-- hain zuzen ere, aldi bakoitzean bi n, bakarrik urrats bat gehiago hartzen du. Beraz, asko hobeto baino, esan, denbora lineala. Zein da bikoiztu n izanez gero, urratsen kopuru bikoitza hartzen du. Hirukoiztu duzun n bada, hartzen hirukoiztu urrats kopurua. Urrats bat aleko. 

Gero gauzak more-- apur bat lortzeko zertxobait gutxiago handia bertatik. Lineal denbora erritmikoa daukazu, batzuetan log denbora lineala deitzen edo besterik nn saioa. Eta adibide bat egingo dugu algoritmo bat dagoela n log n, hau da, oraindik hobea eskailerak quadratic aldia n baino karratu. Edo polinomio denbora, n bi Edozein kopurua bi baino handiagoa. Denbora esponentzialean edo, bertan are worse-- C n da. Beraz kopurua konstante batzuk planteatu sarrera tamaina du boterea. Beraz, ez da 1,000-- du galtzen Datuak sartzea size 1.000 da, C hartuko luke du 1.000 boterera. Da polinomio denbora asko baino okerrago. 

Factorial denbora are okerragoa da. Eta hain zuzen ere, ez dago benetan ez existitzen denbora infinitua algoritmoak, besteak beste, orain arte bezala ergelak deiturikoak, gisa zeinen lana da array bat ausaz nahastuko eta, ondoren, aztertu du horrela antolatu ala ez. Eta ez da, bada, ausaz berriro nahastu array eta egiaztatu du horrela antolatu den ikusteko. Eta zuk ziurrenik imagine-- ahal bezain egoera bat imajinatu dezakezu non txarrena kasuan, borondate horren inoiz benetan sorta batekin hasi. Algoritmo betiko exekutatu litzateke. Eta beraz, hori izango litzateke infinitua denbora algoritmoa. Zorionez, ezin izango da idazten duzun edozein faktore edo infinitua denbora CS50 algoritmoak. 

Beraz, dezagun pixka bat gehiago sinpleagorik begirada hormigoia konputazional konplexutasunaren klaseak. Beraz, adibide bat dugu edo bi adibide hemen denbora konstante algoritmoak, horrek beti hartu kasurik txarrenaren eragiketa bakarrean. Beraz, lehen adibide funtzio bat dela 4 deitzen duzu, eta horrek tamaina 1.000 array bat hartzen du. Baina gero, itxuraz Ez du benetan itxura at it ez du benetan axola zer da horren barruan, array horren. Beti bakarrik lau itzultzen. Beraz, algoritmo hori, dela nahiz 1.000 elementu hartzen ez badu haiekin ezer egin. Just lau itzultzen. Beti da pauso bakar bat. 

Izan ere, gehitu 2 nums-- bertan Nik bezala well-- aurretik dugu bi zenbaki osoen prozesuak. Ez da pauso bakar bat. Egia esan, pare bat urrats. Bat lortuko duzu, lortu duzu b, horiek gehitzen duzunean elkarrekin, eta zuk irteera emaitzekin. Beraz, 84 pausu da. Baina etengabeko beti da, edo b kontuan hartu gabe. Bat eskuratu ahal izango duzu, b, gehitu Haiekin batera, emaitza irteera. Beraz, denbora etengabe algoritmo bat da. 

Hona hemen adibide bat denbora lineala algoritmo garamatzan gets-- algoritmo bat Urrats bat gehiago, seguru asko, Zure sarrera 1 eta hazi ahala. Beraz, demagun bilatzen ari gara 5. zenbakian array baten barnealdea. Baliteke egoera bat non duzu nahiko goiz da aurkitu dezakezu. Baina, era berean, ezin duzu egoera bat non array azken elementua izan liteke. Tamaina 5 array bat, bada ere 5 zenbakia bilatzen ari gara. 5 urrats hartuko luke. Eta hain zuzen ere, imajinatu ez dagoela da Ez 5 array honen edozein lekutan. Oraindik ere, benetan dugu begiratzen array elementu bakar behin izateko zehazteko ere ala ez, 5 dago. 

Beraz, kasurik txarrenaren, hau da, hori ere elementua array azken da edo ez da existitzen. Oraindik ere begiratzen dugu n elementu guztiak. Eta, beraz, algoritmo hau denbora lineal exekutatzen. Hori baieztatu dezakezu arabera Pixka bat estrapolatu esanez, 6-elementu array bat izan badugu eta 5 zenbakia bilatzen ari ginen, 6 urrats iraun dezake. 7-elementu array bat bada, eta 5 zenbakia bilatzen ari gara. 7 urratsetan iraun dezake. Elementu bat gehiago gehitu nahi dugu gure array, urrats bat gehiago hartzen du. Hori algoritmo lineal bat da Txarrena-kasuan. 

Bikote galdera azkar duzu. Zer da runtime-- du zer da kasurik txarrenaren exekuzio kode hau bereziki? Beraz, 4 begizta bat hemen doa daukat tik j funtzioak 0, m gehienez modu guztiak. Eta hemen zer ikusten dut, hori da Begizta gorputza denbora etengabe exekutatzen. Beraz, hori terminologia erabiliz dugu dagoeneko hitz egin zer naizenean kasurik txarrenaren litzateke Algoritmo honen exekuzio? Hartu segundo bat. Barneko begizta zatia denbora etengabe exekutatzen. Eta kanpoaldeko zatia begizta da m aldiz exekutatu behar. Beraz, zein da kasurik txarrenaren exekuzio hemen? Ba m-big-O asmatzen duzu? Eskubidea litzaidake. 

Nola beste bat buruz? Oraingo honetan bat egin behar dugu begizta baten barruan amaitzen da. Kanpoko begizta bat daukagu hutsetik p doa. Eta hori exekutatzen barneko begizta bat daukagu zerotik p, eta horren barruan, Dut adierazi gorputzean dela begizta denbora etengabe exekutatzen. Beraz, zein da kasurik txarrenaren exekuzio kode hau bereziki? Beno, berriz, bat dugu p aldiz exekutatzen duen kanpoko begizta. Eta, aldi bakoitzean iterazio begizta hori, baizik. Barneko begizta bat daukagu hori ere p aldiz exekutatzen. Eta gero, horren barruan, ez da etorri etengabeko aldia gutxi mozkina ez. 

Beraz, kanpoko begizta bat behar badugu p aldiz barruan dagoen huraxe exekutatzen barneko begizta bat dela exekutatzen p zer da garaietatik kasurik txarrenaren exekuzio kode honen? Ba or big-O asmatzen duzun karratu? 

Naiz Doug Lloyd. Hau CS50 da.