[Powered by Google Translate] Jūs tikriausiai girdėjote, žmonės kalba apie greitai ar efektyvus algoritmas
vykdyti savo konkrečią užduotį,
Bet ką tiksliai tai reiškia algoritmą, greitai ir efektyviau?
Na, tai kalbame ne apie matavimo realiu laiku,
kaip sekundėmis arba minutėmis.
Tai yra todėl, kad kompiuterinės įrangos
ir programinės įrangos labai drastiškai.
Mano programa gali veikti lėčiau, nei tavo,
nes aš jį rodyti senesnius kompiuterius,
arba dėl to, kad aš atsitikti, kad bus žaisti interneto vaizdo žaidimą
tuo pačiu metu, kuris Žuvo visą mano atmintį,
ar aš mano programa gali būti vykdoma naudojant įvairias programinės įrangos
skirtingai bendrauja su mašina žemo lygio.
Tai kaip lyginti obuolius ir apelsinus.
Tiesiog, nes mano lėtesnis kompiuteris užtrunka ilgiau
kaip tavo duoti atsakymą
nereiškia, turite efektyvesnis algoritmas.
>> Taip, nes mes negali tiesiogiai palyginti programų Runtimes
sekundžių ar minučių,
kaip mes lyginti 2 skirtingus algoritmus
nepriklausomai nuo jų įrangos ar programinės įrangos aplinką?
Norėdami sukurti vienodą matavimo algoritmų efektyvumą,
kompiuterių mokslininkai ir matematikai, sukūrė
koncepcijos matavimo asimptotinio programos sudėtingumą
ir žymėjimą, vadinamą "Big Ohnotation"
aprašyti tai.
Formalus apibrėžimas yra tas, kad funkcija f (x)
veikia g tvarka (x)
jei egzistuoja šiek tiek (x) vertę, x ₀ ir
kai konstanta, C, kuris
f (x) yra mažesnis arba lygus
kad nuolatinis kartus g (x)
su visais x didesnis nei X ₀.
>> Tačiau nereikia būti nubaidyta formalaus apibrėžimo.
Ką tai iš tikrųjų reiškia mažiau teoriniu aspektu?
Na, tai iš esmės būdas analizuoti
kaip greitai programos Runtime auga asimptotiškai.
Tai reiškia, kad, kaip savo sąnaudas dydis didėja link begalybės,
sako, jūs rūšiavimas dydžio 1000 masyvas, masyvo dydis 10.
Kaip savo programą Runtime augti?
Pavyzdžiui, įsivaizduokite, skaičiavimas simbolių skaičių
į eilutę paprasčiausias būdas
vaikščioti per visą eilutę
laiškas raidžių ir kiekvieno požymio skaitiklis pridedant 1.
Šis algoritmas yra sakoma, kad paleisti eilutėmis
dėl ženklų skaičiaus,
"N" į eilutę.
Trumpai tariant, jis veikia O (n).
Kodėl taip yra?
Na, naudojant šį metodą, laikas, reikalingas
feed visą eilutę
yra proporcingas simbolių skaičių.
Skaičiavimo simbolių skaičių 20 simbolių ilgio eilutę
ketina imtis dvigubai ilgiau, nes joje
suskaičiuoti simbolių 10 simbolių ilgio eilutę,
nes jūs turite pažvelgti į visų simbolių
ir kiekvienas personažas mano laikas pažvelgti į tą pačią sumą.
Kaip jums padidinti simbolių skaičių,
Runtime didėja linijiniu būdu su įėjimo ilgio.
>> Dabar įsivaizduokite, jei jums nuspręsti, kad linijinis laiko,
O (n), tiesiog nebuvo pakankamai greitai jums?
Gal jūs saugoti didžiulius eilutes,
ir jūs negalite sau leisti papildomo laiko, kad būtų priimti
feed visus savo simbolių, skaičiuojant po vieną.
Taigi, jūs nuspręsite išbandyti kažką kita.
Ką daryti, jei nutiktų jau saugoti simbolių skaičių
į eilutę, tarkim, į kintamąjį vadinamą "ilg"
anksti programos,
prieš jus net saugomi pirmųjų savo eilutę simbolį?
Tada visi jūs turite padaryti dabar sužinoti eilutės ilgis,
yra patikrinti, kokia kintamojo reikšmė yra.
Jūs neturite pažvelgti į eilutę, ne visi,
ir prie kintamojo vertę kaip len
asimptotiškai nuolatinio laiko operacija,
arba O (1).
Kodėl taip yra? Na, prisiminkite, ką asimptotinė sudėtingumo.
Kaip Runtime dydžio pasikeitimas,
iš savo sąnaudas auga?
>> Pasakyti bandėte gauti didesnį eilutės simbolių skaičių.
Na, tai nesvarbu kiek daug jums padaryti eilutę,
net milijonų ženklai ilgai,
visi jūs turite padaryti, kad surastumėte styginių ilgio su šio požiūrio,
skaityti kintamojo len vertę,
kuri jau padaryta.
Įvesties ilgis, tai yra, eilutę, kurį bandote rasti ilgis,
neturi įtakos, kaip greitai jūsų programa veikia.
Tai savo programos dalis veikia vienodai greitai vieną simbolių ilgio eilutę
ir tūkstančių simbolių eilutė,
ir tai, kodėl ši programa būtų minima kaip veikia nuolat
atsižvelgiant į įėjimo dydžio.
>> Žinoma, nėra trūkumas.
Jums praleisti daugiau atminties jūsų kompiuteryje
saugoti kintamąjį
papildomo laiko, pateksite
padaryti faktinio saugojimo kintamojo,
bet esmė vis dar stovi,
išsiaiškinti, kaip ilgai jūsų eilutė
nepriklauso nuo ilgio eilutę, ne visi.
Taigi, ji veikia O (1) arba pastovaus laiko.
Tai, žinoma, nebūtinai turi reikšti
kad jūsų kodas veikia 1 žingsnio,
bet nesvarbu, kiek žingsnių jis yra,
jei jis neturi pakeisti sąnaudų dydžio,
jis vis dar yra asimptotiškai pastovus, kurią mes atstovaujame kaip O (1).
>> Kaip jums greičiausiai gali atspėti,
yra daug skirtingų Big O katilas matuoti algoritmai.
O (n) ² algoritmai yra asimptotiškai lėčiau nei O (n) algoritmų.
Tai yra, kaip elementų skaičius (n) auga,
galiausiai O (n) ² algoritmai bus daugiau laiko
nei O (n) algoritmai paleisti.
Tai nereiškia, kad O (n) algoritmai visada paleisti greičiau
nei O (n) ² algoritmų, net toje pačioje aplinkoje,
tame pačiame kompiuteryje.
Gal mažų sąnaudų dydžio,
O (n) ² algoritmas iš tiesų gali dirbti greičiau,
bet, galų gale, įvesties dydis didina
link begalybės, O (n) ² algoritmo veikimo laikas
galų gale užtemimas Runtime O (n) algoritmas.
Tiesiog kaip ir bet kvadratin matematinė funkcija
galų gale aplenkti bet kurios tiesinės funkcijos,
nesvarbu, kiek galvos pradėti Tiesinės funkcijos prasideda nuo.
Jei dirbate su dideliais duomenų kiekiais,
algoritmai, kurie veikia O (n) ² laikas tikrai gali baigtis lėtėja savo programą,
bet mažų dydžių įvesties,
tikriausiai net nepastebi.
>> Kitas asimptotinė sudėtingumas yra,
logaritminė laikas, O (log n).
Algoritmą, kuris veikia tai greitai pavyzdys
yra klasikinis dvejetainis paieškos algoritmas,
rasti elementą jau surūšiuoti elementų sąrašo.
>> Jei jūs neturite žinoti, dvejetainis paieškos,
Aš paaiškinti jums tikrai greitai.
Tarkime, kad jūs ieškote skaičiumi 3
šiame sveikųjų skaičių masyvas.
Jis žiūri į vidurinės masyvo elementu
ir klausia: "Ar elementas Noriu didesnis nei, lygus arba mažesnis nei šis?"
Jei tai vienodos, tai puikus. Jums rasti elementą, ir baigsite.
Jei jis didesnis, tuomet jūs žinote, elementas
turi būti dešinėje pusėje masyvo,
ir jūs galite tik pažvelgti į ateitį,
ir jei jis mažesnis, tuomet jūs žinote, jis turi būti kairėje pusėje.
Šis procesas kartojamas su mažesnio dydžio masyvas
iki teisingas elementas nerasta.
>> Šis galingas algoritmas sumažina masyvo dydį per pusę kiekvienos operacijos.
Taigi, rasti elementą rūšiuotas masyvo dydis 8,
ne daugiau kaip (prisijungti ₂ 8),
3 iš šių operacijų arba
vidurinįjį elementą patikrinti, tada pjovimo masyvo pusę bus reikalaujama,
o dydis 16 masyvas užima (log ₂ 16)
arba 4 operacijas.
Tai tik 1 daugiau operacija dvigubai dydžio masyvą.
Padvigubinti masyvo dydį
padidina Runtime tik 1 riekė šio kodekso.
Vėlgi, tikrinant viduryje sąrašo elementą, tada padalijimas.
Taigi, tai sakė veikti logaritminis metu,
O (log n).
Bet palaukit, jūs sakote,
ne tai priklauso nuo to, kur sąraše elementas jūs ieškote?
Ką daryti, jeigu pirmasis elementas pažvelgti būna, kad teisingas?
Tada, tai trunka tik 1 operaciją
nesvarbu, kaip didelis sąrašas.
>> Na, tai kodėl kompiuterių mokslininkai turi daugiau terminų
asimptotinio sudėtingumo, kuri atspindi geriausiu atveju
ir blogiausią algoritmą spektakliai.
Tiksliau, viršutinė ir apatinė ribos
Runtime.
Geriausiu atveju dvejetainis paieškos elementas yra
teisę ten per vidurį,
ir jūs gaunate jį nuolat,
nesvarbu, kaip didelis likusi masyvo.
Tai simbolis, naudojamas Ω.
Taigi, šis algoritmas yra sakoma, kad paleisti Ω (1).
Geriausiu atveju, ji nustato elementą greitai,
nesvarbu, kaip didelis masyvas,
bet blogiausiu atveju,
turi atlikti (log n) padalinti patikrinimus
masyvo rasti tinkamą elementą.
Blogiausiu atveju viršutinės ribos yra nurodytos su dideliu "O", kad jūs jau žinote.
Taigi, tai O (log n), o Ω (1).
>> Linijinis paieška, priešingai,
, kuriame jūs vaikščioti per kiekvienas masyvo elementas
rasti vieną norite,
yra geriausia Ω (1).
Vėlgi, pirmasis elementas norite.
Taigi, nesvarbu, kaip didelis masyvas.
Blogiausiu atveju, tai paskutinis masyvo elementas.
Taigi, jūs turite pereiti per visų n elementų masyvo jį rasti,
patinka, jei jūs ieškote už 3.
Taigi, ji veikia O (n) laiko
, nes jis proporcingas masyvo elementų skaičius.
>> Dar vienas simbolis, naudojamas Θ.
Tai gali būti naudojama aprašyti algoritmai, kur atskiram geriausius ir blogiausius atvejus
yra tas pats.
Tai string ilgio algoritmų, mes kalbėjome apie anksčiau atveju.
Tai yra, jei mes saugome jį į kintamąjį prieš
mes saugome eilutę ir vėliau pasiekti nuolat.
Nesvarbu, kokiu numeriu
mes saugoti toje kintamojo, mes turime pažvelgti į ją.
Geriausiu atveju, mes žiūrime į jį
ir rasti eilutės ilgį.
Taigi Ω (1) arba geriausiu atveju nuolatinio laiko.
Blogiausiu atveju,
mes žiūrime į ją ir rasti eilutės ilgį.
Taigi, O (1) arba nuolatinio laiko blogiausiu atveju.
Taip, nes geriausiu atveju ir blogiausiu atveju yra tas pats,
tai galima teigti, paleisti Θ (1) metu.
>> Apibendrinant galima pasakyti, mes turime gerų būdų, samprotauti apie kodus efektyvumo
nežinant nieko apie realaus pasaulio laiką, jos imasi vykdyti,
, kuris veikia daug išorinių veiksnių,
įskaitant skiriasi įrangos, programinės įrangos,
arba savo kodą specifika.
Be to, ji leidžia samprotauti ir apie tai, kas nutiks
kai įėjimai didėja dydis.
>> Jei vykdote O (n) ² algoritmas,
arba, dar blogiau, O (2 ⁿ) algoritmas,
viena iš sparčiausiai augančių rūšių,
jūs tikrai pradėsite pastebėti sulėtėjimą
kai pradėsite dirbti su didesniais duomenų kiekiais.
>> Štai asimptotinė sudėtingumas. Ačiū.