Programos laiko efektyvumas pagal atitinkamą algoritmą. Algoritmų ir duomenų struktūrų sudėtingumo ir efektyvumo sampratos. Ką darysime su gauta medžiaga?

Algoritmo efektyvumas yra algoritmo savybė, susieta su algoritmo naudojamais skaičiavimo ištekliais. Algoritmas turi būti išanalizuotas, siekiant nustatyti algoritmui reikalingus išteklius. Algoritmo efektyvumas gali būti laikomas analogišku pasikartojančių arba nuolatinių procesų gamybos našumui.

Siekdami maksimalaus efektyvumo, norime sumažinti išteklių naudojimą. Tačiau skirtingi ištekliai (pvz., laikas ir atmintis) negali būti tiesiogiai lyginami, todėl kuris iš dviejų algoritmų laikomas efektyvesniu, dažnai priklauso nuo to, kuris veiksnys yra svarbesnis, pvz., didelės spartos reikalavimas, minimalus atminties naudojimas ar kitas efektyvumą.

Atkreipkite dėmesį, kad šis straipsnis NE apie algoritmo optimizavimą, apie kurį kalbama straipsniuose programos optimizavimas, optimizuojantis kompiliatorius, ciklo optimizavimas, objekto kodo optimizavimo priemonė, ir taip toliau. Pats terminas „optimizavimas“ yra klaidinantis, nes viskas, ką galima padaryti, patenka į „tobulinimo“ skėtį.

Fonas

1843 m. Ada Lovelace pabrėžė efektyvumo svarbą, pabrėžiant vykdymo laiką, dėl Charleso Babbage'o mechaninio analitinio variklio:

„Beveik visuose skaičiavimuose yra didelis konfigūracijų pasirinkimas, leidžiantis sėkmingai užbaigti procesą, o skirtingos sutartys turėtų turėti įtakos pasirinkimui atliekant skaičiavimą. Esminis dalykas yra pasirinkti tokią konfigūraciją, kuri sumažins skaičiavimo laiką.

Ankstyvieji elektroniniai kompiuteriai buvo labai riboti tiek greičiu, tiek atmintimi. Kai kuriais atvejais buvo suprasta, kad yra laiko ir atminties kompromisas, kai užduotis turi naudoti daug atminties, kad pasiektų didelį greitį, arba naudoti lėtesnį algoritmą, kuris naudoja nedidelį kiekį darbinės atminties. Šiuo atveju buvo naudojamas greičiausias algoritmas, kuriam pakako turimos atminties.

Šiuolaikiniai kompiuteriai yra daug greitesni nei tie ankstyvieji kompiuteriai ir turi daug daugiau atminties (gigabaitų, o ne kilobaitų). Tačiau Donaldas Knuthas pabrėžia, kad efektyvumas išlieka svarbus veiksnys:

„Įprastose inžinerijos srityse 12% patobulinimas yra lengvai pasiekiamas ir niekada nebuvo laikomas pernelyg dideliu, ir manau, kad tas pats turėtų būti ir programuojant.

Apžvalga

Algoritmas laikomas efektyviu, jei jo išteklių suvartojimas (arba išteklių kaina) yra tam tikru priimtinu lygiu arba mažesnis. Grubiai tariant, „priimtinas“ reiškia „algoritmas veiks pagrįstą laiką turimame kompiuteryje“. Kadangi nuo šeštojo dešimtmečio gerokai išaugo kompiuterių apdorojimo galia ir turima atmintis, dabartinis „priimtinas lygis“ nebuvo priimtinas net prieš 10 metų.

Kompiuterių gamintojai periodiškai išleidžia naujus modelius, dažnai galingesnius. Programinės įrangos kaina gali būti gana didelė, todėl kai kuriais atvejais lengviau ir pigiau pasiekti geresnį našumą įsigyjant greitesnį kompiuterį, suderinamą su esamu kompiuteriu.

Yra daug būdų, kaip išmatuoti algoritmo naudojamus išteklius. Du dažniausiai naudojami matavimai yra greitis ir naudojama atmintis. Kiti matavimai gali apimti perdavimo greitį, laikiną disko naudojimą, ilgalaikį disko naudojimą, energijos suvartojimą, bendras nuosavybės išlaidas, reakcijos į išorinius signalus laiką ir pan. Daugelis šių matavimų priklauso nuo algoritmo įvesties duomenų dydžio (ty kiekių, kuriems reikia duomenų apdorojimo). Matavimai taip pat gali priklausyti nuo duomenų pateikimo būdo (pavyzdžiui, kai kurie rūšiavimo algoritmai prastai veikia jau surūšiuotus duomenis arba kai duomenys rūšiuojami atvirkštine tvarka).

Praktikoje yra ir kitų veiksnių, turinčių įtakos algoritmo efektyvumui, pavyzdžiui, reikalingas tikslumas ir (arba) patikimumas. Kaip paaiškinta toliau, algoritmo įgyvendinimo būdas taip pat gali turėti didelės įtakos faktiniam našumui, nors daugelis diegimo aspektų yra optimizavimo problemos.

Teorinė analizė

Atliekant teorinę algoritmų analizę, įprasta įvertinti algoritmo sudėtingumą jo asimptotinėje elgsenoje, ty atspindėti algoritmo sudėtingumą kaip įvesties dydžio funkciją. n Naudojamas didelis O žymėjimas. Šis įvertinimas paprastai yra gana tikslus dideliems n, bet gali lemti neteisingas išvadas esant mažoms vertėms n(Taigi, burbulų rūšiavimas, kuris laikomas lėtu, gali būti greitesnis nei greitasis rūšiavimas, jei reikia rūšiuoti tik kelis elementus).

Paskyrimas	vardas	Pavyzdžiai
O(1) (\displaystyle O(1)\,)	nuolatinis	Nustatyti, ar skaičius yra lyginis ar nelyginis. Naudojant pastovaus dydžio paieškos lentelę. Tinkamos maišos funkcijos naudojimas elementui pasirinkti.
O (log ⁡ n) (\displaystyle O(\log n)\,)	logaritminis	Elemento radimas surūšiuotame masyve naudojant dvejetainę paiešką arba subalansuotą medį, panašiai kaip dvinario krūvos operacijos.
O(n) (\displaystyle O(n)\,)	linijinis	Elemento radimas nesurūšiuotame sąraše arba nesubalansuotame medyje (blogiausiu atveju). Dviejų pridėjimas n-bitų numeriai naudojant nuo galo iki galo perdavimą.
O (n log ⁡ n) (\displaystyle O(n\log n)\,)	kvazilinearinis, logaritmiškai tiesinis	Apskaičiuokite greitą Furjė transformaciją, rūšiavimą į krūvą, greitą rūšiavimą (geriausiu ir vidutiniu atveju), sujungimo rūšiavimą
O (n 2) (\displaystyle O(n^(2))\,)	kvadratas	Padauginus du n-skaitmenų skaičiai naudojant paprastą algoritmą, burbulų rūšiavimas (blogiausiu atveju), apvalkalo rūšiavimas, greitasis rūšiavimas (blogiausiu atveju), pasirinkimo rūšiavimas, įterpimo rūšiavimas
O (c n) , c > 1 (\displaystyle O(c^(n)),\;c>1)	eksponentinis	Ieškoti keliaujančio pardavėjo problemos (tikslaus) sprendimo naudojant dinaminį programavimą. Nustatyti, ar du loginiai teiginiai yra lygiaverčiai naudojant išsamią paiešką

Patikrinimo testai: našumo matavimas

Naujoms programinės įrangos versijoms arba palyginimui su konkuruojančiomis sistemomis kartais naudojami etalonai santykiniam algoritmų našumui palyginti. Pavyzdžiui, jei išleidžiamas naujas rūšiavimo algoritmas, jį galima palyginti su pirmtakais, siekiant užtikrinti, kad algoritmas žinomų duomenų atžvilgiu būtų toks pat veiksmingas kaip ir kiti. Naudotojai gali naudoti našumo testus, norėdami palyginti skirtingų gamintojų produktus, kad įvertintų, kuris gaminys geriausiai atitiks jų reikalavimus funkcionalumo ir našumo požiūriu.

Kai kurie etaloniniai testai pateikia lyginamąją skirtingų kompiliavimo ir interpretavimo kalbų analizę, pvz., Roy Longbottom PC Benchmark Collection ir Kompiuterių kalbos etalonų žaidimas lygina kai kurių programavimo kalbų tipinių užduočių įgyvendinimų našumą.

Įgyvendinimo klausimai

Diegimo problemos taip pat gali turėti įtakos faktiniam našumui. Tai apima programavimo kalbos pasirinkimą ir algoritmo faktinio kodavimo būdą, pasirinktos kalbos vertėjo pasirinkimą arba naudojamas kompiliatoriaus parinktis ir net naudojamą operacinę sistemą. Kai kuriais atvejais kalba, įdiegta kaip vertėjas, gali būti žymiai lėtesnė nei kalba, įdiegta kaip kompiliatorius.

Yra ir kitų veiksnių, kurie gali turėti įtakos laiko ar atminties naudojimui, kurių programuotojas negali kontroliuoti. Tai apima duomenų suderinimą, detalizuojant, šiukšlių surinkimas , instrukcijų lygiagretumas ir paprogramių iškvietimas .

Kai kurie procesoriai turi galimybę atlikti vektorines operacijas, o tai leidžia viena operacija apdoroti kelis operandus. Gali būti, kad tokiomis funkcijomis naudotis programavimo ar kompiliavimo lygiu gali būti paprasta arba ne. Nuosekliam skaičiavimui skirtus algoritmus gali tekti visiškai pertvarkyti, kad būtų galima atlikti lygiagretųjį skaičiavimą.

Kita problema gali kilti dėl procesoriaus suderinamumo, kai instrukcijos gali būti įgyvendinamos skirtingai, todėl kai kurių modelių instrukcijos gali būti santykinai lėtesnės kituose modeliuose. Tai gali būti problema optimizuojančiam kompiliatoriui.

Išteklių naudojimo matavimas

Išmatavimai paprastai išreiškiami kaip įėjimo dydžio funkcija n.

Du svarbiausi matmenys yra šie:

Laikas: Kiek laiko algoritmas užtrunka CPU.
Atmintis: Kiek darbinės atminties (dažniausiai RAM) reikia algoritmui. Yra du aspektai: kodo atminties kiekis ir duomenims, kuriuos veikia kodas, atminties kiekis.

Baterijomis maitinamiems kompiuteriams (pvz., nešiojamiesiems kompiuteriams) arba labai ilgiems / dideliems skaičiavimams (pvz., superkompiuteriams) svarbu atlikti kitokį matavimą:

Tiesioginis energijos suvartojimas: Energija, reikalinga kompiuteriui paleisti.
Netiesioginis energijos suvartojimas: Energija reikalinga vėsinimui, apšvietimui ir kt.

Kai kuriais atvejais reikalingi kiti, retesni matavimai:

Pavaros dydis: Pralaidumas gali būti ribojantis veiksnys. Suspaudimas gali būti naudojamas siekiant sumažinti perduodamų duomenų kiekį. Pateikus grafiką ar vaizdą (pvz., „Google“ logotipą), gali būti perkelta dešimtys tūkstančių baitų (šiuo atveju – 48 KB). Palyginkite tai su šešių baitų perdavimu žodyje „Google“.
Išorinė atmintis: reikalinga atmintis diske arba kitame išoriniame saugojimo įrenginyje. Šią atmintį galima naudoti laikinai arba naudoti ateityje.
Atsakymo laikas: Šis nustatymas ypač svarbus realaus laiko programoms, kuriose kompiuteris turi greitai reaguoti į išorinius įvykius.
Bendros nuosavybės išlaidos: parametras svarbus, kai jis skirtas vienam algoritmui vykdyti.

Laikas

teorija

Šis testo tipas taip pat labai priklauso nuo programavimo kalbos pasirinkimo, kompiliatoriaus ir jo parinkčių, todėl lyginami algoritmai turi būti realizuoti vienodomis sąlygomis.

Atmintis

Šiame skyriuje aprašomas algoritmui reikalingos pagrindinės atminties (dažnai RAM) naudojimas. Kaip ir atliekant pirmiau pateiktą laiko analizę, paprastai naudojamas algoritmas erdvinis algoritmo sudėtingumasįvertinti reikalingą vykdymo atmintį kaip įvesties dydžio funkciją. Rezultatas paprastai išreiškiamas „O“ didele.

Yra keturi atminties naudojimo aspektai:

Atminties kiekis, reikalingas algoritmo kodui išsaugoti.
Atminties kiekis, reikalingas įvesties duomenims.
Atminties kiekis, reikalingas bet kokiam išėjimui (kai kurie algoritmai, pvz., rūšiavimas, dažnai pertvarko įvestį ir nereikalauja papildomos atminties išvesties).
Atminties, reikalingos skaičiavimo procesui skaičiavimo metu, kiekis (įskaitant įvardintus kintamuosius ir bet kokią dėklo vietą, reikalingą paprogramių iškvietimams, kurios gali būti reikšmingos naudojant rekursiją).

Ankstyvieji elektroniniai kompiuteriai ir namų kompiuteriai turėjo palyginti mažą darbinės atminties talpą. Taigi 1949 metais EDSAC maksimali darbinė atmintis buvo 1024 17 bitų žodžiai, o 1980 metais buvo išleistas Sinclair ZX80 su 1024 baitais darbinės atminties.

Šiuolaikiniai kompiuteriai gali turėti gana daug atminties (galbūt gigabaitų), todėl algoritmo naudojamą atmintį suspausti į tam tikrą atminties kiekį reikia mažiau nei anksčiau. Tačiau svarbu, kad egzistuoja trys skirtingos atminties kategorijos:

Talpykla (dažnai statinė RAM) – veikia panašiu greičiu kaip CPU
Pagrindinė fizinė atmintis (dažnai dinaminė RAM) – veikia šiek tiek lėčiau nei CPU
Virtuali atmintis (dažnai diske) – sukuria didžiulės atminties iliuziją, tačiau veikia tūkstančius kartų lėčiau nei RAM.

Algoritmas, kurio reikiama atmintis telpa į kompiuterio talpyklą, yra daug greitesnis nei algoritmas, kuris telpa į pagrindinę atmintį, o tai, savo ruožtu, bus daug greitesnis nei algoritmas, kuris naudoja virtualią erdvę. Viską apsunkina tai, kad kai kurios sistemos turi iki trijų talpyklos lygių. Skirtingos sistemos turi skirtingą šių tipų atminties kiekį, todėl algoritmo atminties efektas gali labai skirtis įvairiose sistemose.

Pirmosiomis elektroninio skaičiavimo dienomis, jei algoritmas ir jo duomenys netilpo į pagrindinę atmintį, jo nebuvo galima naudoti. Šiomis dienomis naudojant virtualiąją atmintį gaunama didžiulė atmintis, tačiau tai kainuoja našumą. Jei algoritmas ir jo duomenys telpa talpykloje, galima pasiekti labai didelį greitį, todėl reikiamos atminties sumažinimas padeda sumažinti laiką. Algoritmas, kuris visiškai netelpa į talpyklą, bet suteikia nuorodų vieta, gali dirbti gana greitai.

Veiksmingų algoritmų pavyzdžiai

Kritika dabartinei programavimo būklei

Programos lėtėja greičiau nei kompiuteriai.

May teigia:

Plačiai paplitusiose sistemose perpus sumažinus komandų vykdymą baterijos veikimo laikas gali padvigubėti, o dideli duomenys suteikia galimybę sukurti geresnius algoritmus: operacijų skaičiaus sumažinimas nuo N x N iki N x log(N) turi stiprų poveikį dideliam N... N. =30 milijardų, šie pokyčiai yra panašūs į 50 metų technologinius patobulinimus.

Konkursas dėl geriausio algoritmo

Kuriant geriausius algoritmus, kurių kokybės kriterijus nustato teisėjai, kviečia dalyvauti šios varžybos:

taip pat žr

Aritmetinis kodavimas yra entropinio kodavimo rūšis su kintamu kodo ilgiu efektyviam duomenų glaudinimui
Asociatyvus masyvas yra duomenų struktūra, kurią naudojant galima padaryti efektyvesnę medžiai PATRICIJA arba Judy masyvai
Veiklos testas – palyginamojo vykdymo laiko matavimo metodas tam tikrais atvejais
Geriausias, blogiausias ir vidutinis atvejis- trijų scenarijų vykdymo laiko įvertinimo taisyklės
Dvejetainė paieška yra paprastas ir efektyvus būdas ieškoti surūšiuotame sąraše
Šakų stalas

Paskaitos tikslai ir uždaviniai: supažindinimas su algoritmų ir duomenų struktūrų sudėtingumo ir efektyvumo analizės metodais

Pagrindiniai klausimai: eksperimentinė ir analitinė algoritmų efektyvumo analizė.

Klasikinis N. Wirtho teiginys „Gera programa yra gerai apgalvoto algoritmo ir efektyvių duomenų struktūrų vienybė“.

Algoritmo analizė
„Algoritmo ir duomenų struktūrų“ sąvokos yra pagrindinės kompiuterinių technologijų srityje, tačiau tam, kad tam tikras duomenų struktūras ir algoritmus būtų galima pavadinti „kokybiškomis ir efektyviomis“, reikia naudoti tikslius jų analizės metodus. Kaip natūralų kokybės kriterijų, natūralu, visų pirma, akcentuoti vykdymo laiką. Taip pat svarbus atminties ir vietos disko resursų kiekis, duomenų prieigos greitis (duomenų struktūros efektyvumas). Taip pat reikėtų atkreipti dėmesį į sprendimų patikimumą ir patikimumą, jų stabilumą.

Algoritmas neturėtų būti susietas su konkrečiu įgyvendinimu. Dėl naudojamų programavimo įrankių įvairovės skirtingi algoritmai gali duoti rezultatus, kurių efektyvumas skiriasi.

Algoritmo arba operacijos su duomenų struktūra vykdymo laikas, kaip taisyklė, priklauso nuo daugelio veiksnių. Paprasčiausias būdas nustatyti laiką, reikalingą algoritmui vykdyti, yra išmatuoti laiką prieš ir po algoritmo vykdymo.

Tačiau reikia atsiminti, kad šis laiko įvertinimo metodas nėra tikslus, visų pirma, reikia suprasti, kad šiuolaikinėse operacinėse sistemose galima atlikti keletą užduočių lygiagrečiai ir bandomojo atvejo vykdymą galima derinti su kitais tipais; veiklos. Be to, reikia suprasti, kad stabilią priklausomybę galima pasiekti tik atliekant pakartotinius bandymus, kitaip dėl atsitiktinių veiksnių, priklausančių nuo pradinių duomenų specifikos ir kitų veiksnių, įtakos galutiniam darbo rezultatui, atlikimas. algoritmo laikas taip pat bus atsitiktinis dydis. Atliekant tyrimą, algoritmą reikia paleisti su skirtingu pradinių duomenų rinkiniu, dažniausiai patys duomenys generuojami atsitiktinai, todėl dėl skirtingų duomenų rinkinių skirsis ir laikas.

Gavus įverčių rinkinį, galima sudaryti ir apytiksliai apskaičiuoti grafiką.

Tokia analizė visada turėtų būti naudojama naudojant netrivialius algoritmus, tai panašu į rekomendaciją sukurti programą, derinimui naudojant ne bandomąjį kelių dešimčių įrašų ar elementų rinkinį, o visus tikrus duomenis, kurie išvengia modifikavimo ar net; visiškai perdaryti algoritmo arba struktūrų duomenis, jei vėliau jie pasirodys nepraktiški. Turėdami eksperimentinių rezultatų rinkinį, galite atlikti interpoliaciją ir ekstrapoliaciją bei nustatyti algoritmo elgesį realiomis sąlygomis.

Apibendrinant galima teigti, kad algoritmo ar duomenų struktūros metodo vykdymo laikas didėja didėjant šaltinio duomenų dydžiui, nors tai priklauso ir nuo duomenų tipo, net jei dydis yra lygus. Be to, vykdymo laikas priklauso nuo techninės įrangos (procesoriaus, laikrodžio dažnio, atminties dydžio, vietos diske ir kt.) ir programinės įrangos (operacinės aplinkos, programavimo kalbos, kompiliatoriaus, interpretatoriaus ir kt.), su kuria vykdomas diegimas, kompiliavimas ir algoritmo vykdymas. Pavyzdžiui, jei visi kiti dalykai yra vienodi, tam tikro šaltinio duomenų kiekio algoritmo vykdymo laikas bus mažesnis, kai naudojamas galingesnis kompiuteris arba rašant algoritmą kaip programą mašininiu kodu, palyginti su jo vykdymu virtualioje mašinoje. interpretuojant jį į baitų kodus.

Peršasi išvada, kad atlikti empirinę algoritmų analizę nėra tikrai patikima. Pagrindinius trūkumus galima sumažinti iki šių trijų punktų:

1) eksperimentai gali būti atliekami tik naudojant ribotą pradinių duomenų rinkinį; į rezultatus, gautus naudojant kitą rinkinį, neatsižvelgiama.

2) norint palyginti dviejų algoritmų efektyvumą, būtina, kad eksperimentai jų vykdymo laikui nustatyti būtų atliekami ta pačia technine ir programine įranga;
3) eksperimentiškai ištirti algoritmo vykdymo laiką, būtina atlikti jo įgyvendinimą ir vykdymą.

Taigi, algoritmams analizuoti reikia naudoti bendruosius analizės metodus, kurie leidžia:

1) atsižvelgia į įvairius įvesties duomenis;

2) leidžia įvertinti bet kurių dviejų algoritmų santykinį efektyvumą, neatsižvelgiant į aparatinę ir programinę įrangą;

3) gali būti atliktas pagal algoritmo aprašymą be tiesioginio jo įgyvendinimo ar eksperimentų.

Bendrosios analizės esmė ta, kad funkcija f=f(n1, .., nm) priskiriama tam tikram algoritmui. Paprasčiausia forma tai yra vieno kintamojo n1 – įvesties duomenų kiekio – funkcija. Tačiau gali būti ir kitų kintamųjų – pavyzdžiui, skaičiavimo tikslumas ar jo patikimumas. Taigi, norint nustatyti, ar tam tikras skaičius yra pirminis, esant dideliems skaičiams (dvejetainio atvaizdo ilgis didesnis nei 200 bitų), naudojamas tikimybinis metodas, kurio patikimumą galima keisti. Labiausiai žinomos funkcijos yra tiesinės, galios ir logaritminės. Todėl turėtumėte skirti laiko prisiminti darbo su jais pagrindus.

Konstruojant algoritmus, pirmasis etapas vyksta naudojant ne programavimo kalbą, o aprašymą žmogaus kalba. Tokie aprašymai nėra programos, bet tuo pačiu jie yra labiau struktūruoti nei įprastas tekstas. Visų pirma, „aukšto lygio“ aprašymai sujungia natūralią kalbą ir įprastas programavimo kalbos struktūras, todėl jie yra prieinami, tačiau yra informatyvūs. Tokie aprašymai palengvina aukšto lygio duomenų struktūros ar algoritmo analizę. Tokie aprašymai paprastai vadinami pseudokodu. Taip pat reikėtų pažymėti, kad pseudokodas dažnai yra naudingesnis analizei nei kodas konkrečioje programavimo kalboje.

Kartais reikia įrodyti tam tikrus teiginius, susijusius su tam tikra duomenų struktūra ar algoritmu. Pavyzdžiui, turite parodyti algoritmo teisingumą ir greitį. Norint griežtai įrodyti teiginius, būtina naudoti matematinę kalbą, kuri pasitarnaus kaip teiginių įrodymas ar pagrindimas. Yra keletas paprastų būdų tai įrodyti.

Kartais teiginiai rašomi apibendrinta forma: „Aibėje s yra elementas x su savybe v. Norint įrodyti šį teiginį, pakanka pateikti pavyzdį x „priklauso“ s, kuris turi šią savybę. Tokia apibendrinta forma, kaip taisyklė, rašomi mažai tikėtini teiginiai, pavyzdžiui: „Kiekvienas aibės s elementas x turi savybę P“. Norint įrodyti šio teiginio klaidingumą, pakanka tiesiog pateikti pavyzdį: x „priklauso“ s, neturinčiam savybės P. Šiuo atveju elementas x veiks kaip priešinis pavyzdys.

Pavyzdys: Teigiama, kad bet koks 2^n - 1 formos skaičius yra pirminis, jei n yra sveikasis skaičius, didesnis už 1. Teiginys klaidingas.

Įrodymas: Norėdami įrodyti, kad kažkas klysta, turite rasti priešingą pavyzdį.

Tai yra priešingas pavyzdys: 2^4 - 1 = 15, 15 = 3 * 5.

Yra ir kitas būdas, pagrįstas įrodinėjimu prieštaravimu (naudojant neigimą). Pagrindiniai metodai šiuo atveju yra priešprieša ir prieštaravimas. Kontrastinių metodų naudojimas yra panašus į atspindėjimą: norėdami įrodyti, kad „jei x yra teisingas, tada y yra tiesa“, teigsime priešingai: „jei y yra klaidingas, tai x yra klaidingas“. Loginiu požiūriu šie teiginiai yra identiški, tačiau patogesnė yra antroji išraiška, kuri yra pirmosios kotropozicija.

Pavyzdys: Jei a*b yra nelyginis skaičius, tai a yra nelyginis arba b yra nelyginis.

Įrodymas: Norėdami įrodyti šį teiginį, apsvarstykite priešpriešą: „Jei a yra lyginis skaičius, o b yra nelyginis, tai a*b yra lyginis. Tegu a = 2*x tam tikram sveikajam skaičiui x. Tada a*b = 2*i*b, todėl sandauga a*b yra lyginė.

Taikant įrodinėjimo prieštaravimu būdus, pravartu pasitelkti logiką.

A arba b = reikia įvykdyti a arba b, arba abu a ir b tuo pačiu metu.
. a ir b = reikia, kad a ir b būtų vykdomi vienu metu.
. a xor b = reikia vykdyti a, bet ne b, arba b, bet ne a.

Naudojant prieštaravimo metodą norint įrodyti, kad teiginys q yra teisingas, pirmiausia daroma prielaida, kad q yra klaidinga, o tada parodoma, kad tokia prielaida sukelia prieštaravimą (pvz., 2 * 2<>4). Atsižvelgdami į tokį prieštaravimą galime teigti, kad situacija, kurioje q yra klaidinga, neegzistuoja, todėl q yra teisinga.

Daugeliu atvejų teiginiuose apie programos vykdymo laiką arba erdvės naudojimą naudojamas sveikasis skaičius n (nurodantis problemos „dydį“). Tada, kai suformuluojame teiginį x(n), tada n reikšmių rinkiniui tokie teiginiai yra lygiaverčiai. Kadangi šis teiginys taikomas „begaliniam“ skaičių rinkiniui, neįmanoma pateikti išsamaus tiesioginio įrodymo. Tokiose situacijose naudojami indukciniai metodai. Indukcijos metodas pagrįstas faktu; kad bet kuriam n > 1. Yra baigtinė veiksmų seka, kuri prasideda nuo to, kas žinoma kaip tiesa, ir galiausiai įrodo, kad q(n) yra tiesa. Taigi, įrodinėjimas indukcija prasideda teiginiu, kad q(n) yra teisingas, kai n=1,2,3 ir t.t. iki kokios nors pastovios k. Toliau įrodome, kad kitas indukcijų q(n+1), q(n+2) „žingsnis“ taip pat tinka n > k.

Analizuojant algoritmus, skaičiuojant operacijų skaičių ir jų vykdymo laiką, nereikėtų atsižvelgti į „smulkias detales“ ir nepaisyti konstantų. Praktikoje vartojama didelės funkcijos sąvoka APIE. Tarkime, kad yra dvi funkcijos f(n) ir g(n), daroma prielaida, kad f(n)<= O(g(n)) , т.е. функция О ограничивает сверху значения функции f, начиная с n=n0.

Pavyzdžiui, nuliui lygių elementų skaičiaus masyve skaičiavimo algoritmas apibūdinamas O(n), kur n yra elementų skaičius.

1) 20n3+7.2n2-21.78n + 5 apibūdinamas kaip O(n3)

2)xn-2 + a(0) apibūdinamas kaip O(xn).

2) 3*log(n) + log(log(n)) apibūdinamas kaip O(log(n)).

3) 2100 apibūdinamas kaip O(1)

4) 5/n apibūdinamas kaip O(1/n).

Atkreipkite dėmesį, kad funkcija o(n) riboja tikslinę laiko sąnaudų funkciją iš viršaus, tačiau visada turėtumėte stengtis pasirinkti tokią funkciją O(n), kad būtų maksimalus tikslumas.

Garsiausios O funkcijos didėjančia tvarka:

Naudodami asimptotinę analizę būkite atsargūs, kad naudodami O žymėjimą dažnai nepaisysite pastovių veiksnių ir pridėjimo konstantų. Tačiau jei ši reikšmė yra pakankamai didelė, nors funkcijos O(1) forma yra geresnė nei algoritmas, aprašytas funkcija O(n), tai, žinoma, antrasis algoritmas bus pritaikytas praktiškai.

Priklausomai nuo funkcijos f(n) tipo, išskiriamos šios algoritmų sudėtingumo klasės.

Algoritmo sudėtingumo klasės priklausomai nuo sudėtingumo funkcijos
Žiūrėti f(n)	Algoritmų klasės charakteristikos
	Dauguma daugumos funkcijų instrukcijų vykdomos vieną ar kelis kartus. Jei visos programos instrukcijos turi šią savybę, tada programos vykdymo laikas yra pastovus.
log N	Kai programos vykdymo laikas yra logaritminis, programa tampa lėtesnė, nes didėja N. Tokie vykdymo laikai paprastai siejami su programomis, kurios sumažina didelę problemą iki mažesnių subproblemų rinkinio, sumažindamos problemos dydį tam tikru pastoviu veiksniu kiekviename žingsnyje. Bazės keitimas neturi didelės įtakos logaritmo reikšmės pokyčiui: n
N	Kai programos vykdymo laikas yra tiesinis, tai paprastai reiškia, kad kiekvienas įvesties elementas mažai apdorojamas.
N log N	Vykdymo laikas, proporcingas N log N, atsiranda, kai algoritmas išsprendžia problemą, suskaidydamas ją į smulkesnes dalis, išspręsdamas jas savarankiškai ir sujungdamas sprendimus.
N 2	Kai algoritmo veikimo laikas yra kvadratinis, jis yra naudingas praktiniam naudojimui sprendžiant palyginti mažas problemas. Kvadratinis vykdymo laikas paprastai rodomas algoritmuose, kurie apdoroja visas duomenų elementų poras (galbūt dvigubo įdėjimo cikle).
N 3	Panašus algoritmas, apdorojantis duomenų elementų tripletus (galbūt trigubo lizdo kilpoje), turi kubinį vykdymo laiką ir praktiškai taikomas tik nedidelėms problemoms spręsti.
2 N	Tik keli algoritmai, kurių veikimo laikas yra eksponentinis, turi praktinį pritaikymą, nors tokie algoritmai atsiranda natūraliai bandant tiesiogiai išspręsti problemą, pvz., brutalią jėgą.

Remiantis matematiniais begalybės sudėtingumo asimptotinių funkcijų tyrimo metodais, išskiriamos penkios algoritmų klasės.

1. Greitų algoritmų klasė su pastoviu vykdymo laiku, jų sudėtingumo funkcija O(1). Tarpinę būseną užima O (log N) sudėtingumo algoritmai, kurie taip pat priskiriami šiai klasei.

2. Racionaliųjų arba polinominių algoritmų klasė, kurios sudėtingumo funkcija nustatoma polinomiškai iš įvesties parametrų. Pavyzdžiui, O(N), O(N 2, O(N 3).

3. Subeksponentinių algoritmų klasė su sudėtingumo laipsniu O(N log N).

4. Eksponentinių algoritmų, kurių sudėtingumo laipsnis O(2 N), klasė.

5. Viršeksponentinių algoritmų klasė. Yra faktorinio sudėtingumo algoritmų, tačiau jie paprastai neturi praktinio pritaikymo.

Atminties būsena algoritmo vykdymo metu nustatoma pagal reikšmes, kurioms reikia skirti tam tikras sritis. Šiuo atveju, sprendžiant problemą, galima naudoti papildomą ląstelių skaičių. Pagal algoritmo A reikalingą atminties kiekį D įėjimui, turime omenyje maksimalų atminties langelių skaičių, naudojamą vykdant algoritmą. Algoritmo talpos sudėtingumas apibrėžiamas kaip algoritmo blogiausio atvejo atminties talpos funkcijos asimptotinis įvertinimas.

Taigi, algoritmo išteklių sudėtingumas blogiausiu, vidutiniu ir geriausiu atveju apibrėžiamas kaip sutvarkyta laiko ir pajėgumo sudėtingumo funkcijų klasių pora, nurodyta asimptotiniu žymėjimu ir atitinkanti nagrinėjamą atvejį.

Pagrindinės procedūrinio programavimo algoritminės konstrukcijos yra sekimas, šakojimas ir kilpa. Norint gauti sudėtingumo funkcijas geriausiam, vidutiniam ir blogiausiam atvejui su fiksuotu įvesties matmeniu, būtina atsižvelgti į pagrindinių algoritminių struktūrų vertinimo skirtumus.

„Following“ konstrukcijos sudėtingumas yra vienas po kito einančių blokų sudėtingumo suma: f=f 1 +f 2 +...+f n .
„Branching“ dizaino sudėtingumas nustatomas pagal perėjimo prie kiekvienos instrukcijos tikimybę, kurią lemia sąlyga. Tuo pačiu metu būklės patikrinimas taip pat yra sudėtingas. Blogiausio atvejo sudėtingumui apskaičiuoti galima pasirinkti sudėtingiausią išsišakojusį bloką geriausiu atveju, galima pasirinkti mažiau sudėtingą bloką. f, jei =f 1 +f, tada p, tada +f kitaip (1-p tada)
„Cilpos“ konstrukcijos sudėtingumas nustatomas apskaičiuojant kilpos užbaigimo sąlygą (dažniausiai 0(1) eilės) ir užbaigtų ciklo iteracijų skaičiaus sandaugą pagal didžiausią įmanomą kilpos korpuso operacijų skaičių. Jei naudojamos įdėtos kilpos, jų sudėtingumas padidėja.

Taigi, norint įvertinti algoritmo sudėtingumą, galima suformuluoti bendrą sudėtingumo funkcijos gavimo metodą.

Algoritmo išskaidymas apima pagrindinių algoritmo struktūrų nustatymą ir sudėtingumo įvertinimą. Šiuo atveju atsižvelgiama į šias pagrindines algoritmines struktūras.
Pagrindinės kalbos operacijų darbo intensyvumo analizė eilutė po eilutės reiškia arba kaupiamąją analizę (atsižvelgiant į visas operacijas), arba operatyvinę analizę (atsižvelgiant į kiekvienos operacijos sudėtingumą).
Atvirkštinė sudėtingumo funkcijos sudėtis, pagrįsta pagrindinių algoritminių struktūrų geriausiu, vidutiniu ir blogiausiu atveju analizės metodika.

Rekursinių algoritmų išteklių efektyvumo vertinimo ypatybė yra būtinybė atsižvelgti į papildomas atminties sąnaudas ir rekursijos organizavimo mechanizmą. Todėl rekursinių algoritmų diegimų sudėtingumas yra susijęs su operacijų, atliktų per vieną rekursinį skambutį, skaičiumi, taip pat su tokių skambučių skaičiumi. Taip pat atsižvelgiama į verčių grąžinimo ir valdymo perdavimo iškvietimo punktui išlaidas. Apskaičiuojant reikalingą dėklo atmintį, reikia atsižvelgti į tai, kad tam tikru momentu krūvoje saugomas ne rekursinis fragmentas, o rekursinių iškvietimų grandinė. Todėl krūvos dydis nustatomas pagal maksimalų galimą vienu metu gaunamų pasikartojančių skambučių skaičių.

Programuotojo biblioteka

„Jei derinimas yra klaidų pašalinimo procesas, tai programavimas turėtų būti jų įvedimo procesas“

E. Dijkstra

1.2. Kodėl studijuoti algoritmus? Algoritmų efektyvumas

Pirma, algoritmai yra gyvybiškai svarbūs komponentai sprendžiant bet kokias problemas įvairiose kompiuterių mokslo srityse. Algoritmai vaidina pagrindinį vaidmenį dabartiniame technologijų vystymosi etape. Čia galite prisiminti tokias įprastas užduotis kaip:

įvairaus sudėtingumo matematinių lygčių sprendimas, matricų sandauga, atvirkštinės matricos;
rasti optimalius krovinių ir žmonių transportavimo būdus;
ieškant optimalių galimybių paskirstyti išteklius tarp įvairių mazgų (gamintojų, mašinų, darbuotojų, procesorių ir kt.);
rasti genome atitinkančias sekas;
informacijos paieška pasauliniame internete;
finansinių sprendimų priėmimas elektroninėje prekyboje;
garso ir vaizdo informacijos apdorojimas ir analizė.

Šis sąrašas tęsiasi ir tęsiasi, ir iš tikrųjų beveik neįmanoma rasti kompiuterių mokslo ir informacijos mokslo srities, kurioje nebūtų naudojami tam tikri algoritmai.

Antra, kokybiški ir veiksmingi algoritmai gali būti proveržių katalizatoriai iš pirmo žvilgsnio nuo informatikos tolimosiose pramonės šakose (kvantinė mechanika, ekonomika ir finansai, evoliucijos teorija).

Ir trečia, algoritmų studijos taip pat yra nepaprastai įdomus procesas, lavinantis mūsų matematinius gebėjimus ir loginį mąstymą.

1.3. Algoritmų efektyvumas

Tarkime, kad kompiuterio greitį ir jo atminties kiekį galima didinti neribotai. Ar tada reikėtų tirti algoritmus? Taip, bet tik siekiant parodyti, kad atsiejimo metodas turi ribotą veikimo laiką ir kad jis pateikia teisingą atsakymą. Jei kompiuteriai būtų be galo greiti, tiktų savavališkas teisingas problemos sprendimo būdas. Žinoma, tuomet dažniausiai būtų pasirenkamas lengviau įgyvendinamas būdas.

Šiandien kompiuteriai yra labai galingi, tačiau jų greitis nėra begalinis, taip pat ne begalinė atmintis. Taigi skaičiuojant tai yra tiek ribotas išteklius, kiek reikia atminties. Šie ištekliai turėtų būti naudojami protingai, o tai palengvina algoritmų, kurie yra efektyvūs laiko ir atminties išteklių naudojimo požiūriu, naudojimas.

Algoritmai, sukurti tai pačiai problemai išspręsti, dažnai gali labai skirtis efektyvumu. Šie skirtumai gali būti daug labiau pastebimi nei tie, kuriuos sukelia skirtinga aparatinė ir programinė įranga.

Kaip minėta pirmiau, šiame skyriuje pagrindinis dėmesys bus skiriamas rūšiavimo užduočiai. Pirmasis algoritmas, kuris bus svarstomas, įtraukimo rūšiavimas, reikalauja laiko dirbti, kurio kiekis apskaičiuojamas kaip c 1 n 2, kur n yra įvesties duomenų dydis (rūšiuojamų sekos elementų skaičius), c 1 yra tam tikra konstanta. Ši išraiška nurodo, kaip algoritmo veikimo laikas priklauso nuo šaltinio duomenų apimties. Įtraukimo rūšiavimo atveju ši priklausomybė yra kvadratinė. Antrasis algoritmas, sujungimo rūšiavimas, reikalauja laiko, kurio dydis yra 2 nLog 2 n. Paprastai įtraukimo rūšiavimo konstanta yra mažesnė nei sujungimo rūšiavimo konstanta, ty c12 auga greičiau, kai didėja n, nei funkcija ILog 2 n. O kai kuriai reikšmei n = n 0 bus pasiektas momentas, kai nustos reikšmės konstantų skirtumo įtaka ir ateityje funkcija c 2 nLog 2 n bus mažesnė už c 1 n 2 bet kuriam n > n 0.

Norėdami tai parodyti, apsvarstykite du kompiuterius – A ir B. Kompiuteris A yra greitesnis ir vykdo rūšiavimo algoritmą, o kompiuteris B yra lėtesnis ir vykdo sujungimo rūšiavimo algoritmą. Abu kompiuteriai turi rūšiuoti rinkinį, sudarytą iš milijono skaičių. Tarkime, kad kompiuteris A atlieka milijardą operacijų per sekundę, o kompiuteris B tik dešimt milijonų, yra A veikia 100 kartų greičiau nei B. Kad skirtumas būtų labiau pastebimas, tarkime, kad įjungimo metodo kodą parašė geriausias. programuotojas pasaulyje, naudodamas instrukcijas procesoriui, o norint surūšiuoti n skaičių pagal šį algoritmą, reikia atlikti 2n 2 operacijas (ty C 1 = 2). Sujungimo rūšiavimą kompiuteryje B parašė naujokas programuotojas, naudodamas aukšto lygio kalbą, o gautam kodui reikia 50nlog 2 n operacijų (ty c 2 = 50). Taigi, norint surūšiuoti milijoną skaičių, reikės kompiuterio A

ir į kompiuterį B -

Todėl naudojant kodą, kurio veikimo laikas didėja lėčiau, net ir esant blogam kompiuteriui ir blogam kompiliatoriui, reikia eilės tvarka mažiau procesoriaus laiko! Rūšiuojant 10 000 000 skaitmenų, suliejamo rūšiavimo pranašumas tampa dar labiau pastebimas: kai įtraukimo rūšiavimas tokiai užduočiai atlikti užtrunka apie 2,3 dienos, tai suliejant mažiau nei 20 minučių. Bendra taisyklė yra ta, kad kuo didesnis rūšiuojamų elementų skaičius, tuo didesnis sujungimo rūšiavimo pranašumas. Aukščiau pateiktas pavyzdys parodo, kad algoritmai, kaip ir kompiuterių programinė įranga, yra technologija. Bendras sistemos veikimas priklauso tiek nuo algoritmo efektyvumo, tiek nuo aparatinės įrangos galios.

Taigi, svarstomi įvairūs skaičiavimo mašinų variantai – nuo paprasčiausių Tiuringo mašinų iki vienalytės skaičiavimo aplinkos. Visi jie gali būti naudojami sprendžiant tas problemas, kurioms yra sukurtas algoritmas. Remiantis šiais modeliais, sukuriami labiau specializuoti skaičiavimo modeliai, būtent: nešakojančios aritmetinės programos, bitinis skaičiavimas, dvejetainis vektorių skaičiavimas ir sprendimų medžiai.

Algoritmai turi šias charakteristikas:

a) sudėtingumas;

b) darbo intensyvumas;

c) patikimumas ir kt.

Yra daug algoritmų sudėtingumo vertinimo kriterijų. Dažniausiai susidomėsime augimo tvarka laikas ir atminties talpa, reikalinga problemai išspręsti, nes didėja įvesties duomenų kiekis. Su kiekviena konkrečia užduotimi susiekime tam tikrą skaičių, vadinamą jo dydis. Pavyzdžiui, matricos daugybos uždavinio dydis gali būti didžiausias faktorių matricų dydis; uždavinio dydis grafe gali būti duoto grafo briaunų skaičius ir kt.

Laikas, kurį algoritmas užima kaip problemos dydžio funkcija, vadinamas laiko sudėtingumasšis algoritmas. Šio sudėtingumo elgesys riboje, kai problemos dydis didėja, vadinamas asimptotinis laiko sudėtingumas. Panašiai apibrėžta talpinis sudėtingumas Ir asimptotinis talpinis sudėtingumas.

Svarbi motyvacija svarstyti formalius skaičiavimo modelius yra noras atskleisti įvairių problemų skaičiavimo sudėtingumą, siekiant gauti apatines skaičiavimo laiko ribas. Norint parodyti, kad nėra algoritmo, galinčio atlikti tam tikrą užduotį per trumpesnį nei tam tikrą laiką, reikia tiksliai, o kartais ir labai specializuotai apibrėžti, kas yra algoritmas. Vienas iš tokio apibrėžimo pavyzdžių yra Tiuringo mašinos.

4.1.1. Rėmas ir rėmų mašinos*

Apsvarstykite du automobilius:

1. Mašinos su laisvąja prieiga prie atminties (vienodos prieigos adreso mašina - RAM) modeliuoja kompiuterį su vienu sumtuvu, kuriame programos instrukcijos negali pačios keistis.

2. Išsaugotos programos modelis yra mašina su atsitiktine prieiga prie atminties ir galimybe keisti instrukcijas (RAM*).

2.9 pav. RAM mašinų struktūra (RAM*)

RAM atveju programa neįrašoma į atmintį, todėl programa pati nesikeičia. Programa yra pažymėtų komandų seka. Yra aritmetinės instrukcijos, I/O instrukcijos, netiesioginio adresavimo instrukcijos ir šakų instrukcijos. Visi skaičiavimai atliekami registre r 0 (sudėtojas), kuris, kaip ir bet kuris kitas atminties registras, gali saugoti savavališką sveikąjį skaičių. Kiekviena komanda susideda iš dviejų dalių – operacijos kodo ir adreso. PAM komandos yra surinkimo kalbos komandų poaibis; šis pogrupis gali būti išplėstas savo nuožiūra, tačiau užduočių sudėtingumo tvarka nesikeis.

Operandas gali būti vieno iš šių tipų:

1. =i reiškia visą skaičių i ir vadinamas pažodžiu;

2. i- registruoti turinį i (i turi būti ne neigiamas);

3. *i reiškia netiesioginį adresavimą, tai yra, operando reikšmė yra registro turinys j, Kur j- sveikasis skaičius, kuris yra registre aš;Jei j<0, automobilis sustoja.

Galite nustatyti programos vertę R naudojant du objektus: atvaizdavimą c iš neneigiamų sveikųjų skaičių rinkinio į sveikųjų skaičių rinkinį ir „komandų skaitiklį“, kuris nustato kitą komandą, kurią reikia vykdyti. Funkcija c yra atminties ekranas, būtent c(i)- sveikasis skaičius, esantis registro numeryje aš (turinys Registruotis aš).

Pradžioje с(i)=0 visiems i 0 , programos skaitiklis nustatytas pagal pirmąją komandą P, o išvesties juosta tuščia. Po egzekucijos k komanda iš R skaitiklis automatiškai persijungia į (k+1)-oji (tai yra, į kitą) komandą, jei k-Mano komanda nebuvo tokia komanda kaip JUMP, HALT, JGTZ ir panašiai.

RAM* programa yra atminties registruose. Kiekviena RAM* komanda užima du iš eilės einančius atminties registrus: pirmame registre yra operacijos kodas, antrajame – adresas. RAM* instrukcijų rinkinys sutampa su atitinkamu RAM rinkiniu viskuo, išskyrus netiesioginį adresavimą, kuris neįtraukiamas: RAM* gali imituoti netiesioginį adresavimą, keisdama instrukcijas programos vykdymo metu.

Be patikrinimo, ar studento įdiegtas algoritmas kaip sprendimas yra pajėgus pateikti teisingą atsakymą į uždavinį, esant tam tikrais pradiniais duomenimis, tikrinant sprendimą atsižvelgiama ir į programos veikimo laiką. Tai nereiškia, kad gyvybiškai svarbu parašyti optimalius algoritmus visoms užduotims be išimties (tai dažnai gali užtrukti daug laiko kompetentingam jų įgyvendinimui ir derinimui). Tai tiesiog reiškia, kad kai kuriose atskirose užduotyse laiko parametras gali atlikti labai svarbų vaidmenį. Gali atsitikti taip, kad kokiame nors olimpiados etape nebus nei vienos problemos, kuriai reikia optimalumo. Tačiau gali nutikti ir priešingai.

Taigi, tiek studentai, tiek mokytojai turėtų turėti galimybę palyginti skirtingus algoritmus pagal jų efektyvumą. Moksleiviai – norėdami tinkamu momentu pasirinkti tinkamiausią problemos sprendimo būdą, mokytojai – kompetentingai parinkti užduotis ir suprasti, kokį sprendimą konkrečios problemos autorius turėjo omenyje nustatydamas būtent tokius laiko limitus.

Algoritmo efektyvumui įvertinti naudojama sudėtingumo funkcija, žymima O (skaitykite „apie didelį“). Tiesą sakant, yra ir kitokių vertinimų, tačiau tokioje stadijoje, kai studentas tik pradeda susipažinti su įvairiais algoritmais, jų tikrai nereikia. Sudėtingumo funkcija atspindi modelį, pagal kurį programos vykdymo laikas padidės, priklausomai nuo šaltinio duomenų arba jų kiekio.

Algoritmo, kurio vykdymo laikas priklauso nuo pradinių duomenų, pavyzdys yra visų natūraliųjų skaičiaus N daliklių suradimo algoritmas. Akivaizdu, kad kuo didesnis skaičius, tuo daugiau kilpos žingsnių reikės atlikti. Algoritmo, kurio vykdymo laikas priklauso nuo įvesties duomenų kiekio, pavyzdys būtų didžiausio skaičiaus masyve paieška. Kuo ilgesnis masyvas, tuo daugiau palyginimo operacijų reikia atlikti siekiant nustatyti, kuris skaičius yra didžiausias.

Pagrindinės funkcijos yra šios:

l O(1) - tokia sudėtingumo funkcija rodo, kad bet kokių pradinių duomenų programos veikimo laikas yra pastovus;

l O(N) – operacijų skaičius auga proporcingai N (čia N gali būti arba užduoties parametras, arba elementų skaičius masyve).

l O(log N) - operacijų skaičius auga proporcingai N logaritmui (būtent toks sudėtingumas yra, pavyzdžiui, puselių metodas ieškant elemento sutvarkytame masyve). N didėjant dydžiu, operacijų skaičius pasikeičia vienu. Logaritmo pagrindas dažniausiai nenurodomas, mus domina augimo pobūdis (greitas/lėtas), o ne tiksli laiko reikšmė.

l O(N2) – operacijų skaičius didėja proporcingai N kvadratui. Apskritai tai gali būti O(Nk) priklausomai nuo problemos sudėtingumo.

l O(N!) - operacijų skaičius didėja proporcingai faktorialui N.

Čia yra nemažai subtilybių dėl to, kad ne visos operacijos atliekamos per tą patį laiką, todėl vertinant laiko sudėtingumą, naudojamos tos operacijos, kurioms reikia daugiausiai laiko.

Dažniausiai aprašant algoritmus jų veikimo laikas pateikiamas gryna forma, tai yra neatsižvelgiant į įvesties/išvesties operacijas.

Pavyzdys: įvertinkime programos, kuri įveda iš klaviatūros masyvą ir randa didžiausią elementą, sudėtingumą.

Sudėkime operacijų skaičių N+(N-1)+1=2N. Tai yra, yra tokia konstanta, kad bet kurio N operacijų skaičius neviršija CN. Todėl algoritmo sudėtingumas yra O(N).

Pavyzdys: įvertinkime programos sudėtingumą, kuri klaviatūra įveda į masyvą ir randa jame elementą su nurodyta savybe (pavyzdžiui, lygi tam tikrai reikšmei).

Algoritmas susideda iš šių žingsnių:

Masyvo įvedimas (N įvesties operacijų) ieškant elemento su nurodyta savybe (kaip pasisekė: elementas gali būti arba arčiau masyvo pradžios, arba pačioje pabaigoje; jei elemento nėra, tuomet reikia Atlikite visus N palyginimus, kad tuo įsitikintumėte) išvesdami rezultatą .

Geriausiu atveju šis algoritmas pareikalaus N+2 operacijų (viso masyvo įvestis, vienas palyginimas, išvestis), blogiausiu atveju (kai tokio elemento nėra – 2N+1 operacijų). Jei N yra didelis skaičius, pavyzdžiui, apie 106, tada vienybės galima nepaisyti. Todėl algoritmo sudėtingumas yra O(N).

Pavyzdys: nustatykime L ilgio žodžių šifravimo algoritmo sudėtingumo funkciją keitimo metodu. Tebūnie lentelė, kurioje prie kiekvieno abėcėlės simbolio užrašomas simbolis, kuriuo jis turi būti pakeistas. Pažymime S abėcėlės raidžių skaičių.

Algoritmas susideda iš šių žingsnių:

Žodžio įvedimas (viena operacija) ciklas per visus simbolius

1. kiekvienam simboliui lentelėje raskite jo pakaitalą (jei lentelė nesutvarkyta ir neturi jokių paiešką palengvinančių savybių, tai blogiausiu atveju yra S operacijos vienam simboliui, jei ieškomas elementas yra pačiame galas)

2. rasto simbolio išvestis

Ciklo pabaiga

Bendras operacijų skaičius – 1+(S+1)*L. Esant pakankamai dideliems S ir L vienetams, galima nepaisyti, paaiškėja, kad šio algoritmo sudėtingumo funkcija yra O(S*L).

Pavyzdys: apibrėžkime natūraliojo skaičiaus N konvertavimo į dvejetainę skaičių algoritmo sudėtingumo funkciją (be duomenų įvesties ir išvesties operacijų).

Algoritmas susideda iš šių žingsnių:

Kartokite kilpą, kol skaičių padalijus iš 2 rezultatas bus 0

1. skaičių padalinkite iš 2 ir prisiminkite likusią dalį

2. paimti padalijimo rezultatą kaip naują skaičių

Ciklo pabaiga

Bendras operacijų skaičius neviršija 1+log2N. Todėl šio algoritmo sudėtingumas yra O(log N).

Jei programa susideda iš kelių dalių su skirtingo sudėtingumo funkcijomis, tada O Didesnio sudėtingumo funkcija „sugers“ mažesnius. Pavyzdžiui, jei įvesite O (N) masyvo, rūšiuojate O (N2) ir išvesite O (N) iš užsakyto masyvo, galite sakyti, kad visa programa turi O (N2) sudėtingumą.

Praktinis žinių apie algoritmų sudėtingumo funkcijas pritaikymas yra dvejopas. Pirma, tam tikrai užduočiai atlikti galima pasirinkti optimalesnį algoritmą, jei apie tai literatūroje yra atitinkamų duomenų. Antra, žinodamas savo sprendimo vykdymo trukmę viename pradinių duomenų rinkinyje, studentas gali apytiksliai įvertinti tos pačios programos veikimo laiką duomenims, kurie atitinka maksimalius tam tikros problemos apribojimus.

Klausimai

Šios užduotys yra naudojamos savarankiškam pateiktos medžiagos patikrinimui ir nėra privalomos.

1. Nustatykite kvadratinės lygties sprendimo algoritmo sudėtingumo funkciją.

2. Nustatykite taisyklingo daugiakampio nubrėžimo naudojant tam tikrą skaičių kraštinių algoritmo sudėtingumo funkciją.

3. Nustatykite elemento įterpimo į masyvą tam tikroje padėtyje algoritmo sudėtingumo funkciją (preliminariai perkeliant visus elementus, kurių skaičiai yra didesni arba lygūs duotam, po vieną į dešinę).

4. Nustatykite dviejų natūraliųjų skaičių sudėjimo į stulpelį algoritmo sudėtingumo funkciją (tegul A yra pirmojo skaičiaus skaitmenų skaičius, B - antrojo skaitmenų skaičius).

5. Nustatykite dviejų natūraliųjų skaičių stulpelyje daugybos algoritmo sudėtingumo funkciją.