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