Vlerësimi i kompleksitetit llogaritës. Kompleksiteti kohor i algoritmit

Përcaktimi i kompleksitetit të një algoritmi

Vlerësimi i funksionit të kompleksitetit i marrë në analizën asimptotike quhet kompleksiteti i algoritmit.

Duhet të kihet parasysh se ekzistojnë disa vlerësime të kompleksitetit të algoritmit.

Sjellja asimptotike e funksionit të kompleksitetit është kompleksiteti operacional. Përveç tij, ju mund të specifikoni llojet e mëposhtme të vështirësive.

E përkohshme kompleksiteti - një vlerësim asimptotik i kohës së funksionimit të algoritmit në të dhënat hyrëse të gjatësisë P. Natyrisht, në mungesë të paralelizimit të procedurave llogaritëse, koha e funksionimit të algoritmit përcaktohet në mënyrë unike nga numri i operacioneve të kryera. Koeficientët konstant që shprehin kohëzgjatjen e operacioneve nuk ndikojnë në rendin e kompleksitetit kohor, kështu që formulat për kompleksitetin operacional dhe kohor shpesh përkojnë me njëra-tjetrën.

kapacitore kompleksiteti - një vlerësim asimptotik i numrit të skalarëve ekzistues në të njëjtën kohë kur ekzekutohet algoritmi në të dhënat hyrëse të gjatësisë P.

Strukturore kompleksiteti - një karakteristikë e numrit të strukturave të kontrollit në algoritëm dhe specifikave të pozicionit të tyre relativ.

njohës kompleksiteti - një karakteristikë e disponueshmërisë së një algoritmi për të kuptuar nga ekspertët në fushat e aplikimit.

Llojet dhe shënimi i asimptotikëve

Në analizën asimptotike të algoritmeve, është zakon të përdoret shënimi i analizës asimptotike matematikore. Në këtë rast, merren parasysh tre vlerësime (asimptotikë) të kompleksitetit të algoritmeve, të cilat shënohen si më poshtë:

1) /(i) = O^(n))- vlerësimi asimptotikisht i saktë i funksionit të kompleksitetit /(«), ose kompleksitetit operacional të algoritmit;
2) /(n) = 0 (§(n)) - Vlerësimi i sipërm i saktë asimptotik i funksionit të kompleksitetit /( P);
3) /(l) = ?2(#(l)) - vlerësim më i ulët asimptotikisht i saktë i funksionit të inputit të punës /( P).

Në vend të emërtimit C1^(n)) shumë shpesh më e thjeshta o(^(“)) përdoret me shkronjën “o” kursive të vogla.

Le të shpjegojmë semantikën e formulave duke përdorur një shembull: nëse shkruhet / (n) = 0 (^2 (n)), ATËHERË KJO do të thotë se funksioni g(n)=og2 (n)është një vlerësim asimptotik i saktë i funksionit të kompleksitetit /(«). Në fakt, ekziston një përkufizim me dy pozicione në formën e një pohimi:

Nëse f(n)= @(log2 (")),

mo g(n)\u003d regjistri 2 (l) - Vlerësimi i saktë asimptotik i f(n).

Vini re se faktori konstant nuk ndikon në rendin e kompleksitetit të algoritmit, kështu që baza e logaritmit hiqet kur specifikohet kompleksiteti logaritmik, dhe ata thjesht shkruajnë f(l) = @(lо§(l)), që do të thotë se logaritmi ka një bazë arbitrare më të madhe se një.

Përkufizimet formale të asimptotikëve

Vlerësimi i saktë asimptotikisht i funksionit të inputit të punës me, Me 2 , l 0 , i tillë që për l>l 0 funksioni /(l), deri në faktorë konstant, nuk ndryshon nga funksioni g( k), pastaj funksioni g(n) quhet një vlerësim i saktë asimptotik i funksionit /(k).

3 s ] , s 2 e DHE, me x > 0, me 2 > 0:
- (3 l 0 e K, l 0 > 0: (/l e K, l > l 0:0 g(n) /(l) = 0(?(l)),

ku 9^, N janë bashkësitë e të gjithë numrave realë dhe natyrorë, përkatësisht.

Kufiri i sipërm i saktë asimptotikisht për funksionin e kompleksitetit përkufizohet verbalisht si më poshtë: nëse ka numra pozitivë Me dhe l 0 , i tillë që për l>l 0 funksioni /(l) nuk rritet më shpejt se funksioni g(n) deri në një faktor konstant c, pastaj funksioni g(n) quhet kufiri i sipërm i saktë asimptotikisht për funksionin Ap).

Një përkufizim zyrtar më i saktë ka formën:

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

Një kufi i poshtëm i saktë asimptotikisht për funksionin e kompleksitetit përkufizohet verbalisht si më poshtë: nëse ka numra pozitivë Me dhe l 0 , i tillë që për l>l 0 funksioni /(l) nuk rritet më ngadalë se funksioni g(n) deri në një faktor konstant me, atëherë funksioni?(k) quhet një kufi i poshtëm i saktë asimptotik për funksionin

Një përkufizim zyrtar më i saktë ka formën:

3 Me e 9^, Me > 0:
- (3 i 0 e X, i 0 > 0: (/i e K, i > Unë 0: 0 s? g(n)

/ (Unë) = 0.^(n))

Vini re sa vijon:

1) pabarazitë e treguara në përkufizimet formale të asimptotikëve, në rastin e përgjithshëm, mund të plotësohen jo nga një, por nga një grup i caktuar funksionesh, shpesh me një grup termash të panumërueshëm, kështu që ndërtimet Q(g(n)), 0^(n)) dhe 0.^(n)) simbolizojnë grup funksionesh, me të cilin krahasohet funksioni i hetuar i inputit të punës /(i); për shkak të kësaj, në shënimin e asimptotikës së formës /(n) = 0(?(n)), /(/0 = 0(? max (n)), Dn) = ?2(? m1n (n )) në vend të shenjës "= » do të ishte më racionale të përdoret shenja "e";
2) dizajne (d^(n)), 0^(n)) dhe ?1^(n)), përdoret si emërtim për disa sasi, duhet të lexohet në përputhje me rrethanat si më poshtë: çdo funksion që është i njëjtë, nuk rritet më shpejt dhe nuk rritet më ngadalë g(n).

Rastësia dhe ndryshimi i asimptotikëve

Le t'i kushtojmë vëmendje faktit të mëposhtëm: vlerësimi f(s) = 0(?(s)) përcakton për f(s) vlerësimet e sipërme dhe të poshtme, pasi përkufizimi i tij supozon vlefshmërinë e relacionit c g g(n)

Vetia e mëposhtme e asimptotikës është mjaft e dukshme: nëse vlerësimi φ(n) = ©^(n)) ekziston, atëherë barazitë /( P) = 0(^(n)) dhe /(n) = ?2(#(n)), d.m.th. vlerësimet e sipërme dhe të poshtme të intensitetit të punës përkojnë me njëri-tjetrin; nëse /(i) = 0(? max (i)) dhe φ(n) = C1^ mn (n)), dhe g max (n)Фg m 1n(i), atëherë nuk ka asnjë funksion g(n), e tillë që /(i) = 0(?(i)).

Koincidenca e vlerësimeve të sipërme dhe të poshtme të intensitetit të punës është e mundur në rastet e mëposhtme:

1) funksioni i kompleksitetit për të gjitha vlerat e gjatësisë së hyrjes është një funksion përcaktues (jo i rastësishëm), d.m.th. numri i operacioneve të kryera nuk varet nga specifikat e vlerave fillestare të të dhënave; të tilla, për shembull, janë funksionet e varësisë së numrit të operacioneve të shumëzimit dhe pjesëtimit nga numri i sasive të panjohura në algoritmin për zgjidhjen e sistemeve të ekuacioneve algjebrike lineare me metodën e zgjerimit IS;
2) funksioni i intensitetit të punës është një funksion i rastësishëm, d.m.th. numri i operacioneve të kryera varet nga specifikat e të dhënave fillestare dhe (ose) renditja e mbërritjes së tyre, dhe ju mund të specifikoni funksionet / m | megjithatë, të dy këto funksione kanë të njëjtat dominante, për shembull, ato janë polinome të të njëjtin rend.

Ekzistojnë tre rregulla të rëndësishme që duhen mbajtur parasysh kur bëhet fjalë për vlerësimin e rendit të kompleksitetit operacional:

1) faktorët konstant nuk kanë rëndësi për përcaktimin e rendit të kompleksitetit, d.m.th. 0 (k? g(n)) = 0(g("));
2) rendi i kompleksitetit të produktit të dy funksioneve është i barabartë me produktin e kompleksitetit të tyre, pasi barazia është e vërtetë:
0 (gl(i) §2(i)) = 0 (?| (i)) 0 (#2(i)) ;
3) rendi i kompleksitetit të shumës së funksioneve është i barabartë me rendin e dominantit të termave, për shembull: 0 (i e. + n 2 + n) = 0 (i 5).

Rregullat e mësipërme përdorin simbolin e vetëm një asimptotike 0 ("), por ato janë të vlefshme për të gjitha vlerësimet asimptotike - dhe për 0( ) , dhe &.{ ).

Në grupin e funksioneve elementare, mund të specifikoni një listë të dominimit funksional: nëse është një ndryshore, a, b- konstante numerike, atëherë pohimet e mëposhtme janë të vërteta: i" dominon i!; i! dominon a"; a" dominon Zj” nëse a>b a fq dominon P b, nëse a> 1 për çdo b e 9? ; n a dominon a/ nëse a>b i dominon log q(i) nëse a > 1.

Vlerësimi i intensitetit mesatar të punës

Në praktikë, re Llogaritjet me interes të konsiderueshëm janë vlerësimi /(n) i pritshmërisë matematikore të kompleksitetit të M, pasi në shumicën dërrmuese të rasteve /(n) është një funksion i rastësishëm. Sidoqoftë, në procesin e studimeve eksperimentale të algoritmeve me /(n) rastësore, lind një problem shtesë - zgjedhja e numrit të provave për një vlerësim të besueshëm të M. Kapërcimi i këtij problemi është një detyrë qendrore në. Zgjidhja e propozuar bazohet në përdorimin e shpërndarjes beta për të përafërt /(n). Kjo është një teknikë shumë konstruktive dhe e gjithanshme. Megjithatë, në kushtet moderne, kur performanca e kompjuterit është mjaft e lartë, në shumë raste është e mundur të përdoret një metodë më e thjeshtë për zgjedhjen e fushës së testeve, bazuar në monitorimin e ndryshueshmërisë aktuale të vlerave. f(n) - vlerat vlerësohen derisa varianca e vlerësimeve të bëhet më e vogël se gabimi i specifikuar.

Vlerësimi i kompleksitetit operacional të një algoritmi

Kompleksiteti i një algoritmi mund të përcaktohet bazuar në analizën e strukturave të tij të kontrollit. Algoritmet pa unaza dhe thirrjet rekursive kanë kompleksitet të vazhdueshëm. Prandaj, përkufizimi i kompleksitetit të një algoritmi reduktohet kryesisht në analizën e cikleve dhe thirrjeve rekursive.

Merrni parasysh algoritmin e fshirjes te-elementi i një grupi madhësish P, i përbërë nga lëvizja e elementeve të grupit nga (në + 1) -të për P-kthehu një pozicion prapa në fillim të grupit dhe zvogëlo numrin e elementeve P për njësi. Kompleksiteti i ciklit të përpunimit të vargjeve është Oh (p-k), pasi ekzekutohet trupi i ciklit (operacioni lëvizës). PC herë, dhe kompleksiteti i trupit të lakut është 0(1), d.m.th. është një konstante.

Në shembullin në shqyrtim, kompleksiteti karakterizohet nga asimptotika 0("), pasi numri i operacioneve të kryera në këtë algoritëm nuk varet nga specifikat e vlerave të të dhënave. Funksioni i kompleksitetit është përcaktues dhe të gjitha llojet e asimptotikave përkojnë me njëra-tjetrën: f(n) = Q(n-k), f(n) = 0(n-k) dhe f(n) = Q(n- në). Ky fakt dëshmohet nga treguesi saktësisht i ©( ). Përdorni 0(*) dhe/ose?2(*) vetëm nëse këto asimptotikë ndryshojnë.

Lloji i lakut (për, ndërsa, përsërit) nuk ndikon në kompleksitetin. Nëse një lak është i vendosur brenda një tjetri dhe të dy lakët varen nga madhësia e së njëjtës variabël, atëherë i gjithë ndërtimi karakterizohet nga kompleksiteti kuadratik. Folezimi i përsëritjeve është një faktor kryesor në rritjen e kompleksitetit. Si shembull, ne paraqesim kompleksitetin e algoritmeve të njohura të kërkimit dhe renditjes për një grup të madhësive P:

numri i operacioneve të krahasimit në kërkimin sekuencial: 0(n);
numri i operacioneve të krahasimit në kërkimin binar: 0 (log 2 P);
numri i operacioneve të krahasimit në metodën e thjeshtë të shkëmbimit (radhitje me flluska): 0(n 2);
numri i operacioneve të ndërrimit në renditje flluskë: 0 (n 2);

Vini re se numri i operacioneve të krahasimit në metodën e thjeshtë të shkëmbimit ka asimptotikë 0 (n 2), dhe numri i operacioneve të ndërrimit ka dy asimptotika të ndryshme 0 (fq 2) dhe?2(0), sepse numri i krahasimeve nuk varet nga specifika e vlerave të të dhënave të renditura, ndërsa numri i permutacioneve përcaktohet nga kjo specifikë. Permutacionet mund të mos kryhen fare - nëse grupi i të dhënave fillimisht është renditur saktë, ose numri i permutacioneve mund të jetë maksimal - i rendit P 2, - nëse grupi i renditur fillimisht është renditur në drejtim të kundërt.

Emri i funksionit g(n) në asimptotikën /(x) = @(x(x)) dhe /(a) = 0 (g(n)) funksioni i kompleksitetit /(«) përdoret për të karakterizuar algoritmin. Kështu, flitet për algoritme të kompleksitetit polinomial, eksponencial, logaritmik etj.

Me siguri ju keni hasur shpesh në shënime si O (log n) ose keni dëgjuar fraza si "kompleksiteti llogaritës logaritmik" në lidhje me ndonjë algoritëm. Dhe nëse ende nuk e kuptoni se çfarë do të thotë kjo, ky artikull është për ju.

Vlerësimi i vështirësisë

Kompleksiteti i algoritmeve zakonisht vlerësohet nga koha e ekzekutimit ose nga memoria e përdorur. Në të dyja rastet, kompleksiteti varet nga madhësia e të dhënave hyrëse: një grup prej 100 elementësh do të përpunohet më shpejt se një i ngjashëm me 1000. Në të njëjtën kohë, pak njerëz kujdesen për kohën e saktë: varet nga procesori, lloji i të dhënave, gjuha e programimit dhe shumë parametra të tjerë. Vetëm kompleksiteti asimptotik është i rëndësishëm, d.m.th., kompleksiteti pasi madhësia e hyrjes priret në pafundësi.

Le të themi se disa algoritme duhet të ekzekutojnë 4n 3 + 7n operacione të kushtëzuara për të përpunuar n elementë të të dhënave hyrëse. Ndërsa n rritet, koha totale e funksionimit do të ndikohet dukshëm më shumë duke ngritur n në kub sesa duke e shumëzuar me 4 ose duke shtuar 7n. Atëherë themi se kompleksiteti kohor i këtij algoritmi është i barabartë me O(n 3), d.m.th., varet në mënyrë kubike nga madhësia e të dhënave hyrëse.

Përdorimi i kapitalit O (ose i ashtuquajturi shënim O) vjen nga matematika, ku përdoret për të krahasuar sjelljen asimptotike të funksioneve. Formalisht, O(f(n)) do të thotë që koha e funksionimit të algoritmit (ose sasia e memories së zënë) rritet në varësi të sasisë së të dhënave hyrëse jo më shpejt se disa konstante shumëzuar me f(n) .

Shembuj

O(n) - kompleksiteti linear

Një kompleksitet i tillë ka, për shembull, algoritmin për gjetjen e elementit më të madh në një grup të pazgjedhur. Duhet të kalojmë nëpër të gjithë n elementët e grupit për të kuptuar se cili është më i madhi.

O (log n) - kompleksiteti i regjistrit

Shembulli më i thjeshtë është kërkimi binar. Nëse grupi është i renditur, ne mund të kontrollojmë nëse ai përmban një vlerë të caktuar duke ndarë në dysh. Le të kontrollojmë elementin e mesëm, nëse është më i madh se ai i dëshiruar, atëherë do të heqim gjysmën e dytë të grupit - definitivisht nuk është atje. Nëse më pak, atëherë anasjelltas - ne hedhim gjysmën fillestare. Dhe kështu ne do të vazhdojmë të ndajmë në gjysmë, si rezultat, ne do të kontrollojmë elementet log n.

O(n 2) - kompleksiteti kuadratik

Një kompleksitet i tillë ka, për shembull, algoritmin e renditjes së futjes. Në zbatimin kanonik, ai përbëhet nga dy sythe të mbivendosur: një për të kaluar nëpër të gjithë grupin dhe e dyta për të gjetur një vend për elementin tjetër në pjesën tashmë të renditur. Kështu, numri i operacioneve do të varet nga madhësia e grupit si n * n , pra n 2 .

Ka vlerësime të tjera të vështirësisë, por të gjitha bazohen në të njëjtin parim.

Ndodh gjithashtu që koha e funksionimit të algoritmit të mos varet fare nga madhësia e të dhënave hyrëse. Atëherë kompleksiteti shënohet si O(1) . Për shembull, për të përcaktuar vlerën e elementit të tretë të një grupi, nuk keni nevojë të mbani mend elementët ose t'i përsërisni mbi to disa herë. Ju gjithmonë duhet vetëm të prisni për elementin e tretë në rrjedhën e të dhënave hyrëse dhe ky do të jetë rezultati, llogaritja e të cilit për çdo sasi të dhënash kërkon të njëjtën kohë.

Në mënyrë të ngjashme, vlerësimi kryhet nga kujtesa, kur është i rëndësishëm. Megjithatë, algoritmet mund të përdorin dukshëm më shumë memorie kur madhësia e hyrjes rritet se të tjerët, por gjithsesi funksionojnë më shpejt. Dhe anasjelltas. Kjo ndihmon për të zgjedhur mënyrat më të mira për zgjidhjen e problemeve bazuar në kushtet dhe kërkesat aktuale.

Termi: 8 janar 2010

Para afatit, artikulli nuk duhet të redaktohet nga pjesëmarrësit e tjerë të projektit faqe interneti. Në fund të tij, çdo pjesëmarrës ka të drejtë të korrigjojë këtë artikull sipas gjykimit të tij dhe të fshijë këtë paralajmërim të shfaqur duke përdorur shabllonin ((Detyra)).

Shiko gjithashtu udhëzime mbi përdorimin e burimit faqe interneti në procesin arsimor.

Teoria e kompleksitetit llogaritës Një degë e teorisë llogaritëse që studion sasinë e punës së nevojshme për të zgjidhur një problem llogaritës.

Një detyrë konsiderohet e vështirë nëse zgjidhja e problemit kërkon një sasi të madhe burimesh, pavarësisht nga algoritmi i përdorur për ta zgjidhur atë. Teoria e zyrtarizon këtë nocion intuitiv duke prezantuar modele matematikore të llogaritjes për të studiuar këto probleme dhe për të përcaktuar sasinë e burimeve të nevojshme për t'i zgjidhur ato, si përdorimi i kohës dhe i kujtesës. Masat tjera të kompleksitetit janë të mundshme, si: numri i mesazheve (kompleksiteti i komunikimit), numri i elementeve në qarkun e elementeve funksionale (kompleksiteti i qarkut) dhe numri i procesorëve. Në veçanti, teoria e kompleksitetit llogaritës përcakton kufizimet praktike në atë që kompjuterët mund dhe nuk mund të bëjnë.

E lidhur ngushtë me teorinë e kompleksitetit llogaritës është analiza e algoritmeve dhe teoria e llogaritshmërisë. Dallimi kryesor midis teorisë së kompleksitetit llogaritës dhe analizës së algoritmit është se kjo e fundit merret me analizën e sasisë së burimeve të kërkuara nga një algoritëm i caktuar për të zgjidhur një problem, ndërsa i pari shtron një pyetje më të përgjithshme për të gjithë algoritmet e mundshme që mund të përdoren për të zgjidh të njëjtin problem.problem. Më saktësisht, teoria e kompleksitetit llogaritës përpiqet të klasifikojë problemet që mund ose nuk mund të zgjidhen nga një sasi e përshtatshme burimesh të kufizuara. Nga ana tjetër, vendosja e kufizimeve në burimet e disponueshme është ajo që e dallon teorinë e kompleksitetit llogaritës nga teoria e llogaritshmërisë: kjo e fundit pyet se cilat probleme mund të zgjidhen në parim në mënyrë algoritmike pa kufizuar burimet llogaritëse.

Probleme llogaritëse

Rastet e detyrave

Problemet (problemet) llogaritëse mund të shihen si një grup i pafund çiftesh: (shembull problemi, zgjidhje për një shembull të caktuar). Vargu i hyrjes për një problem llogaritës është një varg që përshkruan shembullin e problemit. Vargu i daljes për një problem llogaritës është një përshkrim i zgjidhjes për shembullin e problemit të përshkruar nga vargu hyrës. Për shembull, problemi i njohjes së thjeshtësisë së një numri: një shembull i problemit është një numër për të cilin duhet të përcaktohet nëse është i thjeshtë apo jo, zgjidhja është vargu "po" nëse ky numër është i thjeshtë dhe "jo". "përndryshe. Teoria e kompleksitetit llogaritës merr në konsideratë vetëm probleme masive, d.m.th. kërkesa që grupi i instancave të detyrave të jetë i pafund është i detyrueshëm.

Pamja e detyrave

Kur merren parasysh problemet llogaritëse, përshkrimi i një shembulli problemi është një varg mbi alfabetin. Si rregull, alfabeti merret si binar (d.m.th., grupi (0,1)). Objekte të ndryshme matematikore duhet të kodohen në përputhje me rrethanat. Kështu, për shembull, numrat e plotë mund të përfaqësohen në binar, dhe grafët mund të kodohen drejtpërdrejt përmes matricave të tyre të afërsisë ose përmes kodimit të listave të fqinjësisë në binar.

Detyrat e njohjes

Problemi i njohjes është një nga objektet qendrore të studimit në teorinë e kompleksitetit llogaritës. Një problem njohjeje është një lloj i veçantë i problemit llogaritës, përgjigja e të cilit është ose "po" ose "jo" (1 ose 0). Problemi i njohjes mund të formulohet si problemi nëse një varg hyrës i përket një nëngrupi (gjuhe) të caktuar të grupit të të gjitha vargjeve hyrëse. Vargu i hyrjes së problemit i përket gjuhës përkatëse nëse dhe vetëm nëse përgjigja e këtij vargu është "po". Kështu, detyra e njohjes është detyra e njohjes që një varg hyrës i përket një gjuhe të caktuar.

Një shembull i një problemi njohjeje. Vargu i hyrjes: përshkrimi i një grafi arbitrar. Problemi është të vendoset nëse grafiku i dhënë është i lidhur apo jo. Gjuha e grafikëve të lidhur është grupi i përshkrimeve të të gjithë grafikëve të lidhur. Për të marrë një përkufizim të saktë të kësaj gjuhe, duhet vendosur se si grafët kodohen si vargje binare.

Detyrat e kërkimit

Një detyrë kërkimi është një detyrë llogaritëse ku vlera e daljes është më komplekse sesa në një detyrë njohjeje (d.m.th., nuk është vetëm "po" ose "jo").

Një shembull i një problemi kërkimi është problemi i shitësit udhëtues. Problemi i shitësit udhëtues (shitës udhëtues) është një nga problemet më të famshme të optimizimit kombinator. Detyra është të gjeni rrugën më fitimprurëse duke kaluar nëpër qytetet e specifikuara të paktën një herë dhe më pas të ktheheni në qytetin origjinal. Në kushtet e problemit tregohet kriteri i përfitueshmërisë së itinerarit (kriteri më i shkurtër, më i lirë, kumulativ etj.) dhe matricat përkatëse të distancave, kostove etj.. Si rregull tregohet që itinerari duhet të kalojë. çdo qytet vetëm një herë - në këtë rast, zgjedhja bëhet midis cikleve Hamiltoniane. Vargu i hyrjes: përshkrimi i një grafiku të peshuar (d.m.th. me shenja numerike në skajet). Vargu i prodhimit është një përshkrim i rrugës optimale të shitësit udhëtues.

Ekziston një marrëdhënie çift midis detyrave të njohjes dhe detyrave të kërkimit. Problemi i kërkimit mund të formulohet si një problem njohjeje. Për shembull, për problemin e kërkimit "shumëzimi i dy numrave", problemi përkatës i njohjes së çiftit mund të përfaqësohet si një grup treshe (A, B, C) në mënyrë që marrëdhënia A × B = C të jetë e kënaqur.

Matja e Vështirësisë

Teoria e kompleksitetit llogaritës lindi nga nevoja për të krahasuar shpejtësinë e algoritmeve, për të përshkruar qartë sjelljen e tyre (koha e ekzekutimit, sasia e memories së kërkuar, etj.) në varësi të madhësisë së hyrjes dhe daljes.

Numri i operacioneve elementare të shpenzuara nga algoritmi për të zgjidhur një shembull të caktuar të problemit varet jo vetëm nga madhësia e të dhënave hyrëse, por edhe nga vetë të dhënat. Për shembull, numri i operacioneve të algoritmit të renditjes së futjes është shumë më i vogël nëse të dhënat hyrëse janë tashmë të renditura. Për të shmangur vështirësi të tilla, merrni parasysh konceptin e kompleksitetit kohor të algoritmit në rastin më të keq.

Kompleksiteti kohor i një algoritmi (në rastin më të keq) është një funksion i madhësisë së të dhënave hyrëse dhe dalëse, i barabartë me numrin maksimal të operacioneve elementare të kryera nga algoritmi për të zgjidhur një shembull problemi të madhësisë së specifikuar. Në problemet ku madhësia e daljes nuk e kalon ose është proporcionale me madhësinë e hyrjes, mund të konsiderohet kompleksiteti kohor vetëm si funksion i madhësisë së të dhënave hyrëse.

Ngjashëm me konceptin e kompleksitetit kohor në rastin më të keq, është përcaktuar koncepti i kompleksitetit kohor të një algoritmi në rastin më të mirë. Konsideroni gjithashtu konceptin e kohës mesatare të algoritmit, domethënë pritshmërinë matematikore të kohës së algoritmit. Ndonjëherë thuhet thjesht: "Kohë kompleksiteti i algoritmit" ose "Koha e algoritmit", duke iu referuar kompleksitetit kohor të algoritmit në rastin më të keq, më të mirë ose mesatar (në varësi të kontekstit).

Në analogji me kompleksitetin kohor, ata përcaktojnë kompleksitetin hapësinor të algoritmit, vetëm këtu nuk po flasin për numrin e operacioneve elementare, por për sasinë e memories së përdorur.

Përkundër faktit se funksioni i kompleksitetit kohor të një algoritmi mund të përcaktohet saktësisht në disa raste, në shumicën e rasteve është e pakuptimtë të kërkosh vlerën e tij të saktë. Çështja është se, së pari, vlera e saktë e kompleksitetit kohor varet nga përkufizimi i operacioneve elementare (për shembull, kompleksiteti mund të matet në numrin e veprimeve aritmetike ose operacioneve në një makinë Turing), dhe së dyti, si madhësia e të dhënat hyrëse rriten, kontributi i faktorëve konstant dhe termave të urdhrave më të ulët, që shfaqen në shprehjen për kohën e saktë të funksionimit, bëhet jashtëzakonisht i parëndësishëm.

Marrja parasysh e të dhënave të mëdha hyrëse dhe vlerësimi i rendit të rritjes së kohës së funksionimit të algoritmit çon në konceptin e kompleksitetit asimptotik të algoritmit. Në të njëjtën kohë, një algoritëm me më pak kompleksitet asimptotik është më efikas për të gjitha të dhënat hyrëse, përveç, ndoshta, për të dhënat me përmasa të vogla.

Kompleksiteti përcaktohet në bazë të modelit llogaritës në të cilin kryhen llogaritjet.

Modelet Llogaritëse

Ka shumë modele të ndryshme të llogaritjes: Makina postare, makina Minsky, llogaritja lambda, funksionet pjesërisht rekursive, algoritmet normale Markov, makinat me akses të rastësishëm në memorie (makinat RAM), etj. Le të përmendim vetëm modelin llogaritës më të njohur - Turing makinë.

Makina Turing

Makina Turing (MT) është një ekzekutues abstrakt (kompjuter abstrakt). Ai u propozua nga Alan Turing në 1936 për të zyrtarizuar konceptin e një algoritmi.

Makina Turing është një zgjatim i automatit të fundëm dhe, sipas tezës Church-Turing, është në gjendje të imitojë të gjithë ekzekutuesit e tjerë (duke vendosur rregullat e tranzicionit) që zbatojnë disi procesin e llogaritjes hap pas hapi, në të cilin çdo llogaritje hapi është mjaft elementar.

Përbërja e makinës Turing përfshin një shirit që është i pafund në të dy drejtimet (makinat Turing që kanë disa shirita të pafund janë të mundshme), të ndara në qeliza dhe një pajisje kontrolli të aftë për të qenë në një nga gjendjet e shumta. Numri i gjendjeve të mundshme të pajisjes së kontrollit është i fundëm dhe i dhënë saktësisht.

Pajisja e kontrollit mund të lëvizë majtas dhe djathtas përgjatë shiritit, të lexojë dhe të shkruajë simbole të disa alfabeteve të fundme në qelizat e shiritit. Alokohet një simbol i veçantë bosh, i cili mbush të gjitha qelizat e shiritit, me përjashtim të atyre prej tyre (një numër i kufizuar) në të cilin janë shkruar të dhënat hyrëse.

Pajisja e kontrollit funksionon sipas rregullave të tranzicionit, të cilat përfaqësojnë algoritmin e zbatuar nga kjo makinë Turing. Çdo rregull tranzicioni e udhëzon makinën, në varësi të gjendjes aktuale dhe simbolit të vëzhguar në qelizën aktuale, të shkruajë një simbol të ri në këtë qelizë, të shkojë në gjendjen e re dhe të lëvizë një qelizë majtas ose djathtas. Disa gjendje të makinës Turing mund të shënohen si terminale dhe kalimi në ndonjë prej tyre nënkupton përfundimin e punës, ndalimin e algoritmit.

Një makinë Turing thuhet se është përcaktuese nëse çdo kombinim i simbolit të gjendjes dhe shiritit në tabelë i korrespondon më së shumti një rregulli. Nëse ka një çift (simbol kasetë - gjendje) për të cilin ka 2 ose më shumë udhëzime, një makinë e tillë Turing quhet jo-përcaktuese.

Modeli i makinës Turing lejon zgjerime të ndryshme. Mund të konsiderohen makina Turing me një numër arbitrar shiritash dhe shirita shumëdimensionale me kufizime të ndryshme; makina që përdorin një burim rastësie.

Makina Turing është një nga modelet kryesore të llogaritjes në teorinë e kompleksitetit.

Klasat e vështirësisë

Klasat e kompleksitetit janë grupe problemesh llogaritëse që janë afërsisht të njëjta për sa i përket kompleksitetit llogaritës. Ka klasa kompleksiteti gjuhësor dhe klasa kompleksiteti funksional. Klasa e kompleksitetit të gjuhëve është një grup kallëzuesish (funksione që marrin një fjalë si hyrje dhe kthejnë një përgjigje prej 0 ose 1) që përdorin afërsisht të njëjtën sasi burimesh për të llogaritur. Koncepti i një klase të kompleksitetit funksional është i ngjashëm, përveç se nuk është një grup kallëzuesish, por një grup funksionesh. Në teorinë e kompleksitetit, si parazgjedhje, klasa e kompleksitetit është klasa e kompleksitetit të gjuhëve. Një përkufizim tipik i një klase kompleksiteti duket si ky:

Një klasë kompleksiteti X është një grup kallëzuesish P(x) që janë të llogaritshëm në makinat Turing dhe përdorin një burim O(f(n)) për të llogaritur, ku n është gjatësia e fjalës x.

Burimet zakonisht merren si kohë llogaritëse (numri i cikleve të punës së makinës Turing) ose zona e punës (numri i qelizave të përdorura në shirit gjatë funksionimit). Gjuhët e njohura nga kallëzuesit e një klase të caktuar (domethënë grupi i fjalëve për të cilat kallëzuesi kthen 1) thuhet gjithashtu se i përkasin të njëjtës klasë.

Përveç kësaj, shumë klasa mund të përshkruhen edhe në aspektin e logjikës matematikore ose teorisë së lojës.

Klasat zakonisht shënohen me shkronja të mëdha. Komplementi i klasës C (d.m.th., klasa e gjuhëve, plotësimet e të cilave i përkasin C) shënohet bashkë-C.

Për çdo klasë, ekziston një kategori detyrash që janë "më të vështirat". Kjo do të thotë që çdo detyrë nga një klasë reduktohet në një detyrë të tillë dhe, për më tepër, vetë detyra qëndron në klasë. Probleme të tilla quhen probleme të plota për një klasë të caktuar.

Klasa P

Klasa P (nga polinomi anglez) - një grup problemesh njohjeje që mund të zgjidhen në një makinë Turing përcaktuese në kohë polinomi në gjatësinë e hyrjes. Në mënyrë të ngjashme, për problemet e kërkimit, përcaktohet klasa FP (nga polinomi funksional anglisht).

Më formalisht, merrni parasysh makinat Turing përcaktuese që llogaritin përgjigjen e dhënë një fjalë në shiritin e hyrjes nga alfabeti i hyrjes. Koha e funksionimit të një makinerie Turing për një fjalë hyrëse fikse xështë numri i cikleve të punës së makinës Turing nga fillimi deri në ndalimin e makinës. Kompleksiteti i një funksioni të llogaritur nga disa makina Turing është një funksion që varet nga gjatësia e fjalës hyrëse dhe është e barabartë me kohën maksimale të funksionimit të makinës mbi të gjitha fjalët hyrëse me një gjatësi fikse:

Nëse për funksionin f ka një makinë Turing M të tillë që për një numër c dhe mjaft e madhe n, atëherë themi se i përket klasës FP, ose është polinom në kohë.

Klasa P është një nga ato themelore në teorinë e kompleksitetit llogaritës.

Klasa NP

Klasa NP (nga polinomi jo-përcaktues anglez) është një grup problemesh njohjeje, koha e zgjidhjes së të cilave varet ndjeshëm nga madhësia e të dhënave hyrëse; në të njëjtën kohë, ekziston një algoritëm që, pasi të ketë marrë, së bashku me përshkrimin e vlerave hyrëse, disa informacione shtesë (dëshmia e zgjidhjes), mund të zgjidhë mjaft shpejt (në një kohë që nuk e kalon polinomin e madhësisë së të dhënave). problemin.

Më formalisht, një gjuhë L thuhet se i përket klasës NP nëse ekziston një kallëzues me dy vende R(x, y) nga klasa P (d.m.th., i llogaritshëm në kohë polinomiale) dhe një polinom p i tillë që për çdo fjalë x e gjatësisë n kushti "x i përket L" është ekuivalent me kushtin "ka y me gjatësi më të vogël se p(n) në mënyrë që R(x, y) të jetë e vërtetë". Fjala y quhet dëshmi se x i përket gjuhës L. Kështu, nëse kemi një fjalë që i përket gjuhës dhe një fjalë tjetër dëshmitare me gjatësi të kufizuar (e cila mund të jetë e vështirë për t'u gjetur), atëherë mund të verifikojmë shpejt se x realisht i përket L. Çdo problem që i përket NP mund të zgjidhet në kohë eksponenciale duke numëruar të gjithë dëshmitarët e mundshëm me gjatësi më të vogël se p(n).

Një shembull i një problemi nga NP: problemi i njohjes "Ekzistenca e një zgjidhjeje të plotë për një sistem pabarazish lineare". Dëshmitari është zgjidhja e sistemit të pabarazive. Është e lehtë të kontrollohet në kohë polinomi se zgjidhja e dëshmitarit përshtatet.

Klasa NP përfshin klasën P.

Çështje të hapura

Ka shumë probleme të pazgjidhura në teorinë e kompleksitetit llogaritës, ato kryesisht kanë të bëjnë me çështjet e ndarjes ose foleve të klasave të caktuara të kompleksitetit. Një nga këto pyetje është problemi i barazisë së klasave P dhe NP.

Problemi i barazisë së klasave P dhe NP

Në fund të fundit, problemi i barazisë së klasave P dhe NP është ky: nëse një përgjigje pozitive për një pyetje mund të kontrollohet shpejt (në kohë polinomiale), atëherë a është e vërtetë që përgjigja për këtë pyetje mund të gjendet shpejt (në kohë polinomiale )?

Nga përkufizimi i klasave P dhe NP rrjedh menjëherë përfundimi: . Megjithatë, asgjë nuk dihet deri më tani për ashpërsinë e kësaj përfshirjeje, d.m.th. nëse ekziston një algoritëm që është në NP por jo në P. Nëse nuk ekziston një algoritëm i tillë, atëherë të gjitha problemet që i përkasin klasës NP mund të zgjidhen në kohë polinomiale, gjë që premton një përfitim të madh llogaritës. Tani problemet më të vështira NP (të ashtuquajturat probleme të plota NP) mund të zgjidhen në kohë eksponenciale, gjë që është pothuajse gjithmonë e papranueshme.

Çështja e barazisë së këtyre dy klasave konsiderohet si një nga problemet e hapura më të vështira në fushën e shkencës teorike kompjuterike. Aktualisht, shumica e matematikanëve besojnë se këto klasa nuk janë të barabarta. Instituti i Matematikës Clay e ka përfshirë këtë problem në listën e Problemeve të Mijëvjeçarit, duke ofruar një shpërblim prej një milion dollarësh për zgjidhjen e tij.

Letërsia

Gehry M., Johnson D. Makinat kompjuterike dhe probleme të vështira për t'u zgjidhur. Shtëpia Botuese Mir në 1982. - 420 f. Monografia e shkencëtarëve amerikanë i kushtohet zgjidhjes së problemeve komplekse (përfshirë NP-hard) kombinuese që lindin në optimizimin diskret, programimin matematik, algjebër, teorinë e automatëve me shembuj.
Kormen, Thomas H.; Leizerson, Charles I.; Rivest, Ronald L.; Stein, Clifford Algorithms: Construction and Analysis, 2nd edition = Introduction to Algorithms edicioni i dytë. - M.: "Williams", 2005. -

Ne tashmë e dimë se korrektësia është larg nga cilësia e vetme që duhet të ketë një program i mirë. Një nga më të rëndësishmet është efikasiteti, i cili karakterizon, para së gjithash, kohë të çojë programe për të dhëna të ndryshme hyrëse (parametër ).

Gjetja e varësisë së saktë për një program të caktuar është një detyrë mjaft e vështirë. Për këtë arsye, zakonisht është i kufizuar vlerësime asimptotike ky funksion, domethënë një përshkrim i sjelljes së tij të përafërt për vlera të mëdha të parametrit. Ndonjëherë, për vlerësimet asimptotike, përdoret lidhja tradicionale (lexo "Big O") midis dy funksioneve. , përkufizimi i të cilit mund të gjendet në çdo tekst shkollor për analizën matematikore, megjithëse përdoret më shpesh relacioni i ekuivalencës(lexo "theta e madhe"). Përkufizimi i tij formal është, për shembull, në libër, megjithëse tani për tani do të mjaftojë që ta kuptojmë këtë çështje në terma të përgjithshëm.

Si shembull i parë, le të kthehemi te programet që sapo morëm parasysh për gjetjen e faktorialit të një numri. Është e lehtë të shihet se numri i operacioneve që duhet të kryhen për të gjetur faktorialin! numri në përafrimin e parë është drejtpërdrejt proporcional me këtë numër, sepse numri i përsëritjeve të ciklit (përsëritjeve) në këtë program është i barabartë me . Në një situatë të tillë, është zakon të thuhet se programi (ose algoritmi) ka kompleksiteti linear(kompleksiteti ose).

A është e mundur të llogaritet faktoriali më shpejt? Rezulton se po. Është e mundur të shkruhet një program që do të japë rezultatin e saktë për të njëjtat vlera për të cilat bëjnë të gjitha programet e mësipërme, pa përdorur as përsëritje ose rekursion. Kompleksiteti i tij do të jetë , që në fakt nënkupton organizimin e llogaritjeve sipas ndonjë formule pa përdorimin e cikleve dhe thirrjeve rekursive!

Jo më pak interesant është shembulli i llogaritjes së numrit të Fibonaçit. Në procesin e studimit të tij, në fakt, tashmë është zbuluar se kompleksiteti i tij është eksponenciale dhe e barabartë me . Programe të tilla praktikisht nuk janë të zbatueshme në praktikë. Kjo është shumë e lehtë për t'u verifikuar duke u përpjekur të llogarisni numrin e 40-të të Fibonaccit me të. Për këtë arsye, problemi i mëposhtëm është mjaft i rëndësishëm.

Detyra 5.4 kompleksiteti linear.

Këtu është një zgjidhje për këtë problem, në të cilin variablat j dhe k përmbajnë vlerat e dy numrave të njëpasnjëshëm Fibonacci.

Teksti i programit

klasa publike FibIv1 ( boshllëku publik statik kryesor (String args) hedh Përjashtim ( int n = Xterm.inputInt ("Enter n ->< 0) { Xterm.print(" не определено\n"); } else if (n < 2) { Xterm.println(" = " + n); } else { long i = 0; long j = 1; long k; int m = n; while (--m >0) ( k = j; j += i; i = k; ) Xterm.println (" = " + j); ) ))

Pyetja tjetër është mjaft e natyrshme - a është e mundur të gjesh numrat e Fibonaçit edhe më shpejt?

Pas studimit të seksioneve të caktuara të matematikës, është mjaft e thjeshtë të nxirret formula e mëposhtme për numrin -th Fibonacci, e cila është e lehtë të kontrollohet për vlera të vogla:

Mund të duket se, bazuar në të, është e lehtë të shkruhet një program me kompleksitet, i cili nuk përdor përsëritje ose rekursion.

Teksti i programit

klasa publike FibIv2 ( boshllëku publik statik kryesor (String args) hedh Përjashtim ( int n = Xterm.inputInt ("Enter n -> "); f dyfishtë = (1.0 + Math.sqrt(5.)) / 2.0; int j = (int)(Math.pow(f,n) / Math.sqrt(5.) + 0.5); Xterm.println("f(" + n + ") = " + j); ) )

Në fakt, ky program përdor një thirrje për funksionin e fuqizimit ( Math.pow(f,n) ), i cili nuk mund të zbatohet më shpejt se në kohën logaritmike (). Rreth algoritmeve në të cilat numri i operacioneve është afërsisht proporcional (është e zakonshme në shkencën kompjuterike të mos tregohet baza e logaritmit binar) ata thonë se ata kanë kompleksiteti logaritmik ().

Për të llogaritur numrin e Fibonaçit, ekziston një algoritëm i tillë, zbatimin e softuerit të të cilit do ta japim pa komente shtesë, përndryshe duhet të shpjegoni shumë (lidhja e numrave Fibonacci me fuqitë e një matrice të caktuar të rendit dy, duke përdorur klasa për punë me matrica, algoritëm për ngritjen e shpejtë të matricës në fuqi).

Detyra 5.5. Shkruani një program që printon numrin -të Fibonacci që ka kompleksiteti logaritmik.

Teksti i programit

klasa publike FibIv3 ( publike statike void main (string args) hedh Përjashtim ( int n = Xterm.inputInt ("Enter n -> "); Xterm.print ("f(" + n + ")"); nëse (n< 0) { Xterm.println(" не определено"); } else if (n < 2) { Xterm.println(" = " + n); } else { Matrix b = new Matrix(1, 0, 0, 1); Matrix c = new Matrix(1, 1, 1, 0); while (n>0) ( nëse ((n&1) == 0) ( n >>>= 1; c. katror (); ) tjetër ( n -= 1; b.mul (c); ) ) Xterm.println (" = " +b.fib()); ) ) ) Matrica e klasës ( private e gjatë a, b, c, d; matricë publike (e gjatë a, e gjatë b, e gjatë c, e gjatë d) ( this.a = a; this.b = b; this.c = c; kjo.d = d; ) zbrazëti publike mul(Matrica m) ( e gjatë a1 = a*m.a+b*m.c; e gjatë b1 = a*m.b+b*m.d; e gjatë c1 = c*m.a+ d *m.c; e gjatë d1 = c*m.b+d*m.d; a = a1; b = b1; c = c1; d = d1; ) katror publik i zbrazët () ( mul(kjo); ) fib i gjatë publik ( ) (kthimi b;))

Nëse përpiqeni të llogaritni numrin e dhjetë miliontë të Fibonacci duke përdorur këtë dhe programin e mëparshëm, atëherë ndryshimi në kohën e llogaritjes do të jetë mjaft i dukshëm. Fatkeqësisht, rezultati do të jetë i pasaktë (në të dyja rastet) për shkak të gamës së kufizuar të numrave të llojit të gjatë .

Si përfundim, japim një tabelë krahasuese të kohërave të ekzekutimit të algoritmeve me kompleksitet të ndryshëm dhe shpjegojmë pse, me rritjen e shpejtësisë së kompjuterit, rëndësia e përdorimit të algoritmeve të shpejta rritet ndjeshëm.

Konsideroni katër algoritme për zgjidhjen e të njëjtit problem me kompleksitetet , dhe , respektivisht. Supozoni se i dyti prej këtyre algoritmeve kërkon saktësisht një minutë kohë për t'u ekzekutuar në një kompjuter me vlerën e parametrit. Atëherë koha e ekzekutimit të të gjithë këtyre katër algoritmeve në të njëjtin kompjuter me vlera të ndryshme të parametrit do të jetë afërsisht e njëjtë si në 10 300000 vjet

Kur programuesit fillestar testojnë programet e tyre, vlerat e parametrave nga të cilët varen janë zakonisht të vogla. Prandaj, edhe nëse është përdorur një algoritëm joefikas gjatë shkrimit të një programi, kjo mund të kalojë pa u vënë re. Megjithatë, nëse një program i tillë tentohet të zbatohet në kushte reale, atëherë papërshtatshmëria e tij praktike do të shfaqet menjëherë.

Me një rritje të shpejtësisë së kompjuterëve, rriten edhe vlerat e parametrave për të cilët funksionimi i një ose një algoritmi tjetër përfundon në një kohë të pranueshme. Kështu, vlera mesatare e vlerës rritet dhe, rrjedhimisht, rritet vlera e raportit të kohëve të ekzekutimit të algoritmeve të shpejta dhe të ngadalta. Sa më i shpejtë të jetë kompjuteri, aq më e madhe është humbja relative kur përdorni një algoritëm të keq!

Për të krahasuar algoritmet, është zakon të përdoret një karakteristikë e përgjithësuar e quajtur efikasitet. Thuhet se algoritmi L, më efikase algoritmi A 2, nëse algoritmi L ekzekutohet në më pak kohë dhe (ose) kërkon më pak burime kompjuterike (RAM, hapësirë në disk, trafik në rrjet, etj.).

Një algoritëm efikas duhet të plotësojë kërkesat e kohës së pranueshme të ekzekutimit dhe konsumit të arsyeshëm të burimeve, siç është përmendur tashmë në seksionin 1.1. Kombinimi i këtyre karakteristikave është koncepti i kompleksitetit të algoritmit. Me një rritje në kohën e ekzekutimit të algoritmit dhe (ose) burimeve të përfshira, kompleksiteti rritet. Kështu, konceptet e efikasitetit dhe kompleksitetit janë të kundërta nga njëri-tjetri.

Karakteristika e një algoritmi që pasqyron kohën e shpenzuar për zbatimin e tij quhet kompleksiteti kohor. Një karakteristikë e një algoritmi që pasqyron kostot e burimeve kompjuterike të zbatimit të tij quhet kompleksiteti kapacitiv.

Në vlerësimet sasiore dhe cilësore të algoritmit të lidhur me përcaktimin e kompleksitetit, përdoren dy qasje - praktike dhe teorike.

Qasje praktike lidhur me ekzekutimin e algoritmeve në pajisje fizike specifike. Karakterizohet nga parametra që mund të maten dhe të fiksohen. Kompleksiteti i kohës në këtë qasje mund të shprehet në njësi kohore (p.sh., milisekonda) ose numrin e cikleve të procesorit të nevojshëm për të ekzekutuar algoritmin. Kompleksiteti kapacitiv mund të shprehet në bit (ose njësi të tjera informacioni), kërkesat minimale të harduerit që kërkohen për të ekzekutuar algoritmin, etj.

Rezultati praktik nuk është një masë absolute e performancës së algoritmit. Vlerat sasiore të marra me këtë qasje varen nga shumë faktorë, si p.sh.

karakteristikat teknike të komponentëve që përbëjnë sistemin informatik. Pra, sa më e lartë të jetë frekuenca e orës së procesorit, aq më shumë operacione elementare për njësi të kohës mund të kryhen;
karakteristikat e mjedisit të softuerit (numri i proceseve të ekzekutimit, algoritmi i planifikuesit të detyrave, veçoritë e sistemit operativ, etj.);
gjuha programuese e zgjedhur për zbatimin e algoritmit. Një program i shkruar në një gjuhë të nivelit të lartë ka të ngjarë të funksionojë më ngadalë dhe të kërkojë më shumë burime sesa një program i shkruar në gjuhë të nivelit të ulët që kanë akses të drejtpërdrejtë në burimet e harduerit;
përvoja e programuesit që ka zbatuar algoritmin. Me shumë mundësi, një programues fillestar do të shkruajë një program më pak efikas sesa një programues me përvojë.

Kështu, një algoritëm që funksionon në të njëjtin sistem kompjuterik për të njëjtat të dhëna hyrëse mund të ketë rezultate të ndryshme në kohë të ndryshme. Prandaj, qasja teorike për përkufizimin e kompleksitetit është më e rëndësishme.

Kompleksiteti teorik karakterizon algoritmin pa iu referuar pajisjeve specifike, softuerëve dhe mjeteve të zbatimit. Në këtë rast, kompleksiteti kohor shprehet në terma të numrit të operacioneve, cikleve të makinës Turing etj. Kompleksiteti kapacitiv përcaktohet nga sasia e të dhënave (hyrje, ndërmjetëse, dalje), numri i qelizave të përfshira në shiritin e makinës Tyoring, etj.

Në qasjen teorike të vlerësimit të efikasitetit, konsiderohet se algoritmi është ekzekutuar në disa kompjuter i idealizuar, për të cilin koha e ekzekutimit të çdo lloj operacioni është e njohur dhe konstante. Besohet gjithashtu se burimet e një kompjuteri të tillë janë të pafundme, kështu që kompleksiteti kapacitiv zakonisht nuk përcaktohet në qasjen teorike. Si një karakteristikë kohore e kompleksitetit, zgjidhet numri i instruksioneve (operacioneve) të kryera në një kompjuter të idealizuar.

Vlerësimet sasiore të marra në qasjen teorike mund të varen gjithashtu nga një sërë faktorësh të mëposhtëm:

sasia e të dhënave hyrëse. Sa më i madh të jetë, aq më shumë kohë do të duhet për të ekzekutuar algoritmin;
metoda e zgjedhur për zgjidhjen e problemit. Për shembull, për një sasi të madhe të dhënash hyrëse, algoritmi i renditjes së shpejtë është më efikas se algoritmi i renditjes me flluska, megjithëse çon në të njëjtin rezultat.

Koha e ekzekutimit të algoritmit zakonisht varet nga sasia e të dhënave hyrëse (madhësia e hyrjes), e cila kuptohet si dimensioni i problemit që zgjidhet. Pra, kur renditni një grup vlerash, sasia e të dhënave është numri i elementeve të këtij grupi. Gjatë përpunimit të vargjeve, madhësia e të dhënave hyrëse është gjatësia e vargut.

Le P - sasia e të dhënave hyrëse për disa algoritme. Shënoni me T(p) numri i instruksioneve të ekzekutuara në një kompjuter të idealizuar gjatë ekzekutimit të algoritmit, dhe përcaktohet për "rastin më të keq", kur vëllimi i operacioneve është maksimal.

Koncepti i "rastit më të keq" mund të ilustrohet me një shembull. Le të merret parasysh një algoritëm për kontrollimin e pranisë së një elementi numerik në një grup (varg) numrash. Nëse ky grup është renditur në rend rritës, atëherë, në përgjithësi, nuk ka kuptim të kontrolloni elementët e vendosur pas elementit të parë, i cili është më i madh se ai i dëshiruar. Në këtë rast T(p) n. Megjithatë, në rastin më të keq (për një grup arbitrar të pazgjedhur), do t'ju duhet të shikoni të gjithë elementët e grupit. Natyrisht këtu T(n) = n.

Në përgjithësi, T(p)është një funksion i madhësisë së të dhënave hyrëse P. Ne shume raste T(p) i shprehur si një funksion polinom, fuqi ose logaritmik i P.

Sjellja e vlerës T(p) në varësi të zmadhimit P thirrur kompleksiteti asimptotik algoritmi. Ata thonë se T(n) Ka rendi i kompleksitetit 0 (J(n))(lexo "O i madh nga/nga P") për disa algoritme, nëse ka një konstante Me dhe vëllimi i të dhënave sch sikurse Yn > n 0 dhe ka një pabarazi T(n) s/(n).

Ky fakt shkruhet si T(n) = 0(J(n)) dhe do të thotë se për funksionin T(p) ekziston një funksion i tillë f(n) dhe një с konstante, për të cilën, duke u nisur nga disa n 0, kuptimi T(p) nuk e kalon cf(n).

Funksioni f(n) përfaqëson kufirin e sipërm të vlerave të funksionit T(n). Le të, për shembull, T(n) = 2p A + n 2 . Duke zgjedhur vlerat n 0= 0 dhe c = 5, për çdo n > n 0 ne kemi T(n) = 2p A + f 2 T(n) ka rend i 4 .

Funksioni T(n) lidhet me një algoritëm të caktuar, prandaj shpesh thuhet se rendi i kompleksitetit 0 (/(n)) ka një algoritëm.

Ata thonë se T(p) Ajo ka kufiri i poshtëm Q(g(n))(lexo "omega big off g nga /r") nëse ka një konstante c dhe sasinë e të dhënave n 0 sikurse /P dhe ka një pabarazi T(n) > cg(n).

Ky fakt shkruhet si T(n) = Q(g(n)). Le të, për shembull, T(n) = 2 4+ n 2 . Zgjedhja e një vlere c = 1, për çdo P ne kemi T(p)= 2 4 + n 2 > cn A > Rrjedhimisht, T(n) ka një kufi të poshtëm i 4 .

Është e lehtë të shihet se rendi dhe kufiri i poshtëm nuk janë unik për disa funksione T(n). Në shembujt e mësipërm, ju mund të zgjidhni /(i) si i 5 , i 6 ,..., dhe si g(n) - i 3 , i 2 ,.... Zakonisht, një funksion me një shkallë minimale zgjidhet si /(i), dhe g(n)- me maksimumin.

Rendi i kompleksitetit 0(/(i)) dhe kufiri i poshtëm Q(g(rc)) janë klasa funksioni. Në mënyrë intuitive, Q(g"(n)) mund të kuptohet si një klasë funksionesh që rriten të paktën aq shpejt sa T(n). Po kështu, në mënyrë intuitive 0(f(n)) mund të kuptohet si një klasë funksionesh që rriten jo më shpejt se T(n). NGA Nga pikëpamja praktike, kur vlerësohet kompleksiteti i një algoritmi, është pikërisht klasa e funksioneve që është më e rëndësishmja. 0 (f (n)). Përcaktimi i llojit të funksionit /(i) dhe është detyra kryesore e llogaritjes kompleksiteti teorik i algoritmit.

Për çdo algoritëm, kur përcaktoni shkallën e rritjes, mund të përdorni vetitë e mëposhtme të 0(/(n)):

1) 0 (kf (ji))= 0 (/(i)), ku k= konst. Kështu, faktori konstant në funksion nuk ndikon në shkallën e rritjes. Për shembull,

2) 0(J(ri)"g(n)) = 0(J(n))"0(g(ri)). Kështu, rendi i prodhimit të dy funksioneve është i barabartë me produktin e kompleksitetit të tyre. Për shembull,

Ndonjëherë kjo pronë shkruhet si

3) 0(/(p) + g(n)) barazohet dominuese(funksionet me shkallë maksimale) të funksioneve f(n) dhe g(n). Për shembull,

Në teorinë e kompleksitetit të algoritmeve, dallohen klasat e mëposhtme të funksioneve të kompleksitetit:

1) kompleksiteti konstant 0(1). Koha e funksionimit të algoritmit dhe burimet e përdorura nuk varen nga sasia e të dhënave hyrëse. Në mënyrë tipike, algoritmet që nuk përmbajnë cikle dhe thirrje rekursive kanë një kompleksitet të tillë;
2) kompleksiteti linear 0 (n). Në mënyrë tipike, problemet e këtij kompleksiteti janë ato në të cilat çdo element i të dhënave hyrëse duhet të përpunohet një numër të caktuar herë, të palidhur në asnjë mënyrë me numrin e përpunimit të elementeve të tjerë;
3) kompleksiteti logaritmik 0 (log 2 w), 0 (nog 2 n). Nganjëherë përdoren baza të tjera të logaritmit;
4) kompleksiteti polinomial 0(i 2), 0(i 3), 0(i 4),...;
5) kompleksiteti eksponencial 2 p, 3",....

Ndërsa madhësia e hyrjes rritet, kompleksiteti i secilit lloj funksioni pasues rritet më shpejt se ai i mëparshmi (përveç 0 (log 2 /?)). Për një sasi mjaft të madhe të të dhënave hyrëse, preferohet të përdoren algoritme me më pak kompleksitet.

Kur llogaritet në mënyrë sasiore kompleksiteti, fillimisht zgjidhet një operacion ose një grup operacionesh, i cili është i rëndësishëm për këtë algoritëm (formon bazën e tij). Ato janë zakonisht operacione krahasimi dhe aritmetike. Operacionet e krahasimit përfshijnë kontrollimin e vlerave të dy sasive (më pak se, më e madhe se, e barabartë me, më e vogël ose e barabartë me, më e madhe ose e barabartë me, jo e barabartë me). Ato konsiderohen ekuivalente për sa i përket kohës së ekzekutimit. Veprimet aritmetike, nga ana tjetër, ndahen me aditiv dhe shumëzues. Tek e para (shpesh quhet thjesht shtesë) përfshijnë shtimin, zbritjen, zvogëlimin ose zvogëlimin e një kundërvlere. Tek e dyta (e quajtur thjesht shumëzim) përfshijnë shumëzimin, pjesëtimin, marrjen e modulit të mbetur.

Mbledhjet janë më të shpejta se shumëzimet, prandaj preferohen algoritmet me më pak shumëzime, edhe nëse numri i mbledhjeve rritet në raport me sasinë e uljes së shumëzimeve.

Veprimet e shumëzimit ose pjesëtimit të numrit të plotë me një fuqi prej 2 klasifikohen si operacione shtesë, pasi kur punojnë me qelizat e kujtesës ato reduktohen në një zhvendosje, e cila është ekuivalente me një operacion shtesë.

Pas zgjedhjes së transaksioneve të rëndësishme, ato ndahen në dy kategori:

1) operacionet që ndikojnë drejtpërdrejt në kompleksitetin e algoritmit;
2) operacionet që përbëjnë "kosto të përgjithshme" gjatë ekzekutimit të algoritmit (për shembull, shpërndarja e memories për ruajtjen e të dhënave të ndërmjetme).

Llogaritja e drejtpërdrejtë ose vlerësimi i numrit të operacioneve të kryera ju lejon të vlerësoni T(n).

Për të vlerësuar rendin e kompleksitetit, mund të përdorni analizën e kodit të programit që zbaton algoritmin. ku:

Algoritmet pa unaza dhe thirrjet rekursive kanë kompleksitet të rendit 0(1). Kështu, operacionet e caktimit, hyrjes dhe daljes së të dhënave, ndërtimet e kushtëzuara kanë kompleksitet të vazhdueshëm;
nëse dy pjesë të kodit të programit kanë kompleksitet 0 (J ( (ri)) dhe 0 (J 2 (n)), atëherë ekzekutimi sekuencial ka kompleksitet

nëse trupi i lakut ekzekutohet një herë për çdo element të të dhënave hyrëse, atëherë kompleksiteti i ekzekutimit të ciklit është i rendit 0(p)0( 1) = 0 (n);
rendi i kompleksitetit të ekzekutimit të sytheve të mbivendosur llogaritet nga rregulli i produktit 0(J x (n)f 2 (n)) = 0(/,(/?))- 0 (J 2 (ri)). Nëse secila prej tyre ka kompleksitet të rendit 0 (n), ekzekutimi i sytheve të mbivendosur ka kompleksitet të rendit 0 (n 2).

Shembulli 1.3

Përcaktoni rendin e kompleksitetit të algoritmit të programit në gjuhë

Pascal i paraqitur në Listimin 1.2. Linjat e programit numërohen si komente (shih seksionin 2.6).

Listimi 1.2

(01) për i:=l deri në n bëj

(02) fillojnë

(03) shkruani ("Fut elementin e grupit

me indeksin ",i,": ");

(04) Readln(MyArray[i]);

(05) fundi;

(06) për i:=l deri në n bëj

(07) për j:=1 deri në n bëj

(08) fillojnë

(09) shkruani ("Fut elementin e grupit

me indekse ", i, ",", j, " : ");

(10) Readln (MyDArray);

(11) fundi;

Zgjidhje

Rreshtat 02, 05, 08, 11 nuk përmbajnë deklarata të ekzekutueshme, kështu që ato nuk merren parasysh gjatë përcaktimit të rendit.

Linjat 03 dhe 04 kanë rendin 0(1). Ekzekutimi sekuencial i tyre ka rendin 0(1) + 0(1) = 0(1). Në mënyrë të ngjashme, ekzekutimi sekuencial i rreshtave 09 dhe 10 ka kompleksitet 0(1).

Cikli në rreshtat 01-05 ka kompleksitet të rendit O(n), sythe të mbivendosur në rreshtat 06-11 - rendit 0 (n 2). Kompleksiteti përfundimtar i algoritmit është i rendit

Vlerësimi i kompleksitetit të algoritmit, si koha ashtu edhe burimi, ju lejon të përcaktoni kohën maksimale dhe mesatare të ekzekutimit të algoritmit. Kjo është jashtëzakonisht e rëndësishme kur përpunohen sasi të mëdha informacioni, veçanërisht në detyrat e renditjes dhe kërkimit të diskutuara më poshtë.