[Powered by Google Translate] Vjerojatno ste čuli ljudi govore o brzom ili učinkovit algoritam
za izvršenje svoju posebnu zadaću,
ali što točno to znači za algoritma biti brz ili učinkovit?
Pa, to ne govori o mjerenja u realnom vremenu,
kao sekundi ili minuta.
To je zato što računalo hardver
i softvera razlikuju drastično.
Moj program može izvoditi sporije nego tvoje,
jer sam to trčanje na starijem računalu,
ili zato što sam se dogoditi da se igraju online video igre
u isto vrijeme, što je krdo svinja sve moje memorije,
ili sam možda trčanje moj program kroz različite softver
koja komunicira sa strojem drugačije na niskoj razini.
To je kao da uspoređujete jabuke i naranče.
Samo zato što mi je sporije računalo traje duže
od tvoje vratiti odgovor
ne znači da imate učinkovitiji algoritam.
>> Dakle, budući da ne mogu izravno usporediti runtimes programa
u sekundi ili minuta,
Kako ćemo usporediti dvije različite algoritme
bez obzira na njihovu hardvera ili softvera okoliš?
Za stvaranje ravnomjernije način mjerenja algoritamski učinkovitost,
računalni znanstvenici i matematičari su izmislili
pojmovi za mjerenje asimptotska složenost programa
i zapis pod nazivom 'Big Ohnotation'
za opisivanje to.
Formalna definicija je da funkcija f (x)
radi na nalogu g (x)
ako postoji neki (x) vrijednost, x ₀ i
neki konstanta, C, za koje
f (x) je manja od ili jednaka
da je konstanta puta g (x)
za sve x veće od x ₀.
>> Ali nemojte se bojati daleko od formalne definicije.
Što to zapravo znači u manje teorijskim terminima?
Pa, to je u osnovi način analiziranja
kako brzo program je runtime raste asimptotski.
To je, kao što je veličina vaše inputa povećava prema beskonačnosti,
recimo, ti si sortiranje niz veličine 1.000 u odnosu na niz veličine 10.
Kako izvođenja svog programa rasti?
Na primjer, zamislite brojanja znakova
u nizu najjednostavniji način
šetnjom kroz cijeli niz
pismo-po-slovo i dodavanjem jedne na šalteru za svakog lika.
Ovaj algoritam je rekao da se izvoditi u linearnom vremenu
s obzirom na broj znakova,
'N' u nizu.
Ukratko, to radi u O (n).
Zašto je to?
Pa, koristeći ovaj pristup, vrijeme potrebno
proći cijeli niz
je proporcionalna broju znakova.
Prebrojavanje znakova u 20-znakova
se događa da se dva puta dok traje
računati znakove u 10-znakova,
jer morate pogledati svih likova
i svaki lik uzima istu količinu vremena da pogledate.
Kao što ste povećati broj znakova,
runtime će povećati linearno s ulaznim duljine.
>> Sada, zamislite, ako ste se odlučili da linearno vrijeme,
O (n), samo nije bio dovoljno brz za vas?
Možda ste spremanje ogromne žice,
i ne možete priuštiti više vremena da bi se
proći sve svoje likove računajući jedna po jedna.
Dakle, odlučite probati nešto drugo.
Što ako bi se dogodilo da već pohraniti broj znakova
u nizu, recimo, u varijablu pod nazivom 'len'
rano u programu,
prije nego što čak i pohranjena je prvi znak u vašem nizu?
Zatim, sve što bi morao učiniti sada da biste saznali string duljine,
je provjeriti što je vrijednost varijable je.
Vi ne bi trebali gledati na žici sama na sve,
i pristupa vrijednost varijable poput Len smatra
asimptotski konstantna vrijeme operacije,
ili O (1).
Zašto je to? Pa, sjetite se što asimptotska složenost znači.
Kako izvođenja promjena kao veličini
vašeg ulaza raste?
>> Recimo da su težak da biste dobili broj znakova u većem nizu.
Pa, to ne bi bilo važno koliko je velik možete napraviti niz,
čak milijun znakova,
sve što bi morao učiniti kako bi pronašli stringa dužinu s ovom pristupu,
je očitati vrijednost varijable Len,
koje ste već napravili.
Ulaz duljina, to jest, duljina niza koji pokušavate pronaći,
ne utječe na sve kako brzo vaš program radi.
Ovaj dio svog programa će izvoditi jednako brzo na jedan znakova
i tisuću niz znakova,
i to je razlog zašto je ovaj program će biti upućen kao trčanje u stalnom vrijeme
s obzirom na ulaznu veličinu.
>> Naravno, tu je nedostatak.
Možete potrošiti dodatni memorijski prostor na vašem računalu
spremanje varijable
i dodatno vrijeme da vas vodi
učiniti stvarni pohranu varijable,
ali poanta i dalje stoji,
saznati koliko dugo je niz
ne ovisi o duljini niza na sve.
Dakle, to radi u O (1) ili stalnom vrijeme.
To svakako ne mora značiti
da je vaš kod radi u jednom koraku,
ali bez obzira na to koliko koraka je,
ako to ne mijenja s veličinom od ulaza,
to je još uvijek asimptotski konstanta koja mi predstavljaju kao O (1).
>> Kao što vjerojatno možete pogoditi,
postoji mnogo različitih velike O runtimes za mjerenje algoritme sa.
O (n) ² algoritmi su asimptotski sporiji od O (n) algoritmi.
To je, kao što je broj elemenata (n) raste,
vremenom O (n) ² algoritmi će trebati više vremena
od O (n) algoritmi za pokretanje.
To ne znači da O (n) algoritmi uvijek trčati brže
od O (n) ² algoritama, čak u istom okruženju,
na istom hardveru.
Možda za male ulaznim veličinama,
je O (n) ² algoritam zapravo mogli raditi brže,
ali, na kraju, kao ulazni veličine povećava
prema beskonačnosti, O (n) ² algoritam je runtime
na kraju će zasjeniti runtime od O (n) algoritma.
Baš kao i svaki kvadratni matematički funkcije
na kraju će prestići bilo linearnu funkciju,
bez obzira koliko glave početi linearnu funkciju započinje.
Ako radite s velikom količinom podataka,
algoritmi koji se pokreću u O (n) ² vrijeme stvarno može završiti usporava svoj program,
ali za male ulaznim veličinama,
vjerojatno neće ni primijetiti.
>> Drugi asimptotska složenost je,
Logaritamska vrijeme, O (log n).
Primjer algoritma koji radi to brzo
je klasična binarni algoritam za pretraživanje,
za pronalaženje element u već poredani popis elemenata.
>> Ako ne znate što binarno pretraživanje radi,
Ja ću to objasniti za vas jako brzo.
Recimo da ste u potrazi za brojem 3
u tom nizu brojeva.
To izgleda po srednjem element niza
i pita: "Je li element Želim veći od, jednak ili manji od ovoga?"
Ako je jednaka, onda super. Možete naći element, i gotovi ste.
Ako je veći, onda znate element
mora biti u desnoj strani polja,
i možete samo pogledati kako će u budućnosti,
a ako je manja, onda znate da mora biti na lijevoj strani.
Ovaj proces onda se ponavlja s manjim size niz
do točne element pronađen.
>> Ovaj moćan algoritam smanjuje veličina polja u pola sa svake operacije.
Dakle, kako bi pronašli element u poredani niz veličine 8,
najviše (log ₂ 8),
ili tri od tih operacija,
provjere srednji element, onda rezanje niz na pola će biti potrebno,
dok niz veličine 16 ima (log ₂ 16),
ili četiri operacije.
To je samo jedan više operacija za udvostručio-size array.
Udvostručenje veličine polja
povećava runtime samo jedan komad ovog koda.
Opet, provjeri srednji element liste, onda cijepanje.
Dakle, to je rekao da radi u logaritamskom vremenu,
O (log n).
Ali čekajte, što reći,
ne to ovisi o tome gdje se u popisu element tražite je?
Što ako je prvi element pogledate dogoditi da bude onaj pravi?
Zatim, to traje samo jedan rad,
bez obzira koliko je velik je popis.
>> Pa, to je razlog zašto računalni znanstvenici imaju više termina
za asimptotska složenosti koji odražavaju najbolje slučaj
i najgori slučaj nastupi algoritma.
Još točnije, gornja i donja granica
na izvođenja.
U najboljem slučaju za binarno pretraživanje, naš element
tamo u sredini,
i što ste ga dobili u stalnom vrijeme,
bez obzira koliko veliki ostatak niza je.
Simbol se koristi za to je Ω.
Dakle, ovaj algoritam je rekao da se izvoditi u Ω (1).
U najboljem slučaju, to nađe element brzo,
bez obzira koliko veliki niz je,
ali u najgorem slučaju,
to mora obaviti (log n) Split provjere
od niza pronaći pravu element.
Najgori slučaj-gornje granice nazivaju se s velikom "O" koje već znate.
Dakle, to je O (log n), ali Ω (1).
>> Linearno pretraživanje, s druge strane,
u kojoj ste šetnja kroz svaki element niza
pronaći onaj koji želite,
je u najboljem Ω (1).
Opet, prvi element želite.
Dakle, to ne obzira koliko je velik polje je.
U najgorem slučaju, to je posljednji element u polju.
Dakle, morate proći kroz svih n elemenata u niz kako bi ga pronašli,
kao i ako ste bili u potrazi za tri.
Dakle, to radi u O (n) vremena
jer to je proporcionalna broju elemenata u polju.
>> Još jedan simbol koji se koristi je Θ.
To se može koristiti za opisivanje algoritama gdje je najbolje i najgore slučajeve
su isti.
To je slučaj u string duljine algoritama razgovarali smo o tome ranije.
To je, ako ćemo ga spremiti u varijablu prije
mi pohraniti string i pristupiti kasnije u stalnom vrijeme.
Bez obzira na broj
mi smo skladištenje u tu varijablu, morat ćemo gledati na to.
Najbolji slučaj je, mi gledamo na njega
i naći duljinu niza.
Dakle Ω (1) ili najbolje slučaj konstantna vrijeme.
Najgori slučaj je,
gledamo i pronaći duljinu niza.
Dakle, O (1) ili konstantna vrijeme u najgorem slučaju.
Dakle, budući najboljem slučaju i najgorih slučajeva su isti,
to može se reći da se izvoditi u Θ (1) vremena.
>> U sažetku, imamo dobre načine kako razloga o kodovima učinkovitosti
ne znajući ništa o stvarnom svijetu vremena su poduzeti za pokretanje,
koja je pogođena puno vanjskih faktora,
uključujući različitog hardvera, softvera,
ili specifičnosti kodu.
Također, omogućuje nam da je razlog i tome što će se dogoditi
kada je veličina od ulaza povećava.
>> Ako radite u O (n) ² algoritma,
ili još gore, O (2 ⁿ) algoritam,
jedan od najbrže rastućih vrsta,
stvarno ćete početi primijetiti usporavanje
kada počnete raditi s većim količinama podataka.
>> To je asimptotska složenost. Hvala.