Tidseffektiviteten til programmet i henhold til den tilsvarende algoritmen. Konsepter for kompleksitet og effektivitet av algoritmer og datastrukturer. Hva vil vi gjøre med det mottatte materialet?

Algoritme effektivitet er en egenskap til en algoritme som er assosiert med beregningsressursene som brukes av algoritmen. Algoritmen må analyseres for å bestemme ressursene som kreves av algoritmen. Algoritmeeffektivitet kan betraktes som analogt med produksjonsproduktiviteten til repeterende eller kontinuerlige prosesser.

For å oppnå maksimal effektivitet ønsker vi å redusere ressursbruken. Ulike ressurser (som tid og minne) kan imidlertid ikke sammenlignes direkte, så hvilken av to algoritmer som anses som mer effektiv avhenger ofte av hvilken faktor som er viktigst, for eksempel kravet til høy hastighet, minimalt minnebruk eller et annet mål på effektivitet.

Vær oppmerksom på at denne artikkelen IKKE om algoritmeoptimalisering, som er omtalt i artiklene programoptimalisering, optimalisering av kompilator, syklusoptimalisering, objektkodeoptimerer, og så videre. Begrepet "optimering" i seg selv er misvisende fordi alt som kan gjøres faller inn under paraplyen "forbedring".

Bakgrunn

Viktigheten av effektivitet med vekt på utførelsestid ble understreket av Ada Lovelace i 1843 angående Charles Babbages mekaniske analytiske motor:

"I nesten all databehandling er det et stort utvalg av konfigurasjoner som er mulig for å fullføre prosessen, og ulike konvensjoner bør påvirke valget for å utføre beregningen. Det vesentlige er å velge en konfigurasjon som vil resultere i å minimere tiden som kreves for å utføre beregningen."

Tidlige elektroniske datamaskiner var svært begrenset i både hastighet og minne. I noen tilfeller har man innsett at det er en avveining mellom tid og minne, der en oppgave enten må bruke en stor mengde minne for å oppnå høy hastighet, eller bruke en langsommere algoritme som bruker en liten mengde arbeidsminne. I dette tilfellet ble den raskeste algoritmen brukt som det tilgjengelige minnet var tilstrekkelig til.

Moderne datamaskiner er mye raskere enn de tidlige datamaskinene og har mye mer minne (gigabyte i stedet for kilobyte). Donald Knuth understreker imidlertid at effektivitet fortsatt er en viktig faktor:

"I etablerte ingeniørdisipliner er en forbedring på 12 % lett oppnåelig og har aldri blitt ansett som uoverkommelig, og jeg tror det samme bør gjelde i programmering."

Anmeldelse

En algoritme anses som effektiv hvis ressursforbruket (eller ressurskostnaden) er på eller under et akseptabelt nivå. Grovt sett betyr "akseptabel" her "algoritmen vil kjøre i rimelig tid på en tilgjengelig datamaskin." Fordi det har vært en betydelig økning i prosessorkraft og tilgjengelig minne til datamaskiner siden 1950-tallet, var det nåværende "akseptable nivået" ikke akseptabelt selv for 10 år siden.

Dataprodusenter slipper med jevne mellomrom nye modeller, ofte kraftigere. Kostnaden for programvare kan være ganske høy, så i noen tilfeller er det enklere og billigere å få bedre ytelse ved å kjøpe en raskere datamaskin som er kompatibel med din eksisterende datamaskin.

Det er mange måter å måle ressursene som brukes av en algoritme. De to mest brukte målingene er hastighet og minne som brukes. Andre målinger kan inkludere overføringshastighet, midlertidig diskbruk, langsiktig diskbruk, strømforbruk, totale eierkostnader, responstid på eksterne signaler og så videre. Mange av disse målingene avhenger av størrelsen på algoritmens inngangsdata (det vil si mengdene som krever databehandling). Målinger kan også avhenge av måten dataene presenteres på (for eksempel fungerer noen sorteringsalgoritmer dårlig på allerede sorterte data eller når dataene er sortert i omvendt rekkefølge).

I praksis er det andre faktorer som påvirker effektiviteten til algoritmen, for eksempel nødvendig nøyaktighet og/eller pålitelighet. Som forklart nedenfor kan måten en algoritme implementeres på også ha en betydelig effekt på faktisk ytelse, selv om mange aspekter ved implementeringen er optimaliseringsproblemer.

Teoretisk analyse

I den teoretiske analysen av algoritmer er det vanlig praksis å estimere kompleksiteten til en algoritme i dens asymptotiske oppførsel, det vil si å reflektere kompleksiteten til algoritmen som en funksjon av størrelsen på inngangen. n Stor O-notasjon brukes. Dette anslaget er generelt ganske nøyaktig for store n, men kan føre til uriktige konklusjoner ved små verdier n(Derfor kan boblesortering, som anses som sakte, være raskere enn rask sortering hvis du bare trenger å sortere noen få elementer).

Betegnelse	Navn	Eksempler
O(1) (\displaystyle O(1)\,)	fast	Bestemme om et tall er partall eller oddetall. Bruke en oppslagstabell med konstant størrelse. Bruke en passende hash-funksjon for å velge et element.
O (log ⁡ n) (\displaystyle O(\log n)\,)	logaritmisk	Finne et element i en sortert matrise ved hjelp av binært søk eller balansert tre, som ligner på operasjoner på binomialhaugen.
O(n) (\displaystyle O(n)\,)	lineær	Finne et element i en usortert liste eller ubalansert tre (verste tilfelle). Tillegg av to n-bit tall ved bruk av ende-til-ende-bære.
O (n log ⁡ n) (\displaystyle O(n\log n)\,)	kvasilineær, logaritmisk lineær	Beregn rask Fourier-transformasjon, heapsort, quicksort (beste og gjennomsnittlig tilfelle), flette sortering
O (n 2) (\displaystyle O(n^(2))\,)	torget	Multiplisere to n-sifrede tall ved hjelp av en enkel algoritme, boblesortering (verste tilfelle), Shell-sortering, quicksort (verste tilfelle), utvalgssortering, innsettingssortering
O (c n) , c > 1 (\displaystyle O(c^(n)),\;c>1)	eksponentiell	Finne en (eksakt) løsning på det reisende selgerproblemet ved hjelp av dynamisk programmering. Avgjøre om to logiske utsagn er likeverdige ved å bruke uttømmende søk

Verifikasjonstester: Måling av ytelse

For nye versjoner av programvare eller for å gi sammenligning med rivaliserende systemer, brukes noen ganger benchmarks for å sammenligne den relative ytelsen til algoritmer. Hvis for eksempel en ny sorteringsalgoritme slippes, kan den sammenlignes med forgjengere for å sikre at algoritmen er minst like effektiv på kjente data som andre. Ytelsestester kan brukes av brukere til å sammenligne produkter fra ulike produsenter for å vurdere hvilket produkt som best vil passe deres krav når det gjelder funksjonalitet og ytelse.

Noen benchmark-tester gir komparativ analyse av forskjellige kompilerings- og tolkespråk, for eksempel Roy Longbottoms PC Benchmark Collection, og Computer Language Benchmarks-spillet sammenligner ytelsen til implementeringer av typiske oppgaver i noen programmeringsspråk.

Implementeringsspørsmål

Implementeringsproblemer kan også påvirke faktisk ytelse. Dette inkluderer valg av programmeringsspråk og måten algoritmen faktisk er kodet på, valg av oversetter for det valgte språket eller kompilatoralternativene som brukes, og til og med operativsystemet som brukes. I noen tilfeller kan et språk implementert som tolk være betydelig tregere enn et språk implementert som en kompilator.

Det er andre faktorer som kan påvirke timing eller minnebruk som er utenfor programmererens kontroll. Dette inkluderer datajustering, detaljering, søppelinnsamling , parallellitet på instruksjonsnivå og subrutineanrop .

Noen prosessorer har muligheten til å utføre vektoroperasjoner, noe som gjør at en operasjon kan behandle flere operander. Det kan være enkelt å bruke slike funksjoner på programmerings- eller kompileringsnivå. Algoritmer designet for sekvensiell databehandling kan kreve fullstendig redesign for å imøtekomme parallell databehandling.

Et annet problem kan oppstå med prosessorkompatibilitet, der instruksjoner kan implementeres annerledes, slik at instruksjoner på noen modeller kan være relativt tregere på andre modeller. Dette kan være et problem for optimaliseringskompilatoren.

Måling av ressursbruk

Mål er vanligvis uttrykt som en funksjon av størrelsen på inngangen n.

De to viktigste dimensjonene er:

Tid: Hvor lang tid tar algoritmen på CPU.
Hukommelse: Hvor mye arbeidsminne (vanligvis RAM) er nødvendig for algoritmen. Det er to aspekter ved dette: mengden minne for koden og mengden minne for dataene som koden opererer på.

For batteridrevne datamaskiner (som bærbare datamaskiner) eller for svært lange/store beregninger (som superdatamaskiner), er en annen type måling av interesse:

Direkte energiforbruk: Energi som kreves for å kjøre en datamaskin.
Indirekte energiforbruk: Energi som kreves for kjøling, belysning osv.

I noen tilfeller er det nødvendig med andre, mindre vanlige målinger:

Girstørrelse: Båndbredde kan være den begrensende faktoren. Komprimering kan brukes til å redusere mengden data som overføres. Visning av grafikk eller bilde (som Google-logoen) kan føre til at titusenvis av byte overføres (48K i dette tilfellet). Sammenlign dette med å overføre de seks bytene i ordet "Google".
Eksternt minne: Minne kreves på en disk eller annen ekstern lagringsenhet. Dette minnet kan brukes til midlertidig lagring eller til fremtidig bruk.
Responstid: Denne innstillingen er spesielt viktig for sanntidsapplikasjoner der datamaskinen må reagere raskt på eksterne hendelser.
Totalkostnad av eierskap: Parameteren er viktig når den er ment å utføre en enkelt algoritme.

Tid

Teori

Denne typen tester avhenger også vesentlig av valg av programmeringsspråk, kompilator og dets alternativer, slik at de sammenlignede algoritmene må implementeres under de samme betingelsene.

Hukommelse

Denne delen tar for seg bruken av hovedminne (ofte RAM) som trengs av algoritmen. Som med timinganalyse ovenfor, bruker analyse av en algoritme vanligvis romlig kompleksitet av algoritmenå estimere nødvendig kjøretidsminne som en funksjon av inngangsstørrelsen. Resultatet uttrykkes vanligvis i form av "O" stor.

Det er fire aspekter ved minnebruk:

Mengden minne som kreves for å lagre algoritmekoden.
Mengden minne som kreves for inndataene.
Mengden minne som kreves for enhver utgang (noen algoritmer, for eksempel sorteringer, omorganiserer ofte inngangen og krever ikke ekstra minne for utgangen).
Mengden minne som kreves av beregningsprosessen under beregning (dette inkluderer navngitte variabler og eventuell stabelplass som kreves for subrutineanrop, noe som kan være betydelig ved bruk av rekursjon).

Tidlige elektroniske datamaskiner og hjemmedatamaskiner hadde relativt liten arbeidsminnekapasitet. Således hadde EDSAC i 1949 et maksimalt arbeidsminne på 1024 17-bits ord, og i 1980 ble Sinclair ZX80 utgitt med 1024 byte arbeidsminne.

Moderne datamaskiner kan ha relativt store mengder minne (kanskje gigabyte), så å komprimere minnet som brukes av en algoritme til en gitt mengde minne er mindre nødvendig enn før. Imidlertid er eksistensen av tre forskjellige kategorier av hukommelse betydelig:

Cache (ofte statisk RAM) - kjører med hastigheter som kan sammenlignes med CPU
Fysisk hovedminne (ofte dynamisk RAM) - går litt tregere enn CPU
Virtuelt minne (ofte på disk) - gir en illusjon av enormt minne, men fungerer tusenvis av ganger tregere enn RAM.

En algoritme hvis nødvendige minne passer inn i datamaskinens hurtigbuffer er mye raskere enn en algoritme som passer inn i hovedminnet, som igjen vil være mye raskere enn en algoritme som bruker virtuelt rom. Det som kompliserer saken er at noen systemer har opptil tre nivåer med cache. Ulike systemer har forskjellige mengder av disse typer minne, så minneeffekten på en algoritme kan variere betydelig fra ett system til et annet.

I de tidlige dagene av elektronisk databehandling, hvis en algoritme og dens data ikke passet inn i hovedminnet, kunne den ikke brukes. I disse dager gir bruk av virtuelt minne massivt minne, men på bekostning av ytelse. Hvis algoritmen og dens data passer inn i hurtigbufferen, kan svært høy hastighet oppnås, så minimering av minnet som kreves bidrar til å minimere tiden. En algoritme som ikke passer helt inn i cachen, men gir lokaliteten av lenker, kan fungere relativt raskt.

Eksempler på effektive algoritmer

Kritikk av nåværende tilstand av programmering

Programmer blir tregere raskere enn datamaskiner blir raskere.

May sier:

I utbredte systemer kan halvering av instruksjonsutførelse doble batterilevetiden, og big data gir mulighet for bedre algoritmer: Å redusere antall operasjoner fra N x N til N x log(N) har en sterk effekt for store N... For N =30 milliarder, disse endringene ligner på 50 år med teknologiske forbedringer.

Konkurranse om den beste algoritmen

Følgende konkurranser inviterer til deltakelse i utviklingen av de beste algoritmene, hvis kvalitetskriterier bestemmes av dommerne:

se også

Aritmetisk koding er en type entropikoding med variabel kodelengde for effektiv datakomprimering
En assosiativ matrise er en datastruktur som kan gjøres mer effektiv når den brukes trær PATRICIA eller Judy-arrayer
Ytelsestest - en metode for å måle komparativ utførelsestid i visse tilfeller
Beste, verste og gjennomsnittlige tilfelle- konvensjoner for å estimere utførelsestid for tre scenarier
Binært søk er en enkel og effektiv teknikk for å søke i en sortert liste
Grenbord

Mål og mål for forelesningen: introduksjon til metoder for å analysere kompleksiteten og effektiviteten til algoritmer og datastrukturer

Hovedspørsmål: eksperimentell og analytisk analyse av effektiviteten til algoritmer.

N. Wirths klassiske utsagn "Et godt program er enheten av en gjennomtenkt algoritme og effektive datastrukturer."

Algoritmeanalyse
Begrepene «algoritme og datastrukturer» er sentrale innen datateknologi, men for å kalle visse datastrukturer og algoritmer «høykvalitets og effektiv», må det benyttes presise teknikker for å analysere dem. Som et naturlig kvalitetskriterium er det naturlig å fremheve for det første gjennomføringstid. Også viktig er mengden minne og diskplass som brukes, hastigheten på datatilgang (effektiviteten til datastrukturen). Oppmerksomhet bør også rettes mot påliteligheten og påliteligheten til beslutninger, deres stabilitet.

Algoritmen bør ikke være knyttet til en spesifikk implementering. På grunn av mangfoldet av programmeringsverktøy som brukes, kan algoritmer som er forskjellige i implementering gi resultater som varierer i effektivitet.

Utførelsestiden for en algoritme eller operasjon på en datastruktur avhenger som regel av en rekke faktorer. Den enkleste måten å bestemme tiden som kreves for å utføre en algoritme, er å måle tiden før og etter at algoritmen kjører.

Det bør imidlertid huskes at denne metoden for å estimere tid ikke er nøyaktig; først og fremst bør det forstås at i moderne operativsystemer kan flere oppgaver utføres parallelt og utførelsen av en testsak kan kombineres med andre typer av aktivitet. Videre bør det forstås at en stabil avhengighet bare kan oppnås ved å utføre gjentatte tester, ellers, på grunn av påvirkningen på det endelige resultatet av arbeidet med tilfeldige faktorer avhengig av spesifikasjonene til de første dataene, og andre faktorer, utførelsen tid for algoritmen vil også være en tilfeldig variabel. Når du utfører forskning, er det nødvendig å kjøre algoritmen med et annet sett med innledende data; vanligvis genereres selve dataene tilfeldig, så på grunn av forskjellige sett med data, vil tidsbruken også variere.

Når et sett med estimater er oppnådd, kan en graf konstrueres og tilnærmes.

En slik analyse bør alltid brukes når du bruker ikke-trivielle algoritmer; dette ligner på anbefalingen om å utvikle en applikasjon, ved å bruke for feilsøking ikke et prøvesett med flere dusin poster eller elementer, men virkelige data i sin helhet, som unngår modifikasjon eller til og med fullstendig omarbeiding av algoritmen eller strukturdataene hvis de senere viser seg å være upraktiske. Ved å ha et sett med eksperimentelle resultater, kan du utføre interpolering og ekstrapolering og bestemme algoritmens oppførsel under reelle forhold.

Generelt kan vi si at utførelsestiden for en algoritme eller datastrukturmetode øker når størrelsen på kildedataene øker, selv om det også avhenger av typen data, selv om størrelsen er lik. I tillegg avhenger utførelsestiden av maskinvaren (prosessor, klokkefrekvens, minnestørrelse, diskplass osv.) og programvare (driftsmiljø, programmeringsspråk, kompilator, tolk osv.) som implementeringen, kompileringen utføres med og utførelse av algoritmen. For eksempel, alt annet likt, vil utførelsestiden for en algoritme for en viss mengde kildedata være mindre når du bruker en kraftigere datamaskin eller når du skriver algoritmen som et program i maskinkode sammenlignet med dens utførelse av en virtuell maskin tolke det til bytekoder.

Konklusjonen er at å gjennomføre empiriske analyser av algoritmer ikke er virkelig pålitelig. De viktigste ulempene kan reduseres til følgende tre punkter:

1) eksperimenter kan bare utføres ved å bruke et begrenset sett med innledende data; resultater oppnådd med et annet sett tas ikke i betraktning.

2) for å sammenligne effektiviteten til to algoritmer, er det nødvendig at eksperimenter for å bestemme utførelsestiden utføres på samme maskinvare og programvare;
3) for å eksperimentelt studere utførelsestiden til algoritmen, er det nødvendig å gjennomføre implementeringen og utførelsen.

Dermed kommer vi til behovet for å bruke generelle analysemetoder for å analysere algoritmer, som tillater:

1) tar hensyn til ulike typer inndata;

2) lar deg evaluere den relative effektiviteten til alle to algoritmer, uavhengig av maskinvare og programvare;

3) kan utføres i henhold til beskrivelsen av algoritmen uten direkte implementering eller eksperimenter.

Essensen av den generelle analysen er at funksjonen f=f(n1, .., nm) er tilordnet en viss algoritme. I sin enkleste form er det en funksjon av én variabel n1 – mengden inndata. Det kan imidlertid være andre variabler - for eksempel nøyaktigheten av beregningen eller dens pålitelighet. Så for å bestemme om et visst tall er primtall i tilfellet med store tall (lengden på den binære representasjonen er mer enn 200 biter), brukes en sannsynlighetsmetode, hvis pålitelighet kan varieres. De mest kjente funksjonene er lineær, potens og logaritmisk. Derfor bør du ta deg tid til å huske det grunnleggende om å jobbe med dem.

Når du konstruerer algoritmer, skjer det første trinnet ved bruk av ikke et programmeringsspråk, men en beskrivelse på menneskelig språk. Slike beskrivelser er ikke programmer, men de er samtidig mer strukturerte enn vanlig tekst. Spesielt kombinerer "høynivå" beskrivelser naturlig språk og vanlige programmeringsspråkstrukturer, noe som gjør dem tilgjengelige, men likevel informative. Slike beskrivelser letter analyse av datastrukturen eller algoritmen på høyt nivå. Slike beskrivelser kalles vanligvis pseudokode. Det bør også bemerkes at pseudokode ofte er mer nyttig for analyse enn kode i et spesifikt programmeringsspråk.

Noen ganger er det behov for å bevise visse utsagn i forhold til en bestemt datastruktur eller algoritme. For eksempel må du demonstrere riktigheten og hastigheten på utførelse av algoritmen. For å strengt bevise utsagn, er det nødvendig å bruke matematisk språk, som vil tjene som bevis eller begrunnelse for utsagn. Det er flere enkle måter å bevise dette på.

Noen ganger skrives utsagn i en generalisert form: «Sammensetningen s inneholder et element x med egenskap v. For å bevise denne påstanden er det nok å gi et eksempel x "tilhører" s, som har denne egenskapen. I en slik generalisert form skrives som regel usannsynlige utsagn, for eksempel: "Hvert element x i settet s har egenskapen P." For å bevise feilslutningen i denne påstanden er det nok å gi et eksempel: x "tilhører" s, som ikke har egenskapen P. I dette tilfellet vil elementet x fungere som et moteksempel.

Eksempel: Det er oppgitt at et hvilket som helst tall på formen 2^n - 1 er primtall hvis n er et heltall større enn 1. Utsagnet er usant.

Bevis: For å bevise at noen tar feil, må du finne et moteksempel.

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

Det er en annen måte, basert på bevis ved motsigelse (ved å bruke negasjon). Hovedmetodene i dette tilfellet er kontraposisjon og selvmotsigelse. Bruken av kontrastmetoder ligner på speiling: for å bevise at "hvis x er sann, så er y sann," vil vi påstå det motsatte, "hvis y er usant, så er x usann." Fra et logisk synspunkt er disse uttalelsene identiske, men det andre uttrykket, som er en kotroposisjon av det første, er mer praktisk.

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

Bevis: for å bevise denne påstanden, tenk på motsetningen: «Hvis a er et partall og b er oddetall, så er a*b partall. La a = 2*x, for et heltall x. Da er a*b = 2*i*b, og derfor er produktet a*b partall.

Når du bruker metoder for bevis ved selvmotsigelse, er det nyttig å bruke logikk.

A eller b = krever at a eller b utføres, eller både a og b samtidig.
. a og b = krever at a og b utføres samtidig.
. a xor b = krever utførelse av a, men ikke b, eller b, men ikke a.

Når man bruker motsigelsesmetoden for å bevise at en påstand q er sann, antar man først at q er usann og viser deretter at en slik antagelse fører til en selvmotsigelse (for eksempel 2 * 2<>4). Etter å ha kommet til en slik selvmotsigelse, kan vi argumentere for at en situasjon der q er usann ikke eksisterer, og derfor er q sann.

I de fleste tilfeller bruker utsagn om programkjøringstid eller plassbruk en heltallsparameter n (som representerer "størrelsen" på problemet). Når vi så formulerer et utsagn x(n), er slike utsagn ekvivalente for et sett med verdier n. Siden denne uttalelsen gjelder et "uendelig" sett med tall, er det umulig å gi et uttømmende direkte bevis. I slike situasjoner brukes induksjonsmetoder. Metoden for induksjon er basert på faktum; at for enhver n > 1. Det er en begrenset sekvens av handlinger som starter med noe som er kjent for å være sant og til slutt fører til et bevis på at q(n) er sant. Dermed begynner et induksjonsbevis med påstanden om at q(n) er sann for n=1,2,3 osv. opp til noen konstant k. Deretter beviser vi at neste "trinn" av induksjoner q(n+1), q(n+2) også er sant for n > k.

Når man analyserer algoritmer, beregner antall operasjoner og deres utførelsestid, bør man ikke ta hensyn til "små detaljer"; konstante faktorer og konstanter bør neglisjeres. I praksis brukes begrepet en stor funksjon OM. anta at det er to funksjoner f(n) og g(n), det antas at f(n)<= O(g(n)) , т.е. функция О ограничивает сверху значения функции f, начиная с n=n0.

For eksempel er algoritmen for å telle antall elementer lik null i en matrise beskrevet av O(n), hvor n er antall 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)) er beskrevet som O(log(n)).

3) 2100 er beskrevet som O(1)

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

Vær oppmerksom på at funksjonen o(n) begrenser måltidskostnadsfunksjonen ovenfra, men du bør alltid tilstrebe å velge en slik funksjon O(n) at det er maksimal nøyaktighet.

De mest kjente O-funksjonene i stigende rekkefølge:

Når du bruker asymptotisk analyse, vær forsiktig med at når du bruker O-notasjon, neglisjerer du ofte konstante faktorer og addisjonskonstanter. Men hvis denne verdien er stor nok, selv om formen til funksjonen O(1) er mer å foretrekke enn algoritmen beskrevet av funksjonen O(n), er det selvfølgelig den andre algoritmen som vil få praktisk anvendelse.

Avhengig av typen funksjon f(n), skilles følgende klasser av kompleksitet av algoritmer.

Algoritmekompleksitetsklasser avhengig av kompleksitetsfunksjonen
Vis f(n)	Kjennetegn ved klassen av algoritmer
	De fleste instruksjoner for de fleste funksjoner utføres en eller flere ganger. Hvis alle instruksjoner i et program har denne egenskapen, er utførelsestiden for programmet konstant.
logg N	Når et programs utførelsestid er logaritmisk, blir programmet tregere når N øker. Slike utførelsestider er typisk assosiert med programmer som reduserer et stort problem til et sett med mindre delproblemer, og reduserer størrelsen på problemet med en eller annen konstant faktor ved hvert trinn. Å endre basen påvirker ikke i stor grad endringen i verdien av logaritmen: n
N	Når et programs utførelsestid er lineær, betyr det vanligvis at hvert inngangselement gjennomgår liten prosessering.
N log N	Kjøretid proporsjonal med N log N oppstår når en algoritme løser et problem ved å dele det opp i mindre delproblemer, løse dem uavhengig og deretter kombinere løsningene.
N 2	Når kjøretiden til en algoritme er kvadratisk, er den nyttig for praktisk bruk for å løse relativt små problemer. Kvadratisk utførelsestid vises vanligvis i algoritmer som behandler alle par av dataelementer (kanskje i en dobbelt nestet sløyfe).
N 3	En lignende algoritme som behandler tripletter av dataelementer (eventuelt i en trippel-nesting-sløyfe) har en kubisk utførelsestid og er praktisk talt anvendelig kun for små problemer.
2 N	Bare noen få algoritmer med eksponentiell kjøretid har praktiske anvendelser, selv om slike algoritmer oppstår naturlig når man forsøker å løse et problem direkte, for eksempel brute force.

Basert på matematiske metoder for å studere asymptotiske funksjoner av kompleksitet i det uendelige, identifiseres fem klasser av algoritmer.

1. En klasse av raske algoritmer med konstant utførelsestid, deres kompleksitetsfunksjon er O(1). Mellomtilstanden er okkupert av algoritmer med kompleksitet O(log N), som også er klassifisert i denne klassen.

2. En klasse av rasjonelle eller polynomiske algoritmer, hvis kompleksitetsfunksjon bestemmes polynomisk fra inngangsparametrene. For eksempel O(N), O(N 2, O(N 3).

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

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

5. Klasse av overeksponentielle algoritmer. Det finnes algoritmer med faktoriell kompleksitet, men de har generelt ingen praktisk anvendelse.

Minnetilstanden under kjøring av algoritme bestemmes av verdiene som krever at visse områder tildeles. I dette tilfellet, i løpet av å løse problemet, kan et ekstra antall celler brukes. Med mengden minne som kreves av algoritme A for inngang D, mener vi det maksimale antallet minneceller som brukes under utførelsen av algoritmen. Kapasitetskompleksiteten til en algoritme er definert som det asymptotiske estimatet av algoritmens verste minnekapasitetsfunksjon.

Dermed er ressurskompleksiteten til en algoritme i de verste, gjennomsnittlige og beste tilfellene definert som et ordnet par av klasser av funksjoner av tid og kapasitetskompleksitet, spesifisert ved asymptotisk notasjon og tilsvarer tilfellet som vurderes.

De viktigste algoritmiske konstruksjonene i prosedyreprogrammering er følge, forgrening og looping. For å få kompleksitetsfunksjonene for de beste, gjennomsnittlige og verste tilfellene med en fast inputdimensjon, er det nødvendig å ta hensyn til forskjeller i evalueringen av de viktigste algoritmiske strukturene.

Kompleksiteten til «Følgende»-konstruksjonen er summen av kompleksiteten til blokkene som følger hverandre: f=f 1 +f 2 +...+f n .
Kompleksiteten til "Branching" -designet bestemmes av sannsynligheten for overgang til hver av instruksjonene, bestemt av tilstanden. Samtidig har det en viss kompleksitet å sjekke tilstanden. For å beregne kompleksiteten til det verste tilfellet, kan den forgreningsblokken som har mest kompleksitet velges; for det beste tilfellet kan blokken med mindre kompleksitet velges. f hvis =f 1 +f så p så +f annet (1-p da)
Kompleksiteten til "løkke"-konstruksjonen bestemmes ved å beregne sløyfetermineringsbetingelsen (vanligvis av størrelsesorden 0(1)) og produktet av antall fullførte iterasjoner av sløyfen med størst mulig antall operasjoner av løkkelegemet. Hvis nestede løkker brukes, multipliseres kompleksiteten deres.

For å estimere kompleksiteten til en algoritme, kan en generell metode for å oppnå kompleksitetsfunksjonen formuleres.

Dekomponering av algoritmen innebærer å identifisere de grunnleggende strukturene i algoritmen og estimere kompleksiteten. I dette tilfellet vurderes følgende av de viktigste algoritmiske strukturene.
Linje-for-linje-analyse av arbeidsintensitet for grunnleggende språkoperasjoner innebærer enten en kumulativ analyse (som tar hensyn til alle operasjoner) eller operasjonsanalyse (som tar hensyn til kompleksiteten til hver operasjon).
Invers sammensetning av kompleksitetsfunksjonen basert på metodikken for å analysere grunnleggende algoritmiske strukturer for de beste, gjennomsnittlige og verste tilfellene.

Et trekk ved å vurdere ressurseffektiviteten til rekursive algoritmer er behovet for å ta hensyn til ekstra minnekostnader og mekanismen for å organisere rekursjon. Derfor er kompleksiteten til rekursive implementeringer av algoritmer relatert til antall operasjoner utført i løpet av en rekursiv samtale, så vel som antallet slike samtaler. Det tas også hensyn til kostnadene ved å returnere verdier og overføre kontroll til melderen. Når du estimerer nødvendig stabelminne, må du ta i betraktning at på et bestemt tidspunkt er det ikke et rekursjonsfragment som er lagret på stabelen, men en kjede av rekursive anrop. Derfor bestemmes stabelstørrelsen av maksimalt mulig antall samtidige rekursive anrop som mottas.

Programmerers bibliotek

"Hvis feilsøking er en prosess for å fjerne feil, bør programmering være en prosess for å introdusere dem"

E. Dijkstra

1.2. Hvorfor studere algoritmer? Effektivitet av algoritmer

For det første er algoritmer viktige komponenter for å løse eventuelle problemer innen ulike områder av informatikk. Algoritmer spiller en nøkkelrolle på det nåværende stadiet av teknologiutvikling. Her kan du huske slike vanlige oppgaver som:

løse matematiske ligninger av varierende kompleksitet, finne produktet av matriser, inverse matriser;
finne optimale måter å transportere varer og mennesker på;
finne optimale alternativer for å distribuere ressurser mellom ulike noder (produsenter, maskiner, arbeidere, prosessorer, etc.);
finne sekvenser i genomet som matcher;
søk etter informasjon på det globale Internett;
å ta økonomiske beslutninger i e-handel;
behandling og analyse av lyd- og videoinformasjon.

Denne listen fortsetter og fortsetter, og faktisk er det nesten umulig å finne et område innen informatikk og informasjonsvitenskap der visse algoritmer ikke brukes.

For det andre kan høykvalitets og effektive algoritmer være katalysatorer for gjennombrudd i bransjer som ved første øyekast er langt fra informatikk (kvantemekanikk, økonomi og finans, evolusjonsteorien).

Og for det tredje er det å studere algoritmer også en utrolig interessant prosess som utvikler våre matematiske evner og logiske tenkning.

1.3. Effektivitet av algoritmer

La oss anta at hastigheten til en datamaskin og mengden minne kan økes i det uendelige. Ville det være behov for å studere algoritmer da? Ja, men bare for å demonstrere at avkoblingsmetoden har en begrenset kjøretid og at den gir riktig svar. Hvis datamaskiner var uendelig raske, ville en vilkårlig korrekt metode for å løse et problem gjøre det. Selvfølgelig vil oftest metoden som er lettere å implementere bli valgt.

I dag er datamaskiner veldig kraftige, men hastigheten er ikke uendelig, og det er heller ikke minnet. I kalkulus er det derfor en like begrenset ressurs som mengden minne som kreves. Disse ressursene bør brukes klokt, noe som tilrettelegges ved bruk av algoritmer som er effektive når det gjelder bruk av tids- og minneressurser.

Algoritmer designet for å løse det samme problemet kan ofte variere mye i effektivitet. Disse forskjellene kan være mye mer merkbare enn de som er forårsaket av annen maskinvare og programvare.

Som nevnt ovenfor vil denne delen fokusere på sorteringsoppgaven. Den første algoritmen som vil bli vurdert, inkluderingssortering, krever tid for å fungere, mengden som er estimert til c 1 n 2, der n er størrelsen på inngangsdataene (Antall elementer i sekvensen som skal sorteres), c 1 er en konstant. Dette uttrykket indikerer hvordan kjøretiden til algoritmen avhenger av volumet av kildedata. Ved inklusjonssortering er denne avhengigheten kvadratisk. Den andre algoritmen, merge sort, krever tid, mengden som er estimert til 2 nLog 2 n. Vanligvis er inklusjonssorteringskonstanten mindre enn flettesorteringskonstanten, det vil si at c12 vokser raskere når n øker enn ILog 2n-funksjonen. Og for en eller annen verdi n = n 0 vil et øyeblikk nås når påvirkningen av forskjellen i konstanter slutter å ha betydning og i fremtiden vil funksjonen c 2 nLog 2 n være mindre enn c 1 n 2 for enhver n > n 0.

For å demonstrere dette bør du vurdere to datamaskiner - A og B. Datamaskin A er raskere og kjører sorteringsalgoritmen, og datamaskin B er tregere og kjører flettesorteringsalgoritmen. Begge datamaskinene må sortere et sett bestående av en million tall. La oss si at datamaskin A utfører en milliard operasjoner per sekund, og datamaskin B bare ti millioner, det er A som kjører 100 ganger raskere enn B. For å gjøre forskjellen mer merkbar, la oss si at koden for aktiveringsmetoden ble skrevet av de beste programmerer i verden ved å bruke instruksjoner til prosessoren, og for å sortere n tall med denne algoritmen må du utføre 2n 2 operasjoner (det vil si C 1 = 2). Merge sort på datamaskin B ble skrevet av en nybegynner programmerer som bruker et høynivåspråk, og den resulterende koden krever 50nlog 2 n operasjoner (det vil si c 2 = 50). Derfor, for å sortere en million tall, trenger datamaskin A

og til datamaskin B -

Derfor, bruk av kode hvis kjøretid øker langsommere, selv med en dårlig datamaskin og en dårlig kompilator, krever en størrelsesorden mindre CPU-tid! For sortering av 10 000 000 sifre blir fordelen med flettesortering enda mer merkbar: mens inkluderingssortering krever omtrent 2,3 dager for en slik oppgave, tar det mindre enn 20 minutter for flettesortering. Den generelle regelen er at jo større antall elementer som skal sorteres, desto større er fordelen med flettesortering. Eksempelet ovenfor viser at algoritmer, som dataprogramvare, er det teknologi. Samlet systemytelse avhenger like mye av effektiviteten til algoritmen som av kraften til maskinvaren.

Så ulike alternativer for datamaskiner vurderes, fra de enkleste Turing-maskinene til et homogent datamiljø. Alle kan brukes til å løse de problemene som det finnes en algoritme for. Basert på disse modellene bygges mer spesialiserte beregningsmodeller, nemlig: ikke-forgrenende aritmetiske programmer, bitvis beregning, binær vektorberegning og beslutningstrær.

Algoritmene har følgende egenskaper:

a) kompleksitet;

b) arbeidsintensitet;

c) pålitelighet osv.

Det er mange kriterier for å vurdere kompleksiteten til algoritmer. Oftest vil vi være interessert vekstordre tiden og minnekapasiteten som kreves for å løse problemet ettersom mengden inndata øker. La oss knytte til hver spesifikke oppgave et bestemt nummer som kalles dens størrelse. For eksempel kan størrelsen på et matrisemultiplikasjonsproblem være den største størrelsen på faktormatrisene; størrelsen på et problem på en graf kan være antall kanter på en gitt graf osv.

Tiden som en algoritme tar som funksjon av problemstørrelse kalles tidskompleksitet denne algoritmen. Oppførselen til denne kompleksiteten i grensen ettersom problemstørrelsen øker kalles asymptotisk tidskompleksitet. Tilsvarende definert kapasitiv kompleksitet Og asymptotisk kapasitetskompleksitet.

En viktig motivasjon for å vurdere formelle beregningsmodeller er ønsket om å avdekke beregningskompleksiteten til ulike problemer for å få nedre grenser for beregningstiden. Å vise at det ikke finnes en algoritme som kan fullføre en gitt oppgave på mindre enn en viss tid krever en presis og noen ganger høyspesialisert definisjon av hva en algoritme er. Et eksempel på en slik definisjon er Turing-maskiner.

4.1.1. Ramme- og rammemaskiner*

Tenk på to biler:

1. Maskiner med tilfeldig tilgang til minne (equal access address machine - RAM) modellerer en datamaskin med én adder, der programinstruksjoner ikke kan endre seg selv.

2. Den lagrede programmodellen er en maskin med tilfeldig tilgang til minne og mulighet til å endre instruksjoner (RAM*).

Fig.2.9 Strukturen til RAM-maskiner (RAM*)

For RAM skrives ikke programmet til minnet, så programmet endrer seg ikke. Et program er en sekvens av merkede kommandoer. Det er aritmetiske instruksjoner, I/O-instruksjoner, indirekte adresseringsinstruksjoner og greninstruksjoner. Alle beregninger utføres i register r 0 (adder), som, som ethvert annet minneregister, kan lagre et vilkårlig heltall. Hver kommando består av to deler - en operasjonskode og en adresse. PAM-kommandoer er en undergruppe av Assembly-språkkommandoer; denne delmengden kan utvides etter eget ønske, men rekkefølgen på kompleksiteten til oppgavene vil ikke endres.

Operaanden kan være en av følgende typer:

1. =i betyr hele tallet selv Jeg og kalles en bokstavelig;

2. Jeg- registrere innhold Jeg (Jeg må være ikke-negativ);

3. *Jeg betyr indirekte adressering, det vil si at verdien av operanden er innholdet i registeret j,Hvor j- et heltall som er i registeret Jeg;Hvis j<0, bilen stopper.

Du kan bestemme verdien av programmet R ved å bruke to objekter: en mapping c fra et sett med ikke-negative heltall til et sett med heltall og en "kommandoteller", som bestemmer neste kommando som skal utføres. Funksjon c er minneskjerm, nemlig c(i)- heltall i registernummeret Jeg (innhold registrere Jeg).

I begynnelsen с(i)=0 for alle Jeg 0 , er programtelleren satt til den første instruksjonen i P, og utdatabåndet er tomt. Etter henrettelse k laget fra R telleren skifter automatisk til (k+1)-th (det vil si til neste) kommando, if k-laget mitt var ikke et lag som JUMP, HALT, JGTZ og lignende.

RAM*-programmet er plassert i minneregistrene. Hver RAM*-kommando opptar to påfølgende minneregistre: det første registeret inneholder operasjonskoden, det andre - adressen. Settet med instruksjoner for RAM* faller sammen med det tilsvarende settet for RAM i alt unntatt indirekte adressering, som er ekskludert: RAM* kan simulere indirekte adressering ved å endre instruksjoner under programkjøring.

I tillegg til å kontrollere at algoritmen implementert av studenten som en løsning er i stand til å produsere riktig svar på problemet gitt visse innledende data, når du sjekker løsningen, tas også kjøretiden til programmet i betraktning. Dette betyr ikke at det er avgjørende viktig å skrive optimale algoritmer for alle oppgaver uten unntak (som ofte kan ta mye tid for kompetent implementering og feilsøking). Dette betyr ganske enkelt at i enkelte enkeltoppgaver kan tidsparameteren spille en svært viktig rolle. Det kan godt hende at det på en eller annen OL-runde ikke vil være et eneste problem der optimalitet er nødvendig. Det motsatte kan imidlertid også skje.

Dermed bør både elever og lærere kunne sammenligne ulike algoritmer basert på deres effektivitet. Skolebarn - for å velge den mest hensiktsmessige måten å løse et problem på i rett øyeblikk, lærere - for å kompetent velge oppgaver og forstå hvilken løsning forfatteren av et bestemt problem hadde i tankene da han satte nøyaktig slike tidsbegrensninger.

For å evaluere effektiviteten til algoritmen brukes en kompleksitetsfunksjon, betegnet O (les "om stort"). Faktisk finnes det andre vurderinger, men på det stadiet når en elev akkurat begynner å sette seg inn i ulike algoritmer, er de egentlig ikke nødvendige. Kompleksitetsfunksjonen gjenspeiler mønsteret der programkjøringstiden vil øke avhengig av kildedataene eller deres mengde.

Et eksempel på en algoritme hvis utførelsestid avhenger av de innledende dataene er algoritmen for å finne alle naturlige divisorer av tallet N. Jo større tallet er, jo flere løkketrinn vil det være nødvendig å utføre. Et eksempel på en algoritme hvis utførelsestid avhenger av mengden inndata vil være å søke etter det største antallet i en matrise. Jo lengre matrisen er, jo flere sammenligningsoperasjoner må gjøres for å bestemme hvilket tall som er størst.

Hovedfunksjonene er:

l O(1) - en slik kompleksitetsfunksjon indikerer at kjøretiden til programmet er konstant for alle innledende data;

l O(N) - antall operasjoner vokser proporsjonalt med N (her kan N enten være en oppgaveparameter eller antall elementer i matrisen).

l O(log N) - antall operasjoner vokser proporsjonalt med logaritmen til N (dette er nøyaktig kompleksiteten til for eksempel halveringsmetoden når man søker etter et element i en ordnet matrise). Når N øker med en størrelsesorden, endres antall operasjoner med én. Grunnlaget for logaritmen er vanligvis ikke spesifisert; vi er interessert i vekstens natur (rask/sakte), og ikke den nøyaktige verdien av tid.

l O(N2) - antall operasjoner øker proporsjonalt med kvadratet av N. Generelt kan det være O(Nk) avhengig av problemets kompleksitet.

l O(N!) - antall operasjoner øker proporsjonalt med den faktorielle N.

Det er en rekke finesser her på grunn av det faktum at ikke alle operasjoner utføres på samme tid, så når man estimerer tidskompleksitet, brukes de operasjonene som krever mest tid.

Oftest, når man beskriver algoritmer, gis et estimat for deres driftstid i sin rene form, det vil si uten å ta hensyn til input/output-operasjoner.

Eksempel: la oss anslå kompleksiteten til et program som går inn i en matrise fra tastaturet og finner det største elementet i det.

La oss legge til antall operasjoner N+(N-1)+1=2N. Det vil si at det er en slik konstant at antallet operasjoner for enhver N ikke overstiger CN. Derfor er kompleksiteten til algoritmen O(N).

Eksempel: la oss estimere kompleksiteten til et program som kommer inn i en matrise fra tastaturet og finner i det et element med en gitt egenskap (for eksempel lik en viss verdi).

Algoritmen består av følgende trinn:

Gå inn i en matrise (N input-operasjoner) som søker etter et element med en gitt egenskap (hvor heldig: elementet kan enten være nærmere begynnelsen av matrisen eller helt på slutten; hvis elementet ikke eksisterer, må du foreta alle N sammenligninger for å være sikker på dette) gi resultatet .

I beste fall vil denne algoritmen kreve N+2 operasjoner (inngang av hele matrisen, en enkelt sammenligning, utgang), i verste fall (når det ikke er noe slikt element - 2N+1 operasjoner). Hvis N er et stort tall, for eksempel omtrent 106, kan enhet neglisjeres. Derfor er kompleksiteten til algoritmen O(N).

Eksempel: la oss bestemme kompleksitetsfunksjonen til en ordkrypteringsalgoritme med lengde L ved å bruke substitusjonsmetoden. La det være en tabell der for hvert tegn i alfabetet står tegnet som det må erstattes med. La oss betegne antall bokstaver i alfabetet S.

Algoritmen består av følgende trinn:

Inntasting av et ord (én operasjon) går gjennom alle tegn

1. for hvert tegn, finn erstatningen i tabellen (hvis tabellen ikke er ordnet og ikke har noen egenskaper som letter søket, så er det i verste fall S-operasjoner for ett tegn hvis det søkte elementet er på selve slutt)

2. utgang av funnet symbol

Slutt på syklusen

Totalt antall operasjoner er 1+(S+1)*L. I tilfelle av tilstrekkelig store S- og L-enheter kan neglisjeres, viser det seg at kompleksitetsfunksjonen til denne algoritmen er O(S*L).

Eksempel: la oss definere kompleksitetsfunksjonen til algoritmen for å konvertere det naturlige tallet N til det binære tallsystemet (uten datainn- og utdataoperasjoner).

Algoritmen består av følgende trinn:

Loop til resultatet av å dele et tall med 2 er 0

1. del tallet på 2 og husk resten

2. ta resultatet av divisjon som et nytt tall

Slutt på syklusen

Totalt antall operasjoner overstiger ikke 1+log2N. Derfor har denne algoritmen en kompleksitet på O(log N).

Hvis et program består av flere deler med ulike kompleksitetsfunksjoner, da O Den større kompleksitetsfunksjonen vil "absorbere" de mindre. For eksempel, hvis du gjør O(N) array input, O(N2) sortering og O(N) output for den bestilte arrayen, så kan du si at hele programmet har O(N2) kompleksitet.

Den praktiske anvendelsen av kunnskap om kompleksitetsfunksjonene til algoritmer er todelt. For det første, for en bestemt oppgave, kan en mer optimal algoritme velges hvis det finnes relevante data om den i litteraturen. For det andre, ved å kjenne kjøretiden til løsningen hans på ett sett med innledende data, kan en student omtrent estimere kjøretiden til det samme programmet på data som tilsvarer de maksimale begrensningene for et gitt problem.

Spørsmål

Disse oppgavene brukes til selvtesting av materialet som presenteres og er ikke obligatoriske.

1. Bestem kompleksitetsfunksjonen til algoritmen for å løse en andregradsligning.

2. Bestem kompleksitetsfunksjonen til algoritmen for å tegne en regulær polygon basert på et gitt antall sider.

3. Bestem kompleksitetsfunksjonen til algoritmen for å sette inn et element i en matrise på en gitt posisjon (med en foreløpig forskyvning av alle elementer med tall større enn eller lik den gitte en etter en posisjon til høyre).

4. Bestem kompleksitetsfunksjonen til algoritmen for å legge til to naturlige tall i en kolonne (la A være antall sifre i det første tallet, B antallet sifre i det andre).

5. Bestem kompleksitetsfunksjonen til algoritmen for å multiplisere to naturlige tall i en kolonne.