Algoritme effektivitet er en egenskab ved en algoritme, der er forbundet med de beregningsressourcer, der bruges af algoritmen. Algoritmen skal analyseres for at bestemme de ressourcer, som algoritmen kræver. Algoritmeeffektivitet kan opfattes som analogt med fremstillingsproduktiviteten af ​​gentagne eller kontinuerlige processer.

For at opnå maksimal effektivitet ønsker vi at reducere ressourceforbruget. Forskellige ressourcer (såsom tid og hukommelse) kan dog ikke sammenlignes direkte, så hvilken af ​​to algoritmer der anses for at være mere effektiv afhænger ofte af, hvilken faktor der er vigtigst, såsom kravet om høj hastighed, minimalt hukommelsesforbrug eller et andet mål for effektivitet.

Bemærk venligst, at denne artikel IKKE om algoritme optimering, som diskuteres i artiklerne program optimering, optimering compiler, cyklus optimering, objektkodeoptimering, og så videre. Udtrykket "optimering" i sig selv er vildledende, fordi alt, hvad der kan gøres, falder ind under paraplyen "forbedring".

Baggrund

Betydningen af ​​effektivitet med vægt på udførelsestid blev understreget af Ada Lovelace i 1843 vedrørende Charles Babbages mekaniske analytiske motor:

"I næsten al databehandling er der et stort udvalg af konfigurationer, der er mulige for at fuldføre processen, og forskellige konventioner bør påvirke valget med henblik på at udføre beregningen. Det væsentlige er at vælge en konfiguration, der vil resultere i at minimere den tid, der kræves til at udføre beregningen."

Tidlige elektroniske computere var meget begrænset i både hastighed og hukommelse. I nogle tilfælde har man indset, at der er en afvejning mellem tidshukommelse, hvor en opgave enten skal bruge en stor mængde hukommelse for at opnå høj hastighed, eller bruge en langsommere algoritme, der bruger en lille mængde arbejdshukommelse. I dette tilfælde blev den hurtigste algoritme brugt, hvortil den tilgængelige hukommelse var tilstrækkelig.

Moderne computere er meget hurtigere end de tidlige computere og har meget mere hukommelse (gigabyte i stedet for kilobyte). Donald Knuth understreger dog, at effektivitet fortsat er en vigtig faktor:

"I etablerede ingeniørdiscipliner er en forbedring på 12% let opnåelig og er aldrig blevet betragtet som uoverkommelig, og jeg mener, at det samme burde være tilfældet i programmering."

Anmeldelse

En algoritme anses for at være effektiv, hvis dens ressourceforbrug (eller ressourceomkostninger) er på eller under et acceptabelt niveau. Groft sagt betyder "acceptabel" her "algoritmen vil køre i et rimeligt tidsrum på en tilgængelig computer." Fordi der har været en betydelig stigning i processorkraft og tilgængelig hukommelse på computere siden 1950'erne, var det nuværende "acceptable niveau" ikke acceptabelt selv for 10 år siden.

Computerproducenter frigiver med jævne mellemrum nye modeller, ofte mere kraftfulde. Udgifterne til software kan være ret høje, så i nogle tilfælde er det nemmere og billigere at få bedre ydeevne ved at købe en hurtigere computer, der er kompatibel med din eksisterende computer.

Der er mange måder at måle de ressourcer, der bruges af en algoritme. De to mest anvendte målinger er hastighed og hukommelse. Andre målinger kan omfatte overførselshastighed, midlertidigt diskforbrug, langsigtet diskbrug, strømforbrug, samlede ejeromkostninger, responstid på eksterne signaler og så videre. Mange af disse målinger afhænger af størrelsen af ​​algoritmens inputdata (det vil sige de mængder, der kræver databehandling). Målinger kan også afhænge af den måde, hvorpå dataene præsenteres (for eksempel fungerer nogle sorteringsalgoritmer dårligt på allerede sorterede data, eller når dataene er sorteret i omvendt rækkefølge).

I praksis er der andre faktorer, der påvirker effektiviteten af ​​algoritmen, såsom den nødvendige nøjagtighed og/eller pålidelighed. Som forklaret nedenfor kan den måde, en algoritme implementeres på, også have en betydelig effekt på den faktiske ydeevne, selvom mange aspekter af implementeringen er optimeringsproblemer.

Teoretisk analyse

I den teoretiske analyse af algoritmer er det almindelig praksis at estimere kompleksiteten af ​​en algoritme i dens asymptotiske adfærd, det vil sige at afspejle kompleksiteten af ​​algoritmen som funktion af størrelsen af ​​inputtet n Big O-notation bruges. Dette skøn er generelt ret præcist for store n, men kan føre til forkerte konklusioner ved små værdier n(Således kan boblesortering, som anses for langsom, være hurtigere end hurtig sortering, hvis du kun skal sortere nogle få elementer).

Betegnelse	Navn	Eksempler
O(1) (\displaystyle O(1)\,)	permanent	Bestemmelse om et tal er lige eller ulige. Brug af en opslagstabel med konstant størrelse. Brug af en passende hash-funktion til at vælge et element.
O (log ⁡ n) (\displaystyle O(\log n)\,)	logaritmisk	At finde et element i en sorteret matrix ved hjælp af binær søgning eller balanceret træ, svarende til operationer på den binomiale heap.
O(n) (\displaystyle O(n)\,)	lineær	At finde et element i en usorteret liste eller ubalanceret træ (worst case). Tilføjelse af to n-bit-numre ved hjælp af ende-til-ende-bære.
O (n log ⁡ n) (\displaystyle O(n\log n)\,)	kvasilineær, logaritmisk lineær	Beregn hurtig Fourier-transformation, heapsort, quicksort (bedste og gennemsnitlige tilfælde), flettesortering
O (n 2) (\displaystyle O(n^(2))\,)	firkant	Gang to n-cifrede tal ved hjælp af en simpel algoritme, boble sortering (værste tilfælde), Shell sortering, quicksort (værste tilfælde), valg sortering, indsættelse sortering
O (c n), c > 1 (\displaystyle O(c^(n)),\;c>1)	eksponentiel	At finde en (præcis) løsning på det rejsende sælgerproblem ved hjælp af dynamisk programmering. Bestemmelse af, om to logiske udsagn er ækvivalente ved hjælp af udtømmende søgning

Verifikationstest: Måling af ydeevne

For nye versioner af software eller for at give sammenligning med rivaliserende systemer, bruges benchmarks nogle gange til at sammenligne den relative ydeevne af algoritmer. Hvis der for eksempel udkommer en ny sorteringsalgoritme, kan den sammenlignes med sine forgængere for at sikre, at algoritmen er mindst lige så effektiv på kendte data som de andre. Ydelsestest kan bruges af brugere til at sammenligne produkter fra forskellige producenter for at vurdere, hvilket produkt der bedst passer til deres krav med hensyn til funktionalitet og ydeevne.

Nogle benchmark-tests giver sammenlignende analyse af forskellige kompilerings- og fortolkningssprog, såsom Roy Longbottoms PC Benchmark Collection, og Computersprog benchmarks spil sammenligner udførelsen af ​​implementeringer af typiske opgaver i nogle programmeringssprog.

Implementeringsproblemer

Implementeringsproblemer kan også påvirke den faktiske ydeevne. Dette inkluderer valget af programmeringssprog og den måde, hvorpå algoritmen faktisk er kodet, valget af oversætter til det valgte sprog eller de anvendte kompileringsmuligheder, og endda det anvendte operativsystem. I nogle tilfælde kan et sprog implementeret som en tolk være betydeligt langsommere end et sprog implementeret som en compiler.

Der er andre faktorer, der kan påvirke timing eller hukommelsesforbrug, som er uden for programmørens kontrol. Dette inkluderer datajustering, detaljering, garbage collection , instruktionsniveau parallelisme og subrutinekald .

Nogle processorer har evnen til at udføre vektoroperationer, hvilket tillader én operation at behandle flere operander. Det kan være nemt at bruge sådanne funktioner på programmerings- eller kompileringsniveau. Algoritmer, der er designet til sekventiel databehandling, kan kræve fuldstændig redesign for at imødekomme parallel databehandling.

Et andet problem kan opstå med processorkompatibilitet, hvor instruktioner kan implementeres anderledes, så instruktioner på nogle modeller kan være relativt langsommere på andre modeller. Dette kan være et problem for optimeringskompileren.

Måling af ressourceforbrug

Mål er normalt udtrykt som en funktion af indgangens størrelse n.

De to vigtigste dimensioner er:

• Tid: Hvor lang tid tager algoritmen på CPU'en.
• Hukommelse: Hvor meget arbejdshukommelse (normalt RAM) er nødvendig for algoritmen. Der er to aspekter ved dette: mængden af ​​hukommelse for koden og mængden af ​​hukommelse for de data, som koden opererer på.

For batteridrevne computere (såsom bærbare computere) eller til meget lange/store beregninger (såsom supercomputere) er en anden form for måling af interesse:

• Direkte energiforbrug: Energi, der kræves for at køre en computer.
• Indirekte energiforbrug: Energi nødvendig til køling, belysning mv.

I nogle tilfælde er andre, mindre almindelige målinger nødvendige:

• Gear størrelse: Båndbredde kan være den begrænsende faktor. Komprimering kan bruges til at reducere mængden af ​​overførte data. Visning af grafik eller billede (såsom Google-logoet) kan resultere i, at titusindvis af bytes overføres (48K i dette tilfælde). Sammenlign dette med at overføre de seks bytes i ordet "Google".
• Ekstern hukommelse: Hukommelse påkrævet på en disk eller anden ekstern lagerenhed. Denne hukommelse kan bruges til midlertidig opbevaring eller til fremtidig brug.
• Responstid: Denne indstilling er især vigtig for realtidsapplikationer, hvor computeren skal reagere hurtigt på eksterne hændelser.
• Samlede ejeromkostninger: Parameteren er vigtig, når den er beregnet til at udføre en enkelt algoritme.

Tid

Teori

Denne type test afhænger også væsentligt af valget af programmeringssprog, compiler og dets muligheder, således at de sammenlignede algoritmer skal implementeres under samme betingelser.

Hukommelse

Dette afsnit omhandler brugen af ​​hovedhukommelsen (ofte RAM), der kræves af algoritmen. Som med timinganalyse ovenfor, bruger analyse af en algoritme typisk algoritmens rumlige kompleksitet at estimere den nødvendige runtime-hukommelse som en funktion af inputstørrelsen. Resultatet udtrykkes normalt som "O" stort.

Der er fire aspekter af hukommelsesbrug:

• Mængden af ​​hukommelse, der kræves for at gemme algoritmekoden.
• Mængden af ​​hukommelse, der kræves til inputdata.
• Mængden af ​​hukommelse, der kræves til ethvert output (nogle algoritmer, såsom sorteringer, omarrangerer ofte inputtet og kræver ikke yderligere hukommelse til outputtet).
• Mængden af ​​hukommelse, der kræves af beregningsprocessen under beregning (dette inkluderer navngivne variabler og eventuel stakplads, der kræves til subrutineopkald, hvilket kan være væsentligt, når du bruger rekursion).

Tidlige elektroniske computere og hjemmecomputere havde relativt lille arbejdshukommelseskapacitet. Således havde EDSAC i 1949 en maksimal arbejdshukommelse på 1024 17-bit ord, og i 1980 blev Sinclair ZX80 udgivet med 1024 bytes arbejdshukommelse.

Moderne computere kan have relativt store mængder hukommelse (måske gigabyte), så at komprimere den hukommelse, der bruges af en algoritme, til en given mængde hukommelse er mindre påkrævet end før. Imidlertid er eksistensen af ​​tre forskellige kategorier af hukommelse væsentlig:

• Cache (ofte statisk RAM) - kører med hastigheder, der kan sammenlignes med CPU'en
• Fysisk hovedhukommelse (ofte dynamisk RAM) - kører lidt langsommere end CPU'en
• Virtuel hukommelse (ofte på disk) - giver en illusion af enorm hukommelse, men arbejder tusindvis af gange langsommere end RAM.

En algoritme, hvis påkrævede hukommelse passer ind i computerens cache, er meget hurtigere end en algoritme, der passer ind i hovedhukommelsen, som til gengæld vil være meget hurtigere end en algoritme, der bruger virtuelt rum. Det komplicerende er, at nogle systemer har op til tre niveauer af cache. Forskellige systemer har forskellige mængder af disse typer hukommelse, så hukommelseseffekten på en algoritme kan variere betydeligt fra et system til et andet.

I de tidlige dage af elektronisk databehandling, hvis en algoritme og dens data ikke passede ind i hovedhukommelsen, kunne den ikke bruges. I disse dage giver brug af virtuel hukommelse massiv hukommelse, men på bekostning af ydeevne. Hvis algoritmen og dens data passer ind i cachen, kan der opnås meget høj hastighed, så minimering af den nødvendige hukommelse hjælper med at minimere tiden. En algoritme, der ikke passer helt ind i cachen, men giver lokaliteten af ​​links, kan arbejde relativt hurtigt.

Eksempler på effektive algoritmer

Kritik af programmeringens nuværende tilstand

Programmer bliver hurtigere langsommere end computere bliver hurtigere.

May siger:

I udbredte systemer kan halvering af instruktionsudførelse fordoble batterilevetiden, og big data giver mulighed for bedre algoritmer: Reduktion af antallet af operationer fra N x N til N x log(N) har en stærk effekt for store N... For N =30 milliarder, disse ændringer ligner 50 års teknologiske forbedringer.

Konkurrence om den bedste algoritme

Følgende konkurrencer inviterer til deltagelse i udviklingen af ​​de bedste algoritmer, hvis kvalitetskriterier bestemmes af dommerne:

se også

• Aritmetisk kodning er en type entropikodning med variabel kodelængde for effektiv datakomprimering
• Et associativt array er en datastruktur, der kan gøres mere effektiv, når den bruges træer PATRICIA eller Judy arrays
• Performance test - en metode til at måle sammenlignende udførelsestid i visse tilfælde
• Bedste, værste og gennemsnitlige tilfælde- konventioner for estimering af udførelsestid for tre scenarier
• Binær søgning er en enkel og effektiv teknik til at søge på en sorteret liste
• Grenbord

Forelæsningens mål og formål: introduktion til metoder til at analysere kompleksiteten og effektiviteten af ​​algoritmer og datastrukturer

Hovedspørgsmål: eksperimentel og analytisk analyse af effektiviteten af ​​algoritmer.

N. Wirths klassiske udsagn "Et godt program er enheden af ​​en gennemtænkt algoritme og effektive datastrukturer."

Algoritmeanalyse
Begreberne "algoritme og datastrukturer" er centrale inden for computerteknologi, men for at kalde visse datastrukturer og algoritmer for "højkvalitets og effektive" skal der anvendes præcise teknikker til at analysere dem. Som et naturligt kvalitetskriterium er det naturligt for det første at fremhæve udførelsestid. Også vigtig er mængden af ​​hukommelse og diskpladsressourcer brugt, hastigheden af ​​dataadgang (effektiviteten af ​​datastrukturen). Der bør også lægges vægt på pålideligheden og pålideligheden af ​​beslutninger, deres stabilitet.

Algoritmen bør ikke være bundet til en specifik implementering. På grund af de mange forskellige programmeringsværktøjer, der anvendes, kan algoritmer, der er forskellige i implementering, give resultater, der adskiller sig i effektivitet.

Udførelsestiden for en algoritme eller operation på en datastruktur afhænger som regel af en række faktorer. Den enkleste måde at bestemme den tid, der kræves for at udføre en algoritme, er at måle tiden før og efter algoritmen kører.

Det skal dog huskes, at denne metode til at estimere tid ikke er nøjagtig; først og fremmest skal det forstås, at i moderne operativsystemer kan flere opgaver udføres parallelt, og udførelsen af ​​en testcase kan kombineres med andre typer af aktivitet. Yderligere skal det forstås, at en stabil afhængighed kun kan opnås ved at udføre gentagne tests, ellers på grund af indflydelsen på det endelige resultat af arbejdet af tilfældige faktorer afhængigt af detaljerne i de indledende data og andre faktorer, udførelsen tidspunktet for algoritmen vil også være en tilfældig variabel. Når man udfører forskning, er det nødvendigt at køre algoritmen med et andet sæt indledende data; normalt genereres selve dataene tilfældigt, så på grund af forskellige datasæt, vil tidsforbruget også variere.

Når først et sæt estimater er opnået, kan en graf konstrueres og tilnærmes.

En sådan analyse bør altid bruges, når der bruges ikke-trivielle algoritmer; dette svarer til anbefalingen om at udvikle en applikation, hvor der til fejlfinding ikke bruges et prøvesæt af flere dusin poster eller elementer, men virkelige data i sin helhed, som undgår modifikation eller endda fuldstændig omarbejdning af algoritme- eller strukturdataene, hvis de efterfølgende viser sig at være upraktiske. Med et sæt eksperimentelle resultater kan du udføre interpolation og ekstrapolation og bestemme algoritmens opførsel under virkelige forhold.

Generelt kan vi sige, at eksekveringstiden for en algoritme eller datastrukturmetode stiger i takt med at størrelsen af ​​kildedataene øges, selvom det også afhænger af typen af ​​data, selvom størrelsen er ens. Derudover afhænger eksekveringstiden af ​​den hardware (processor, clock-frekvens, hukommelsesstørrelse, diskplads osv.) og software (driftsmiljø, programmeringssprog, compiler, fortolker osv.), som implementeringen, kompileringen udføres med og udførelse af algoritmen. For eksempel vil eksekveringstiden for en algoritme for en vis mængde kildedata alt andet lige være mindre ved brug af en mere kraftfuld computer eller ved skrivning af algoritmen som et program i maskinkode sammenlignet med dens eksekvering af en virtuel maskine fortolker det til bytekoder.

Konklusionen er, at det ikke er rigtig pålideligt at udføre empiriske analyser af algoritmer. De største ulemper kan reduceres til følgende tre punkter:

1) eksperimenter kan kun udføres ved hjælp af et begrænset sæt indledende data; resultater opnået med et andet sæt tages ikke i betragtning.

2) for at sammenligne effektiviteten af ​​to algoritmer er det nødvendigt, at eksperimenter for at bestemme deres udførelsestid udføres på den samme hardware og software;
3) for eksperimentelt at studere eksekveringstiden for algoritmen, er det nødvendigt at udføre dens implementering og udførelse.

Således kommer vi til behovet for at bruge generelle analysemetoder til at analysere algoritmer, som tillader:

1) tager højde for forskellige typer inputdata;

2) giver dig mulighed for at evaluere den relative effektivitet af to algoritmer, uanset hardware og software;

3) kan udføres i henhold til beskrivelsen af ​​algoritmen uden dens direkte implementering eller eksperimenter.

Essensen af ​​den generelle analyse er, at funktionen f=f(n1, .., nm) er tildelt en bestemt algoritme. I sin enkleste form er det en funktion af én variabel n1 – mængden af ​​inputdata. Der kan dog være andre variabler - for eksempel nøjagtigheden af ​​beregningen eller dens pålidelighed. Så for at bestemme, om et bestemt tal er prime i tilfælde af store tal (længden af ​​den binære repræsentation er mere end 200 bits), bruges en probabilistisk metode, hvis pålidelighed kan varieres. De mest kendte funktioner er lineær, potens og logaritmisk. Derfor bør du tage dig tid til at huske det grundlæggende i at arbejde med dem.

Når man konstruerer algoritmer, sker den første fase ved at bruge ikke et programmeringssprog, men en beskrivelse på menneskesprog. Sådanne beskrivelser er ikke programmer, men de er samtidig mere strukturerede end almindelig tekst. Især "højt niveau" beskrivelser kombinerer naturligt sprog og fælles programmeringssprog strukturer, hvilket gør dem tilgængelige, men alligevel informative. Sådanne beskrivelser letter analyse på højt niveau af datastrukturen eller algoritmen. Sådanne beskrivelser kaldes normalt pseudokode. Det skal også bemærkes, at pseudokode ofte er mere nyttig til analyse end kode i et specifikt programmeringssprog.

Nogle gange er der behov for at bevise bestemte udsagn i forhold til en bestemt datastruktur eller algoritme. For eksempel skal du demonstrere rigtigheden og hastigheden af ​​udførelsen af ​​algoritmen. For strengt at bevise udsagn er det nødvendigt at bruge matematisk sprog, som vil tjene som bevis eller begrundelse for udsagn. Der er flere enkle måder at bevise dette på.

Nogle gange skrives udsagn i en generaliseret form: "Mængden s indeholder et element x med egenskaben v. For at bevise dette udsagn er det nok at give et eksempel x "tilhører" s, som har denne egenskab. I en sådan generaliseret form skrives der som regel usandsynlige udsagn, for eksempel: "Hvert element x i mængden s har egenskaben P." For at bevise fejlslutningen af ​​dette udsagn er det nok blot at give et eksempel: x "tilhører" s, som ikke har egenskaben P. I dette tilfælde vil elementet x fungere som et modeksempel.

Eksempel: Det er angivet, at ethvert tal på formen 2^n - 1 er primtal, hvis n er et heltal større end 1. Udsagnet er falsk.

Bevis: For at bevise, at nogen tager fejl, skal du finde et modeksempel.

Dette er et modeksempel: 2^4 - 1 = 15, 15= 3 * 5.

Der er en anden måde, baseret på bevis ved modsigelse (ved at bruge negation). De vigtigste metoder i dette tilfælde er kontraposition og modsigelse. Brugen af ​​kontrastmetoder ligner spejling: for at bevise, at "hvis x er sand, så er y sand", vil vi hævde det modsatte, "hvis y er falsk, så er x falsk." Fra et logisk synspunkt er disse udsagn identiske, men det andet udtryk, som er en sammensætning af det første, er mere bekvemt.

Eksempel: Hvis a*b er et ulige tal, så er a ulige eller b er ulige.

Bevis: for at bevise dette udsagn, overvej modsætningen: "Hvis a er et lige tal, og b er ulige, så er a*b lige. Lad a = 2*x for et helt tal x. Så er a*b = 2*i*b, og derfor er produktet a*b lige.

Når du bruger metoder til bevis ved modsigelse, er det nyttigt at bruge logik.

A eller b = kræver, at a eller b udføres, eller både a og b på samme tid.
. a og b = kræver, at a og b udføres samtidigt.
. a xor b = kræver udførelse af a, men ikke b, eller b, men ikke a.

Når man bruger modsigelsesmetoden til at bevise, at et udsagn q er sandt, antager man først, at q er falsk og viser derefter, at en sådan antagelse fører til en modsigelse (f.eks. 2 * 2<>4). Når vi er kommet til en sådan modsigelse, kan vi argumentere for, at en situation, hvor q er falsk, ikke eksisterer, og derfor er q sand.

I de fleste tilfælde bruger udsagn om programudførelsestid eller pladsforbrug en heltalsparameter n (repræsenterer "størrelsen" af problemet). Når vi så formulerer et udsagn x(n), så er sådanne udsagn ækvivalente for et sæt værdier n. Da dette udsagn gælder for et "uendeligt" sæt tal, er det umuligt at give et udtømmende direkte bevis. I sådanne situationer anvendes induktionsmetoder. Metoden til induktion er baseret på det faktum; at for enhver n > 1. Der er en begrænset rækkefølge af handlinger, der starter med noget, der vides at være sandt og i sidste ende fører til et bevis for, at q(n) er sandt. Et induktionsbevis begynder således med udsagnet om, at q(n) er sandt for n=1,2,3 osv. op til nogle konstante k. Dernæst beviser vi, at det næste "trin" af induktioner q(n+1), q(n+2) også er sandt for n > k.

Når man analyserer algoritmer, beregner antallet af operationer og deres udførelsestid, bør man ikke tage "små detaljer" i betragtning; konstante faktorer og konstanter bør negligeres. I praksis bruges begrebet en stor funktion OM. antag at der er to funktioner f(n) og g(n), det antages at f(n)<= O(g(n)) , т.е. функция О ограничивает сверху значения функции f, начиная с n=n0.

For eksempel er algoritmen til at tælle antallet af elementer lig med nul i et array beskrevet ved O(n), hvor n er antallet af elementer.

1) 20n3+7,2n2-21,78n + 5 er beskrevet som O(n3)

2)xn-2 + a(0) er beskrevet som O(xn).

2) 3*log(n) + log(log(n)) beskrives som O(log(n)).

3) 2100 er beskrevet som O(1)

4) 5/n er beskrevet som O(1/n).

Bemærk venligst, at funktionen o(n) begrænser måltidsomkostningsfunktionen fra oven, men du bør altid stræbe efter at vælge en sådan funktion O(n), at der er maksimal nøjagtighed.

De mest berømte O-funktioner i stigende rækkefølge:

Når du bruger asymptotisk analyse, skal du være forsigtig med, at når du bruger O-notation, ignorerer du ofte konstante faktorer og additionskonstanter. Men hvis denne værdi er stor nok, selvom formen af ​​funktionen O(1) er mere at foretrække end algoritmen beskrevet af funktionen O(n), er det naturligvis den anden algoritme, der vil få praktisk anvendelse.

Afhængigt af typen af ​​funktion f(n) skelnes følgende klasser af kompleksitet af algoritmer.

Algoritme kompleksitetsklasser afhængig af kompleksitetsfunktionen
Vis f(n)	Karakteristika for klassen af ​​algoritmer
	De fleste instruktioner for de fleste funktioner udføres en eller flere gange. Hvis alle instruktioner i et program har denne egenskab, så er programmets udførelsestid konstant.
log N	Når et programs eksekveringstid er logaritmisk, bliver programmet langsommere i takt med, at N. Sådanne eksekveringstider er typisk forbundet med programmer, der reducerer et stort problem til et sæt af mindre delproblemer, hvilket reducerer problemets størrelse med en eller anden konstant faktor ved hvert trin. Ændring af basen påvirker ikke ændringen i værdien af ​​logaritmen i høj grad: n
N	Når et programs eksekveringstid er lineær, betyder det normalt, at hvert input-element gennemgår lidt behandling.
N log N	Kørselstid proportional med N log N opstår, når en algoritme løser et problem ved at opdele det i mindre underproblemer, løse dem uafhængigt og derefter kombinere løsningerne.
N 2	Når køretiden for en algoritme er kvadratisk, er den nyttig til praktisk brug ved løsning af relativt små problemer. Kvadratisk eksekveringstid vises typisk i algoritmer, der behandler alle par af dataelementer (måske i en dobbelt-indlejret løkke).
N 3	En lignende algoritme, der behandler tripletter af dataelementer (eventuelt i en triple-nesting-løkke) har en kubisk eksekveringstid og er praktisk talt kun anvendelig til små problemer.
2 N	Kun få algoritmer med eksponentiel køretid har praktiske anvendelser, selvom sådanne algoritmer opstår naturligt, når man forsøger at løse et problem direkte, såsom brute force.

Baseret på matematiske metoder til at studere asymptotiske funktioner af kompleksitet i det uendelige, identificeres fem klasser af algoritmer.

1. En klasse af hurtige algoritmer med konstant udførelsestid, deres kompleksitetsfunktion er O(1). Mellemtilstanden er optaget af algoritmer med kompleksitet O(log N), som også er klassificeret i denne klasse.

2. En klasse af rationelle eller polynomielle algoritmer, hvis kompleksitetsfunktion bestemmes polynomielt ud fra inputparametrene. For eksempel O(N), O(N2, O(N3).

3. En klasse af subeksponentielle algoritmer med en grad af kompleksitet O(N log N).

4. Klasse af eksponentielle algoritmer med en grad af kompleksitet O(2 N).

5. Klasse af overeksponentielle algoritmer. Der er algoritmer med faktoriel kompleksitet, men de har generelt ingen praktisk anvendelse.

Hukommelsestilstanden under udførelse af algoritme bestemmes af de værdier, der kræver, at bestemte områder tildeles. I dette tilfælde kan et yderligere antal celler bruges under løsning af problemet. Med mængden af ​​hukommelse, der kræves af algoritme A for input D, mener vi det maksimale antal hukommelsesceller, der bruges under udførelsen af ​​algoritmen. Kapacitetskompleksiteten af ​​en algoritme er defineret som det asymptotiske estimat af algoritmens worst-case hukommelseskapacitetsfunktion.

Således er ressourcekompleksiteten af ​​en algoritme i de værste, gennemsnitlige og bedste tilfælde defineret som et ordnet par af klasser af funktioner af tids- og kapacitetskompleksitet, specificeret ved asymptotisk notation og svarende til det pågældende tilfælde.

De vigtigste algoritmiske konstruktioner i proceduremæssig programmering er følgende, forgrening og looping. For at opnå kompleksitetsfunktionerne for de bedste, gennemsnitlige og værste tilfælde med en fast inputdimension er det nødvendigt at tage højde for forskelle i evalueringen af ​​de vigtigste algoritmiske strukturer.

• Kompleksiteten af ​​"Følgende" konstruktionen er summen af ​​kompleksiteten af ​​de blokke, der følger efter hinanden: f=f 1 +f 2 +...+f n .
• Kompleksiteten af ​​"Branching"-designet bestemmes gennem sandsynligheden for overgang til hver af instruktionerne, bestemt af betingelsen. Samtidig har kontrol af tilstanden også en vis kompleksitet. For at beregne kompleksiteten af ​​det værste tilfælde kan den forgreningsblok, der har den største kompleksitet, vælges; i det bedste tilfælde kan den blok med mindre kompleksitet vælges. f hvis =f 1 +f så p så +f andet (1-p derefter)
• Kompleksiteten af ​​"løkke"-konstruktionen bestemmes ved at beregne sløjfetermineringsbetingelsen (sædvanligvis af størrelsesorden 0(1)) og produktet af antallet af fuldførte iterationer af sløjfen ved det størst mulige antal operationer af sløjfelegemet. Hvis indlejrede sløjfer bruges, multipliceres deres kompleksitet.

For at estimere kompleksiteten af ​​en algoritme kan der således formuleres en generel metode til at opnå kompleksitetsfunktionen.

1. Dekomponering af algoritmen involverer at identificere de grundlæggende strukturer i algoritmen og estimere kompleksiteten. I dette tilfælde overvejes følgende af de vigtigste algoritmiske strukturer.
2. Linje-for-linje-analyse af arbejdsintensitet for grundlæggende sprogoperationer indebærer enten en kumulativ analyse (der tager højde for alle operationer) eller operationel analyse (under hensyntagen til kompleksiteten af ​​hver operation).
3. Omvendt sammensætning af kompleksitetsfunktionen baseret på metoden til at analysere grundlæggende algoritmiske strukturer for de bedste, gennemsnitlige og værste tilfælde.

Et træk ved vurdering af ressourceeffektiviteten af ​​rekursive algoritmer er behovet for at tage højde for yderligere hukommelsesomkostninger og mekanismen til organisering af rekursion. Derfor er kompleksiteten af ​​rekursive implementeringer af algoritmer relateret til antallet af operationer udført under et rekursivt opkald, såvel som antallet af sådanne opkald. Der tages også højde for omkostningerne ved returnering af værdier og overførsel af kontrol til alarmcentralen. Når du estimerer den nødvendige stakhukommelse, skal du tage højde for, at det på et bestemt tidspunkt ikke er et rekursionsfragment, der er gemt på stakken, men en kæde af rekursive kald. Derfor bestemmes stakstørrelsen af ​​det maksimalt mulige antal modtagne samtidige rekursive opkald.

Programmers bibliotek

"Hvis fejlretning er en proces med at fjerne fejl, så bør programmering være en proces med at introducere dem"

E. Dijkstra

1.2. Hvorfor studere algoritmer? Effektivitet af algoritmer

For det første er algoritmer vitale komponenter til at løse eventuelle problemer inden for forskellige områder af datalogi. Algoritmer spiller en nøglerolle i den nuværende teknologiske udvikling. Her kan du huske sådanne almindelige opgaver som:

• løse matematiske ligninger af varierende kompleksitet, finde produktet af matricer, inverse matricer;
• finde optimale måder at transportere varer og mennesker på;
• finde optimale muligheder for fordeling af ressourcer mellem forskellige knudepunkter (producenter, maskiner, arbejdere, processorer osv.);
• finde sekvenser i genomet, der matcher;
• søgning efter information på det globale internet;
• træffe økonomiske beslutninger inden for e-handel;
• behandling og analyse af lyd- og videoinformation.

Denne liste bliver ved og ved, og faktisk er det næsten umuligt at finde et område inden for datalogi og informationsvidenskab, hvor visse algoritmer ikke bruges.

For det andet kan højkvalitets og effektive algoritmer være katalysatorer for gennembrud i industrier, der ved første øjekast er langt fra datalogi (kvantemekanik, økonomi og finans, evolutionsteorien).

Og for det tredje er det at studere algoritmer også en utrolig interessant proces, der udvikler vores matematiske evner og logiske tænkning.

1.3. Effektivitet af algoritmer

Lad os antage, at en computers hastighed og mængden af ​​dens hukommelse kan øges i det uendelige. Ville der så være behov for at studere algoritmer? Ja, men kun for at demonstrere, at afkoblingsmetoden har en begrænset køretid, og at den giver det rigtige svar. Hvis computere var uendeligt hurtige, ville en vilkårlig korrekt metode til at løse et problem gøre det. Selvfølgelig vil man så oftest vælge den metode, der er nemmere at implementere.

I dag er computere meget kraftfulde, men deres hastighed er ikke uendelig, og det er deres hukommelse heller ikke. I calculus er det således en lige så begrænset ressource som den nødvendige mængde hukommelse. Disse ressourcer bør bruges fornuftigt, hvilket lettes af brugen af ​​algoritmer, der er effektive i forhold til brugen af ​​tids- og hukommelsesressourcer.

Algoritmer designet til at løse det samme problem kan ofte variere meget i effektivitet. Disse forskelle kan være meget mere mærkbare end dem, der skyldes forskellig hardware og software.

Som nævnt ovenfor vil dette afsnit fokusere på sorteringsopgaven. Den første algoritme, der vil blive overvejet, inklusionssortering, kræver tid at arbejde, hvis mængde estimeres til c 1 n 2, hvor n er størrelsen af ​​inputdataene (Antal elementer i sekvensen, der skal sorteres), c 1 er en konstant. Dette udtryk angiver, hvordan køretiden for algoritmen afhænger af mængden af ​​kildedata. I tilfælde af inklusionssortering er denne afhængighed kvadratisk. Den anden algoritme, merge sort, kræver tid, hvis mængde er estimeret til 2 nLog 2 n. Typisk er inklusionssorteringskonstanten mindre end flettesorteringskonstanten, dvs. c12 vokser hurtigere, når n stiger end ILog 2n-funktionen. Og for en eller anden værdi vil n = n 0 nås et øjeblik, når indflydelsen af ​​forskellen i konstanter ophører med at have betydning, og i fremtiden vil funktionen c 2 nLog 2 n være mindre end c 1 n 2 for enhver n > n 0.

For at demonstrere dette skal du overveje to computere - A og B. Computer A er hurtigere og kører sorteringsalgoritmen, og computer B er langsommere og kører flettesorteringsalgoritmen. Begge computere skal sortere et sæt bestående af en million numre. Lad os sige, at computer A udfører en milliard operationer i sekundet, og computer B kun ti millioner, der kører A 100 gange hurtigere end B. For at gøre forskellen mere mærkbar, lad os sige, at koden til aktiveringsmetoden blev skrevet af de bedste programmør i verden ved hjælp af instruktioner til processoren, og for at sortere n tal med denne algoritme skal du udføre 2n 2 operationer (det vil sige C 1 = 2). Merge sort på computer B blev skrevet af en nybegynder programmør ved hjælp af et højt niveau sprog, og den resulterende kode kræver 50nlog 2 n operationer (det vil sige c 2 = 50). For at sortere en million numre ville computer A derfor have brug for

og til computer B -

Derfor kræver det en størrelsesorden mindre CPU-tid at bruge kode, hvis køretid stiger langsommere, selv med en dårlig computer og en dårlig compiler! For sortering af 10.000.000 cifre bliver fordelen ved flettesortering endnu mere mærkbar: mens inklusionssortering kræver omkring 2,3 dage for en sådan opgave, så tager det mindre end 20 minutter for flettesortering. Den generelle regel er, at jo større antal elementer, der skal sorteres, jo større er fordelen ved flettesortering. Ovenstående eksempel viser, at algoritmer, ligesom computersoftware, er teknologi. Samlet systemydelse afhænger lige så meget af effektiviteten af ​​algoritmen, som den gør af hardwarens kraft.

Så forskellige muligheder for computermaskiner overvejes, fra de enkleste Turing-maskiner til et homogent computermiljø. Alle kan bruges til at løse de problemer, som der findes en algoritme til. Baseret på disse modeller bygges mere specialiserede beregningsmodeller, nemlig: ikke-forgrenende aritmetiske programmer, bitvis beregning, binær vektorberegning og beslutningstræer.

Algoritmerne har følgende egenskaber:

a) kompleksitet;

b) arbejdsintensitet;

c) pålidelighed mv.

Der er mange kriterier for at vurdere kompleksiteten af ​​algoritmer. Oftest vil vi være interesserede vækstordre den tid og hukommelseskapacitet, der kræves for at løse problemet, efterhånden som mængden af ​​inputdata stiger. Lad os knytte et bestemt nummer til hver specifik opgave, der kaldes dens størrelse. For eksempel kan størrelsen af ​​et matrixmultiplikationsproblem være den største størrelse af faktormatricerne; størrelsen af ​​et problem på en graf kan være antallet af kanter på en given graf osv.

Den tid, en algoritme tager som funktion af problemets størrelse, kaldes tidskompleksitet denne algoritme. Opførselen af ​​denne kompleksitet i grænsen, når problemets størrelse øges, kaldes asymptotisk tidskompleksitet. Tilsvarende defineret kapacitiv kompleksitet Og asymptotisk kapacitetskompleksitet.

En vigtig motivation for at overveje formelle beregningsmodeller er ønsket om at afsløre den beregningsmæssige kompleksitet af forskellige problemer for at opnå nedre grænser for beregningstiden. At vise, at der ikke findes en algoritme, der kan udføre en given opgave på mindre end en vis tid, kræver en præcis og til tider meget specialiseret definition af, hvad en algoritme er. Et eksempel på en sådan definition er Turing-maskiner.

4.1.1. Ramme- og rammemaskiner*

Overvej to biler:

1. Maskiner med tilfældig adgang til hukommelse (equal access address machine - RAM) modellerer en computer med én adder, hvor programinstruktionerne ikke kan ændre sig selv.

2. Den lagrede programmodel er en maskine med tilfældig adgang til hukommelse og mulighed for at ændre instruktioner (RAM*).

Fig.2.9 Struktur af RAM-maskiner (RAM*)

For RAM skrives programmet ikke til hukommelsen, så programmet ændrer ikke sig selv. Et program er en sekvens af mærkede kommandoer. Der er regneinstruktioner, I/O-instruktioner, indirekte adresseringsinstruktioner og greninstruktioner. Alle beregninger udføres i register r 0 (adder), der ligesom ethvert andet hukommelsesregister kan lagre et vilkårligt heltal. Hver kommando består af to dele - en operationskode og en adresse. PAM-kommandoer er en undergruppe af Assembly-sprogkommandoer; denne delmængde kan udvides efter ønske, men rækkefølgen af ​​opgavernes kompleksitet ændres ikke.

Operanden kan være en af ​​følgende typer:

1. =i betyder selve hele tallet jeg og kaldes en bogstavelig;

2. jeg- registrere indhold jeg (jeg skal være ikke-negativ);

3. *jeg betyder indirekte adressering, dvs. værdien af ​​operanden er indholdet af registret j,Hvor j- et heltal, der er i registret jeg;Hvis j<0, bilen stopper.

Du kan bestemme værdien af ​​programmet R ved hjælp af to objekter: en mapping c fra et sæt af ikke-negative heltal til et sæt af heltal og en "kommandotæller", som bestemmer den næste kommando, der skal udføres. Funktion c er hukommelse display, nemlig c(i)- heltal indeholdt i registernummeret jeg (indhold Tilmeld jeg).

I begyndelsen с(i)=0 for alle jeg 0 , indstilles programtælleren til den første instruktion i P, og udgangsbåndet er tomt. Efter henrettelse k holdet fra R tælleren skifter automatisk til (k+1)-th (det vil sige til den næste) kommando, if k-mit hold var ikke et hold som JUMP, HALT, JGTZ og lignende.

RAM*-programmet er placeret i hukommelsesregistre. Hver RAM*-kommando optager to på hinanden følgende hukommelsesregistre: Det første register indeholder operationskoden, det andet - adressen. Instruktionssættet for RAM* falder sammen med det tilsvarende sæt for RAM i alt undtagen indirekte adressering, hvilket er udelukket: RAM* kan simulere indirekte adressering ved at ændre instruktioner under programafvikling.

Ud over at kontrollere, at algoritmen implementeret af eleven som en løsning er i stand til at producere det korrekte svar på problemet givet visse indledende data, når man tjekker løsningen, tages der også højde for programmets køretid. Dette betyder ikke, at det er afgørende vigtigt at skrive optimale algoritmer til alle opgaver uden undtagelse (hvilket ofte kan tage meget tid for deres kompetente implementering og debugging). Det betyder ganske enkelt, at i nogle enkelte opgaver kan tidsparameteren spille en meget vigtig rolle. Det kan godt ske, at der ved en eller anden OL-runde ikke vil være et eneste problem, hvor optimalitet er nødvendig. Det modsatte kan dog også ske.

Således bør både elever og lærere være i stand til at sammenligne forskellige algoritmer baseret på deres effektivitet. Skolebørn - for at vælge den mest passende måde at løse et problem på på det rigtige tidspunkt, lærere - til kompetent at vælge opgaver og forstå, hvilken løsning forfatteren til et bestemt problem havde i tankerne, da han satte præcis sådanne tidsgrænser.

For at evaluere effektiviteten af ​​algoritmen bruges en kompleksitetsfunktion, betegnet O (læs "om stort"). Faktisk er der andre vurderinger, men på det stadie, hvor en elev lige er begyndt at sætte sig ind i forskellige algoritmer, er der ikke rigtig brug for dem. Kompleksitetsfunktionen afspejler det mønster, i hvilket programudførelsestiden vil stige afhængigt af kildedataene eller deres mængde.

Et eksempel på en algoritme, hvis udførelsestid afhænger af de indledende data, er algoritmen til at finde alle naturlige divisorer af tallet N. Jo større tallet er, jo flere loop-trin vil det være nødvendigt at udføre. Et eksempel på en algoritme, hvis udførelsestid afhænger af mængden af ​​inputdata, ville være at søge efter det største antal i et array. Jo længere arrayet er, jo flere sammenligningsoperationer skal der udføres for at bestemme, hvilket tal der er det største.

Hovedfunktionerne er:

l O(1) - en sådan kompleksitetsfunktion angiver, at programmets køretid er konstant for alle indledende data;

l O(N) - antallet af operationer vokser i forhold til N (her kan N enten være en opgaveparameter eller antallet af elementer i arrayet).

l O(log N) - antallet af operationer vokser i forhold til logaritmen af ​​N (dette er præcis kompleksiteten af ​​f.eks. halveringsmetoden, når man søger efter et element i et ordnet array). Når N stiger med en størrelsesorden, ændres antallet af operationer med én. Grundlaget for logaritmen er normalt ikke specificeret; vi er interesserede i vækstens natur (hurtig/langsom), og ikke den nøjagtige værdi af tid.

l O(N2) - antallet af operationer stiger i forhold til kvadratet af N. Generelt kan det være O(Nk) afhængig af problemets kompleksitet.

l O(N!) - antallet af operationer stiger i forhold til det faktorielle N.

Der er en række finesser her på grund af det faktum, at ikke alle operationer udføres på samme tid, så når man estimerer tidskompleksitet, bruges de operationer, der kræver mest tid.

Oftest, når man beskriver algoritmer, gives et estimat af deres driftstid i sin rene form, det vil sige uden at tage hensyn til input/output operationer.

Eksempel: Lad os anslå kompleksiteten af ​​et program, der kommer ind i et array fra tastaturet og finder det største element i det.

Lad os tilføje antallet af operationer N+(N-1)+1=2N. Det vil sige, at der er en sådan konstant, at antallet af operationer for enhver N ikke overstiger CN. Derfor er kompleksiteten af ​​algoritmen O(N).

Eksempel: Lad os estimere kompleksiteten af ​​et program, der kommer ind i et array fra tastaturet og i det finder et element med en given egenskab (f.eks. lig med en bestemt værdi).

Algoritmen består af følgende trin:

Indtastning af et array (N input-operationer), der søger efter et element med en given egenskab (hvor heldigt: elementet kan placeres enten tættere på begyndelsen af ​​arrayet eller helt til sidst; hvis elementet ikke eksisterer, skal du foretag alle N sammenligninger for at sikre dette) udsender resultatet .

I det bedste tilfælde vil denne algoritme kræve N+2 operationer (input af hele arrayet, en enkelt sammenligning, output), i værste fald (når der ikke er et sådant element - 2N+1 operationer). Hvis N er et stort tal, for eksempel omkring 106, så kan enheden negligeres. Derfor er kompleksiteten af ​​algoritmen O(N).

Eksempel: lad os bestemme kompleksitetsfunktionen af ​​en ordkrypteringsalgoritme med længden L ved hjælp af substitutionsmetoden. Lad der være en tabel, hvor for hvert tegn i alfabetet er skrevet det tegn, som det skal erstattes med. Lad os betegne antallet af bogstaver i alfabetet S.

Algoritmen består af følgende trin:

Indtastning af et ord (én operation) går gennem alle tegn

1. for hvert tegn, find dets erstatning i tabellen (hvis tabellen ikke er ordnet og ikke har nogen egenskaber, der letter søgningen, så er der i værste fald S-operationer for et tegn, hvis det søgte element er på selve ende)

2. output af det fundne symbol

Slut på cyklussen

Det samlede antal operationer er 1+(S+1)*L. I tilfælde af at tilstrækkeligt store S- og L-enheder kan negligeres, viser det sig, at kompleksitetsfunktionen af ​​denne algoritme er O(S*L).

Eksempel: lad os definere kompleksitetsfunktionen af ​​algoritmen til at konvertere det naturlige tal N til det binære talsystem (uden datainput- og outputoperationer).

Algoritmen består af følgende trin:

Loop indtil resultatet af at dividere et tal med 2 er 0

1. divider tallet med 2 og husk resten

2. tag resultatet af division som et nyt tal

Slut på cyklussen

Det samlede antal operationer overstiger ikke 1+log2N. Derfor har denne algoritme en kompleksitet på O(log N).

Hvis et program består af flere dele med forskellige kompleksitetsfunktioner, så O Den større kompleksitetsfunktion vil "absorbere" de mindre. For eksempel, hvis du laver O(N) array input, O(N2) sortering og O(N) output af det bestilte array, så kan du sige, at hele programmet har O(N2) kompleksitet.

Den praktiske anvendelse af viden om kompleksitetsfunktionerne af algoritmer er todelt. For det første kan der til en bestemt opgave vælges en mere optimal algoritme, hvis der er relevante data om den i litteraturen. For det andet, ved at kende køretiden for sin løsning på et sæt indledende data, kan en elev omtrent estimere køretiden for det samme program på data, der svarer til de maksimale begrænsninger for et givet problem.

Spørgsmål

Disse opgaver bruges til selvtestning af det præsenterede materiale og er ikke obligatoriske.

1. Bestem kompleksitetsfunktionen af ​​algoritmen til løsning af en andengradsligning.

2. Bestem kompleksitetsfunktionen af ​​algoritmen til at tegne en regulær polygon ud fra et givet antal sider.

3. Bestem kompleksitetsfunktionen af ​​algoritmen til at indsætte et element i et array på en given position (med en foreløbig forskydning af alle elementer med tal større end eller lig med den givne en efter en position til højre).

4. Bestem kompleksitetsfunktionen af ​​algoritmen til at tilføje to naturlige tal i en kolonne (lad A være antallet af cifre i det første tal, B antallet af cifre i det andet).

5. Bestem kompleksitetsfunktionen af ​​algoritmen til at gange to naturlige tal i en kolonne.