[Powered by Google Translate] Sa oled ilmselt kuulnud inimesed räägivad kiiresti või tõhus algoritm
teostamiseks oma konkreetne ülesanne,
Aga mida täpselt tähendab see algoritm peab olema kiire või tõhus?
Noh, see ei räägi mõõtmine reaalajas
nagu sekundites või minutites.
Seda seetõttu, et arvuti riistvara
ja tarkvara väga oluliselt erineda.
Minu programm võib käivitada aeglasem kui sinu oma,
sest ma olen töötab see vanem arvuti,
või sellepärast, et ma juhtumisi mängib online videomäng
samal ajal, mis on hogging kõik mu mälu,
või ma võib olla töötab minu programm läbi erinevate tarkvara
mis suhtleb masin erinevalt madalal tasemel.
See on nagu võrrelda õunu ja apelsine.
Lihtsalt, sest minu aeglasem arvuti võtab kauem
kui sinu oma tagasi anda vastus
ei tähenda, teil on tõhusam algoritm.
>> Niisiis, kuna me ei saa otseselt võrrelda runtimes programmide
sekundites või minutites,
Kuidas me võrrelda 2 erinevat algoritmid
sõltumata nende riistvara või tarkvara keskkonnas?
Et luua ühtne viis mõõta algoritmilise tõhususe,
arvuti teadlased ja matemaatikud on välja töötatud
mõisted mõõtmiseks asümptootilisest keerukus programmi
ja märge "suure Ohnotation"
kirjeldamiseks seda.
Formaalne definitsioon on, et funktsioon f (x)
töötab järjekorras g (x)
kui on olemas mõned (x) väärtus, x ₀ ja
mingite konstantide, c, mille
f (x) on väiksem või võrdne
et pidev korda g (x)
iga x suurem kui x ₀.
>> Aga ei karda kaugusel ametlik definitsioon.
Mida see tegelikult tähendab vähem teoreetiline mõttes?
Noh, see on põhimõtteliselt nii, et analüüsida
kui kiiresti programmi Runtime kasvab asümptootiliselt.
See tähendab, et kui suurust oma sisendid suurendab suunas lõpmatus,
Ütle, et sa sorteerimine massiivi suurus 1000 võrreldes massiivi suurus 10.
Kuidas Runtime oma programmi kasvama?
Oletagem näiteks, loendades tähemärki
aastal string lihtsaim viis
jalgsi läbi terve rea
täht-täht ja lisades 1 kuni loendur iga märk.
See algoritm on öelnud, et sõidetud lineaarne aeg
seoses märkide arvu,
"N" string.
Ühesõnaga, see jookseb O (n).
Miks see nii on?
Noh, kes seda meetodit kasutavad, vajalik aeg
läbida kogu string
on võrdeline arvu märke.
Counting märkide arvu 20-märgijada
see aega võtab kaks korda nii kaua kui vaja
lugema märkide 10-märgijada,
sest sa pead vaatama kõik märgid
ja iga märk võtab sama palju aega vaadata.
Nagu te suurendada arvu märke,
Runtime kasvab lineaarselt sisend pikkus.
>> Nüüd kujutage ette, kui sa otsustad, et lineaarne aeg,
O (n), lihtsalt ei olnud piisavalt kiire Teie jaoks?
Võib-olla olete ladustamiseks tohutu stringid,
ja sa ei saa endale rohkem aega, mis kulub
läbida kõik oma omadustelt lugedes ühe poolt-üks.
Niisiis, sa otsustad proovida midagi muud.
Mis siis, kui juhtuks juba salvestada mitu sümbolit
aastal string, ütleme, muutuja nimega "len"
varakult programmi
enne kui isegi salvestatud kõige esimene märk teie string?
Siis kõik soovid on teha nüüd välja selgitada stringi pikkus,
on vaadata, mida muutuja väärtus on.
Sa ei pea vaatama string ise üldse,
ja pääseda väärtus muutuja nagu len peetakse
asümptootiliselt pidevalt aega operatsiooni
või O (1).
Miks see nii on? Noh, mäletad, mida asümptootilisest keerukus tähendab.
Kuidas Runtime muutunud suurus
oma sisendid kasvab?
>> Ütle, et sa üritad saada tähemärkide arv suurem stringi.
Noh, see pole oluline, kui suur teete stringi,
isegi miljoni tähemärki pikk,
kõik soovid on teha, et leida jada pikkusest selline lähenemine,
on lugeda läbi muutuja len,
mis sa juba teinud.
Sisend pikkus, see, stringi pikkusena te üritate leida,
ei mõjuta üldse, kui kiiresti teie programm töötab.
See osa teie programmi läheks sama kiiresti edasi ühe märgijada
ja tuhande märgijada,
ja sellepärast see programm oleks edaspidi töötab pidevalt aega
suhtes sisend suurus.
>> Muidugi, seal on puudus.
Sa veedad pildi mälu arvutis
ladustamiseks muutuja
ja lisaaeg kulub teil
teha tegelikku salvestusmahtu muutuja,
kuid küsimus on endiselt jõus,
teada saada, kui kaua teie string oli
ei sõltu stringi pikkusena üldse.
Niisiis, see jookseb O (1) või pidevalt aega.
See kindlasti ei tähenda
et sinu kood töötab 1 aste,
Aga ükskõik kui palju samme on,
kui see ei muutu suurusest sisendid,
see on ikka asümptootiliselt konstant, mis me esindame kui O (1).
>> Nagu näete ilmselt arvan,
seal on palju eri suur O runtimes mõõta algoritme.
O (n) ² algoritmid on asümptootiliselt aeglasem kui O (n) algoritme.
See tähendab, et kui mitu elementi (n) kasvab,
lõpuks O (n) ² algoritme võtab rohkem aega
kui O (n) algoritme joosta.
See ei tähenda, O (n) algoritme alati kulgema kiiremini
kui O (n) ² algoritme, isegi samas keskkonnas,
sama riistvara.
Võib-olla väikeste sisend suurused,
O (n) ² algoritm võib tegelikult töötavad kiiremini,
kuid lõpuks, nagu sisend suurus kasvab
suunas lõpmatusse, O (n) ² algoritmi käitusaja
lõpuks Eclipse Runtime O (n) algoritmi.
Nagu iga ruutkeskmised matemaatiline funktsioon
lõpuks mööduda mis tahes lineaarfunktsioonina
ükskõik kui palju edumaa lineaarfunktsioon hakkab liikuma.
Kui töötate koos suurte andmemahtude,
algoritmide O (n) ² aega saab tõesti lõpuks aeglustub oma programmi,
kuid väikese panuse suurused,
siis ilmselt ei märka.
>> Teine asümptootilisest keerukus on
logaritmiline aeg, O (log n).
Näide algoritm, mis töötab selle kiiresti
on klassikaline binaarne otsing algoritm,
leidmiseks element juba sorteeritud elementide loetelu.
>> Kui te ei tea, mida Kahendotsingupuu teeb,
Ma seletan seda teile tõesti kiiresti.
Oletame, et te otsite number 3
Selles valikus täisarvud.
Vaadeldakse keskel element massiivi
ja küsib: "Kas element Ma tahan sellest suurem võrdne või vähem kui see?"
Kui see on võrdne, siis suur. Sa leidsid element, ja sa oled teinud.
Kui see on suurem, siis sa tead element
peab olema paremal pool massiiv,
ja saab ainult vaadata, et tulevikus,
ja kui see on väiksem, siis sa tead, see peab olema vasakul poolel.
Seda protsessi korratakse väiksema suurusega massiiv
kuni õige element on leitud.
>> See võimas algoritm lõikab massiivi suurus pooleks iga operatsiooni.
Niisiis, leida element sorditud massiivi suurus 8,
kõige rohkem (log ₂ 8)
või 3 nimetatud toimingute,
kontroll keskel element, seejärel lõikamise massiivi poole on vaja,
arvestades massiivi suurus 16 võtab (log ₂ 16)
või .4.
See on vaid 1 operatsiooni kahekordistunud suurus massiiv.
Kahekordistades massiivi
suurendab Runtime vaid 1 patakas see kood.
Jällegi, kontroll keskel element loendis, siis jagamine.
Niisiis, see ütles, et tegutseda logaritmiline ajal
O (log n).
Aga oota, sa ütled,
ei see sõltub sellest, millises nimekirjas element otsite on?
Mis siis, kui esimene element te vaatate juhtub olema õige?
Siis, see võtab vaid 1 toiming,
kuitahes suur nimekiri on.
>> Noh, et miks arvuti teadlased on rohkem mõttes
jaoks asümptootilisest keerukust, mis kajastaks parimal juhul
ja halvima etendused algoritm.
Rohkem korralikult, ülemise ja alumise piire
edasi tööaega.
Parimal juhul jaoks Kahendotsingupuu, meie element on
seal keskel,
ja sa saad selle konstantse ajaga,
kuitahes suur ülejäänud massiiv on.
Sümbol, mida kasutatakse see on Ω.
Niisiis, see algoritm on öelnud, et sõidetud Ω (1).
Parimal juhul leiab element kiiresti,
ükskõik kui suur massiiv on,
kuid halvimal juhul
see peab läbima (log n) jagatud kontroll
on massiiv leida õige element.
Halvima ülemised piirid on nimetatud suurte "O", et sa juba tead.
Nii, see on O (log n), kuid Ω (1).
>> Lineaarne otsing seevastu
kus te kõndida läbi iga element massiivi
leida üks soovite,
on parimal Ω (1).
Jällegi, esimene element, mida soovite.
Niisiis, see ei ole oluline, kui suur massiiv on.
Halvimal juhul on see viimase elemendi massiivist.
Nii, teil on kõndida läbi kõik n elementi massiivi seda leida,
nagu kui sa olid otsivad 3.
Niisiis, see jookseb O (n) ajaga
sest see on võrdeline elementide arvu massiivis.
>> Veel üks sümbol, mida kasutatakse on Θ.
Seda saab kasutada, et kirjeldada algoritme, kus on parimad ja halvimal juhul
on samad.
See on nii jada pikkusega algoritme me rääkisime varem.
See tähendab, et kui me seda säilitada muutuja enne
me salvestada string ja seda hiljem pidevalt aega.
Ükskõik, mis number
me salvestamine et muutuja, me peame vaatama seda.
Parimal juhul on, vaatame seda
ja leida stringi pikkusena.
Nii Ω (1) või parimal juhul konstantset aega.
Halvim on see,
me vaatame seda ja leida stringi pikkusena.
Nii, O (1) või pidev aja halvim.
Niisiis, kuna parimal juhul ja halvimal juhul on sama,
võib seda öelda töötamine Θ (1) aeg.
>> Kokkuvõttes on meil häid võimalusi põhjus umbes koodid tõhususe
tundmata midagi reaalse aja nad joosta,
mis mõjutab palju välistest teguritest,
sealhulgas erinevate riist-ja tarkvara,
või spetsiifikat oma kood.
Samuti võimaldab see meil Mõelge hästi järele, mis juhtub
kui suurus sisendite suureneb.
>> Kui näed O (n) ² algoritm,
või veel hullem, O (2 ⁿ) algoritm,
üks kiiremini kasvavaid liike,
sa tõesti hakata märkama aeglustumine
kui alustate tööd suuremate andmemahtude.
>> See on asümptootilisest keerukus. Aitäh.