[Powered by Google Translate] Pravdepodobne ste počuli ľudia hovoria o rýchly, alebo efektívny algoritmus
pre vykonávanie váš konkrétnu úlohu,
ale čo presne to znamená pre algoritmus, ktorý bude rýchlo, alebo efektívny?
No, to nehovorím o meranie v reálnom čase,
ako sekundách alebo minútach.
To je preto, že počítačový hardvér
a softvér radikálne líšiť.
Môj program môže bežať pomalšie ako vy,
pretože som beží to na staršom počítači,
alebo preto, že som sa náhodou hrať online videohru
súčasne dobe, ktorá je hogging všetky moje pamäti,
alebo by som mohol byť spustený môj program prostredníctvom rôznych softvér
ktorý komunikuje so strojom inak na nízkej úrovni.
Je to ako porovnávať jablká s hruškami.
Len preto, že môj pomalší počítač trvá dlhšie
ako vaše vrátiť odpoveď
neznamená, že budete mať viac efektívny algoritmus.
>> Takže, pretože nemôžeme priamo porovnávať runtime programov
v sekundách alebo minútach,
ako sme tieto 2 rôzne algoritmy
bez ohľadu na ich hardvérové ​​alebo softvérové ​​prostredie?
Ak chcete vytvoriť viac jednotný spôsob merania efektivity algoritmov,
počítačové vedci a matematici vymysleli
koncepty pre meranie asymptotickej zložitosť programu
a zápis názvom "Big Ohnotation"
pre popis tohto.
Formálne definície je, že funkcia f (x)
beží na poradie g (x)
či existuje nejaký (x) hodnoty, x ₀ a
nejaká konštanta, C, pre ktoré
f (x) je menší ako alebo rovný
že konštantné časy g (x)
pre všetky x väčšie ako x ₀.
>> Ale neboj sa preč formálne definíciu.
Čo to vlastne znamená v menej teoretických pojmoch?
No, je to v podstate spôsob, ako analyzovať
Ako rýchlo programu runtime rastie asymptoticky.
To je, ako veľkosť vašich vstupov zvyšuje smerom k nekonečnu,
povedzme, že ste triedenie poľa o veľkosti 1000 v porovnaní s radom veľkosťou 10.
Ako runtime vášho programu rast?
Predstavte si napríklad, počítanie počtu znakov
v reťazci najjednoduchší spôsob, ako
pešo cez celý reťazec
Letter podľa písmen a pridaním 1 k prepážke pre každého znaku.
Tento algoritmus je povedal, aby spustenie v lineárnom čase
s ohľadom na počet znakov,
"N" v reťazci.
Stručne povedané, to beží v O (n).
Prečo to je?
No, použitie tohto prístupu, čas potrebný
prejsť celý reťazec
je úmerná počtu znakov.
Počítanie znakov v 20-znakový reťazec
bude trvať dvakrát tak dlho, ako bude potrebné
počítať znaky v 10-znakový reťazec,
pretože sa musíte pozrieť na všetky znaky
a každá postava má rovnaké množstvo času pozrieť sa na.
Ako zvýšiť počet znakov,
runtime zvýši lineárne s dĺžkou vstupného.
>> Teraz si predstavte, keď sa rozhodnete, že lineárny čas,
O (n), jednoducho nie je dostatočne rýchly pre vás?
Možno ste ukladanie obrovské reťazca,
a môžete si dovoliť čas navyše, že by trvať
prejsť všetky ich znaky počítanie jeden po-one.
Takže, ste sa rozhodli skúsiť niečo iné.
Čo keď sa stane už uložiť počet znakov
v reťazci, teda v premennej s názvom "ľan"
na začiatku programu,
ešte predtým, než uloží úplne prvý znak vo vašom reťazci?
Potom všetko, čo budem musieť urobiť, zistiť dĺžku reťazca,
je zistiť, čo hodnota premennej je.
Nemala by ste sa pozrieť na reťazec sám vôbec,
a prístup k hodnotu premennej ako ľan sa považuje
asymptoticky konštantný čas operácie,
alebo O (1).
Prečo to je? No, spomenúť si, čo asymptotickej zložitosť znamená.
Ako runtime zmena, ako je veľkosť
z vašich vstupov rastie?
>> Povedzme, že ste sa snažili dostať počet znakov v reťazci väčší.
No, to by nebolo jedno, aký veľký urobíte reťazec,
dokonca miliónov znakov,
všetko, čo budem musieť urobiť, nájsť aktívnu dĺžku struny s týmto prístupom,
je prečítať hodnotu premennej ľan,
ktoré ste už vykonaná.
Vstupné dĺžka, to znamená, že dĺžka reťazca, ktorý sa snažíte nájsť,
nemá vplyv vôbec, ako rýchlo váš program beží.
Táto časť programu by bežať rovnako rýchlo na jeden reťazec znakov
a tisíc znakový reťazec,
a to je dôvod, prečo by tento program byť odvolával sa na ako beh v konštantnom čase
s ohľadom na vstupné veľkosť.
>> Samozrejme, je tu nevýhodu.
Môžete stráviť ďalšie pamäť v počítači
ukladanie premenné
a viac času to bude trvať
robiť skutočné uloženie premenné,
ale bod stále stojí,
zistiť, ako dlho bude reťazec bol
nezávisí na dĺžke reťazca vôbec.
Takže, to beží v O (1), alebo konštantné čas.
To rozhodne nemusí znamenať,
že váš kód beží v 1 kroku,
ale bez ohľadu na to, koľko krokov je to,
ak nemenia s veľkosťou vstupov,
je to stále asymptoticky konštanta, ktorá sa predstavuje ako O (1).
>> Ako asi tušíte,
existuje veľa rôznych veľkých O behové merať algoritmy s
O (n) ² algoritmy sú asymptoticky pomalší ako algoritmy O (n).
To znamená, že aj počet prvkov (n) rastie,
nakoniec O (n) ² algoritmy budú mať viac času
ako O (n) algoritmy pre spustenie.
To neznamená, O (n) algoritmy vždy bežať rýchlejšie
ako O (N) ² algoritmov, a to aj v rovnakom prostredí,
na rovnakom hardvéri.
Možno, že pre malé vstupné veľkosti,
O (n) ² algoritmus v skutočnosti môže pracovať rýchlejšie,
ale, nakoniec, ako vstupné veľkosti zvyšuje
k nekonečnu, O (n) ² algoritmu runtime
nakoniec zatieniť runtime O (n) algoritmu.
Rovnako ako nejaké kvadratickej matematické funkcie
nakoniec predbehnú všetky lineárne funkcie,
bez ohľadu na to, koľko z hlavy kto lineárne funkciu začína s
Ak pracujete s veľkým množstvom dát,
algoritmy, ktoré pracujú v O (n) ² doba sa môže naozaj skončiť spomalenie programu,
ale pre malé vstupné veľkosti,
pravdepodobne ani nevšimnete.
>> Ďalšie asymptotickej zložitosť je,
logaritmickej čas, O (log n).
Príkladom algoritmu, ktorý beží tak rýchlo
je klasický binárny vyhľadávací algoritmus,
pre zistenie prvku v už triedenom zozname prvkov.
>> Ak neviete, čo binárne vyhľadávacie robí,
Vysvetlím ti to pre teba naozaj rýchlo.
Povedzme, že hľadáte pre číslo 3
v tomto poli celých čísel.
Zdá sa na strednej prvku matice
a pýta sa: "Je element chcem väčší, rovná alebo menšia ako toto?"
Ak je to rovnaké, potom skvelé. Našli ste prvok, a máte hotovo.
Ak je to väčšia, potom viete, že prvok
musí byť v pravej časti poľa,
a môžete sa pozrieť na, že v budúcnosti,
a, ak je to menšie, potom viete, že má byť na ľavej strane.
Tento proces sa opakuje s menšou veľkosťou poľa
až do dosiahnutia správnej prvok nájdený.
>> Tento výkonný algoritmus znižuje veľkosť poľa na polovicu každej operácii.
Takže, nájsť element v triedenom poli o veľkosti 8,
najviac (log ₂ 8),
alebo 3 z týchto operácií,
kontrolu strednej prvok, potom delenie poľa na polovicu bude nutné,
vzhľadom k tomu, pole o veľkosti 16 má (log ₂ 16),
alebo 4 operácie.
To je len 1 viac prevádzku na dvojnásobok veľkosti poľa.
Zdvojnásobenie veľkosti poľa
zvyšuje runtime iba 1 kus tohto kódu.
Opäť, kontrola prostredný prvok zoznamu, potom rozdelenie.
Takže, je to údajne v prevádzke v logaritmickom čase,
O (log n).
Ale počkajte, vy hovoríte,
nie je to závisí od toho, kde v zozname, prvok, ktorý hľadáte, je?
Čo keď prvý prvok sa pozriete na stane sa pravý?
Potom, to trvá len 1 operáciu,
bez ohľadu na to, aký veľký je zoznam.
>> No, to je dôvod, prečo počítačoví odborníci majú viac pojmov
pre asymptotickej zložitosti, ktoré odrážajú najlepšie prípad
a najhoršie vystúpenie algoritmu.
Viac správne, horná a dolná hranica
na behu.
V najlepšom prípade pre binárne vyhľadávanie, náš prvok
priamo tam uprostred,
a dostanete ho v konštantnom čase,
bez ohľadu na to, aký veľký zvyšok poľa je.
Symbol používa pre toto je Ω.
Takže, je tento algoritmus hovorí bežať Ω (1).
V najlepšom prípade, že nájde prvok rýchlo,
bez ohľadu na to, aký veľký je pole,
ale v najhoršom prípade,
má vykonať (log n) rozštiepené kontroly
z poľa nájsť ten správny prvok.
Najhoršie hornej hranice sú odvolával sa na s veľkým "O", ktoré už poznáte.
Takže, je to O (log n), ale Ω (1).
>> Lineárne vyhľadávanie, naopak,
, V ktorom sa prejdete každý prvok poľa
nájsť ten, ktorý chcete,
je v najlepšom prípade Ω (1).
Opäť, prvý prvok, ktorý chcete.
Takže, nezáleží na tom, aký veľký je pole.
V najhoršom prípade, je to posledný prvok v poli.
Takže, budete musieť prejsť všetky n prvkov v poli nájsť,
ako keď hľadali 3.
Takže, to beží v O (n) čas
, Pretože je to priamo úmerná počtu prvkov v poli.
>> A ešte jedna použitý symbol je Θ.
To môže byť použitý k popisu algoritmov, kde je najlepšie a najhoršie prípady
sú rovnaké.
To je prípad v reťazci dĺžky algoritmov sme hovorili o skôr.
To znamená, že ak uložíme ju do premennej pred
uložíme reťazec a prístup neskôr v konštantnom čase.
Bez ohľadu na to, aký počet
sme skladovanie v tejto premennej, budeme sa musieť pozrieť na to.
Najlepšia vec je, že sme sa na to pozrieť
a nájsť dĺžku reťazca.
Takže Ω (1) alebo best case konštantný čas.
Najhorší prípad je,
Pozrieme sa na to a nájsť dĺžku reťazca.
Takže, O (1), alebo konštantné čas v najhoršom prípade.
Takže, pretože najlepšie veci a najhoršie prípady sú rovnaké,
Tento sa dá povedať, že beží v Θ (1), je čas.
>> Stručne povedané, máme dobré spôsoby, ako uvažovať o účinnosti kódy
bez toho aby vedel niečo o real-svetového času kedy prijmú bežať,
ktorá je ovplyvnená množstvom vonkajších faktorov,
vrátane odlišného hardvéru, softvéru,
alebo špecifiká vášho kódu.
Tiež, to nám umožňuje rozum, dobre o tom, čo sa stane
kedy veľkosť vstupov zvyšuje.
>> Ak beží v O (n) ² algoritmus,
alebo ešte horšie, O (2 ⁿ) algoritmus,
jeden z najrýchlejšie rastúcich typov,
budete naozaj začnete si uvedomovať, spomalenie
keď začnete pracovať s veľkým množstvom dát.
>> To je asymptotickej zložitosť. Vďaka.