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