Dakle, razmatraju se različite varijante računala od najjednostavnijih Turingovih strojeva do homogenog računalnog okruženja. Svi se oni mogu koristiti za rješavanje onih problema za koje postoji algoritam. Na temelju ovih modela grade se specijaliziraniji računski modeli i to: aritmetički programi bez grananja, računanja po bitovima, binarna vektorska izračunavanja i stabla odlučivanja.
Algoritmi imaju sljedeće karakteristike:
a) složenost;
b) mukotrpnost;
c) pouzdanost, itd.
Postoji mnogo kriterija za procjenu složenosti algoritama. Najčešće će nas zanimati redoslijeda rasta potrebna za rješavanje problema vremena i kapaciteta memorije s povećanjem broja ulaznih podataka. Svakom konkretnom zadatku pridružite određeni broj, koji se naziva veličina. Na primjer, veličina problema množenja matrice može biti najveća veličina matrica - faktora; veličina problema na grafu može biti broj bridova zadanog grafa i tako dalje.
Vrijeme potrebno algoritmu kao funkcija veličine zadatka se naziva vremenska složenost ovaj algoritam. Ponašanje ove složenosti u granici kako se veličina problema povećava naziva se asimptotska vremenska složenost. The kapacitivna složenost i asimptotička kapacitivna složenost.
Važan motiv za razmatranje formalnih računskih modela je želja da se otkrije računska složenost različitih problema kako bi se dobile donje granice vremena računanja. Da bi se pokazalo da ne postoji algoritam koji obavlja zadani zadatak za manje od određenog vremena, potrebna je precizna i ponekad visoko specijalizirana definicija toga što je algoritam. Turingovi strojevi su jedan primjer takve definicije.
4.1.1. Strojevi za okvire i okvire*
Razmotrimo dva stroja:
1. Strojevi s slučajnim pristupom memoriji (ekvivalentni adresni stroj - RAM) modeliraju računalo s jednim zbrajačem, u kojem se programske upute ne mogu mijenjati same.
2. Model pohranjenog programa je stroj s slučajnim pristupom memoriji i mogućnošću modifikacije instrukcija (PAM*).
Slika 2.9 Struktura PAM strojeva (PAM *)
Za RAM, program se ne zapisuje u memoriju, tako da se program ne mijenja sam. Program je niz označenih naredbi. Postoje aritmetičke upute, I/O upute, upute za neizravno adresiranje i upute za grananje. Svi proračuni se izvode u registru r 0 (zbrajaču), koji, kao i svaki drugi memorijski registar, može pohraniti proizvoljan cijeli broj. Svaka naredba sastoji se od dva dijela - koda operacije i adrese. PAM instrukcije su podskup uputa asemblerskog jezika; ovaj se podskup može proširiti po želji, ali se redoslijed složenosti problema neće promijeniti.
Operand može biti jedan od sljedećih tipova:
1. =i znači sam cijeli broj i i naziva se literal;
2. i- sadržaj registra i (i mora biti nenegativan)
3. *i znači neizravno adresiranje, odnosno vrijednost operanda je sadržaj registra j,gdje j- cijeli broj koji je u registru ja;ako j<0, auto stane.
Može odrediti vrijednost programa R uz pomoć dva objekta: mape c iz skupa nenegativnih cijelih brojeva u skup cijelih brojeva i “brojača naredbi”, koji određuje sljedeću izvršenu naredbu. Funkcija c je mapiranje memorije, naime c(i)- cijeli broj sadržan u broju registra ja (sadržaj Registar ja).
isprva c(i)=0 za sve i 0 , programski brojač je postavljen na prvu instrukciju u P, a izlazna traka je prazna. Nakon obavljanja k-ti tim iz R brojač se automatski prebacuje na (k+1)-th (to jest, na sljedeću) naredbu, ako k-ta naredba nije bila SKOK, HALT, JGTZ i slično.
RAM*-program se nalazi u memorijskim registrima. Svaka PAM* instrukcija zauzima dva uzastopna memorijska registra: prvi registar sadrži operacijski kod, drugi - adresu. Skup instrukcija za PAM* isti je kao odgovarajući skup za PAM osim za neizravno adresiranje, što je isključeno: PAM* može simulirati neizravno adresiranje promjenom instrukcija tijekom izvođenja programa.
Algoritam- skup uputa koje opisuju redoslijed radnji izvođača za postizanje nekog rezultata.
Vremenska učinkovitost je pokazatelj brzine algoritma
procijenjen brojem osnovnih operacija koje algoritam mora izvesti prilikom obrade ulaznih podataka veličine n
Važan je redoslijed rasta vremena izvršenja algoritma ovisno o n
Prostorna učinkovitost pokazuje koliko je dodatne RAM memorije potrebno da bi algoritam radio. Učinkovitost se ocjenjuje u najgorim, najboljim i prosječnim slučajevima.
Vrste analize: matematička i empirijska
Mjerenje vremena izvršenja algoritma
1. Izravna (empirijska analiza)
2. Određivanje broja osnovnih operacija koje algoritam mora izvesti prilikom obrade ulaznih podataka veličine n (matematička analiza)
Redoslijed rasta
Uz male ulazne veličine, nemoguće je uočiti razliku u vremenu izvršenja između učinkovitog i neučinkovitog algoritma. Za velike vrijednosti n izračunava se redoslijed rasta funkcije.
Učinkovitost algoritma u različitim slučajevima
Postoji veliki broj algoritama čije vrijeme izvršenja ovisi ne samo o veličini ulaznih podataka, već i o specifičnostima ulaznih podataka (primjer je pretraživanje).
Učinkovitost se mjeri za:
Primjer: prosječan broj usporedbi u pretraživanju:
Tako:
Prilikom razvoja algoritama vrlo je važno znati procijeniti resurse potrebne za izvođenje proračuna, a rezultat procjene je u funkciji složenosti (uloženog rada). Procijenjeni resurs je najčešće CPU vrijeme (složenost računanja) i memorija (memorijska složenost algoritma). Procjena vam omogućuje da predvidite vrijeme izvršenja i usporedite izvedbu algoritama.
Učinkovitost algoritma je svojstvo algoritma koje je povezano s računskim resursima koje algoritam koristi. Algoritam se mora analizirati kako bi se odredili resursi potrebni algoritmu. Učinkovitost algoritma može se promatrati kao analogna proizvodnoj izvedbi ponavljajućih ili kontinuiranih procesa.
Kako bismo postigli maksimalnu učinkovitost, želimo smanjiti korištenje resursa. Međutim, različiti resursi (kao što su vrijeme i memorija) ne mogu se izravno uspoređivati, pa koji se od dva algoritama smatra učinkovitijim često ovisi o tome koji je čimbenik važniji, kao što je zahtjev za velikom brzinom, minimalno korištenje memorije ili neka druga mjera učinkovitosti.
Imajte na umu da ovaj članak NE o optimizaciji algoritma, o čemu se govori u člancima optimizacija programi, optimizacija prevoditelj, optimizacija ciklusa, optimizator objektnog koda, itd. Izraz "optimizacija" sam po sebi je pogrešan, jer sve što se može učiniti spada pod definiciju "poboljšanja".Enciklopedijski YouTube
1 / 5
✪CS50. Asimptotska notacija
✪ 1. Algoritmi i strukture podataka. Uvod | Technostream
✪ Algoritamska učinkovitost
✪ Knuth-Morris-Prattov algoritam
✪ 2. Algoritmi i strukture podataka. Popisi, stog, red, dec | Technostream
titlovi
Vjerojatno ste čuli kako ljudi govore o brzim ili učinkovitim algoritmima za obavljanje zadanog zadatka, ali što točno mislite pod brzim i učinkovitim u slučaju algoritama? Oni zapravo ne govore o mjerenjima stvarnog vremena u sekundama ili minutama. Budući da je računalni hardver i softver vrlo raznolik. Moj program može raditi sporije od vašeg jer ga pokrećem na starijem računalu ili zato što istovremeno igram mrežnu igricu koja mi jede svu memoriju. Ili sam pokrenuo svoj program kroz drugi softver koji na svoj način komunicira s hardverom na niskoj razini. To je kao da uspoređujete toplo s mekim. Samo zato što mojem sporijem računalu treba više vremena da pronađe odgovor ne znači da je vaš algoritam učinkovitiji. Budući da ne možemo izravno usporediti vrijeme izvršavanja programa u sekundama ili minutama, kako možemo usporediti dva različita algoritma bez ovisnosti o hardveru ili softveru? Kako bi ujedinili način mjerenja algoritamske učinkovitosti, matematičari i informatičari pronašli su rješenje u mjerenju asimptotske složenosti programa i tzv. "Big O" notaciju kako bi ga opisali. Formalna definicija je: Funkcija f(x) je reda g(x) ako postoji takva vrijednost "x", "x₀" i neka konstanta "C" za koju je f(x) manja ili jednaka ovoj konstanta pomnožena s g (x) za bilo koji "x" veći od "x₀". Međutim, neka vas formalna definicija ne plaši. Što to zapravo znači u manje teorijskim terminima? Pa, pojednostavljeno rečeno, to je način analize koliko brzo raste asimptotičko vrijeme izvršavanja programa. To jest, kako se veličina ulaza povećava prema beskonačnosti. Recimo da sortiramo niz od 1000 elemenata i niz od 10. Kako će se povećati vrijeme izvršavanja programa? Na primjer, zamislite da brojite broj znakova u nizu na najjednostavniji način, petljajući kroz cijeli niz slovo po slovo i svaki put dodajući jedan na brojač. Za algoritam se kaže da radi u linearnom vremenu u broju znakova (n) u nizu. Ili ukratko, potrebno je O(n). Zašto je to? Pa, s ovim pristupom, vrijeme potrebno za prolazak kroz cijeli niz proporcionalno je broju znakova u njemu. Brojanje broja znakova u nizu od 20 znakova trajat će dvostruko duže od brojanja u nizu od 10 znakova, jer morate pogledati sve znakove, a gledanje svakog znaka traje isto vrijeme. Kako se broj znakova povećava, vrijeme izvršenja će se povećavati zajedno s duljinom izvornih podataka. Sada, recimo da ste odlučili da linearno vrijeme, O(n), nije dovoljno brzo. Možda pohranjujete ogromne nizove i ne možete si priuštiti dodatno vrijeme da prođete kroz sve likove, brojeći ih jedan po jedan. I odlučite probati nešto drugačije. Što ako će broj znakova za niz već biti pohranjen u varijablu, recimo "len". Pohranjuje se u program ranije, čak i prije nego što ste pohranili prvi znak svog niza. Tada sve što trebate učiniti da pronađete duljinu niza je pročitati vrijednost te varijable. Uopće ne biste morali gledati sam niz, a čitanje vrijednosti "len" trebala bi biti operacija koja traje asimptotski konstantno vrijeme, ili O(1). Zašto je to? Prisjetite se što znači asimptotska složenost. Kako se mijenja vrijeme izvršenja kako veličina ulaza raste? Recimo da dobijete broj znakova u dužem nizu. Općenito, nije važno koliko je dugo. Najmanje milijun znakova. S ovim pristupom, sve što trebate učiniti da biste pronašli duljinu niza je pročitati vrijednost varijable "len" koju već imate. Veličina ulaza, u našem slučaju niza čiji duljinu želimo pronaći, uopće neće utjecati na brzinu izvođenja programa. Ovaj dio vašeg programa radit će jednako brzo na retku od jednog znaka kao i na retku od tisuću znakova. I zato će se smatrati da se program izvodi u konstantnom vremenu u odnosu na veličinu ulaznih podataka. Naravno, postoje i nedostaci. Gubite dodatnu memoriju na računalu za pohranu varijable, kao i dodatno vrijeme za popunjavanje njezine vrijednosti. Ali ipak ima smisla. Vrijeme za dobivanje broja znakova u nizu uopće ne ovisi o duljini niza. Dakle, radi u O(1) ili konstantnom vremenu. Naravno, to ne znači nužno da vaš kod čini samo jedan korak. Međutim, nije važno koliko koraka ima, sve dok se njihov broj ne promijeni kada se promijeni veličina ulaza. Bit će asimptotski konstantan, što označavamo s O(1). Kao što ste mogli pretpostaviti, postoji mnogo različitih "velikih O" za mjerenje vremena izvršenja algoritama. O(n²) algoritmi su asimptotski sporiji od O(n) algoritama. To znači da kako se broj elemenata, n, povećava, O(n²) algoritmi će na kraju trajati dulje od O(n) algoritama. To ne znači da su O(n) algoritmi uvijek brži od O(n²) algoritama, čak i u istom okruženju na istom hardveru. Može biti da će za male ulaze algoritam O(n²) zapravo raditi brže, ali s vremenom, kako se veličina ulaznih podataka povećava prema beskonačnosti, vrijeme izvršenja O(n²) algoritma će na kraju pomračiti vrijeme izvršenja algoritma O(n). Kao i svaka kvadratna matematička funkcija će na kraju prestići bilo koju linearnu funkciju. I nije važno koliko je velik hendikep vrijednosti linearne funkcije na samom početku. Ako radite s velikim količinama podataka, tada će algoritmi koji se izvode u O(n²) na kraju usporiti vaš program, ali na malim veličinama ulaznih podataka to, najvjerojatnije, nećete ni primijetiti. Druga vrsta asimptotske složenosti je logaritamsko vrijeme, O(log n). Primjer algoritma koji radi ovako brzo je klasični algoritam binarnog pretraživanja za pronalaženje elementa u prethodno sortiranom skupu. Ako ne znate kako se radi binarno pretraživanje, brzo ću vam sve objasniti za trenutak. Recimo da tražite broj 3 u nizu cijelih brojeva. Uzimamo središnji element niza i pitamo: "Je li element koji mi treba veći od, manji ili jednak ovome?" Ako je jednako, super. Našli smo pravi element, to je sve. Ako više, onda je jasno da bi naš element trebao biti u nizu negdje desno, a onda možete gledati samo na desnu stranu. Ako je manje, onda je jasno da je element negdje lijevo. Zatim ovaj postupak ponavljamo sa sve kraćim nizovima dok ne pronađemo željeni element. Ovaj moćni algoritam prepolovi veličinu niza nakon svake operacije. To jest, da bi se pronašao element u sortiranom nizu duljine 8, nisu potrebne više od (log₂8) ili tri takve operacije za provjeru središnjeg elementa i odabir željene polovice. U isto vrijeme, niz duljine 16 zahtijevao bi (log₂16) ili četiri operacije. A ovo je samo jedna dodatna operacija kod udvostručavanja duljine niza. Udvostručenje veličine povećava vrijeme izvršenja za samo jedan dio koda. Još jednom provjeravamo središnji element i dijelimo niz. Dakle, ovo se zove logaritamsko vrijeme, O(log n). Ali čekajte, kažete, zar to ne ovisi o tome gdje se u nizu nalazi element koji tražite? Što ako je prvi element koji provjeravamo onaj? Tada je potrebna samo jedna operacija, bez obzira koliko je niz velik. Zato u informatici još uvijek postoje drugi koncepti asimptotske složenosti, koji odražavaju performanse u najboljem i najgorem slučaju. Ili, strože, gornje i donje granice vremena izvršenja algoritma. U najboljem slučaju za binarno pretraživanje, naš element je upravo ovdje u središtu. Nalazimo ga u stalnom vremenu, bez obzira na veličinu ostatka niza. Da biste to učinili, koristite simbol Ω. To jest, kaže se da algoritam radi u Ω(1). U najboljem slučaju, vrlo brzo pronalazi element. Nije važno koliko je velik niz. Ali u najgorem slučaju, trebate izvršiti (log n) provjere i podijeliti niz kako biste pronašli željeni element. Gornja granica za najgori slučaj označena je s "velikim O", kao što već znate. Tako ispada O(log n), ali Ω(1). Za usporedbu, linearno pretraživanje, u kojem pregledavamo svaki element u nizu kako bismo pronašli onaj pravi, u najboljem slučaju Ω (1). To jest, opet se ispostavlja da je prvi element onaj koji tražimo. Stoga, nije važno koliko je velik naš niz. U najgorem slučaju, element koji tražite nalazi se na samom kraju. I morate proći kroz svih n elemenata niza da biste ga pronašli. Ovako, ako tražimo 3. To jest, njegovo vrijeme izvršenja je O(n), budući da je proporcionalno broju elemenata niza. Također se koristi simbol Θ. Koristi se za opisivanje algoritama koji imaju ista najbolja i najgora vremena. Kao iu slučaju algoritma za traženje duljine niza o kojem smo ranije govorili. Onaj gdje duljinu prethodno pohranjujemo u varijablu, a kasnije je samo čitamo u konstantnom vremenu. Bez obzira koji broj pohranimo u ovu varijablu, pogledat ćemo ga. U najboljem slučaju gledamo vrijednost i dobivamo duljinu niza. To je Ω(1) ili konstantno vrijeme za najbolji slučaj. U najgorem slučaju gledamo vrijednost i dobivamo duljinu niza. To je O(1) ili konstantno vrijeme u najgorem slučaju. Stoga su najbolji i najgori slučajevi isti. I možemo reći da se algoritam izvršava u vremenu Θ(1). Ukratko, imamo dobre načine rasuđivanja o učinkovitosti koda bez otkrivanja koliko će stvarnog vremena biti potrebno za izvršenje. Ovo vrijeme ovisi o velikom broju vanjskih čimbenika, poput hardvera i softvera, kao i o specifičnostima samog koda. Također možemo jasno zaključiti što će se dogoditi kada se veličina ulaznih podataka poveća. Ako imamo O(n²) algoritam, ili još gore algoritam O(2ⁿ), tj. jedan od najbrže rastućih tipova, tada je usporavanje zaista teško propustiti kada se radi o sve većim količinama podataka. Ovo je asimptotska složenost. Hvala na pažnji.
Pozadina
Važnost učinkovitosti s naglaskom na vremenu izvršenja naglasila je Ada Lovelace 1843. s obzirom na Charles Babbageov mehanički analitički stroj:
“U gotovo svim proračunima moguć je širok raspon konfiguracija za uspješan završetak procesa, a različite konvencije trebale bi utjecati na izbor za izvođenje izračuna. Bitno je odabrati konfiguraciju koja će rezultirati minimiziranjem vremena potrebnog za završetak izračuna.
Rana elektronička računala bila su vrlo ograničena u brzini i memoriji. U nekim slučajevima, uočeno je da postoji kompromis između vremena i memorije u kojem zadatak mora ili koristiti veliku količinu memorije da bi postigao veliku brzinu, ili koristiti sporiji algoritam koji koristi malu količinu radne memorije. U ovom slučaju korišten je najbrži algoritam za koji je bilo dovoljno raspoložive memorije.
Moderna računala su mnogo brža od onih ranih računala i imaju mnogo više memorije (gigabajta umjesto kilobajta). Međutim, Donald Knuth naglašava da učinkovitost ostaje važan čimbenik:
“U etabliranim inženjerskim disciplinama, poboljšanje od 12% je lako ostvarivo, nikada se nije smatralo neuobičajenim, a vjerujem da bi isto trebalo biti istinito i u programiranju.”
Pregled
Algoritam se smatra učinkovitim ako je resurs koji troši (ili cijena resursa) na ili ispod neke prihvatljive razine. Grubo govoreći, "prihvatljivo" ovdje znači "algoritam će raditi razumno vrijeme na dostupnom računalu". Budući da je od 1950-ih došlo do značajnog povećanja računalne snage i raspoložive memorije računala, postojeća "prihvatljiva razina" nije bila prihvatljiva ni prije 10 godina.
Proizvođači računala povremeno objavljuju nove modele, često moćnije. Cijena softvera može biti prilično visoka, pa je u nekim slučajevima lakše i jeftinije postići bolje performanse kupnjom bržeg računala koje je kompatibilno s vašim postojećim računalom.
Postoji mnogo načina za mjerenje resursa koje koristi algoritam. Dvije najčešće korištene mjere su brzina i iskorištena memorija. Ostala mjerenja mogu uključivati brzinu prijenosa, privremenu upotrebu diska, dugotrajnu upotrebu diska, potrošnju energije, ukupni trošak vlasništva, vrijeme odziva na vanjske signale i tako dalje. Mnoga od tih mjerenja ovise o veličini unosa algoritma (tj. količini podataka koju treba obraditi). Mjerenja mogu ovisiti i o načinu na koji su podaci predstavljeni (na primjer, neki algoritmi za razvrstavanje ne rade dobro na već sortiranim podacima ili kada su podaci razvrstani obrnutim redoslijedom).
U praksi postoje i drugi čimbenici koji utječu na učinkovitost algoritma, kao što su potrebna točnost i/ili robusnost. Kao što je objašnjeno u nastavku, način na koji se algoritam implementira također može imati značajan učinak na stvarnu izvedbu, iako su mnogi aspekti implementacije problemi optimizacije.
Teorijska analiza
U teorijskoj analizi algoritama uobičajena je praksa procjenjivati složenost algoritma u njegovom asimptotičkom ponašanju, odnosno odražavati složenost algoritma kao funkciju veličine ulaza. n koristi se oznaka "O" velika. Ova je procjena općenito prilično točna za velike n, ali može dovesti do netočnih zaključaka pri malim vrijednostima n(Dakle, mjehurasto sortiranje, koje se smatra sporim, može biti brže od "brzog sortiranja" ako je potrebno sortirati samo nekoliko elemenata.)
Neki primjeri velike oznake "O":
| Oznaka | Ime | Primjeri |
|---|---|---|
| O(1) (\displaystyle O(1)\,) | trajna | Određivanje je li broj paran ili neparan. Korištenje tablice za pretraživanje konstantne veličine. Korištenje odgovarajuće hash funkcije za odabir elementa. |
| O (log n) (\displaystyle O(\log n)\,) | logaritamski | Pronalaženje elementa u sortiranom nizu pomoću binarnog pretraživanja ili uravnoteženog stabla, baš kao operacije na binomnoj hrpi. |
| O(n)(\displaystyle O(n)\,) | linearni | Pronalaženje elementa u nerazvrstanom popisu ili neuravnoteženom stablu (u najgorem slučaju). Zbrajanje dva n-bitni brojevi koji koriste prijenos s kraja na kraj. |
| O (n log n) (\displaystyle O(n\log n)\,) | kvazilinearni, logaritamski linearni | Izračunavanje brze Fourierove transformacije, sortiranje hrpe, brzo sortiranje (najbolji i prosječni slučajevi), sortiranje spajanjem |
| O(n 2) (\displaystyle O(n^(2))\,) | kvadrat | Množenje dva n-znamenkasti brojevi s jednostavnim algoritmom, sortiranje mjehurićima (najgori slučaj), sortiranje ljuske, brzo sortiranje (najgori slučaj), sortiranje odabirom, sortiranje umetanjem |
| O (c n) , c > 1 (\displaystyle O(c^(n)),\;c>1) | eksponencijalna | Pronalaženje (točnog) rješenja za problem trgovačkog putnika pomoću dinamičkog programiranja. Određivanje jesu li dvije Booleove izjave ekvivalentne korištenjem iscrpne grube sile |
Verifikacijski testovi: Mjerenje performansi
Za nove verzije softvera ili za usporedbu s konkurentskim sustavima, mjerila se ponekad koriste za usporedbu relativnih performansi algoritama. Ako se, na primjer, objavi novi algoritam za sortiranje, može se usporediti s prethodnicima kako bi se osiguralo da je algoritam barem jednako učinkovit na poznatim podacima kao i ostali. Korisnici mogu koristiti referentne vrijednosti za usporedbu proizvoda različitih proizvođača kako bi procijenili koji će proizvod najbolje odgovarati njihovim zahtjevima u smislu funkcionalnosti i performansi.
Neke referentne vrijednosti pružaju način za usporedbu različitih jezika prevoditelja i interpretatora, kao što je zbirka PC Benchmark Collection Roya Longbottoma i Računalna jezična mjerila uspoređuje izvedbu implementacija tipičnih zadataka u nekim programskim jezicima.
Problemi s provedbom
Problemi s implementacijom također mogu utjecati na stvarnu izvedbu. To uključuje izbor programskog jezika i načina na koji je algoritam zapravo kodiran, izbor prevoditelja za odabrani jezik ili korištene opcije prevoditelja, pa čak i korišteni operativni sustav. U nekim slučajevima, jezik implementiran kao tumač može biti znatno sporiji od jezika implementiranog kao prevodilac.
Postoje i drugi čimbenici koji mogu utjecati na korištenje vremena ili memorije koji su izvan kontrole programera. To uključuje usklađivanje podataka, granularnost podataka, prikupljanje smeća, paralelizam na razini instrukcija i pozivi potprograma.
Neki procesori imaju sposobnost izvođenja vektorskih operacija, što omogućuje jednoj operaciji obradu više operanada. Može ili ne mora biti lako koristiti takve značajke na razini programiranja ili kompilacije. Algoritme dizajnirane za serijsko računanje možda će biti potrebno potpuno redizajnirati kako bi se koristilo paralelno računanje.
Drugi problem može nastati s kompatibilnošću procesora, u kojima se instrukcije mogu različito implementirati, tako da upute na nekim modelima mogu biti relativno sporije na drugim modelima. To može biti problem za optimizirajući prevodilac.
Mjerenje korištenja resursa
Mjerenja se obično izražavaju kao funkcija ulazne veličine. n.
Dva najvažnija mjerenja su:
- Vrijeme: koliko dugo algoritam traje CPU.
- Memorija: koliko radne memorije (obično RAM-a) treba algoritmu. Ovdje postoje dva aspekta: količina memorije za kod i količina memorije za podatke s kojima kod radi.
Za računala na baterije (npr. prijenosna računala) ili za vrlo duge/velike izračune (npr. superračunala) zanimljiva je druga vrsta mjerenja:
- Izravna potrošnja energije: Energija potrebna za rad računala.
- Neizravna potrošnja energije: energija potrebna za hlađenje, osvjetljenje itd.
U nekim slučajevima potrebna su druga, manje uobičajena mjerenja:
- Veličina prijenosa: Širina pojasa može biti ograničavajući faktor. Kompresija se može koristiti za smanjenje količine prenesenih podataka. Prikazivanje slike ili slike (kao što je Googleov logotip) može rezultirati prijenosom desetaka tisuća bajtova (48K u ovom slučaju). Usporedite ovo sa slanjem šest bajtova u riječi "Google".
- Vanjska memorija: Memorija potrebna na disku ili drugom vanjskom uređaju za pohranu. Ova memorija se može koristiti za privremenu pohranu ili za buduću upotrebu.
- Vrijeme odziva: Ova je postavka posebno važna za aplikacije u stvarnom vremenu gdje računalo mora brzo reagirati na vanjske događaje.
- Ukupna cijena vlasništva: Parametar je važan kada se namjerava izvršiti samo jedan algoritam.
Vrijeme
Teorija
Ova vrsta testova također značajno ovisi o izboru programskog jezika, prevoditelja i njegovih opcija, tako da se uspoređeni algoritmi moraju implementirati pod istim uvjetima.
Memorija
Ovaj odjeljak bavi se korištenjem glavne memorije (često RAM-a) koju zahtijeva algoritam. Što se tiče gornje vremenske analize, za analizu se obično koristi analiza algoritma prostorna složenost algoritma za procjenu potrebne runtime memorije kao funkcije veličine ulaza. Rezultat se obično izražava u terminima "O" veliki.
Postoje četiri aspekta korištenja memorije:
- Količina memorije potrebna za pohranjivanje koda algoritma.
- Količina memorije potrebna za ulazne podatke.
- Količina memorije potrebna za bilo koji izlaz (neki algoritmi, poput sortiranja, često preuređuju ulaz i ne zahtijevaju dodatnu memoriju za izlaz).
- Količina memorije koja je potrebna za računski proces tijekom izračunavanja (ovo uključuje imenovane varijable i bilo koji prostor steka potreban za pozivanje potprograma, što može biti značajno kada se koristi rekurzija).
Rana elektronička računala i kućna računala imala su relativno malo radne memorije. Tako je 1949. EDSAC imao maksimalnu radnu memoriju od 1024 17-bitne riječi, a 1980. proizveden je Sinclair ZX80 sa 1024 bajta radne memorije.
Moderna računala mogu imati relativno velike količine memorije (možda gigabajta), tako da je potrebno manje komprimiranja memorije koju koristi algoritam u danu količinu memorije nego što je to bilo prije. Međutim, bitno je postojanje tri različite kategorije sjećanja:
- Cache (često statična RAM memorija) - radi brzinom usporedivom s CPU-om
- Glavna fizička memorija (često dinamička RAM) - nešto sporija od CPU-a
- Virtualna memorija (često na disku) – daje iluziju ogromne memorije, ali je tisućama puta sporija od RAM-a.
Algoritam čija se potrebna memorija uklapa u predmemoriju računala radi puno brže od algoritma koji se uklapa u glavnu memoriju, koja će, zauzvrat, biti mnogo brža od algoritma koji koristi virtualni prostor. Stvar je komplicirana činjenica da neki sustavi imaju do tri razine predmemorije. Različiti sustavi imaju različite količine ovih vrsta memorije, tako da se učinak memorije na algoritam može jako razlikovati od jednog sustava do drugog.
U ranim danima elektroničkog računalstva, ako algoritam i njegovi podaci nisu stali u glavnu memoriju, nije se mogao koristiti. Ovih dana korištenje virtualne memorije pruža veliku memoriju, ali po cijenu performansi. Ako algoritam i njegovi podaci stane u predmemoriju, može se postići vrlo velika brzina, tako da minimiziranje potrebne memorije pomaže da se minimizira vrijeme. Algoritam koji se ne uklapa u potpunosti u predmemoriju, ali pruža lokalitet veze može trčati relativno brzo.
NA zatvor daje se dosljedan, logički koherentan prikaz dobivenih rezultata i njihova povezanost s općim ciljem (hipotezom) i ciljevima istraživanja, donose se generalizirani zaključci, formuliraju se stavovi i prijedlozi autora o poboljšanju problematike koja se proučava. Volumen teksta zaključka u završnom kvalifikacijskom radu nije strogo reguliran - obično je 1,5 - 3 stranice.
NA popis korištenih izvora oni dokumenti, građa, periodika, literatura koji se koriste u studiji su naznačeni bez izostanka. Nemojte činiti popis prevelikim; također je neprihvatljivo uključivati tekstove koji nisu vezani uz proučavani problem.
Sastavljanje popisa korištenih izvora i literature jedna je od najvažnijih faza u radu na studiji, jer odražava samostalan, kreativan pristup autora izboru znanstvene literature i proučavanju odabranog problema te omogućuje prosuditi stupanj ozbiljnosti i valjanosti studije.
Ako je potrebno, bibliografski popis može uključivati, na primjer, odjeljke kao što su:
1. Dokumenti državnih tijela i javnih organizacija;
2. Dokumenti arhiva;
3. Referentne i statističke publikacije;
4. Obrazovne i obrazovne publikacije;
5. Znanstvene monografije i članci;
7. Periodika;
Popis periodičnih i obrazovnih publikacija, literature, disertacija i sažetaka formiran je abecednim redom prema imenima autora i naslovima knjiga/članaka.
Broj izvora u bibliografskom popisu završnog kvalifikacijskog rada ne može biti manje od 25-30 stavki.
Izdaje se u skladu s GOST 2003 ili GOST R 7.0.5-2008 "Bibliografska referenca".
Primjeri bibliografskih opisa citiranih izvora
1. Turuta E.F. Aktivne SMD komponente: označavanje, karakteristike, zamjena. - Sankt Peterburg: Znanost i tehnologija, 2006. - 544 str.
2. Ulrich V.A. Mikrokontroleri PIC16X7XX. - Sankt Peterburg: Znanost i tehnologija, 2002. - 320 str.
Knjiga ima urednika
1. Remizevič T.V. Mikrokontroleri za ugrađene aplikacije: od općih prijelaza do Motorolaovih HC05 i HC08 obitelji. / ur. Kiryukhina I.S. - M.: DODEKA, 2000. - 272 str.
Određena vrsta rada (udžbenik, priručnik, enciklopedija itd.)
1. Finkelstein M.I. Osnove radara: Proc. za sveučilišta. - M.: Radio i komunikacija, 1983. - 536 str.
2. Guk M. Hardver IBM PC: Enciklopedija. - Sankt Peterburg: Izdavačka kuća "Petar", 1999. - 816 str.
1. Iglovsky I.G. Niskostrujni električni releji: priručnik / I.G. Iglovsky, G.V. Vladimirov. - M.: KUBK-a, 1996. - 560 str.
2. Romanycheva E.T. Inženjerstvo i računalna grafika / E.T. Romanycheva, T.Yu. Sokolova, G.F. Šandurin. – M.: DMK Press, 2001. – 592 str.
Ako su knjigu napisala četiri autora, a publikacija ima urednika, svi su navedeni iza kose crte (/). Ako knjiga ima više od četiri autora, prva tri se navode iza naslova, nakon čega slijedi kosa crta (/) i dodaju se riječi “et al”.
3. Radiotehnički sustavi: Zbornik radova. za sveučilišta na posebnim "Radiotehnika" / Yu.P. Grišin, V.P. Ipatov, Yu.M. Kazarinov i drugi; Ed. Yu.M. Kazarinov. - M .: Više. škola, 1990. - 496 str.
Ako publikacija nema urednika, onda blok “; Ed. Yu.M. Kazarinova.“, odsutan.
Knjiga je prevedena s drugog jezika i nema autora
1. Resursi Microsoft Windows Server 4.0. Knjiga 1: prev. s engleskog. - Sankt Peterburg: BHV - Sankt Peterburg, 1997. - 408 str.
Članci iz časopisa
1. Odnobokov V.V. Obrazloženje glavne metode optimalne raspodjele resursa Nauchno-tekhnicheskie vedomosti. - Sankt Peterburg: Izdavačka kuća St. Petersburg State Polytechnical University, 2003. - sv. 4. - P.55-62.
Članci iz zbirke
1. Glazyrin B. E. Automatizacija pojedinačnih operacija u Wordu 2000 // Office 2000: 5 knjiga. u 1 - M., 2002. - T. 3, Ch. 14. - S. 281-298.
Opis članka se navodi u naslovu ako knjigu pišu četiri ili više autora. Ako su članak napisala četiri autora, svi su navedeni iza kose crte (/).
1. A. N. Bogolyubov, A. L. Delitsyn i M. D. Malykh, “O stvarnim rezonancijama u valovodu s nehomogenim punjenjem”, Vestn. Moskva sveučilište Ser. 3, Fizika. Astronomija. - 2001. - Broj 5. - S. 23–25.
Standardi
1. Sheme algoritama, programa, podataka i sustava. Simboli i pravila provedbe: GOST 19.701–90 (ISO 5807–85). – Uveden 1992–01–01. - M .: Gosstandart SSSR-a: Izdavačka kuća standarda, 1991. - 26 str.
2. Elektronička oprema za kućanstvo. Ulazni i izlazni parametri i vrste povezivanja. Tehnički zahtjevi: GOST R 51771–2001. – Uvedeno 2002–01–01. - M.: Gosstandart Rusije: Izdavačka kuća standarda, 2001. - 27 str.
Patentni dokumenti
1. Primopredajnik: Pat. 2187888 Ros. Federacija / Chugaeva V.I.; podnositelj zahtjeva i nositelj patenta Voronjež. znanstveno istraživanje in-t veza. - broj 2000131736/09; dec. 18/12/00; publ. 20.08.02, Bik. broj 23 (II dio). - 3 s.
Elektronički resursi za daljinski pristup
1. Yu. A. Kochetov. Teorija odlučivanja / Novosibirsko državno sveučilište. – Način pristupa: http://math.nsc.ru/LBRT/k5/or.html
2. M. Perov. Organizacija rada s listama u obliku stabla // Mir PK - Electron. časopis. - Izdavačka kuća "Otvoreni sustavi", 2008. - br. 1. - Način pristupa časopisu: http://www.osp.ru
3. Istraživan u Rusiji: višepredmetni. znanstvenim časopis / Moskva. fizike i tehnologije u-t. – Elektron. časopis - Dolgoprudny: MIPT, 1998. - Način pristupa časopisu: http://zhurnal.mipt.rssi.ru. - Ne, država. registracija 0329900013.
Elektronički resursi lokalnog pristupa
1. Internet korak po korak. – Elektron. Dan. i progr. - St. Petersburg. : PiterKom, 1997. - 1 elektron. opt. disk (CD-ROM) + pril. (127 str.)
2. Veliki objašnjavajući rječnik engleskog i ruskog jezika: 2 u 1. - Elektron. Dan. i progr. - Maccelesfield (UK): Europa House, 1999. - 1 elektron. opt. disk (CD-ROM).
3. Visio Professional: knjižnica inženjera dizajna 5.0. – Elektron. Dan. i progr. - 1997. - 1 elektron. opt. disk (CD-ROM).
Popis uključuje 2 članka na ruskom jeziku (obavezno ) + 2 prevedeno na engleski. (neobavezno), napisano uz sudjelovanje podnositelja zahtjeva.
Prijave
Prilozi su uključeni samo ako postoje dodatni i popratni materijali koji zatrpavaju tekst glavnog dijela WRC-a i na koje se upućuje u samom djelu.
Prijave mogu uključivati sljedeće materijale:
- čin uvođenja rezultata istraživanja u proizvodnju ili u obrazovni proces;
– zahtjev za patent ili korisni model;
– izvješće o istraživanju pristiglom na natječaj studentskih radova;
- izgled uređaja, aplikacijski softverski paketi, informacije o izvješćima na konferencijama na temu WRC-a itd.
– protokoli istraživanja itd.
3.3 Priprema i izvedba konačne verzije WRC-a
Zahtjevi za dizajn
Tekst WRC-a mora se ispisati pomoću računala i pisača na jednoj strani bijelog papira A4 u skladu s GOST 9327-60.
Glavni tekst rada tiska se u intervalima od 1,5 (27-30 redaka po stranici) i u 1 intervalu (linkovi i fusnote) u Times New Romanu, veličine 14 (glavni tekst), 12 - tekst u poveznicama, fusnotama i tablicama. Veličina lijeve margine je 30 mm, desne margine 10 mm, gornje i donje margine po 20 mm. Tekst rada je usklađen u širinu.
Kvaliteta tiskanog teksta te dizajn ilustracija i tablica moraju zadovoljiti uvjet za njihovu preglednu reprodukciju. WRC treba imati jasne linije, slova, brojeve i znakove.
Greške, otisci i druge netočnosti pronađene u tekstu mogu se ispraviti brisanjem ili farbanjem bijelom bojom, nakon čega slijedi strojno ili rukopisno nanošenje ispravljenog teksta (grafika). Naljepnice, oštećenja WRC listova, mrlje nisu dopuštene.
Prezimena, nazivi ustanova i druga vlastita imena u tekstu WRC-a navode se na izvornom jeziku. Dopušteno je transliterirati vlastita imena i dati nazive ustanova prevedene na ruski uz dodatak (pri prvom spominjanju) izvornog naziva. Imena treba pisati sljedećim redoslijedom: prezime, ime, patronim ili - prezime, inicijali odvojeni razmacima, nije dopušteno prenošenje inicijala odvojeno od prezimena u sljedeći redak.
Skraćenica ruskih riječi i izraza u tekstu WRC-a provodi se u skladu s GOST 7.12-93, skraćenica riječi na stranim europskim jezicima - u skladu s GOST 7.11-2004. Skraćenice sljedećih riječi i izraza nisu dopuštene: “otkad”, “takozvani”, “tako”, “tako”, “na primjer”. Ako je WRC usvojio poseban sustav kratica za riječi i nazive, tada popis prihvaćenih kratica treba navesti u strukturnom elementu WRC-a "Definicije, oznake i kratice". U tekstu WRC-a, uz općeprihvaćene abecedne kratice, dopušteno je koristiti i abecedne kratice koje su uveli njihovi autori, a koje su skraćivale sve pojmove iz relevantnih područja znanja. U ovom slučaju, prvi spomen takvih skraćenica naznačen je u zagradama nakon punog imena, ubuduće se koriste u tekstu bez dekodiranja.
Numeracija odjeljaka, pododjeljaka, stavaka, podstavaka
Nazivi strukturnih elemenata "SADRŽAJ", "DEFINICIJE, SIMBOLI I KRATICE", "UVOD", "ZAKLJUČAK", "POPIS KORIŠTENIH IZVORA" naslovi su strukturnih elemenata WRC-a.
Naslovi strukturnih elemenata WRC-a ispisani su u sredini retka velikim slovima bez točke, a ne podvučeni, na primjer:
UVOD
Svaki strukturni element WRC-a treba ispisati s novog lista (stranice), uključujući dijelove glavnog dijela.
Odjeljci, pododjeljci, stavci i podstavci trebaju biti numerirani arapskim brojevima i napisani s uvlakom odlomka. Odjeljke treba numerirati uzastopno u cijelom tekstu, s izuzetkom dodataka. Primjer - 1, 2, 3, itd. Na primjer:
3 Studija učinkovitosti dobivenih rješenja
Pododjeljci su numerirani unutar odjeljka. Broj pododjeljka uključuje brojeve odjeljka i pododjeljka odvojene točkom. Na primjer, 1.1, 1.2, 1.3, itd.
Stavke treba uzastopno numerirati unutar svakog pododjeljka. Broj stavke uključuje broj odjeljka i serijski broj pododjeljka i stavke, odvojene točkom. Na primjer, 1.1.1, 1.1.2, itd.
Broj podstavka uključuje broj odjeljka, pododjeljka, stavka i serijski broj podstavka, odvojen točkom. Na primjer, 1.1.1.1, 1.1.1.2, itd. Ako se odjeljak sastoji od jednog pododjeljka, tada pododjeljak nije numeriran. Ako se pododjeljak sastoji od jednog stavka, onda se paragraf ne numerira. Ako se paragraf sastoji od jednog podstavka, onda se podstavak ne numerira. Ne stavljajte točku iza broja odjeljka, pododjeljka, stavka i podstavka u tekstu.
Primjer izravno SADRŽAJ
UVOD5
1 Pregled zadataka i radova na temu istraživanja 7
2 Projektiranje informacijskih modela i razvoj algoritama10
2.1 Izbor metoda i alata dizajna10
2.2 Projektiranje logičkog sustava11
2.3 Projektiranje fizičkog sustava13
2.4 Dizajniranje izgleda korisničkog sučelja15
2.5 Algoritmi rada18
3 Tehnologija programske implementacije razvijenih modela i algoritama25
4.1 Izbor alata za implementaciju25
4.2 Softverska implementacija korisničkog sučelja sustava29
4.3 Osiguranje operativne i informacijske sigurnosti razvijenog sustava33
4.4 Opravdanost i ekonomski izračun troškova razvoja sustava39
4 Studija učinkovitosti dobivenih rješenja43
4.1 Studija učinkovitosti projektnih rješenja43
4.2 Proučavanje učinkovitosti tehnoloških rješenja48
4.3 Proučavanje učinkovitosti razvijenih algoritama51
ZAKLJUČAK55
LITERATURA57
PRILOZI59
P.1 Grafički materijal za objašnjenje59
A.2 Popis potprograma za filtriranje i grupiranje podataka 61
P.3 Zakon o provedbi razvoja 65
Odjeljci i pododjeljci trebaju imati naslove. Naslovi trebaju jasno i sažeto odražavati sadržaj odjeljaka, pododjeljaka.
Naslove odjeljaka, pododjeljke treba ispisati s uvlakom odlomka od velikog slova bez točke na kraju, bez podvlačenja. Ako se naslov sastoji od dvije rečenice, one su odvojene točkom. Prevođenje riječi u naslovima nije dopušteno. Naslov pododjeljka ne smije biti zadnji redak na stranici.
Svakoj stavci u nabrajanju mora prethoditi crtica. Ako je potrebno, u tekstu WRC-a upućivanje na jedan od elemenata nabrajanja, umjesto crtice, stavljaju se mala slova po redoslijedu ruske abecede, počevši od slova a (s izuzetkom ë, z , j, o, h, ʺ, y, ʹ). Za daljnje detaljiziranje nabrajanja potrebno je koristiti arapske brojeve, nakon čega se stavlja zagrada, a unos se vrši iz uvlake odlomka.
Na primjer,
Paginacija
Stranice WRC-a trebaju biti numerirane arapskim brojevima, slijedeći kontinuirano numeriranje u cijelom tekstu. Broj stranice nalazi se u sredini dna lista bez točke.
Naslovna stranica, zadatak za WRC i sadržaj uključeni su u opću numeraciju stranica WRC-a, brojevi stranica se na njima ne stavljaju.
Ilustracije i tablice smještene u tekstu WRC-a na posebnim listovima uključene su u opću numeraciju stranica. Ilustracije i tablice na A3 listu (297×420) računaju se kao jedna stranica.
Numeracija stranica WRC-a i priloga uključenih u WRC treba biti kontinuirana.
Formule
Formule se upisuju pomoću uređivača formula Microsoft Equation (dio MS Officea). U ovom slučaju, "formula" znači svaki niz od najmanje dva znaka koji nije riječ (ime, kratica) na ruskom ili bilo kojem drugom jeziku.
Formule su numerirane striktno uzastopno (po redoslijedu objašnjenja u tekstu), u zagradama, arapskim brojevima, počevši od 1. Brojevi formula ispisuju se strogo na desnom rubu. U ovom slučaju numeriraju se samo one formule koje su navedene u tekstu. Formule koje nisu navedene u tekstu članka nisu numerirane.
Tekst formule poravnat je s lijeve strane na udaljenosti od 1,25 centimetara od lijevog ruba teksta (od crvene linije), bez obzira na to je li formula numerirana ili ne:
Ako formula ne stane u redak, onda se prenosi u sljedeći redak iza znaka "=" ili iza matematičkih znakova "+", "-" itd. U ovom slučaju, poravnanje drugog retka od formula ostaje ista - 1,25 centimetara od lijevog ruba tekstualnog članka, kao što je prikazano u primjeru s formulom (2):
| (2) |
Između teksta i sljedeće formule, u višerednim formulama, te između formule i sljedećeg teksta, ostavljene su prazne linije.
Objašnjenje značenja simbola i brojčanih koeficijenata treba dati neposredno ispod formule, istim redoslijedom kojim su dati u formuli. Vrijednost svakog simbola i brojčani koeficijent treba navesti u novom retku. Prvi red objašnjenja počinje riječju "gdje", bez dvotočke iza nje. Na primjer:
Apsolutno smanjenje troškova rada (DT):
DT \u003d T0 - T1,
gdje je T0 – troškovi rada za obradu informacija prema osnovnom slučaju;
T1 - troškovi rada za obradu informacija o predloženoj opciji.
Za upisivanje varijabli (slova) trebate koristiti font Times, kurziv, a ne podebljan (podešeno u postavkama Microsoft Equation): na primjer, t, V, s, U. Za upisivanje brojeva koristite font Times, a ne kurziv ( !), nije podebljano (postavljeno u postavkama Microsoft Equation): na primjer, 1, 2, 15. Veličina fonta za varijable i brojeve je 14 bodova. Veličine ostalih elemenata formule (postavljene u postavkama MicrosoftEquation):
Veliki indeks - 8 bodova;
Mali indeks - 6 bodova;
Veliki simbol (znaci zbroja, integral) - 18 bodova;
Mali simbol - 12 bodova.
Za označavanje vektora, matrica prihvatljivo je koristiti druge elemente stilskog dizajna fontova, na primjer, nekurziv, podebljana slova, font Arial itd.
Za standardne funkcije (trigonometrijske, logaritamske, itd.), kao i za posebne znakove (sup, inf, itd.), trebate koristiti font Times, a ne podebljan, ne kurziv (što odgovara standardnim postavkama Microsoft Equation), na primjer,
Ilustracije
Ilustracije (crteži, grafikoni, dijagrami, dijagrami) postavljeni u WRC moraju biti u skladu sa zahtjevima državnih standarda Jedinstvenog sustava projektne dokumentacije. 9.9.2 Sve ilustracije u tekstu WRC-a (grafovi, crteži, dijagrami, dijagrami itd.) stavljaju se odmah nakon prvog pozivanja na njih (ili na sljedećoj stranici) i označavaju se riječju "Slika".
Tekst pojašnjenja može sadržavati niz ilustracija, a to mogu biti dijagrami algoritama, strukture računskih centara, izgledi proizvodnih dokumenata obrađenih programom, grafike itd. Svi crteži su izrađeni na papiru za crtanje (format A4) na posebnim listovima. Naslovi slika također moraju biti standardnim fontom.
Ilustracije, osim ilustracija priloga, treba numerirati arapskim brojevima kroz numeraciju. Dopušteno je numerirati ilustracije unutar odjeljka. U ovom slučaju, broj ilustracije se sastoji od broja odjeljka i broja ilustracije, odvojenih točkom. Primjerice – slika 1.1. Kada se govori o ilustracijama, treba napisati "... u skladu sa slikom 2" za kontinuirano numeriranje i "... u skladu sa slikom 1.2" za numeriranje unutar odjeljka.
Ilustracije, ako je potrebno, mogu imati naziv i objašnjenja (slikovni tekst). Riječ "Slika" i naziv stavljaju se iza pojašnjavajućih podataka i raspoređuju na sljedeći način: Slika 1 - Detalji uređaja.
Slika 1 - Naslov slike je centriran, ispisan je nepodebljanim slovima veličine 12 točaka i, ako je potrebno, može se
nastavio u sljedećem redu
Nakon naslova slike ostaje jedan prazan redak i dalje se ispisuje tekst članka.
tablice
Svaka tablica treba imati numeriran i tematski (po mogućnosti) naslov.
Zaglavlje numeracije potrebno je kako bi se pojednostavilo povezivanje tablice s tekstom; kod pozivanja na test dovoljno je naznačiti: tab. 1. Tablice su numerirane arapskim brojevima prema redoslijedu u tekstu objašnjenja. Riječ "Tablica" (velikim slovom) i njezin broj ispisani su kurzivom i poravnati udesno. Između riječi "Tablica" i prethodnog stavka ostavljen je jedan prazan redak. Iza broja tablice nema točke.
Ne tako davno, ponuđeno mi je da predajem tečaj iz osnova teorije algoritama u moskovskom liceju. Naravno, rado sam pristala. U ponedjeljak je bilo prvo predavanje na kojem sam dečkima pokušao objasniti metode za procjenu složenosti algoritama. Mislim da bi i nekim čitateljima Habra ova informacija mogla biti korisna, ili barem zanimljiva.
Postoji nekoliko načina za mjerenje složenosti algoritma. Programeri se obično usredotočuju na brzinu algoritma, ali drugi pokazatelji nisu ništa manje važni - zahtjevi za memorijom, slobodni prostor na disku. Korištenje brzog algoritma neće dovesti do očekivanih rezultata ako zahtijeva više memorije nego što računalo ima.
sjećanje ili vrijeme
Mnogi algoritmi nude izbor između veličine memorije i brzine. Problem se može riješiti brzo, koristeći veliku količinu memorije, ili sporije, koristeći manje prostora.Tipičan primjer u ovom slučaju je algoritam za pronalaženje najkraćeg puta. Predstavljajući kartu grada kao mrežu, možete napisati algoritam za određivanje najkraće udaljenosti između bilo koje dvije točke u ovoj mreži. Umjesto da moramo izračunavati te udaljenosti svaki put kada su nam potrebne, možemo ispisati najkraće udaljenosti između svih točaka i pohraniti rezultate u tablicu. Kada trebamo saznati najkraću udaljenost između dvije zadane točke, možemo jednostavno uzeti gotovu udaljenost iz tablice.
Rezultat će se dobiti odmah, ali će zahtijevati veliku količinu memorije. Karta velikog grada može sadržavati desetke tisuća točaka. Tada bi gore opisana tablica trebala sadržavati više od 10 milijardi ćelija. Oni. kako bi se povećala brzina algoritma potrebno je koristiti dodatnih 10 GB memorije.
Iz ove ovisnosti proizlazi ideja o prostorno-vremenskoj složenosti. Ovakvim pristupom algoritam se ocjenjuje i u smislu brzine izvršavanja i u smislu potrošene memorije.
Usredotočit ćemo se na vremensku složenost, ali, ipak, svakako ćemo odrediti količinu potrošene memorije.
Rezultat narudžbe
Pri usporedbi različitih algoritama važno je znati kako njihova složenost ovisi o količini ulaznih podataka. Na primjer, kada se sortira jednom metodom, obrada tisuću brojeva traje 1 s, a obrada milijun brojeva traje 10 s, pri korištenju drugog algoritma može potrajati 2 s. i 5 s. odnosno. U takvim uvjetima nemoguće je jednoznačno reći koji je algoritam bolji.Općenito, složenost algoritma može se procijeniti po redu veličine. Algoritam ima složenost O(f(n)) ako, kako se dimenzija ulaznih podataka N povećava, vrijeme izvršenja algoritma raste istom brzinom kao i funkcija f(N). Uzmimo u obzir kod koji, dano matrici A, pronalazi maksimalni element u svakom retku.
za i:=1 do N učiniti
početi
max:=A;
za j:=1 do N do
početi
ako je A>max onda
max:=A
kraj;
writeln(max);
kraj;
U ovom algoritmu, varijabla i mijenja se iz 1 u N. Svaki put kada se i promijeni, varijabla j također se mijenja iz 1 u N. Tijekom svake od N iteracija vanjske petlje, unutarnja petlja se također izvršava N puta. Ukupan broj iteracija unutarnje petlje je N*N. To određuje složenost algoritma O(N^2).
Prilikom procjene redoslijeda složenosti algoritma potrebno je koristiti samo dio koji najbrže raste. Pretpostavimo da je radni ciklus opisan izrazom N^3+N. U ovom slučaju, njegova će složenost biti jednaka O(N^3). Uzimanje u obzir brzo rastućeg dijela funkcije omogućuje nam da procijenimo ponašanje algoritma kako raste N. Na primjer, za N=100, razlika između N^3+N=1000100 i N=1000000 je samo 100, što je 0,01%.
Prilikom izračunavanja O, možete zanemariti konstantne faktore u izrazima. Algoritam s radnim korakom od 3N^3 smatra se O(N^3). To čini ovisnost relacije O(N) o promjeni veličine zadatka očitijom.
Definicija poteškoća
Najsloženiji dijelovi programa obično su petlje i pozivi procedura. U prethodnom primjeru cijeli se algoritam radi s dvije petlje.Ako jedan postupak poziva drugi, tada je potrebno pažljivije procijeniti složenost potonjeg. Ako se u njemu izvrši određeni broj instrukcija (na primjer, ispis), to praktički nema utjecaja na procjenu složenosti. Ako pozvana procedura ima O(N) koraka, tada funkcija može značajno zakomplicirati algoritam. Ako se postupak poziva unutar petlje, onda utjecaj može biti mnogo veći.
Kao primjer, razmotrite dva postupka: Sporo sa složenošću O(N^3) i Brzo sa složenošću O(N^2).
postupak Sporo;
var
i,j,k: cijeli broj;
početi
za i:=1 do N učiniti
za j:=1 do N do
za k:=1 do N učiniti
(neka akcija)
kraj;
postupak Brz;
var
i,j: cijeli broj;
početi
za i:=1 do N učiniti
za j:=1 do N do
usporiti;
kraj;
postupak Oba;
početi
brzo;
kraj;
Ako se procedura Slow pozove u unutarnjim petljama Fast procedure, tada se složenost postupaka množi. U ovom slučaju, složenost algoritma je O(N^2)*O(N^3)=O(N^5).
Ako glavni program poziva procedure redom, tada se njihova složenost zbraja: O(N^2)+O(N^3)=O(N^3). Sljedeći isječak ima upravo ovu složenost:
postupak Sporo;
var
i,j,k: cijeli broj;
početi
za i:=1 do N učiniti
za j:=1 do N do
za k:=1 do N učiniti
(neka akcija)
kraj;
postupak Brz;
var
i,j: cijeli broj;
početi
za i:=1 do N učiniti
za j:=1 do N do
(neka akcija)
kraj;
postupak Oba;
početi
brzo;
usporiti;
kraj;
Složenost rekurzivnih algoritama
jednostavna rekurzija
Podsjetimo da su rekurzivne procedure procedure koje same sebe pozivaju. Njihovu složenost je teško odrediti. Složenost ovih algoritama ovisi ne samo o složenosti unutarnjih petlji, već i o broju iteracija rekurzije. Rekurzivna procedura može izgledati dovoljno jednostavno, ali može ozbiljno zakomplicirati program pozivajući se više puta.Razmotrimo rekurzivnu implementaciju faktorijalnog izračuna:
funkcija Faktorijal(n: Riječ): cijeli broj;
početi
ako je n > 1 onda
Faktorski:=n*Faktorijalni(n-1)
drugo
faktorijel:=1;
kraj;
Ovaj postupak se izvodi N puta, pa je računska složenost ovog algoritma O(N).
Višestruka rekurzija
Rekurzivni algoritam koji sebe naziva više puta naziva se višestruka rekurzija. Takve postupke je mnogo teže analizirati, a mogu i učiniti algoritam znatno složenijim.Razmotrite ovaj postupak:
procedura DoubleRecursive(N: cijeli broj);
početi
ako je N>0 tada
početi
Dvostruko rekurzivno (N-1);
Dvostruko rekurzivno (N-1);
kraj;
kraj;
Budući da se postupak poziva dvaput, pretpostavilo bi se da bi njegovo vrijeme izvođenja bilo O(2N)=O(N). Ali u stvarnosti je situacija puno kompliciranija. Ako pažljivo ispitate ovaj algoritam, postaje očito da je njegova složenost O(2^(N+1)-1)=O(2^N). Uvijek treba imati na umu da je analiza složenosti rekurzivnih algoritama vrlo netrivijalan zadatak.
Volumenska složenost rekurzivnih algoritama
Za sve rekurzivne algoritme vrlo je važan koncept volumetrijske složenosti. Svaki poziv u proceduru zahtijeva malu količinu memorije, ali se ta količina može značajno povećati tijekom rekurzivnih poziva. Zbog toga je uvijek potrebno provesti barem površnu analizu volumetrijske složenosti rekurzivnih postupaka.Prosječan i najgori slučaj
Procjena složenosti algoritma do reda je gornja granica složenosti algoritama. Ako program ima veliki red složenosti, to uopće ne znači da će algoritam raditi jako dugo. Na nekim skupovima podataka algoritam treba puno manje vremena za dovršetak nego što bi to sugerirala njihova složenost. Na primjer, razmislite o kodu koji traži zadani element u vektoru A.funkcija Locate(podaci: cijeli broj): cijeli broj;
var
i: cijeli broj;
fl: boolean;
početi
fl:=netočno; i:=1;
dok (ne fl) i (i<=N) do
početi
ako je A[i]=podatak onda
fl:=istina
drugo
i:=i+1;
kraj;
ako ne fl onda
i:=0;
Mjesto:=I;
kraj;
Ako se željeni element nalazi na kraju popisa, tada će program morati izvesti N koraka. U ovom slučaju, složenost algoritma bit će O(N). U ovom najgorem slučaju, vrijeme rada algoritma bit će maksimalno.
S druge strane, element koji tražite može biti na prvom mjestu na popisu. Algoritam mora napraviti samo jedan korak. Takav se slučaj naziva najboljim i njegova se složenost može procijeniti kao O(1).
Oba ova slučaja su malo vjerojatna. Najviše nas zanima očekivana varijanta. Ako su elementi popisa u početku nasumično pomiješani, tada se željeni element može pojaviti bilo gdje na popisu. U prosjeku će biti potrebno N/2 usporedbe da se pronađe traženi element. Dakle, složenost ovog algoritma je u prosjeku O(N/2)=O(N).
U ovom slučaju, prosječna i očekivana složenost su iste, ali za mnoge algoritme najgori slučaj je vrlo različit od očekivanog. Na primjer, algoritam brzog sortiranja u najgorem slučaju ima O(N^2) složenost, dok je očekivano ponašanje O(N*log(N)), što je mnogo brže.
Uobičajene funkcije procjene složenosti
Sada ćemo navesti neke od funkcija koje se najčešće koriste za izračunavanje složenosti. Funkcije su navedene po rastućoj složenosti. Što je funkcija viša na ovom popisu, to će se algoritam s ovom procjenom brže izvoditi.1. C je konstanta
2.log(log(N))
3 log (N)
4. N^C, 0
6.N*log(N)
7. N^C, C>1
8. C^N, C>1
9. N!
Ako želimo procijeniti složenost algoritma čija jednadžba složenosti sadrži nekoliko ovih funkcija, onda se jednadžba može svesti na funkciju ispod u tablici. Na primjer, O(log(N)+N!)=O(N!).
Ako se algoritam poziva rijetko i za male količine podataka, tada se složenost O (N ^ 2) može smatrati prihvatljivom, ali ako algoritam radi u stvarnom vremenu, tada O (N) izvedba nije uvijek dovoljna.
Obično algoritmi složenosti N*log(N) rade dobrom brzinom. Algoritmi sa složenošću N^C mogu se koristiti samo za male vrijednosti C. Računska složenost algoritama čiji je redoslijed određen funkcijama C^N i N! je vrlo velik, pa se takvi algoritmi mogu koristiti samo za obradu male količine podataka.
Zaključno, ovdje je tablica koja pokazuje koliko dugo će računalo koje izvodi milijun operacija u sekundi izvršavati neke spore algoritme.
