Video: NKUL 2019 Sesjon 1G: Algoritmisk tenkning og programmering i fagfornyelsen 2024
En funksjon i matematikk er ganske enkelt en måte å kartlegge noen innganger til et svar. Uttrykt på en annen måte er en -funksjon en transformasjon (basert på matematikkoperasjoner) som forvandler (kart) innspillet til et svar.
For bestemte verdier av inngang (vanligvis betegnet med bokstavene x eller n), har du et tilsvarende svar ved hjelp av matematikken som definerer funksjonen. For eksempel forteller en funksjon som f (n) = 2 n at når innspillet ditt er et tall n, ditt svar er tallet n multiplisert med 2.
Bruk av størrelsen på inngangen er fornuftig, gitt at dette er en tidskritisk alder, og folks liv er proppet med en økende mengde data. Å gjøre alt til en matematisk funksjon er litt mindre intuitiv, men en funksjon som beskriver hvordan en algoritme relaterer sin løsning til mengden data det mottar, er noe du kan analysere uten spesifikk maskinvare- eller programvarestøtte. Det er også enkelt å sammenligne med andre løsninger, gitt størrelsen på problemet ditt. Analyse av algoritmer er virkelig et tankebrytende konsept fordi det reduserer en kompleks serie av trinn i en matematisk formel.
Dessuten er det ikke engang en analyse av algoritmer som er interessert i å definere funksjonen nøyaktig. Det du virkelig vil gjøre er å sammenligne en målfunksjon med en annen funksjon. Disse sammenligningsfunksjonene vises innenfor et sett med foreslåtte funksjoner som utfører dårlig når de står i motsetning til målalgoritmen. På denne måten trenger du ikke å koble tall til funksjoner med større eller mindre kompleksitet; I stedet håndterer du enkle, premade og kjente funksjoner. Det kan høres ujevnt, men det er mer effektivt og ligner på å klassifisere algoritmenes ytelse i kategorier, i stedet for å oppnå en nøyaktig ytelsesmåling.
Settet med generelle funksjoner kalles Big O notasjon, og du møter ofte dette lille settet av funksjoner (satt i parentes og foran en kapital O >) brukes til å representere ytelsen til algoritmer. Figuren viser analysen av en algoritme. Et kartesisk koordinatsystem kan representere sin funksjon som målt ved RAM-simulering, hvor abscissa (x-koordinatet) er størrelsen på inngangen og ordinaten (y-koordinaten) er dens resulterende antall operasjoner. Du kan se tre kurver representert. Inngangsstørrelse er viktig. Kvaliteten er imidlertid også viktig (for eksempel når du bestiller problemer, er det raskere å bestille innspill som allerede er nesten bestilt).Følgelig viser analysen verste fallet, f 1 (n), et gjennomsnitt tilfelle, f 2 (n), og et beste tilfelle, f 3 (n). Selv om gjennomsnittssaken kan gi deg en generell ide, er det det verste som du virkelig bryr deg om, fordi det kan oppstå problemer når din algoritme sliter med å nå en løsning. Big O-funksjonen er den som etter en viss verdi
n0
(terskelen for å vurdere en inngang stor) resulterer alltid i et større antall operasjoner som gir samme inngang enn den verste fallfunksjonen > f1
. Dermed er Big O-funksjonen enda mer pessimistisk enn den som representerer algoritmen din, slik at uansett kvaliteten på inngangen, kan du være sikker på at ting ikke kan bli verre enn det.
Kompleksiteten til en algoritme i tilfelle best, gjennomsnittlig og verste inngangssak.
Mange mulige funksjoner kan føre til dårligere resultater, men valget av funksjoner som tilbys av Big O-notatet som du kan bruke, er begrenset fordi målet er å forenkle kompleksitetsmåling ved å foreslå en standard. Følgelig inneholder denne delen bare de få funksjonene som er en del av Big O-notatet. Følgende liste beskriver dem i voksende rekkefølge av kompleksitet:
Samme tid, uansett hvor mye input du oppgir. Til slutt er det et konstant antall operasjoner, uansett hvor lenge inngangsdata er. Dette nivået av kompleksitet er ganske sjelden i praksis.
- Logaritmisk kompleksitet O (log n): Antall operasjoner vokser i lavere takt enn inngangen, noe som gjør algoritmen mindre effektiv med små innganger og mer effektiv med større. En typisk algoritme for denne klassen er binærsøk.
- Linjær kompleksitet O (n): Operasjoner vokser med inngangen i et 1: 1-forhold. En typisk algoritme er iterasjon, som er når du skanner innspilling én gang og bruker en operasjon til hvert element av det.
- Linearitmisk kompleksitet O (n log n): Kompleksitet er en blanding mellom logaritmisk og lineær kompleksitet. Det er typisk for noen smarte algoritmer som brukes til å bestille data, for eksempel Mergesort, Heapsort og Quicksort.
- Kvadratisk kompleksitet O (n 2
- ): Operasjonene vokser som et firkant av antall innganger. Når du har en iterasjon inne i en annen iterasjon (nestet iterasjoner, i datavitenskap), har du kvadratisk kompleksitet. For eksempel har du en liste over navn, og for å finne de mest liknende, sammenligner du hvert navn mot alle de andre navnene. Noen mindre effektive bestillingsalgoritmer presenterer slik kompleksitet: boble sortering, utvalg sortering og innføring sortering. Dette kompleksitetsnivået betyr at algoritmer kan kjøre i flere timer eller til dager før du når en løsning. Kubisk kompleksitet O (n 3
- ): Operasjonene vokser enda raskere enn kvadratisk kompleksitet fordi nå har du flere nestede iterasjoner. Når en algoritme har denne rekkefølgen av kompleksitet, og du må behandle en beskjeden mengde data (100 000 elementer), kan algoritmen din løpe i mange år.Når du har en rekke operasjoner som er en kraft av inngangen, er det vanlig å referere til algoritmen som kjører i polynomisk tid. Eksponentiell kompleksitet O (2 n
- ): Algoritmen tar to ganger antall tidligere operasjoner for hvert nytt element lagt til. Når en algoritme har denne kompleksiteten, kan selv små problemer ta for alltid. Mange algoritmer gjør uttømmende søk har eksponentiell kompleksitet. Det klassiske eksempelet på dette kompleksitetsnivået er imidlertid beregningen av Fibonacci-tall. Faktisk kompleksitet O (n!): Et ekte mareritt av kompleksitet på grunn av det store antall mulige kombinasjoner mellom elementene. Bare tenk: Hvis innspillet ditt er 100 objekter, og en operasjon på datamaskinen tar 10
- -6 sekunder (en rimelig hastighet for hver datamaskin, i dag), trenger du ca 10 140 år for å fullføre oppgaven vellykket (en umulig tid siden universets alder er beregnet som 10 14 år). Et kjent faktorisk kompleksitetsproblem er det reisende selgerproblemet, der en selger må finne den korteste ruten for å besøke mange byer og komme tilbake til startbyen.
