>> 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.