[Powered by Google Translate] Verjetno ste že slišali ljudi govoriti o hitro in učinkovito algoritem Za izvedbo svoje posebno nalogo, Ampak kaj točno to pomeni za algoritmu, ki se hitro in učinkovito? No, to ne govorimo o merjenju v realnem času, kot sekund ali minut. To je zato, ker računalniške strojne opreme in programske opreme, znatno razlikujejo. Moj program lahko teče počasneje, kot je tvoj, ker sem njegov tek na starejšem računalniku, ali zato, ker sem se zgodi, da se igrajo spletne video igre ob istem času, ki je Pregib vse moj spomin ali bi jaz vodil svoj program skozi različne programske opreme , ki je povezan z napravo drugače na nizki ravni. To je tako kot bi primerjali jabolka in pomaranče. Samo zato, ker moj računalnik počasnejši traja dlje kot tvoja vrne odgovor ne pomeni, da imate bolj učinkovito algoritem. 

Torej, ker ne moremo neposredno primerjati runtimes programov v sekundah ali minutah, kako primerjati različne algoritme 2 ne glede na njihovo okolje strojne ali programske opreme? Za ustvarjanje bolj enoten način merjenja učinkovitosti algoritmično, računalniški znanstveniki in matematiki so oblikovale koncepti za merjenje asimptotični kompleksnost programa in zapis se imenuje "Big Ohnotation" za opis tega. Formalna definicija je, da je funkcija f (x) deluje po nalogu g (x) če obstaja nekaj (x) vrednost x ₀ in nekateri konstanta, C, za katera f (x) je manjša ali enaka da stalno krat g (x) za vse x večji od x ₀. 

Ampak ne boj se, proč z uradnim opredelitev. Kaj to dejansko pomeni v manj teoretski način? No, to je v bistvu način za analizo kako hitro raste programa runtime asimptotično. To je, kot je velikost vaše vnose poveča do neskončnosti, pravijo, da ste sortiranje paleto velikosti 1000 v primerjavi z matriko velikosti 10. Kako teka programu rastejo? Predstavljajte si, prešteje število znakov v nizu najenostavnejši način  s hojo skozi celoten niz Pismo, ki ga črk in dodaja 1 do števca za vsak znak. Ta algoritem je dejal, da deluje v linearnem času glede na število znakov, "N" v nizu. Skratka, ta deluje v O (n). Zakaj je tako? No, s tem pristopom, je čas, potreben za prečkanje celotnega niza je sorazmerna s številom znakov. Prešteje število znakov v 20-znakovni niz bo trajalo dvakrat dlje kot traja za štetje znakov v 10-znakovni niz, ker moraš gledati na vse znake in vsak lik ima enako količino časa, da pogledate. Ko se poveča število znakov, runtime bo linearno povečal z vhodno dolžino. 

Zdaj pa si predstavljajte, če ste se odločili, da linearni čas, O (n), prav tako ni bil dovolj hiter za vas? Morda ste shranjevanje velikih nizov, in si ne more privoščiti več časa, da bi potrebovali za prečkanje vseh njihovih znakov štetje eno-by-1. Torej, ste se odločili, da poskusimo nekaj drugega. Kaj pa, če bi se zgodi, da že shranjevanje število znakov v nizu, recimo, v spremenljivko, imenovano "len" zgodaj v programu, še preden se hranijo zelo prvi znak v vašem nizu? Potem, vsi bi si morali storiti zdaj, če želite izvedeti niz dolžine, preverite, kaj se je vrednost spremenljivke. Če ne bi bilo treba pogledati v nizu sama na vse, in dostopa do vrednosti spremenljivke, kot len ​​šteje asimptotično konstantna čas delovanja, ali O (1). Zakaj je tako? No, ne pozabite, kaj asimptotična kompleksnosti. Kako runtime spremembe glede velikosti od vaših vložkov raste? 

Povejte, da ste bili poskuša priti število znakov v večji niz. No, ne bi bilo pomembno, kako velik naredite niz, celo milijonov znakov, Vsi bi morali storiti, da bi našli dolžino niza, je s tem pristopom, je prebral vrednost spremenljivke len, ki jo že. Vhodna dolžina, to je dolžina niza, ki ga poskušate najti, ne vpliva na vse to, kako hitro vaš program teče. Ta del vašega programa naj bi potekal tako hitro na eno niz znakov in tisoč niz znakov, in da je, zakaj bi se ta program imenuje teče nenehno v času glede na vhodni velikosti. 

Seveda, tam je slaba. Ti porabiti dodatnega pomnilnika v računalniku shranjevanje spremenljivke in dodaten čas, da vas popelje narediti dejanski shranjevanje spremenljivke, a bistvo še vedno stoji, ugotovite, kako dolgo je bil niz ni odvisen od dolžine niza sploh. Torej, da teče v času O (1) ali konstantni čas. To pa nikakor ne pomeni nujno kodo, ki teče v koraku 1, ampak ne glede na to, koliko korakov je, če se ne spreminja z velikostjo vložkov, še vedno je asimptotično konstanta, ki jih zastopamo, kot O (1). 

Kot si verjetno lahko uganiti, obstaja veliko različnih veliki O runtimes za merjenje algoritmov s. O (n) ² algoritmi so asimptotično počasnejši od O (n) algoritmov. To pomeni, da je število elementov (n) raste, sčasoma bo O (n) ² algoritmi vzamejo več časa kot O (n), algoritmi za vodenje. To ne pomeni O (n) algoritmi vedno teči hitreje kot O (n) ² algoritmov, celo v istem okolju, na isti strojni opremi. Mogoče za manjše velikosti vhodnih,  O (n) ² algoritem lahko dejansko delajo hitreje, ampak na koncu, kot vhodni velikosti povečuje proti neskončnosti, je O (n) ² algoritma runtime bo sčasoma mrk teka O (n) algoritem. Tako kot vsako kvadratno matematične funkcije  bo na koncu prehitel vse linearno funkcijo, ne glede na to, koliko glav začetek linearno funkcijo se začne s. Če delate z velikimi količinami podatkov, algoritmi, ki se izvajajo v času O (n) ² čas res lahko končala upočasnjuje vaš program, ampak za manjše številke vnosa, verjetno ne boste niti opazili. 

Druga asimptotični kompleksnost, logaritemski čas O (log n). Primer algoritma, ki teče tako hitro Gre za klasično binarno iskanje algoritem, za iskanje elementa v že izločen seznam elementov. 

Če ne veste, kaj binarno iskanje ne, Bom razložil za vas zelo hitro. Recimo, da iščete številko 3 V tem nizom števil. Zdi na srednji element matrike in vpraša: "Ali je element želim več, enako ali manj kot to?" Če je enaka, potem pa super. Si našel element, in ste končali. Če je večja, potem veste element mora biti na desni strani matrike, in lahko si samo poglej, da tudi v prihodnje, in če je manjša, potem veste, da mora biti na levi strani. Ta postopek se nato ponovi z manjšo velikosti matrike dokler se ne najde pravi element. 

Ta zmogljiv algoritem odreže velikost polja na pol, z vsako operacijo. Torej, da bi našli element v matriki razvrščeni po velikosti 8, največ (log ₂ 8) ali 3 od teh operacij preverjanje srednji element, nato pa prerezala na pol matriko bo potrebno, ker je matrika velikosti 16 potrebno (log ₂ 16) 4 ali postopki. To je samo še 1 operacija za podvojila velikosti matrike. Podvojitvijo matrike poveča čas delovanja le za 1 kos te kode. Spet preverjanje srednji element na seznamu, nato pa pokati. Torej, je dejal, da deluje v logaritemski času, O (log n). Toda počakaj, praviš, ni to odvisno od tega, kje na seznamu element iščeš to? Kaj pa, če se prvi element gledate zgodi, da je pravi? Potem je samo 1 postopek, ne glede na to, kako velik je seznam. 

No, to je zato računalniški znanstveniki imajo več izrazov Za asimptotične kompleksnosti, ki odražajo najboljšem primeru in najslabši nastopi algoritmom. Bolj pravilno, zgornja in spodnja meja na runtime. V najboljšem primeru za binarnega iskanja, naš element tam v sredini, in ga dobil v stalnem času, ne glede na to, kako velik je preostanek niza je. Znak za to je Ω. Torej, ta algoritem je dejal, da delujejo v Ω (1). V najboljšem primeru se ugotovi, da je element, hitro, ne glede na to, kako velik je matrika, ampak v najslabšem primeru, mora izpolnjevati (log n) po delih preglede v matriki najti pravo element. Najslabšem primeru višje igrišča so navedene z velikim "O", ki ga že poznamo. Torej, to je O (log n), vendar Ω (1). 

Linearno iskanje, nasprotno, , v kateri hodite po vsakem elementu matrike da bi našli enega, ki ga želite, je v najboljšem primeru Ω (1). Spet je prvi element želite. Torej, ni važno, kako velik je matrika. V najslabšem primeru, to je zadnji element v matriki. Torej, moraš hoditi po vseh n elementov v matriki, da ga najdejo, všeč, če ste iskali za 3. Torej, ta deluje v O (n) časa ker je sorazmeren s številom elementov v matriki. 

Ena bolj uporabljajo simbol je Θ. To se lahko uporablja za opis algoritmov, kjer je najboljši in najslabši zabojev so enaki. Tako je na primer v niz dolžine algoritmov smo govorili o prej. To je, če jo shranite v spremenljivko, preden hranimo niz in dostop kasneje v stalnem času. Ne glede na to, kam smo skladiščenje v te spremenljivke, bomo morali pogledati. Najboljši primer je, gledamo na to in našli dolžino niza. Torej Ω (1) ali najboljšem primeru konstanten čas. V najslabšem primeru je, gledamo na to in najdite dolžino niza. Torej, O (1) ali konstantni čas, v najslabšem primeru. Torej, ker najboljšem primeru in najhujših primerih enaka, to lahko rečemo, da delujejo v Θ (1) časa. 

Skratka, imamo dobre možnosti, da zato o učinkovitosti kode ne da bi vedel ničesar o resničnem času, ko začnejo teči, ki jo je prizadela veliko zunanjih dejavnikov, vključno z različno strojno opremo, programsko opremo, ali posebnosti kode. Prav tako nam omogoča, da dobro razmislite o tem, kaj se bo zgodilo ko je obseg vhodnih povečuje. 

Če delate v O (n) ² algoritem, ali še huje, O (2 ⁿ) algoritem, ena izmed najhitreje rastočih vrst, boste resnično začeli opažati upočasnitev ko začnete delati z večjimi količinami podatkov. 

To je asimptotični kompleksnosti. Hvala.