border=0

Algoritme kompleksiteit

Lit ús noch ien karakteristysk diskusje oer it algoritme - har kompleksiteit. De ûntwikkeling en ferbetterjen fan komputertechnology liedt ta oprjochting fan ferskate algoritmen dy't de oplossing fan ferskate oanwêzige problemen leverje, en sels foar inkeldtartige taken binne in protte algoritme (programma's) makke makke (en wurde makke). Fergelykbere algoritme waarden earder as equivalent neamd. Foar praktyk is lykwols net genôch om te witten dat it oplossen fan in bepaald probleem op in kompjûter yn prinsipe mooglik is (dat is it probleem algoritmysk lêzen). De útfiering fan elke algoritme freget in bepaald bedrach fan komputer ûnthâld om de gegevens en it programma te passe, en ek de CPU-tiid foar it ferwurkjen fan dizze gegevens - dizze boarnen binne beheind en dêrom is de fraach fan 'e effektiviteit fan har gebrûk legitimearre. Sa wurdt yn 't breedste sin it begryp fan effisjinsje ferbûn oan alle komputearjende middels dy't nedich binne foar de wurking fan' e algoritme. Mar meastentiids ûnder 'e meast effisjearje' betsjutte it algoritme dat de heulste resultaten biedt, om't yn praktyske situaasjes it de tiidlimiten binne dy't faak de dominante faktor binne dy't de passaazje fan in algoritme fêststelle. Dêrtroch sil de tiid kompleksiteit fan 'e algoritmen fierder besprutsen wurde.

De rinnende tiid fan 'e algoritme wurdt bepaald as in funksje fan in fariabele karakterisearret de "grutte" fan in bepaalde opdracht, d. it bedrach fan ynputgegevens dy't nedich binne om it op te lossen. Dizze oanpak is handich, om't de relative kompleetiteit fan taken kin wurde troch syn grutte beoardielje. Sûnt de beskriuwing fan it probleem dat bepaald wurdt troch in kompjûterapparaat te behannele wurde kin wurde as in wurd fan finite lingte, fertsjintwurdige troch de tekens fan it finite alfabet, kin de lingte fan it ynfier wurd as formele karakteristyk fan 'e grutte fan it probleem. As der bygelyks in taak is om it maksimum nûmer te bepalen yn in folchoarder fan n eleminten, dan sil de grutte fan it probleem n wêze , om't alle fariant fan 'e ynfier-folchoarder oanjûn wurde kin mei in wurd fan n karakters.

De tiidsyklikheid fan in algoritme is in funksje dy't elke input lingte fan in wurd n de maksimum (foar alle konkrete taken fan deselde lingte n) de tiid jout it algoritme om it op te lossen.

Yn dit gefal wurdt it fanselssprekkend dat alle problemen itselde kodearringskema fan 'e ynputwurden brûke.

Ferskillende algoritmen hawwe ferskillende tiidsynkomstens en útfine hokker fan harren genôch effektyf wêze en wat net, wurdt bepaald troch in soad faktoaren. Dochs binne teoryen belutsen by it ûntwikkeljen en analysearjen fan algoritmen, foar it fergelykjen fan de effektiviteit fan algoritmen, foar in ienfâldige oanpak om de situaasje te ferklearjen. It giet oer it ferskil tusken polynom en eksponjale algoritme.

In polynom is in algoritme dat har tydlike kompleksiteit útdrukt wurdt troch in beskate polynomfunksje fan 'e grutte fan' e probleem n.

Algoritmen dy't har komplekse tiid net op dizze wize bepaald wurde wurde neamd eksponentiell.

It ferskil tusken dizze twa soarten algoritmen wurdt spesjaal spitigernôch as it problemen fan grutte grutte. Foar fergeliking yn 't tafel. 7.2 fertelt gegevens oer de tiid fan it probleemjen fan problemen fan ferskate kompleksiteit (gegevens út it boek fan M. Gary, D. Johnson [15, s.20] en oerienkomme mei de steat fan ûntwikkeling fan de technologytechnology sa'n tweintich jier lyn - dit beynfloedet de absolute wearden fan 'e ferwurkingstiid, mar de relative sifers foar dit sil net feroarje).

It kin sjoen wurde fan de boppesteande data dat earst de ferwurkingstiid fan eksponjale algoritme mei deselde opmaakgrutte (mear as 20) is folle heger as dy fan polynomialen; Tweintich is de taryf fan fergrutting yn 'e ferwurkingstiid mei fergruttend taakgrutte foar eksponjale algoritmen is sterk heger as foar polynomialen.

It ferskil tusken de twa soarten algoritmen is noch mear oertsjûge as wy analysearje it effekt fan it ferheegjen fan de snelheid fan 'e kompjûter op' e útfieringtiid fan 'e algoritme. Yn ljepblêd. 7.3 lit sjen hoefolle de grutte fan it grutste probleem opleveret per ienheid fan komputertiid ferheget, as de snelheid fan 'e kompjûter op 100 en 1000 kear ferheget.

Fan ljepblêd. 7.3 It kin sjoen wurde dat, bygelyks, foar in eksponjial algoritme mei in kompleksiteitfunksje f (n) = 2 n, in ferheging fan de berekkening 1000 kearen liedt allinich it feit dat de grutte fan it grutste probleem mei allinich 10 ienheden ferheget, wylst foar funksje f (n ) = n 5 it ferheget sawat 4 kear.

Tabel 7.2.

Tabel 7.3.

De opjûne foarbylden binne ûntwurpen om te sjen dat lykas de algoritmyske ûnbidige problemen besteane, binne der objektyf komplekse problemen, d. sa, de kompleksiteit wêrfan net mei de ferbettering fan de kompjûter feroarsake wurde kin. In taak wurdt beskôge as lestich as it net mooglik is om in polynomial algoritme oan te bouwen. Dizze ferklearring is net kategoarysk, om't der bekende problemen binne wêrby't eksponjale algoritmeiten effektyf wurkje. In foarbyld is de simplex-metoade, dy't súkses brûkt wurdt by it oplossen fan lineêre programmearproblemen, mei in funksje fan kompleksiteit f (n) = 2 n . Der binne lykwols gjin protte foarbylden fan dizze soarte, en de situaasje moat as generaal erkend wurde: polynomiale algoritme mei funksjes fan kompleksiteit n, n 2 kinne effektiv útfierd wurde. of n 3 . Bygelyks by it oplossen fan it probleem op it te finen fan de winske gegevens fan 'e iene yn it minste gefal, is de kompleksiteit n ; As wy de gemiddelde arbeidsynfetsje (sykdraging) skatte, dan sil it (n + 1) / 2 wêze - yn beide gefallen is de kompleksiteitfunksje lytserlik . yn in bepaalde folchoarder pleatse en fergelykje gegevensgegevens yn in polynom fan 'e 2e graden; De kompleksiteit fan it probleem is te berekkenjen fan de determinant fan in systeem fan η lineêre lyknaasjes mei n ûnbekenden is karakterisearre troch in polynom fan 'e 3e graden. It ferbetterjen fan 'e prestaasjes fan kompjûter eleminten fermindert de útfieringtiid fan' e algoritme, mar ferleget net de mjitte fan komplekse polynom. Dêrom moat de oplossing fan in praktysk probleem wêze op in kompjûter foarôfgeand fan in beoardieling fan har kompleksiteit en bewiis dat it probleem yn in ridlik tiid begeliedt wurdt.





Sjoch ek:

Foarbyld 4.2

Foarbyld 2.8

Besykje fragen en taken

Besykje fragen en taken

Foarbyld 7.7

Gean werom nei Tafel Ynhâld: Teoretyske Stiftingen fan Computer Science

2019 @ edudocs.fun