[Powered by Google Translate] Seguruenik duzu entzun azkar edo eraginkorra algoritmoa buruz hitz
zure ataza jakin exekutatzean,
baina zer esan nahi du algoritmo bat azkar edo eraginkorra izango da?
Beno, ez da denbora errealean neurtzeko bati buruz hitz egiten,
segundotan edo minututan bezala.
Hau da, ordenagailuan hardware delako
eta software erabat aldatu egiten da.
Nire programa zurea baino motelagoa exekutatu dezake,
dut delako exekutatzen zaharrago bat ordenagailuan,
edo gertatuko dudalako online bideo-joko bat jolasten
aldi berean, nire memoria hogging
edo izan liteke nire programa exekutatzen ari dira I software ezberdinen bidez
makina komunikatzen desberdinak maila baxua.
Sagarrak eta laranjak alderatzea bezalakoa da.
Just delako nire motelagoa ordenagailua denbora gehiago behar izaten
atzera baino zurea erantzun bat emateko
ez du esan nahi algoritmoa eraginkorragoa duzu.
>> Beraz, ezin dugu, ez baita zuzenean alderatu programak runtimes
segundo edo minutu
nola egin 2 algoritmo ezberdinak konparatzeko
edozein izanik ere beren hardware edo software ingurumena?
Algoritmikoak eraginkortasuna neurtzeko modu uniforme bat sortzeko,
ordenagailu zientzialari eta matematikariek asmatu dute
programa bat konplexutasuna asymptotic neurtzeko kontzeptuak
eta notazio izeneko 'Big Ohnotation'
hau deskribatzeko.
Formal definizioa da funtzioa f (x)
g (x) ordena exekutatzen
(x) balioa batzuk baldin badago, x ₀ eta
batzuk etengabe, C, eta horrek
f (x) baino txikiagoa edo berdina
konstante aldiz g (x)
x guztietan x ₀ baino handiagoa.
>> Baina ez dira beldur urruntzen definizio formala.
Zer esan nahi du benetan gutxiago termino teoriko esan nahi du?
Beno, batez ere da aztertzeko modu bat
programa baten exekuzio nola azkar hazten asymptotically.
Hau da, zure sarrera-tamaina infinitua bidean handitzen
hitza, tamaina 1000 array bat ari zaren ordenatzeko tamaina array bat 10 aldean.
Nola zure programaren exekuzio du hazteko?
Esate baterako, pentsa karaktere kopurua kontatuta
kate batean modurik errazena
Kate osoa paseoan
gutun-letra eta 1 pertsonaia bakoitzak zenbatzaile bat gehituz.
Algoritmo hori esan denbora lineal
karaktere kopurua dagokionez,
'N' katea.
Azken finean, bidez O (n).
Zergatik da hau?
Beno, planteamendu hau erabiliz, denbora eskatzen
kate osoa zeharkatuko
karaktere kopurua proportzionala da.
20 karaktereko katea batean karaktere kopurua zenbatzea
birritan denbora hartzen joan
zenbatzeko pertsonaien 10-karaktereko katea batean,
, pertsonaia guztiek begiratu behar duzu duelako
eta pertsonaia bakoitzak denbora kopuru bera begiratzen du.
Karaktere kopurua handitzen den bezala,
exekuzio sarrerako luzera linealki handitu egingo.
>> Orain, pentsa garai hartan lineala erabakitzen bada,
O (n), besterik gabe, ez zen azkar duzu nahikoa?
Agian ari zaren handi kateak gordetzeko,
eta ezin duzu ordaindu aparteko denbora behar luke
bere pertsonaiak bat-banan kontatuta guztiak zeharkatzeko.
Beraz, zerbait desberdinak saiatzeko erabakitzen duzu.
Zer dagoeneko karaktere kopurua gorde gertatuko balitz
katea, esan, 'Len izeneko aldagai batean,'
Programaren hasieran,
nahiz eta zure katea oso pertsonaia lehen gorde aurretik?
Ondoren, denek dute orain, kate-luzera jakiteko nahi duzuna,
zer da aldagaiaren balioa egiaztatu da.
Ez litzateke duzu katea bera guztietan begiratu,
eta aldagai baten balioa sartzeko Len bezala jotzen da
asymptotically konstante bat dute,
edo O (1).
Zergatik da hau? Beno, gogoratu konplexutasuna asymptotic zer esan nahi du.
Nola tamaina aldaketa exekuzio du
zure input hazten?
>> Esan karaktere kopurua handiagoa katea izan saiatzen ari zaren.
Beno, ez du axola nola handi katea egin duzu,
are gehiago, milioi bat karaktere luze,
Planteamendu honekin katea luzera aurkituko egin nahi duzuna,
aldakorra Len balioa irakurri
horrek dagoeneko.
Sarrerako luzera, hau da, katea luzera aurkitzeko saiatzen ari zaren,
ez nola azkar zure programa exekutatzen eragina.
Programaren zati hau berdin azkar exekutatu litzateke pertsonaia bat-kate bat
eta mila karaktere kate bat,
eta horregatik programa hau izango litzateke, denbora etengabe exekutatzen gisa aipatzen
sarrerako tamaina aldean.
>> Noski, eragozpen bat da.
Aparteko memoria gastatzen duzu zure ordenagailuan
aldagaia gordetzeko
eta denbora gehigarria hartzen du
aldagaiaren benetako biltegiratze egin ahal izateko,
baina puntua dago,
jakiteko zenbat denboraz zure katea izan zen
ez da kate guztietan luzera araberakoa izango da.
Beraz, O (1) edo etengabeko denbora exekutatzen.
Honek, zalantzarik gabe, ez du esan nahi
zure kodea duten 1 urratsean bidez,
baina ez du axola zenbat urrats da,
input tamaina ez bada aldatzen,
oraindik da asymptotically etengabeko O (1).
>> Dezakezu ziurrenik bezala asmatzen,
daude hainbat big O runtimes algoritmoak neurtu ahal izateko.
O (n) ² algoritmoak asymptotically algoritmoak O (n) baino motelagoa.
Hau da, elementu-kopurua (n) hazten da,
O (n) ² algoritmoak azkenean denbora gehiago behar da
O (n) algoritmoak baino exekutatu.
Horrek ez du esan nahi algoritmoak O (n) beti azkarragoa
O (n) ² algoritmoak baino, nahiz eta ingurune berean,
hardware berean.
Agian sarrera txiki tamainak,
O (n) ² algoritmoa agian benetan lan azkarrago,
baina, azkenean, sarrerako tamaina handitzen
infinitura bidean, O (n) ² algoritmoaren exekuzio
joango Eclipse O (n) algoritmoaren exekuzio.
Just edozein funtzio matematiko quadratic
joango overtake funtzio lineala,
ez du axola zenbat buru bat hasteko funtzioa lineala hasten.
Ari zaren datu kopuru handiak lan egiten badu,
algoritmoak O en (n) ² denbora benetan, azkenean, zure programa motelduz,
baina sarrera txiki tamainak,
Ziurrenik ere ez konturatu.
>> Asymptotic konplexutasuna Another da,
logaritmikoa denbora, O (log n).
Algoritmo bat doan hau azkar baten adibidea
binary bilaketa algoritmoa klasikoa da,
elementuen zerrenda bat dagoeneko horrela antolatu elementu bat aurkitzeko.
>> Ezagutzen ez baduzu binary bilaketa duenaren,
Azaldu dut benetan azkar.
Demagun kopurua 3 bilatzen ari zaren
zenbaki osoen array honetan.
Array-erdiko elementu itxura
eta galdetzen du, "elementu baino handiagoa nahi dut, eta, berdin, edo hori baino gutxiago?"
Da berdin, ondoren, handia bada. Elementu aurkitu duzu, eta zu egin.
Da handiagoa bada, elementu badakizu
array eskuinaldean,
eta bakarrik dezakezu begiratu etorkizunean,
da eta txikiagoa bada, badakizu ezkerraldean izango du.
Ondoren, prozesu hori txikiagoa-tamaina array errepikatzen
elementu egokia aurkitu arte.
>> Algoritmo horrek indartsu array tamaina moztu eta eragiketa bakoitzaren erdia.
Beraz, tamaina 8 array bat ordenatuko elementu bat aurkitzeko,
gehienez (saioa ₂ 8),
edo 3, eragiketa horiek
erdiko elementua markatuz, ondoren array ebaketa erdi beharko da,
tamaina 16 array bat hartzen du (saioa ₂ 16), berriz,
edo 4 eragiketa.
Hori da 1 baino gehiago bikoiztu-tamaina array eragiketa.
Array-tamaina bikoiztuz
exekuzio-1 bakarrik zatia kode hau handitzen du.
Berriz ere, zerrendako elementu erdiko markatuta, gero splitting.
Beraz, esan duenez, denbora logaritmikoa jarduteko,
O (log n).
Baina itxaron, esan duzu,
ez mendekoak dira, non zerrendako elementu bilatzen ari zaren?
Zer gertatzen bada begiratzen duzun lehen elementu eskuineko bat izango?
Ondoren, eragiketa 1 soilik hartzen,
Gaia ez nola big zerrendan.
>> Beno, horregatik, ordenagailu zientzialari termino gehiago dituzte
best-kasuan islatzen konplexutasuna asymptotic
eta txarrena-algoritmo bat kasu emanaldiak ere.
Funtzionatzeko, goiko eta beheko mugetatik
exekuzio gainean.
Binary bilaketa kasuan onena, gure elementu
erdian dago,
eta denbora konstante
ez du axola nola big gainerako array da.
Hau erabiltzen den ikurra Ω da.
Beraz, algoritmo hau esan Ω (1) exekutatu.
Kasu honetan onena, elementu aurkitzen da azkar,
ez du axola nola handi array da,
baina kasu horretan, txarrena,
(log n) egiteko split txekeak du
array eskuineko elementu aurkitu.
Kasurik txarrenaren goiko mugetatik big "O" dagoeneko badakizu aipatzen.
Beraz, O (log n), baina Ω (1) da.
>> Lineal bilaketa bat, aitzitik,
oinez array elementu guztietan bidez
nahi duzun bat aurkitzeko,
Ω onena (1) da.
Berriz ere, lehen elementu nahi duzun.
Beraz, ez du axola nola big array da.
Kasurik okerrenean, array azken elementua da.
Beraz, array elementu guztiak n ibiltzeko aurkituko duzu,
nahi ziren 3 bat bila bazabiltza.
Beraz, O (n) denbora exekutatzen
da array elementu kopuru proportzionala delako.
>> Θ One sinbolo gehiago erabiltzen da.
Algoritmoak non onena eta txarrena kasu deskribatzeko erabil daiteke
berdinak dira.
Kate-luzera algoritmoak buruz hitz egiten dugun kasua da.
Hau da, gorde badugu aldagai batean baino lehen
katea gordetzen dugu, eta sartzeko beranduago, denbora etengabe.
Ez dio axola zer zenbaki
aldagai horretan ari gara gordetzeko, begiratu dugu.
Onena gertatzen da, itxura
eta katearen luzera aurkitu.
Ω (1) edo best-kasuan denbora etengabe, beraz.
Txarrena kasua da,
begiratzen dugu, eta katearen luzera aurkitu.
Beraz, O (1) edo kasu txarrenean etengabeko denbora.
Beraz, kasu onena eta txarrena kasu zenetik berberak dira,
hau esan daiteke Θ (1) denbora exekutatu.
>> Laburbilduz, modu ona daukagu ​​arrazoia buruz kodeak eraginkortasuna
mundu real-time exekutatu dute buruz ezer ezagutu gabe,
den faktore kanpoko asko eragin
desberdinak hardware, software,
edo zure kodea berezitasunak.
Era berean, ondo Arrazoia gurekin zer gertatuko da aukera ematen du
denean input gehikuntza tamaina.
>> O (n) ² algoritmoa exekutatzen ari bada,
edo okerrago, O (2 ⁿ) bildu,
bat geroz azkarrena mota,
benetan, moteltzea nabarituko duzu
datu-kantitate handiagoa duten lanean hasteko.
>> Asymptotic konplexutasuna. Eskerrik asko.