Sveiki! Šios dienos paskaita šiek tiek skirsis nuo kitų. Jis skirsis tuo, kad yra tik netiesiogiai susijęs su Java. Tačiau ši tema yra labai svarbi kiekvienam programuotojui. Pakalbėsime apie algoritmai. Kas yra algoritmas? Kalbėdamas paprasta kalba, tai tam tikra veiksmų seka, kurią reikia atlikti norint pasiekti norimą rezultatą. Kasdieniame gyvenime dažnai naudojame algoritmus. Pavyzdžiui, kiekvieną rytą jūs susiduriate su užduotimi: ateiti į mokyklą ar darbą ir tuo pačiu būti:

• Apsirengęs
• Švarus
• Gerai šeriami

Kuris algoritmas ar leis pasiekti šį rezultatą?

1. Pabusti nuo žadintuvo.
2. Nusiprausk po dušu, nusiprausk veidą.
3. Paruoškite pusryčius, išsivirkite kavos/arbatos.
4. Valgyk.
5. Jei nelyginote drabužių nuo vakaro, išlyginkite juos.
6. Apsirenk.
7. Išeiti iš namų.

Ši veiksmų seka tikrai leis pasiekti norimą rezultatą. Programavime visa mūsų darbo esmė yra nuolat spręsti problemas. Nemaža dalis šių užduočių gali būti atliekamos naudojant jau žinomus algoritmus. Pavyzdžiui, jūs susiduriate su užduotimi: rūšiuoti 100 vardų sąrašą masyve. Ši problema yra gana paprasta, tačiau ją galima išspręsti Skirtingi keliai. Štai vienas sprendimas: Vardų rūšiavimo pagal abėcėlę algoritmas:

1. Pirkite arba atsisiųskite iš interneto „Rusų asmenvardžių žodyno“ 1966 m. leidimas.
2. Šiame žodyne raskite kiekvieną mūsų sąraše esantį vardą.
3. Ant popieriaus lapo užrašykite, kuriame žodyno puslapyje yra vardas.
4. Sudėkite vardus eilės tvarka naudodami užrašus ant popieriaus lapo.

Ar tokia veiksmų seka leis mums išspręsti mūsų problemą? Taip, tai visiškai leis. Ar tai bus sprendimas veiksmingas? Vargu ar. Čia pasiekiame dar vieną labai svarbią algoritmų savybę – jų efektyvumą. Problemą galima išspręsti įvairiais būdais. Bet tiek programuodami, tiek kasdieniame gyvenime renkamės tokį būdą, kuris bus efektyviausias. Jei jūsų užduotis yra pagaminti sumuštinį su sviestu, galite, žinoma, pradėti nuo kviečių sėjimo ir karvės melžimo. Bet tai bus neveiksmingas sprendimas – tai užtruks labai ilgai ir kainuos nemažus pinigus. Norėdami išspręsti savo paprastą problemą, galite tiesiog nusipirkti duonos ir sviesto. Ir algoritmas su kviečiais ir karve, nors ir leidžia išspręsti problemą, yra per sudėtingas, kad jį būtų galima pritaikyti praktiškai. Norint įvertinti programavimo algoritmų sudėtingumą, buvo sukurtas specialus žymėjimas, vadinamas Big-O („didysis O“). Big-O leidžia įvertinti, kiek algoritmo vykdymo laikas priklauso nuo į jį perduodamų duomenų. Pažiūrėkime į paprasčiausią pavyzdį – duomenų perdavimą. Įsivaizduokite, kad jums reikia perduoti tam tikrą informaciją failo pavidalu dideliu atstumu (pavyzdžiui, 5000 kilometrų). Kuris algoritmas bus efektyviausias? Tai priklauso nuo duomenų, su kuriais jis turi dirbti. Pavyzdžiui, turime 10 megabaitų garso failą.
Šiuo atveju efektyviausias algoritmas būtų failo perkėlimas internetu. Tai užtruks tik keletą minučių! Taigi, dar kartą ištarkime savo algoritmą: „Jei jums reikia perduoti informaciją failų pavidalu 5000 kilometrų atstumu, turite naudoti duomenų perdavimą internetu“. Puiku. Dabar paanalizuokime. Ar tai išsprendžia mūsų problemą? Apskritai, taip, tai visiškai išsprendžia. Bet ką galite pasakyti apie jo sudėtingumą? Hmm, štai kur viskas įdomesnė. Faktas yra tas, kad mūsų algoritmas labai priklauso nuo gaunamų duomenų, būtent nuo failų dydžio. Dabar turime 10 megabaitų ir viskas gerai. Ką daryti, jei mums reikia perkelti 500 megabaitų? 20 gigabaitų? 500 terabaitų? 30 petabaitų? Ar mūsų algoritmas nustos veikti? Ne, visus šiuos duomenų kiekius vis tiek galima perkelti. Ar tai užtruks ilgiau? Taip! Dabar žinome svarbią mūsų algoritmo savybę: Kuo didesnis perduodamų duomenų dydis, tuo ilgiau užtruks algoritmas.. Tačiau norėtume tiksliau suprasti, kaip atrodo šis ryšys (tarp duomenų dydžio ir laiko, kurio reikia jiems perduoti). Mūsų atveju algoritmo sudėtingumas bus linijinis. „Tiesijinis“ reiškia, kad didėjant duomenų kiekiui, jų perdavimo laikas pailgės maždaug proporcingai. Jei duomenų yra 2 kartus daugiau, o jų perkėlimas užtruks 2 kartus daugiau laiko. Jei duomenų yra 10 kartų daugiau, perdavimo laikas padidės 10 kartų. Naudojant Big-O žymėjimą, mūsų algoritmo sudėtingumas nustatomas pagal O(N). Šis žymėjimas geriausiai įsimenamas ateityje – jis visada naudojamas tiesinio sudėtingumo algoritmams. Atkreipkite dėmesį: mes čia visai nekalbame apie įvairius „kintamus“ dalykus: interneto greitį, mūsų kompiuterio galią ir pan. Vertinant algoritmo sudėtingumą, tai tiesiog neturi prasmės – mes vis tiek jo nekontroliuojame. Big-O įvertina patį algoritmą, neatsižvelgdamas į „ aplinką“, kurioje jis turės dirbti. Tęskime savo pavyzdį. Tarkime, galiausiai paaiškėja, kad perduodamų failų dydis yra 800 terabaitų. Jei juos perduosime internetu, problema, žinoma, bus išspręsta. Yra tik viena problema: perdavimas per standartinę šiuolaikinę nuorodą (100 megabitų per sekundę greičiu), kurią daugelis iš mūsų naudoja savo namuose, užtruks maždaug 708 dienas. Beveik 2 metai! :O Taigi, mūsų algoritmas čia netinka. Mums reikia kito sprendimo! Staiga mums į pagalbą ateina IT milžinas „Amazon“! „Amazon Snowmobile“ paslauga leidžia įkelti didelius duomenų kiekius į mobilias saugyklas ir sunkvežimiu pristatyti juos norimu adresu!
Taigi turime naują algoritmą! „Jei jums reikia perduoti informaciją failų pavidalu 5000 kilometrų atstumu, o procesas užtruks daugiau nei 14 dienų, kai perduodamas internetu, turite naudoti Amazon sunkvežimių transportą. 14 dienų skaičius čia pasirinktas atsitiktinai: tarkime, tai yra maksimalus laikotarpis, kurį galime sau leisti. Išanalizuokime savo algoritmą. O kaip greitis? Net jei sunkvežimis važiuoja vos 50 km/h greičiu, 5000 kilometrų jis įveiks vos per 100 valandų. Tai šiek tiek daugiau nei keturios dienos! Tai daug geriau nei perdavimo internetu galimybė. O kaip dėl šio algoritmo sudėtingumo? Ar jis taip pat bus tiesinis, O(N)? Ne, nebus. Juk sunkvežimiui nesvarbu, kiek jį pakrausite – jis vis tiek važiuos maždaug tokiu pačiu greičiu ir atvyks laiku. Nesvarbu, ar turime 800 terabaitų, ar 10 kartų daugiau duomenų, sunkvežimis vis tiek pasieks per 5 dienas. Kitaip tariant, duomenų perdavimo sunkvežimiu algoritmas nuolatinis sunkumas. „Pastovi“ reiškia, kad ji nepriklauso nuo algoritmui perduodamų duomenų. Įdėkite 1 GB „flash“ diską į sunkvežimį ir jis atvyks per 5 dienas. Įdėkite ten diskus su 800 terabaitų duomenų ir jie ateis per 5 dienas. Naudojant Big-O, pastovus sudėtingumas žymimas kaip O(1). Nuo tada, kai susipažinome O(N) Ir O(1), dabar pažiūrėkime į daugiau „programuotojo“ pavyzdžių :) Tarkime, jums duotas 100 skaičių masyvas, o užduotis yra išvesti kiekvieną iš jų į konsolę. Rašote reguliarųjį forciklą, kuris atlieka šią užduotį int numbers = new int [100]; // ..užpildykite masyvą skaičiais for (int i: skaičiai) ( System. out. println (i) ; ) Koks parašyto algoritmo sudėtingumas? Tiesinis, O(N). Veiksmų, kuriuos turi atlikti programa, skaičius priklauso nuo to, kiek skaičių į ją buvo perduota. Jei masyve yra 100 skaičių, bus 100 veiksmų (išvestis ekrane), jei masyve yra 10 000 skaičių, reikės atlikti 10 000 veiksmų. Ar galima patobulinti mūsų algoritmą? Nr. Bet kokiu atveju turėsime tai padaryti N praeina per masyvą ir vykdyti N išvestį į konsolę. Pažvelkime į kitą pavyzdį. public static void main (String args) (LinkedList < Integer> skaičiai = naujas LinkedList< >() ; numeriai. add(0, 20202); numeriai. pridėti(0, 123); numeriai. pridėti(0, 8283); ) Turime tuščią LinkedList, į kurį įterpiame keletą skaičių. Turime įvertinti vieno skaičiaus įterpimo į LinkedList algoritmo sudėtingumą mūsų pavyzdyje ir kaip tai priklauso nuo elementų sąraše skaičiaus. Atsakymas bus O(1) – pastovus sudėtingumas. Kodėl? Atkreipkite dėmesį: kiekvieną kartą sąrašo pradžioje įterpiame skaičių. Be to, kaip prisimenate, kai į LinkedList įterpiate skaičių, elementai niekur nejuda – nuorodos apibrėžiamos iš naujo (jei staiga pamiršote, kaip veikia LinkedList, pažiūrėkite į vieną iš mūsų). Jei dabar pirmasis skaičius mūsų sąraše yra skaičius x, o skaičių y įterpiame sąrašo pradžioje, tereikia x. ankstesnis = y; y. ankstesnis = null; y. kitas = x; Šiai nuorodai nepaisyti mums nesvarbu, kiek skaičių dabar yra LinkedList– bent vienas, mažiausiai milijardas. Algoritmo sudėtingumas bus pastovus – O(1).

Logaritminis sudėtingumas

Nepanikuokite! :) Jei žodis „logaritmas“ verčia paskaitą uždaryti ir toliau neskaityti, palaukite porą minučių. Čia matematinių sunkumų nekils (kitur tokių paaiškinimų gausu), o visus pavyzdžius analizuosime „ant pirštų“. Įsivaizduokite, kad jūsų užduotis yra rasti vieną konkretų skaičių 100 skaičių masyve. Tiksliau, patikrinkite, ar jo apskritai yra. Kai tik teisingas numeris rasta, paieška turi būti sustabdyta, o pulte turi būti rodomas įrašas „Reikalingas numeris rastas!“. Jo indeksas masyve = ....“ Kaip išspręstumėte tokią problemą? Čia sprendimas akivaizdus: reikia kartoti masyvo elementus po vieną, pradedant nuo pirmojo (arba paskutinio) ir patikrinti, ar esamas skaičius sutampa su norimu. Atitinkamai, veiksmų skaičius tiesiogiai priklauso nuo elementų skaičiaus masyve. Jei turime 100 skaičių, turime 100 kartų pereiti prie kito elemento ir 100 kartų patikrinti, ar skaičius atitinka. Jei yra 1000 skaičių, tada bus 1000 tikrinimo žingsnių. Tai akivaizdžiai tiesinis sudėtingumas. O(N). Dabar prie mūsų pavyzdžio pridėsime vieną paaiškinimą: masyvas, kuriame reikia rasti skaičių, rūšiuojamas didėjančia tvarka. Ar tai ką nors keičia mūsų užduočiai? Vis dar galime ieškoti norimo numerio žiauria jėga. Tačiau vietoj to galime naudoti gerai žinomą algoritmas dvejetainė paieška .
Viršutinėje vaizdo eilutėje matome surūšiuotą masyvą. Jame turime rasti skaičių 23. Užuot kartoję skaičius, mes tiesiog padaliname masyvą į 2 dalis ir patikriname vidutinį skaičių masyve. Randame skaičių, esantį 4 langelyje, ir patikriname (antra paveikslėlio eilutė). Šis skaičius yra 16, o mes ieškome 23. Dabartinis skaičius yra mažesnis. Ką tai reiškia? Ką visų ankstesnių numerių (kurie yra prieš skaičių 16) tikrinti nereikia: jie tikrai bus mažesni nei mūsų ieškoma, nes mūsų masyvas surūšiuotas! Tęskime paiešką tarp likusių 5 elementų. Atkreipkite dėmesį: atlikome tik vieną patikrinimą, bet pusę galimų variantų jau pašalinome. Mums liko tik 5 elementai. Pakartosime savo žingsnį - vėl padalinkite likusį masyvą iš 2 ir vėl paimkite vidurinį elementą (3 eilutė paveiksle). Šis skaičius yra 56 ir yra didesnis nei tas, kurio ieškome. Ką tai reiškia? Kad atmestume dar 3 variantus – patį skaičių 56, o po jo – du skaičiai (jie tikrai didesni nei 23, nes masyvas surūšiuotas). Mums liko patikrinti tik 2 skaičiai (paskutinė paveikslo eilutė) - skaičiai su masyvo indeksais 5 ir 6. Patikriname pirmąjį iš jų, ir štai ko ir ieškojome - skaičiaus 23! Jo indeksas = 5! Pažiūrėkime į mūsų algoritmo rezultatus ir tada suprasime jo sudėtingumą. (Beje, dabar jūs suprantate, kodėl jis vadinamas dvejetainiu: jo esmė yra nuolat dalyti duomenis iš 2). Rezultatas įspūdingas! Jei ieškotume norimo skaičiaus naudodami tiesinę paiešką, mums reikėtų 10 patikrinimų, bet su dvejetaine paieška tai padarėme per 3! Blogiausiu atveju jų būtų 4, jei paskutiniame žingsnyje mums reikalingas skaičius būtų antras, o ne pirmas. O kaip dėl jo sudėtingumo? Tai labai įdomus momentas :) Dvejetainės paieškos algoritmas daug mažiau priklauso nuo elementų skaičiaus masyve nei tiesinės paieškos algoritmas (tai yra paprastas išvardijimas). At 10 masyvo elementų, tiesinei paieškai reikės ne daugiau kaip 10 patikrinimų, o dvejetainei paieškai – ne daugiau kaip 4 patikras. Skirtumas 2,5 karto. Bet už masyvą 1000 elementų linijinei paieškai reikės 1000 patikrinimų, o dvejetainei paieškai viso 10! Skirtumas jau 100 kartų! Atkreipkite dėmesį: elementų skaičius masyve išaugo 100 kartų (nuo 10 iki 1000), tačiau dvejetainei paieškai būtinų patikrų skaičius išaugo tik 2,5 karto – nuo ​​4 iki 10. Jei gautume 10 000 elementų, skirtumas bus dar įspūdingesnis: 10 000 patikrinimų tiesinei paieškai ir tik 14 čekių dvejetainiam. Ir vėl: elementų skaičius išaugo 1000 kartų (nuo 10 iki 10 000), tačiau patikrinimų skaičius išaugo tik 3,5 karto (nuo 4 iki 14). Dvejetainės paieškos algoritmo sudėtingumas yra logaritminis, arba, jei naudojame Big-O žymėjimą, - O(log n). Kodėl jis taip vadinamas? Logaritmas yra atvirkštinis didinimo į laipsnį. Dvejetainis logaritmas naudojamas 2 galiai apskaičiuoti. Pavyzdžiui, turime 10 000 elementų, kuriuos turime atlikti naudodami dvejetainę paiešką.
Dabar turite vaizdą prieš akis ir žinote, kad tam reikia atlikti daugiausia 14 patikrinimų. Bet ką daryti, jei prieš akis nėra nuotraukos, o reikia apskaičiuoti tikslų būtinų patikrinimų skaičių? Pakanka atsakyti į paprastą klausimą: Iki kokio laipsnio reikia pakelti skaičių 2, kad gautas rezultatas būtų >= tikrinamų elementų skaičius? Už 10 000 tai bus 14-oji galia. Nuo 2 iki 13 laipsnio yra per mažai (8192) Bet 2 iki 14 laipsnio = 16384, šis skaičius atitinka mūsų sąlygą (tai >= elementų skaičius masyve). Radome logaritmą – 14. Būtent tiek patikrinimų mums reikia! :) Algoritmai ir jų sudėtingumas yra per plati tema, kad būtų galima įtraukti į vieną paskaitą. Tačiau tai žinoti labai svarbu: daugelyje interviu susidursite su algoritminėmis problemomis. Dėl teorijos galiu rekomenduoti keletą knygų. Gera vieta pradėti yra „Big-O“ vaizdo įrašas „YouTube“. Iki pasimatymo kitose paskaitose! :)

Dažnai tai pačiai problemai išspręsti galima sugalvoti daugiau nei vieną algoritmą. Šiuo atžvilgiu kyla klausimas: kuris iš algoritmų yra „geresnis“?

Daugeliu atvejų „geresnis“ yra algoritmas, kuris, naudojant tuos pačius įvesties duomenis, sprendžia problemą, sunaudodamas mažiau skaičiavimo resursų (atminties ir laiko). Tai, žinoma, nėra griežtas samprotavimas. Griežtesnei diskusijai pristatome keletą sąvokų.

Algoritmo skaičiavimo procesas yra veiksmų seka, atliekama vykdant algoritmą kai kuriems įvesties duomenims.

Svarbu suprasti skirtumą tarp paties algoritmo ir to algoritmo sugeneruoto skaičiavimo proceso. Pirmasis yra tik apibūdinimas antra.

Algoritmo sudėtingumas laiko atžvilgiu yra laikas \(T\), kurio reikia algoritmo skaičiavimo procesui atlikti kai kuriems įvesties duomenims.

Aišku, vykdymo laikas priklauso nuo individualaus atlikėjo. Tarkime, elektroninis skaičiuotuvas ir superkompiuteris gali naudoti tą patį algoritmą skirtingu laiku.

Tačiau laikas \(T\) gali būti išreikštas elementarių veiksmų skaičiumi \(k\) ir vidutiniu elementaraus veiksmo atlikimo laiku \(t\):

Be to, \(k\) yra nuosavybė pats algoritmas, o \(t\) yra atlikėjo savybė.

Dėl to, kad \(t\) gali būti laikoma konstanta tam tikram vykdytojui, algoritmų sudėtingumas paprastai įvertinamas iki pastovaus koeficiento. Kitaip tariant, įvertinamas algoritmo sudėtingumas augimo tvarka.

Augimo tvarka Teigiama apibrėžtoji funkcija \(g(x)\) turi augimo tvarką \(f(x)\) (parašyta \(g(x)=\mathcal(O)(f(x))\)) jeigu \(\exists c>0: \: \visam x>x_0, \, g(x) \leq c f(x)\).

Priklausomai nuo įvesties duomenų, algoritmas gali veikti skirtingą laiką. Paprastai vertinama vidutinis sudėtingumas ir sudėtingumas blogiausiu atveju. Taip pat yra priklausomybė nuo kiekiaiįvesties duomenys \(n\) . Paprastai apskaičiuojama augimo tvarka nuo \(n\).

Taigi, pavyzdžiui, duomenų skaitymas ir saugojimas atmintyje kaip masyvas bus sudėtingas \(\mathcal(O)(n)\) arba linijinis sudėtingumas, o matricos daugyba jau yra kub\(\mathcal(O)(n^3)\) .

Be algoritmo sudėtingumo laike, jis taip pat yra svarbus erdvinis algoritmo sudėtingumas.

Erdvinis algoritmo sudėtingumas yra skaičius papildomas atmintis \(S\), kuri reikalinga algoritmui veikti. Atmintis \(D\), reikalinga įvesties duomenims saugoti, neįtraukta į \(S\) .

\(S\) bendruoju atveju taip pat priklauso nuo pavaros. Tarkime, jei du vykdymo įrenginiai palaiko sveikuosius skaičius, kurių ilgis yra atitinkamai 4 ir 8 baitai, tada erdvinis algoritmo sudėtingumas 8 baitų sveikiesiems skaičiams bus dvigubai didesnis nei 4 baitų sveikųjų skaičių. Todėl erdvinis sudėtingumas taip pat vertinamas augimo tvarka.

Algoritmo sudėtingumo klasės

Tam tikras sunkumų klasės: Tai panašaus sudėtingumo kategorijos.

Išskiriamos šios pagrindinės sudėtingumo klasės:

DTIME Tiuringo mašina randa problemos sprendimą per ribotą laiką (žingsnių skaičių). Asimptotinis algoritmo elgesys dažnai nurodomas, taigi, tarkime, jei veikimo laiko didėjimo tvarka yra \(T(n) = \mathcal(O)(f(n))\), tada nurodykite \(DTIME(f) (n))\) . P Tiuringo mašina uždavinio sprendimą randa daugianario laiku (žingsnių skaičiumi), t.y. \(T(n) = \mathcal(O)(n^k)\) , kur \(k\in \mathbb(N)\) . \(P=DTIME(n^k)\) EXPTIME Tiuringo mašina problemos sprendimą randa per eksponentinį laiką (žingsnių skaičių), t.y. \(T(n) = \mathcal(O)(2^(n^k))\), kur \(k\in \mathbb(N)\) . \(EXPTIME=DTIME(2^(n^k))\) . DSPACE Turingo mašina randa problemos sprendimą naudodama baigtinį skaičių papildomos atminties(ląstelės). Dažnai nurodomas asimptotinis algoritmo elgesys, taigi, tarkime, jei atminties suvartojimo augimo tvarka yra \(S(n) = \mathcal(O)(f(n))\), tada nurodykite \(DSPACE(f) (n))\) . L Turingo mašina randa logaritminio erdvinio sudėtingumo uždavinio sprendimą, tai yra, \(S(n) = \mathcal(O)(\log n)\). \(L=DSPACE(\log n)\) . PSPACE Tiuringo mašina randa daugianario erdvės sudėtingumo uždavinio sprendimą, ty \(S(n) = \mathcal(O)(n^k)\) , kur \(k\in \mathbb(N)\ ). \(PSPACE=DSPACE(n^k)\) . EXPSPACE Tiuringo mašina randa eksponentinio erdvinio sudėtingumo problemos sprendimą, ty \(S(n) = \mathcal(O)(2^(n^k))\), kur \(k\in \mathbb(N)\) . \(EXPSPACE=DSPACE(2^(n^k))\) .

Be to, yra teorinių sudėtingumo klasių, kurios veikia su koncepcija nedeterministinis Tiuringo mašinos (TMT). Jų apibrėžimai yra tokie patys, kaip ir pirmiau, kai Tiuringo mašina pakeista NMT, o jų pavadinimai yra priešais N (pavyzdžiui, NP), išskyrus NTIME ir NSPACE, kur D pakeičiamas N.

NMT yra grynai teorinė konstrukcija, kurios veikimo principai yra panašūs į MT, su tuo skirtumu, kad kiekvienai būsenai gali būti kai kurie galimus veiksmus. Tuo pačiu metu NMT iš galimų veiksmų visada parenka tą, kuris atveda prie sprendimo minimaliu įmanomu žingsnių skaičiumi. Lygiai taip pat NMT atlieka skaičiavimus Visišakojasi ir pasirenka šaką, kuri veda į sprendimą per minimalų įmanomą žingsnių skaičių.

Kartais galite išgirsti, kad kvantiniai kompiuteriai yra NMT įgyvendinimas. Nors kai kuriais atvejais tai gali atrodyti tiesa, apskritai HMT yra galingesnė sistema nei kvantinis kompiuteris.

Yra žinoma, kad \(P \subseteq NP \subseteq PSPACE \subseteq EXPTIME \subseteq NEXPTIME \subseteq EXPSPACE\)

Be to, \(P \subsetneq EXPTIME\) , \(NP \subsetneq NEXPTIME\) , \(PSPACE \subsetneq EXPSPACE\)

Taip pat žinoma, kad jei \(P = NP\) , tai \(EXPTIME = NEXPTIME\) .

P ir NP lygybės klausimas yra vienas iš pagrindinių neišspręstų šiuolaikinės informatikos klausimų.

Algoritmų pavyzdžiai

Pateiksime keletą paprastų algoritmų pavyzdžių ir apsvarstykime jų sudėtingumą.

Pakėlimas į visą galią

Šis algoritmas buvo aprašytas Senovės Indijoje prieš mūsų erą ir naudojamas apskaičiuoti tikrojo skaičiaus \(x\) natūraliąją galią \(n\).

1. Parašykite \(n\) dvejetainėje skaičių sistemoje
2. Šiame įraše kiekvieną 1 pakeiskite raidžių pora KH, o kiekvieną 0 pakeiskite raide K
3. Nubraukite kairiausią porą KX
4. Skaitydami gautą eilutę iš kairės į dešinę, susidūrę su raide K, rezultatą padėkite kvadratu, o susidūrę su raide X - padauginkite iš x. Pradžioje rezultatas yra x.

Šiame algoritme turime daugybos operacijų skaičių, lygų skaitmenų skaičiui dvejetainėje atvaizde \(n\) geriausiu atveju ir \(2(n-1)\) blogiausiu atveju. Bet kokiu atveju, laiko sudėtingumas.

Efektyviai įgyvendinant algoritmą papildomos atminties praktiškai nereikia ir ji nepriklauso nuo įvesties duomenų, todėl erdvinis sudėtingumas yra \(S(n) = \mathcal(O)(1)\) .

Reikėtų pažymėti, kad yra ir efektyvesnių algoritmų. Tačiau, palyginti su „naiviu“ įgyvendinimu, kuriam reikalingos \(\mathcal(O)(n)\) daugybos operacijos, šis algoritmas yra palyginti efektyvus.

Sveikųjų skaičių dauginimas

Šis daugybos algoritmas kartais vadinamas rusišku arba valstietišku, nors buvo žinomas dar Senovės Egipte.

Pirmasis koeficientas paeiliui dauginamas iš dviejų, o antrasis – iš 2. Rezultatai rašomi dviem stulpeliais, kol antrajame gaunamas 1.

Daugybos rezultatas yra pirmojo stulpelio skaičių suma, priešais kurią yra nelyginiai antrojo stulpelio skaičiai.

Kadangi sveikųjų skaičių padalijimas ir daugyba iš 2 gali būti įgyvendinami perkeliant, šis algoritmas sukuria \(2 \log_2 n\) poslinkio operacijas, kur \(n\) yra mažesnis iš dviejų skaičių. Blogiausiu atveju taip pat atliekamos \(\log_2 n - 1\) pridėjimo operacijos. Bet kokiu atveju, laiko sudėtingumas \(T(n) = \mathcal(O)(\log n)\).

Efektyviam algoritmo įgyvendinimui praktiškai nereikia papildomos atminties ir ji nepriklauso nuo įvesties duomenų, todėl \(S(n) = \mathcal(O)(1)\)

Vėlgi, reikia pažymėti, kad yra ir efektyvesnių algoritmų. Tačiau, palyginti su „naiviu“ įgyvendinimu, kuriam reikalingos \(\mathcal(O)(n)\) pridėjimo operacijos, šis algoritmas yra palyginti efektyvus.

Pavyzdys

23 padauginus iš 43.

Paimkime 23 kaip antrąjį veiksnį.

43	23	nelyginis
86	11	nelyginis
172	5	nelyginis
344	2
688	1	nelyginis

Rezultatas \(43+86+172+688 = 989\)

Gavome 10 pamaininių operacijų ir 4 papildymo operacijas. Nuoroda \(\log_2(23) \apytiksliai 4,52\) .

Algoritmo sudėtingumo nustatymas

Asimptotinės analizės metu gautas sudėtingumo funkcijos įvertis vadinamas algoritmo sudėtingumu.

Reikėtų nepamiršti, kad yra keli algoritmo sudėtingumo įverčiai.

Asimptotinė sudėtingumo funkcijos elgsena yra operacijos sudėtingumas. Be to, galite nurodyti šiuos sunkumų tipus.

Laikinas sudėtingumas – asimptotinis algoritmo veikimo laiko įvertinimas pagal įvesties ilgio duomenis P. Akivaizdu, kad nesant skaičiavimo procedūrų lygiagretinimo, algoritmo veikimo laikas vienareikšmiškai nustatomas pagal atliktų operacijų skaičių. Operacijų trukmę išreiškiantys pastovūs koeficientai neturi įtakos laiko sudėtingumo tvarkai, todėl operacinio ir laiko sudėtingumo formulės dažnai sutampa.

Talpa sudėtingumas – asimptotinis vienu metu esamų skaliarinių dydžių skaičiaus įvertinimas, kai vykdomas algoritmas pagal ilgio įvesties duomenis P.

Struktūrinis sudėtingumas – valdymo struktūrų skaičiaus algoritme charakteristika ir jų santykinės padėties specifika.

Kognityvinis sudėtingumas - algoritmo prieinamumo charakteristika, kad ją suprastų taikymo sričių specialistai.

Asimptotikos rūšys ir žymėjimai

Atliekant asimptotinę algoritmų analizę, įprasta naudoti matematinės asimptotinės analizės žymėjimą. Šiuo atveju nagrinėjami trys algoritmų sudėtingumo įverčiai (asimptotika), kurie žymimi taip:

• 1) /(i) = O^(n))- asimptotiškai tikslus sudėtingumo funkcijos /(«) arba algoritmo veikimo sudėtingumo įvertinimas;
• 2) /(n) = 0 (§(n)) – asimptotiškai tiksli viršutinė sudėtingumo funkcijos riba /( P);
• 3) /(l) = ?2(#(l)) – asimptotiškai tiksli apatinė sudėtingumo funkcijos riba /( P).

Vietoj paskyrimo C1^(n)) labai dažnai naudojamas paprastesnis o(^(«)) su raide „o“, mažosiomis kursyvu.

Paaiškinkime formulių semantiką naudodami pavyzdį: jei parašyta /(i) = 0(^2(l)), TAI TAI reiškia, kad funkcija g(n)=og2 (n) yra asimptotiškai tikslus sudėtingumo funkcijos /(«) įvertinimas. Iš esmės teiginio forma yra dviejų pozicijų apibrėžimas:

Jei f(n)= @(log 2()),

mo g(n)= log 2 (l) - asimptotiškai tikslus įvertis f(n).

Atkreipkite dėmesį, kad pastovus daugiklis neturi įtakos algoritmo sudėtingumo tvarkai, todėl, nurodant logaritminį sudėtingumą, logaritmo bazė praleidžiama ir tiesiog rašoma /(l) = @(1о§(l)), o tai reiškia, kad logaritmas turi savavališką bazę, didesnę už vienetą.

Formalūs asimptotikos apibrėžimai

Asimptotiškai tikslus sudėtingumo funkcijos įvertinimas Su, Su 2, l 0, kad l>l 0 funkcija /(l), iki pastovių koeficientų, nesiskirtų nuo funkcijos g( l), tada funkcija g(n) vadinamas asimptotiškai tiksliu funkcijos f(n) įverčiu.

• 3 s ], s 2 e IR, c x > 0, su 2 > 0:
  • (3 l 0 e K, l 0 > 0: (/l e K, l > l 0:0 g(n) / (l) = 0(?(l)),

kur 9^, N yra atitinkamai visų realiųjų ir natūraliųjų skaičių aibės.

Asimptotiškai aštri viršutinė sudėtingumo funkcijos ribažodžiu apibrėžiamas taip: jei yra teigiamų skaičių Su ir l 0 taip, kad esant l>l 0 funkcija /(l) augtų ne greičiau už funkciją g(n) iki pastovaus koeficiento c, tada funkcija g(n) vadinama asimptotiškai tikslia viršutine funkcijos riba Ap).

Tikslesnis formalus apibrėžimo vaizdas yra toks:

• 3 Su e %s > 0:
  • (3 l 0 e X, l 0 > 0: (/l e K, l > l 0:0 s? #(l))) 0(g(n))

Asimptotiškai griežta apatinė sudėtingumo funkcijos ribažodžiu apibrėžiamas taip: jei yra teigiamų skaičių Su ir l 0 taip, kad l>l 0 funkcija /(l) augtų ne lėčiau nei funkcija g(n) iki pastovaus faktoriaus Su, tada funkcija?(l) vadinama asimptotiškai tikslia apatine funkcijos riba

Tikslesnis formalus apibrėžimo vaizdas yra toks:

• 3 Su e 9^, Su > 0:
  • (3 i 0 e X, i 0 > 0: (/i e K, i > aš 0: 0 s? g(n)

/(aš) = 0.^(n))

Atkreipkite dėmesį į šiuos dalykus:

• 1) formaliuose asimptotikos apibrėžimuose nurodytas nelygybes bendruoju atveju gali tenkinti ne viena, o tam tikras funkcijų rinkinys, dažnai turintis daugybę narių, todėl konstrukcijos Q(g(n)), 0^ (n)) Ir 0.^(n)) simbolizuoti daug funkcijų, su kuria lyginama tiriama darbo intensyvumo funkcija /(i); dėl to formos /(i) = 0(?(i)), /(/0 = O(? max (l)), Dia) = ?2(? t1n (i)) asimptotikos žymėjime ) vietoj ženklo „= „Racionaliau būtų naudoti ženklą „e“;
• 2) dizainai (d^(n)), 0^ (n)) Ir ?1^(n)), vartojamas kaip tam tikrų kiekių žymėjimas turėtų būti atitinkamai skaitomas taip: bet kokia funkcija, kuri sutampa, auga ne greičiau ir auga ne lėčiau g(n).

Asimptotikos sutapimas ir skirtumas

Atkreipkime dėmesį į tokį faktą: įvertis /(i) = 0(?(i)) nustato ir viršutinį, ir apatinį /(i) įvertį, nes jo apibrėžimas suponuoja ryšio pagrįstumą. su g(n)

Visai akivaizdi tokia asimptotikos savybė: jei sąmata f(n) = ©^(n)) egzistuoja, tada lygybės /( P) = 0(^(i)) ir /(i) =?2(#(i)), t.y. viršutinis ir apatinis darbo intensyvumo įverčiai sutampa; jei /(i) = 0(? max(i)) ir f(n) = C1^ mt(n)), Ir g max (n)фg m 1п (i), tada funkcijos nėra g(n), taip, kad /(i) = 0(?(i)).

Viršutinio ir apatinio darbo intensyvumo įverčių sutapimas galimas šiais atvejais:

• 1) sudėtingumo funkcija visoms įvesties ilgio reikšmėms yra deterministinė (neatsitiktinė) funkcija, t.y. atliktų operacijų skaičius nepriklauso nuo konkrečių šaltinio duomenų verčių; tokios, pavyzdžiui, yra daugybos ir dalybos operacijų skaičiaus priklausomybės nuo nežinomų dydžių skaičiaus funkcijos tiesinių sistemų sprendimo algoritme. algebrines lygtis IZ skilimo metodas;
• 2) sudėtingumo funkcija yra atsitiktinė funkcija, t.y. atliekamų operacijų skaičius priklauso nuo pradinių duomenų specifikos ir (ar) jų gavimo eiliškumo, taip pat galite nurodyti funkcijas / m|n (i), / max (i), apibūdinančias minimalų ir maksimalų skaičių. algoritmo vykdytojo atliekamos operacijos tam tikram įvesties ilgiui i, tačiau abi šios funkcijos turi tas pačias dominantes – pavyzdžiui, tai yra tos pačios eilės daugianariai.

Yra trys svarbios taisyklės, kurias reikia atsiminti dėl operacijų sudėtingumo užsakymo įvertinimų:

• 1) sudėtingumo tvarkai nustatyti neturi reikšmės pastovūs veiksniai, t.y. 0 (k?g(n)) = 0(g(«)) ;
• 2) dviejų funkcijų sandaugos sudėtingumo tvarka yra lygi jų sudėtingumo sandaugai, nes lygybė yra teisinga:
• 0 (gl (i) §2(i)) = 0 (?| (i)) 0 (#2(i)) ;
• 3) funkcijų sumos sudėtingumo tvarka lygi terminų dominantės tvarkai, pavyzdžiui: 0(ty e +p 2 +p) = 0 (i 5).

Aukščiau pateiktose taisyklėse naudojamas tik vieno asimptotinio įverčio simbolis 0("), tačiau jos galioja visiems asimptotiniams įverčiams – ir 0( ) , Ir &.{ ).

Elementariųjų funkcijų rinkinyje galite nurodyti funkcinio dominavimo sąrašą: if -kintamasis, a, b - yra skaitinės konstantos, tada teisingi šie teiginiai: Aš" dominuoja aš!; Aš! dominuoja a"; a" Zj dominuoja“ jei a>b a p dominuoja P b, jei A> 1 už bet kurį b e 9? ; p a a/ dominuoja jei a>b i dominuoja log d(i) if A > 1.

Vidutinio darbo intensyvumo įvertinimas

Praktikoje re Skaičiavimo atveju M sudėtingumo matematinio lūkesčio f(i) įvertinimas yra labai svarbus, nes daugeliu atvejų f(i) yra atsitiktinė funkcija. Tačiau atliekant eksperimentinius algoritmų tyrimus su atsitiktine /(i) atsiranda papildoma problema- pasirinkti testų skaičių, kad būtų galima patikimai įvertinti M. Šios problemos įveikimas yra pagrindinė užduotis. Siūlomas sprendimas pagrįstas beta pasiskirstymo naudojimu apytiksliai /(i). Tai labai konstruktyvi ir universali technika. Tačiau šiuolaikinėmis sąlygomis, kai kompiuterio našumas yra gana didelis, daugeliu atvejų galima naudoti paprastesnį testų apimties parinkimo metodą, pagrįstą esamo reikšmių kintamumo stebėjimu. f(n) – vertės įvertinamos tol, kol įverčių kintamumas tampa mažesnis už nurodytą paklaidą.

Algoritmo veikimo sudėtingumo įvertinimas

Algoritmo sudėtingumą galima nustatyti remiantis jo valdymo struktūrų analize. Algoritmai be kilpų ir rekursiniai skambučiai yra nuolat sudėtingi. Todėl algoritmo sudėtingumo nustatymas daugiausia susijęs su kilpų ir rekursinių skambučių analize.

Panagrinėkime pašalinimo algoritmą Į elementas iš dydžio masyvo P, susidedantis iš judančių masyvo elementų iš (k + 1) anksčiau P- viena pozicija atgal į masyvo pradžią ir mažinant elementų skaičių P vienetui. Masyvo apdorojimo ciklo sudėtingumas yra O (p-k), kadangi vykdomas kilpos korpusas (perkėlimo operacija). PC kartų, o kilpos korpuso sudėtingumas lygus 0(1), t.y. yra konstanta.

Nagrinėjamame pavyzdyje sudėtingumas apibūdinamas asimptotika 0("), nes šiame algoritme atliekamų operacijų skaičius nepriklauso nuo duomenų reikšmių specifikos. Sudėtingumo funkcija yra deterministinė, o visų tipų asimptotikos sutampa viena su kita: f(n) = Q(n-k), f(n) = 0(n-k) Ir f(n) = Q(n-k). Šį faktą liudija nuoroda ©( ). Turėtumėte naudoti 0 (*) ir (arba) 2 (*), tik jei šie asimptotikai skiriasi.

Ciklo tipas (for, while, pakartojimas) neturi įtakos sudėtingumui. Jei viena kilpa yra įdėta į kitą ir abi kilpos priklauso nuo to paties kintamojo dydžio, tada visam dizainui būdingas kvadratinis sudėtingumas. Pakartojimų išdėstymas yra pagrindinis veiksnys, didinantis sudėtingumą. Kaip pavyzdį pateikiame gerai žinomų paieškos ir rūšiavimo algoritmų sudėtingumą pagal dydį P:

• palyginimo operacijų skaičius nuoseklioje paieškoje: 0(i);
• palyginimo operacijų skaičius dvejetainėje paieškoje: 0 (log 2 P);
• palyginimo operacijų skaičius paprastu mainų metodu (burbulų rūšiavimas): 0(i 2);
• permutacijos operacijų skaičius rūšiuojant burbulą: 0 (n 2);

Atkreipkite dėmesį, kad palyginimo operacijų skaičius naudojant paprastą keitimo metodą yra asimptotinis 0 (n 2), o permutacijos operacijų skaičius turi dvi skirtingas asimptotikas 0 (n 2) ir?2(0), nes palyginimų skaičius nepriklauso nuo rūšiuojamų duomenų reikšmių specifikos, o permutacijų skaičių lemia būtent ši specifika. Permutacijos gali būti iš viso nevykdomos – jei duomenų masyvas iš pradžių teisingai sutvarkytas arba permutacijų skaičius gali būti maksimalus – apie P 2 – jei surūšiuotas masyvas iš pradžių surikiuotas priešinga kryptimi.

Funkcijos pavadinimas g(n) asimptotikoje /(l) = @(^(l)) ir /(«) = 0 (g (n)) algoritmui apibūdinti naudojama sudėtingumo funkcija /(«). Taigi jie kalba apie daugianario, eksponentinio, logaritminio ir kt. sudėtingumo algoritmus.

Sunkumo funkcija 0(1). Taikant pastovaus sudėtingumo algoritmus, dauguma operacijų programoje atliekamos vieną ar kelis kartus. Bet koks algoritmas, kuriam visada reikia (nepriklausomai nuo duomenų dydžio) tiek pat laiko, yra nuolat sudėtingas.

Sudėtingumo funkcija 0(N). Programos veikimo laikas dažniausiai yra linijinis, kai kiekvieną įvesties duomenų elementą reikia apdoroti tik linijinį skaičių kartų. Ši sudėtingumo funkcija apibūdina paprastą ciklą.

Sudėtingumo funkcija 0 (N 2), 0 (N 3), 0(№) - daugianario sudėtingumo funkcija: operacijų skaičius didėja su kvadratu N. Paprastai tai gali būti O(A^), priklausomai nuo problemos sudėtingumo. Ši sudėtingumo funkcija apibūdina sudėtingą ciklą.

Sunkumo funkcija O(2 žurnalas (A0), 0 (N log2(A0). Tai laikas, kai veikia algoritmai, kurie padalija didelę problemą į daug mažų, o tada, jas išsprendę, sujungia sprendimus.

Sudėtingumo funkcija 0(e N). Eksponentinio sudėtingumo algoritmai dažniausiai atsiranda dėl metodo, vadinamo brutalia jėga.

Sudėtingumo funkcija 0 (M) – operacijų skaičius auga proporcingai faktorialui N.

Programuotojas turi mokėti analizuoti algoritmus ir nustatyti jų sudėtingumą. Algoritmo sudėtingumas laike gali būti apskaičiuotas remiantis jo valdymo struktūrų analize.

Algoritmai be kilpų ir rekursiniai skambučiai yra nuolat sudėtingi. Jei nėra rekursijos ir kilpų, visas valdymo struktūras galima redukuoti į pastovaus sudėtingumo struktūras. Todėl visam algoritmui taip pat būdingas pastovus sudėtingumas. Algoritmo sudėtingumo nustatymas daugiausia susijęs su kilpų ir rekursinių skambučių analize.

Pavyzdžiui, apsvarstykite masyvo elementų apdorojimo algoritmą.

Jei /": = nuo 1 iki N daryti Pradėti

Šio algoritmo sudėtingumas APIE(A), nes ciklo korpusas vykdomas A kartus, o ciklo korpuso sudėtingumas yra 0(1). Jei viena kilpa yra įdėta į kitą ir abi kilpos priklauso nuo to paties kintamojo dydžio, tada visam dizainui būdingas kvadratinis sudėtingumas.

Už /: = nuo 1 iki N daryti Už j: = 1 iki N daryti Pradėti

Šios programos sudėtingumas 0 (N 2).

1 pavyzdys.Įvertinkime programos, kuri įveda iš klaviatūros masyvą ir randa didžiausią elementą jame, sudėtingumą. Algoritmas susideda iš šių žingsnių:

• - masyvo įvedimas (reikia perskaityti A elementus);
• - ieškoti didžiausio elemento (reikia atlikti A - 1 palyginimą);
• - išvesti rezultatą (reikia išvesti vieną skaičių arba eilutę).

Sudėkime operacijų skaičių A + (A - 1) + 1 = 2A, t.y. egzistuoja

tokia konstanta, kad bet kurio A operacijų skaičius neviršytų CA. Todėl algoritmo sudėtingumas yra 0(A).

2 pavyzdys.Įvertinkime programos, kuri iš klaviatūros įveda masyvą ir randa jame elementą su tam tikra savybe (pavyzdžiui, lygi tam tikrai reikšmei), sudėtingumą. Algoritmas susideda iš šių žingsnių:

• - masyvo įvestis (Įvesties operacijos);
• - ieškoti elemento su nurodyta savybe (elementas gali būti arba arčiau masyvo pradžios, arba pačioje pabaigoje; jei elemento nėra, reikia atlikti visus A palyginimus, kad tuo įsitikintume);
• - rezultato išvedimas.

Geriausiu atveju nurodytam algoritmui reikės A + 2 operacijų (viso masyvo įvedimas, vienas palyginimas, išvestis), blogiausiu atveju (kai tokio elemento nėra, 2A + 1 operacijos). Jei A yra didelis skaičius, pavyzdžiui, 10 6, tada vienybės galima nepaisyti. Todėl algoritmo sudėtingumas lygus 0 (N).

3 pavyzdys. Apibrėžkime ilgio žodžio šifravimo algoritmo sudėtingumo funkciją L pakeitimo būdu. Tebūnie lentelė, kurioje prie kiekvieno abėcėlės simbolio užrašomas simbolis, kuriuo jis turi būti pakeistas. Pažymime abėcėlės raidžių skaičių S. Algoritmas susideda iš šių žingsnių:

• - žodžio įvedimas (viena operacija);
• - ciklo organizavimas:
  • 1) kiekvienam simboliui lentelėje raskite jo pakaitalą (jei lentelė nėra užsakyta ir neturi savybių, palengvinančių paiešką, tada blogiausiu atveju jums reikės S operacijos vienam simboliui, jei ieškomas elementas yra pačioje pabaigoje);
  • 2) rasto simbolio išvestis;
• - ciklo pabaiga.

Bendras operacijų skaičius 1 + (S+)L. Esant pakankamai dideliam S Ir L vienetų galima nepaisyti, ir paaiškėja, kad pateikto algoritmo sudėtingumo funkcija yra O(S L).

4 pavyzdys. Apibrėžkime natūraliųjų skaičių vertimo algoritmo sudėtingumo funkciją 1 V į dvejetainę skaičių sistemą (be duomenų įvesties ir išvesties operacijų). Algoritmas susideda iš šių žingsnių:

• - kilpa tol, kol skaičiaus padalijimas iš 2 bus lygus 0:
• - skaičių padalinkite iš 2 ir prisiminkite likusią dalį;
• - padalyti rezultatą kaip naują skaičių;
• - ciklo pabaiga.

Bendras operacijų skaičius neviršija 1 + log 2 A. Todėl aprašytas algoritmas yra sudėtingas 0 (og 2 N).

Paskyrimas	Intuityvus paaiškinimas	Apibrėžimas
	f aukščiau apribota funkcija g	style="max-width: 98%; height: auto; width: auto;" src="/pictures/wiki/files/101/eebfe73c29ff3f9bc886d263bd3e91f3.png" border="0"> arba style="max-width: 98%; height: auto; width: auto;" src="/pictures/wiki/files/100/d96907f9d7419a7e0c74e4089c35c35e.png" border="0">
	f apribota funkcija g(iki pastovaus faktoriaus) asimptotiškai	style="max-width: 98%; height: auto; width: auto;" src="/pictures/wiki/files/48/0fda981f377ae7b8d361f58ce148c173.png" border="0">
	f apribota funkcija g asimptotiškai	0), n_0: \forall (n>n_0) \; |Cg(n)|
	g dominuoja f asimptotiškai	style="max-width: 98%; height: auto; width: auto;" src="/pictures/wiki/files/49/176ce786e936badb831a0bb87f25249d.png" border="0">
	f dominuoja g asimptotiškai	style="max-width: 98%; height: auto; width: auto;" src="/pictures/wiki/files/53/554bc3f42cfa6d0638722e58e4a99d8b.png" border="0">
	f lygiavertis g asimptotiškai

Pavyzdžiai

Pastabos

Reikia pabrėžti, kad blogiausio atvejo vykdymo laiko augimo laipsnis nėra vienintelis ar svarbiausias algoritmų ir programų vertinimo kriterijus. Štai keletas svarstymų, leidžiančių pažvelgti į vykdymo laiko kriterijų iš kitų požiūrių:

Jei n viršūnių grafo tam tikros problemos sprendimas vienu algoritmu užtrunka n C eilės laiko (žingsnių skaičių), o su kitu - n+n!/C, kur C yra pastovus skaičius, tada pagal „polinominę ideologiją“ pirmasis algoritmas yra praktiškai efektyvus, o antrasis – ne, nors, pavyzdžiui, esant C = 10 (10 10) situacija yra kaip tik priešinga.

1. Veiksmingi, bet sudėtingi algoritmai gali būti nepageidaujami, jei paruoštos programos bus remiami asmenys, nedalyvaujantys rašant šias programas. Tikėkimės, kad pagrindiniai efektyvių algoritmų kūrimo technologijos aspektai yra plačiai žinomi, o gana sudėtingi algoritmai laisvai naudojami praktikoje. Tačiau būtina atsižvelgti į galimybę, kad efektyvūs, bet „keblūs“ algoritmai nebus paklausūs dėl savo sudėtingumo ir sunkumų, kylančių bandant juos suprasti.
2. Yra keletas pavyzdžių, kai efektyviems algoritmams reikia tokio didelio kompiuterio atminties kiekio (be galimybės naudoti lėtesnių). išorės lėšos saugojimas), kad šis veiksnys paneigia algoritmo „efektyvumo“ pranašumą.
3. Skaitiniuose algoritmuose algoritmų tikslumas ir stabilumas yra ne mažiau svarbūs nei jų laiko efektyvumas.

Sunkumo klasės

Sudėtingumo klasė yra atpažinimo problemų, kurioms yra panašūs skaičiavimo sudėtingumo algoritmai, rinkinys. Du svarbūs atstovai:

P klasė

P ir NP klasių lygybės problema

Įžymūs mokslininkai

• Leonidas Levinas
• Aleksandras Razborovas
• Edis Šamiras

taip pat žr

Nuorodos

• Jurijus Lifshitsas „Šiuolaikinės teorinės informatikos problemos“. Paskaitų kursas apie NP sudėtingų problemų algoritmus.
• A. A. Razborovas Teorinis kompiuterių mokslas: matematiko požiūris // Kompiuteris. - 2001. - Nr. 2. (alternatyvi nuoroda)
• A. A. Razborovas Dėl skaičiavimų sudėtingumo // Matematinis išsilavinimas. - MCNMO, 1999. - Nr. 3. - P. 127-141.

Wikimedia fondas. 2010 m.

Pažiūrėkite, kas yra „Algoritmo laiko sudėtingumas“ kituose žodynuose:

laiko sudėtingumas (algoritmo)- — Temos informacijos apsauga LT laiko sudėtingumas... Techninis vertėjo vadovas

OPERATORIAUS VEIKLOS KOMPLEKSiškumas- objektyvių veiksnių, turinčių įtakos asmens reikalingų funkcijų valdymo sistemoje atlikimo kokybei ir trukmei, visuma. S. o. ir tt yra suskirstyta į keletą tipų, kurių kiekvienas tam tikru būdu apibūdinamas veiksnių deriniu... ... Enciklopedinis psichologijos ir pedagogikos žodynas

Skaičiavimo funkcija, suteikianti skaitinį algoritmo taikymo šaltinio duomenims procesų sudėtingumo (sudėtingumo) įvertinimą. Išaiškinus A. s. skaičiavimus aptarnauja signalizacijos funkcijos (arba tiesiog signalizacijos) funkcijos samprata, kuri yra pateikta... ... Matematinė enciklopedija

Informatikos moksle ir algoritmų teorijoje algoritmo skaičiavimo sudėtingumas yra funkcija, kuri lemia kokio nors algoritmo atliekamo darbo kiekio priklausomybę nuo įvesties duomenų dydžio. Skyrius, kuriame tiriamas skaičiavimo sudėtingumas, vadinamas teorija... ... Vikipedija

Kompiuterių moksle skaičiavimo sudėtingumo teorija yra skaičiavimo teorijos šaka, tirianti darbo sąnaudas, reikalingas skaičiavimo problemai išspręsti. Vertė paprastai matuojama abstrakčiomis laiko ir erdvės sąvokomis, vadinamomis... ... Vikipedija

Tai elementų išdėstymo sąraše algoritmas. Kai sąrašo elemente yra keli laukai, laukas, kuris naudojamas kaip užsakymo kriterijus, vadinamas rūšiavimo raktu. Praktikoje skaičius dažnai naudojamas kaip raktas, o kitose srityse... ... Vikipedija

Rūšiavimo algoritmas yra elementų išdėstymo sąraše algoritmas. Kai sąrašo elemente yra keli laukai, laukas, kuris naudojamas kaip užsakymo kriterijus, vadinamas rūšiavimo raktu. Praktikoje skaičius dažnai naudojamas kaip raktas, o ... ... Vikipedijoje

- (GM) kriptografinė sistema su viešasis raktas 1982 m. sukūrė Shafi Goldwasseris ir Silvio Micali. GM yra pirmoji tikimybinė viešojo rakto šifravimo schema, kuri yra įrodyta, kad yra stipri pagal standartinę kriptografinę... ... Vikipedija Skaityti daugiau

Ryšys