Rekursjon og sorteringsalgoritmer

jeg skal presentere stort sett alle sorteringsalgoritmer rekursivt, så vi bør nok snakke om rekursjon. Rekursjon er en virkelig tankeutvidelsesteknikk, når du får tak i det. Det er også grunnlaget for det som kunne kalles «matematisk tolkning» av dataprogrammering, så hvis du er csci major, må du bli komfortabel med det før eller senere. Så la oss se på noen enkle algoritmer, både iterativt (ved hjelp av løkker) og rekursivt.

Finne faktorialet

faktorialet til n er definert som produktet \(n (n-1) (n-2) \ldots (2) (1)\), dvs. produktet av alle heltall opp til og med n. det er lett å skrivesom en sløyfe:

int factorial_iter(int n) { int r = 1; // Factorial of 0 is 1 for(int i = 1; i <= n; ++i) r *= i; return r;}

for å skrive dette, eller en annen algoritme, rekursivt, må vi stille to spørsmål:

  • Hva er det minste tilfellet, saken der jeg kan gi svaret med en gang? Dette kalles «base case». (Noen ganger kan det v re mer enn ett minste tilfelle, OG DET ER OK.)

  • For noe som ikke er det minste tilfellet, hvordan bryter jeg det ned for å gjøre det mindre? Dette kalles rekursiv sak.

for faktorialet er basissaken hva som skjer når \(n = 0\): loopdoesnt kjører i det hele tatt, og 1 returneres. Så vi kan starte vår rekursive versjonmed

int factorial_rec(int n) { if(n == 0) return 1; else ...}

for å konstruere det rekursive tilfellet må vi se på hva som skjer når n > 0. Spesielt hvordan kan vi bryte \(n!\) ned i noen \ (n’ !, n ‘ < n\)?Det vanligste tilfellet er \(n ‘ = n – 1\).

En måte å se på dette er å anta at vi allerede har verdien av \((n-1)!\ ), og vi ønsker å få \(n!\ ) fra det. Det vil si at factorial_rec(n - 1) vil fungere og gi oss det riktige svaret; vi trenger bareå konstruere faktorialet av n fra det. Hvordan kan vi gjøre dette?\(n! = n (n-1)!\). Så vi skriver vår rekursive sak som dette:

int fact(int n) { if(n == 0) return 1; else return n * fact(n - 1);}

La oss ta et minutt å gå gjennom prosessen med databehandling factorial_rec(3):

  • fact(3) = 3 * fact(2)

  • fact(2) = 2 * fact(1)

  • fact(1) = 1 * fact(0)

  • fact(0) = 1 og på dette punktet kan vi jobbe oss opp igjen, noe som gir resultatet 3 * 2 * 1 * 1 = 6.

Induktivt bevis

Hvordan viser vi at en funksjon gjør hva den skal gjøre? Vi kan teste det, kjøre det tusenvis eller millioner ganger og verifisere at produksjonen er hva vi forventer, men dette krever at vi kommer opp med en uavhengig måte å definere hva funksjonen gjør (f. eks., en annen måte å beregne factorial), sommight seg selv være feil, og videre kan gjentatt testing bare gi en statistisk tillit til at vår algoritme er riktig. Hvis vi vil væresikker, trenger vi et logisk eller matematisk bevis på at det er riktig. Forrecursive funksjoner, dette tar ofte form av bevis ved induksjon. Aninductive proof er slags matematisk ekvivalent med en rekursiv funksjon.Som en rekursiv funksjon har den base case (s) (en base case, faktisk, for hver base case i funksjonen), og base tilfeller er vanligvis enkle. Det ogsåhar induktiv sak (er) (en for hver rekursiv sak i funksjonen), som er noe vanskeligere, men tillater oss å gjøre noe som rekursjon.

Vurder eksemplet ovenfor. Vi ønsker å bevise at fact(n) = \(n!\ ), hvordefinisjonen av \(n! = n (n-1) (n-2)\ldots (2) (1), 0! = 1\).

Bevis ved induksjon på n (uansett variabel vi gjør rekursjonen på, sier vi at vi gjør «bevis ved induksjon» på den variabelen):

  • Base case, \(n = 0\) deretter fact(0) = 1 = \(0!og vi er ferdige.

  • Induktiv sak: I det induktive tilfellet prøver vi å bevise at fact(n) = \(n!\ ` ‘for noen \(n > 0\). Vi kan bryte ned venstre og høyre side og se at vi faktisk har

    $ $ n \ cdot \ mathtt{fact} (n-1) = n! = n (n-1) (n-2) \ldots (2)(1)$$

    Ved å Dele gjennom med \(n\) får vi

    $$\mathtt{fact} (n-1) = (n-1) (n-2) \ldots(2) (1) = (n-1)!$ $

    med andre ord har vi redusert problemet med å bevise at fact(n) = \(n!\ ) til problemet med å bevise at fact(n-1) = \((n-1)!\). Det virker ikke nyttig, men som i en rekursiv funksjon, hvor vi kan kalle funksjonen selv med et mindre argument, i et induktivt bevis kan vi gjenbruke beviset selv som en antagelse, for en mindre \(n\). Vi kaller denne antagelsen den induktive hypotesen, og det ser slik ut:

    $$\tekst {Anta} \ qquad \ mathtt{fact} (n’) = n’! \qquad \ text{for all}\; n ‘< n$ $

    hvis vi lar \(n’ = n-1\) så har vi

    $$\text{Assume}\qquad\mathtt{fact}(n-1) = (n-1)!$ $

    som er akkurat det vi trengte ovenfor! Ved å erstatte i dette for det ovennevnte får vi

    $$(n-1)! = (n-1)!$ $

    og vi er ferdige.

som rekursjon er hjertet av et induktivt bevis handlingen med å bruke beviset selv som en antagelse om «mindre» verdier (\(n’ < n\)). Teknisk er det to typer induktive bevis:

  • «Naturlig tallinduksjon» lar oss bare anta \ (n ‘ = n-1\). Det vil si at vi bare kan anta en «inngang» som er en mindre enn originalen.

  • «Sterk induksjon» lar oss bruke noen \(n ‘ < n\). Du kan bruke sterk induksjon hvor som helst der du kan bruke naturlig tallinduksjon, men det er ikke alltid nødvendig.

the integer exponent calculation

Husk Da Vi jobbet ut kjøretidskompleksiteten til vår «optimaliserte» \(o(\log n)\) – funksjon for å finne a \(b^n\)? Vi kan skrive en rekursiv versjon av det også. Igjen må vi spørre

  • Hva er base case? I dette tilfellet er det når \(n = 0\). I så fall, \(b^0 = 1\), uansett hva f er (det er noen debatt om \(0^0\)).

  • Hva er rekursiv sak? Hvordan bryter vi ned \(b^n\) til \(b^{n’}\)? Her skal vi ta vår kø fra vår tidligere implementering:

    $$b^n = (b^{n/2})^2 \quad\text{if } n \ text{ er jevn}$$
    $$b^n = b \cdot b^{n-1} \quad\text{hvis } n \ text{ er merkelig}$$

Dette gir oss følgende definisjon:

float powi(float b, int n) { if(n == 0) return 1; else if(n % 2 == 0) { // Even float fp = powi(b, n / 2); return fp * fp; } else if(n % 2 == 1) // Odd return f * powi(b, n - 1);}

Dette har samme kompleksitet som den loop-baserte versjonen, og er uten tvil enklere.

I dette tilfellet, Hvis vi vil bevise at \(\mathtt{powi}(b,n) = b^n\) trenger vi sterk induksjon, fordi en av de rekursive tilfellene krymper inndataav noe annet enn bare -1.

Bevis på at \(\mathtt{powi} (b,n) = b^n\ ) ved sterk induksjon på \(n\):

  • Base sak: \(n = 0\)

    Så ved å se på programmet får vi \(\mathtt{powi} (n, 0) = 1 = b^0\) og vi er ferdige.

  • Induktiv sak: \(n > 0\), bevis \(\mathtt{powi} (b,n) = b^n\). Her er det faktisk to induktive tilfeller, en hver for de to rekursive tilfellene i funksjonen. Vår induktive hypotese (antagelse) er

    $$\mathtt{powi}(b,n’) = b^{n’}\qquad \text{for all}\; n’ < n$$
    • Sak 1, \(n\) er jevn. Deretter erstatter anropet til powi med returverdien har vi

      $$\mathtt{powi}(b, n / 2)^2 = b^n$$ $$\mathtt{powi} (b, n / 2)^2 = (b^{n/2})^2$$

      Tar kvadratroten av begge sider:

      $$\mathtt{powi} (b, n/2) = b^{n/2}$$

      på hvilket tidspunkt kan vi bruke IH, med \(n ‘ = n / 2\), og gir

      $ $ b^{n/2} = b^{n/2}$$
    • Sak 2, \(n\) er merkelig. Deretter utvider vi powi vi får

      $$b \cdot \mathtt{powi}(b,n-1) = b \cdot b^{n-1}$$ $$\mathtt{powi}(b,n-1) = b^{n-1} (n ‘ = n-1)$$

    og beviset er komplett

Gjensidig rekursjon

Gjensidig rekursjon er når vi definerer flere rekursive funksjoner i form av hverandre. For eksempel, vurder følgende definisjon av jevn og merkelig:

  • et naturlig tall n er selv iff \(n-1\) er merkelig.

  • et naturlig tall n er merkelig iff \(n-1\) er jevn.

  • \(1\) er merkelig, \(0\) er jevn. (Dette er våre basissaker.)

Vi kan da definere to funksjoner (predikater) som rekursivt refererer til hverandre:

bool is_even(int n) { if(n == 0) return true; else if(n == 1) return false; else return is_odd(n - 1);}bool is_odd(int n) { if(n == 0) return false; else if(n == 1) return true; else return is_even(n - 1);}

hvis vi sporer behandlingen av å bestemme is_even(4), ser vi detdet hopper frem og tilbake mellom is_even og is_odd.

Binært søk

Vi gjorde et binært søk iterativt, men vi kan også gjøre det rekursivt:

  • det er to grunnleggende tilfeller: når vi finner elementet, eller når søkeplassen er redusert til 0 (indikerer at elementet ikke er funnet).

  • den rekursive kasus sammenligner verdien av målet med verdien ved det nåværende midtpunktet, og reduserer deretter størrelsen på søkeområdet (ved rekursivt å søke på venstre eller høyre side).

Dette ser ut som

template<typename T>int binary_search(const vector<T>& data, int low = 0, int high = data.size()-1, const T& target) { if(low > high) return -1; int mid = low + (high - low) / 2; // Why did I do this? if(data.at(mid) == target) return mid; else if(data.at(mid) < target) // Search right return binary_search(data, mid+1, high, target); else if(data.at(mid) > target) // Search left return binary_search(data, low, mid-1, target);}

Andre eksempler: Telle antall kopier i en vektor. For noen vektor-stil rekursjon, må vi holde styr på vår «startsted» innenforvektoren. Dette skyldes at vi ikke kan gjøre vektoren selv mindre, så vi må sette en markør inn i den som viser hvor vi starter. Vi kan gjøre dettepå to måter, med en parameter int start, eller ved å bruke iteratorer.

template<typename T>int count(vector<T> data, int start, T target) { if(start == data.size()) return 0; else return (data.at(start) == target) + count(data, start + 1, target);}

Med iteratorer:

template<typename T, typename It>int count(It start, It finish, T target) { if(start == finish) return 0; else return (*start == target) + count(start + 1, finish, target);}

Iteratorer er typen som pekere.

Sorteringsalgoritmer

en sorteringsalgoritme er en funksjon som tar en sekvens av elementer og på en eller annen måte konstruerer en permutasjon av dem, slik at de bestilles på en eller annen måte.Vanligvis vil vi at ting skal bestilles i henhold til de normale sammenligningsoperatørene, slik at hvis a < b kommer a før b i den endelige permutasjonen.Fortsatt, det er et par ting vi må sørge for at vi får rett:

  • Selvfølgelig kan vi ikke miste noen elementer gjennom prosessen.

  • det kan være duplikater i originalen, i så fall bør det være like mange duplikater i utgangen.

  • for enkelhets skyld tillater vi sortering av en tom sekvens (som, når den sorteres, resulterer i enda en tom sekvens)

det er noen vilkår knyttet til sortering at det er viktig å være klar over:

  • Stabilitet-når inngangssekvensen har element som sammenligner som like, men som er forskjellige (f.eks. ansatte med identiske navn, men ellers forskjellige personer), oppstår spørsmålet om de i utgangssekvensen forekommer i samme rekkefølge som i originalen. F. eks., hvis ansatt» John Smith «#123 kom før» John Smith » #234 i den opprinnelige sekvensen, så sier vi at en sort er stabil hvis #123 er før # 234 i resultatet.

    Stabilitet er viktig når du sorterer en sekvens på flere kriterier. Hvis vi sorterer basert på fornavn, så basert på etternavn, vil en ustabil sortering ikke gi oss det resultatet vi ønsker: fornavnoppføringene blir alle blandet sammen.

  • Tilpasningsevne – noen inngangssekvenser er allerede delvis (eller helt) sortert; en tilpasningsdyktig sorteringsalgoritme vil kjøre raskere (i big – o-termer) på delvis sorterte innganger. Den optimale kjøretiden for en helt sortert inngang er \(O (n)\), tiden det tar å kontrollere at inngangen allerede er sortert.

  • In-Place-en in-place sorteringsalgoritme er en som ikke trenger ekstra plass (dvs. det er plass kompleksitet er \(O(1)\)) å sortere. Noen algoritmer kan ikke brukes på plass, og må konstruere en separat utgangssekvens av samme størrelse som inngangen, for å skrive resultatene inn.

  • Online-noen datasett er for store til å passe inn i minnet i det hele tatt. En online sorteringsalgoritme er en som krever at alle dataene er tilgjengelige (i minnet). Offline sorteringsalgoritmer kan sortere data som er delvis i minnet, delvis på disk eller annen «langsom» lagring, uten å påvirke tidskompleksiteten.

Utvalg sorter

vi har allerede sett på utvalg sortering, så la oss se på det igjen:

  • for å sortere en liste over elementer, finner vi først det minste elementet i hele listen, og legger det i begynnelsen.

  • deretter finner vi det minste elementet i alt etter det første elementet, og legger det andre.

  • Fortsett til det ikke er noe igjen usortert.

effektivt, utvalg sortering deler listen i den sorterte regionen i begynnelsen, og usortert region på slutten. Den sorterte regionen vokser, mensden usorterte regionen krymper.

utvalgssortering er ikke stabil.

Iterativt ser dette ut som dette:

template<typename T>void selection_sort(vector<T> data) { for(auto it = begin(data); it != end(data)-1; ++it) { // Find smallest auto smallest = it; for(auto jt = it+1; jt != end(data); ++jt) if(*jt < *smallest) smallest = jt; // Swap it into place swap(it, smallest); }}

la oss spore gjennom dette på et lite eksempel for å få en følelse av hvordan det fungerer.

Hvordan kan vi implementere dette rekursivt? I stedet for å passere rundt den faktiske vector, skal vi bare passere rundt iteratorene til begynnelsen og slutten av vektoren. Hvorfor vi gjør dette vil bli åpenbart, kort tid:

template<typename Iterator>void selection_sort(Iterator first, Iterator last) { ...}

la oss analysere rekursjonen:

  • basissaken er når last == first + 1. Det betyr at det bare er 1 element, og en 1-elementliste er alltid sortert.

  • den rekursive saken er når last - first > 1. I så fall bryter vi rekursivt det ned ved

    • Å Finne minimum av regionen, og plassere den i begynnelsen.
    • Rekursivt utvalg-sortering first+1 gjennom last (fordi elementet på first er nå på riktig sted).
template<typename Iterator>void selection_sort(Iterator first, Iterator last) { if(last - first == 1) return; // 1 element, nothing to sort else { // Find minimum Iterator smallest = first; for(Iterator it = first; it != last; ++it) if(*it < *smallest) smallest = it; // Swap into place swap(*smallest, *first); // Recursively sort the remainder selection_sort(first + 1, last); }}

la oss tegne rekursjonstreet for dette. Vi vil ikke spore gjennom løkken, vi vil bare anta (for nå) at det fungerer riktig.

DIAGRAM

Analyse Av Sorteringsalgoritmer

I Tillegg til å analysere den generelle best/worst-case big – o-kjøretiden til en sorteringsalgoritme, er det vanlig å også analysere to andre kjøretidsfunksjoner:

  • antall sammenligninger mellom elementer. Dette teller bare sammenligninger mellom objektene som sorteres, ikke sammenligningen av (f. eks.)

  • antall bytter mellom elementer.

Analysere antall sammenligninger og swaps er nyttig fordi disse operasjonene ligger i hjertet av en sorteringsalgoritme: vi kan ikke vite omelementene er ute av drift før vi sammenligner dem (og hvis elementene er komplekse, kan det ta en ikke-triviell tid), og vi kan ikke sette dem i riktig rekkefølge uten å flytte dem rundt – dvs.bytte dem.

Boblesortering

Boblesortering Er en sorteringsalgoritme som egentlig ikke er egnet for rekursiv implementering. Tanken er å sammenligne tilstøtende elementer i inngangen (f. eks., a og a) og bytte dem hvis de er ute av drift. Vi starter i begynnelsen av inngangen og går gjennom den, bytter veitil slutten. Etter et slikt pass vil det største elementet ha «boblet» opp til det siste elementet i arrayet. Så da kan vi gjøre et nytt pass, men vi hopper over det siste elementet denne gangen. Mens selction sortering gjort mindre og mindre passerer starter fra forsiden, boble sortering gjør mindre og smallerpasses fra slutten.

Boblesortering er stabil.

en implementering ser omtrent slik ut:

template<typename T>void bubble_sort(vector<T>& data) { for(int j = 1; j < data.size(); ++j) for(int i = 0; i < data.size() - j; ++i) if(data.at(i) > data.at(i + 1)) swap(data.at(i), data.at(i + 1));}

som implementert er denne funksjonen av orden \(O (n^2)\) i både de beste og verste tilfellene; nestet sløyfe, med samme «trekantede» struktur vi så før.Vi kan faktisk implementere en enkel optimalisering: i den indre sløyfen, hvis viutfør ingen bytteavtaler, så er inngangen sortert, og vi kan stoppe. Hvis vi sjekker dette, kan det tillate oss å gå ut tidlig.

template<typename T>void bubble_sort(vector<T>& data) { for(int j = 1; j < data.size(); ++j) { bool sorted = true; for(int i = 0; i < data.size() - j; ++i) if(data.at(i) > data.at(i + 1)) { swap(data.at(i), data.at(i + 1)); sorted = false; } if(sorted) return; }}

Hva er de beste og verste tilfellene?

  • det beste tilfellet er når inngangen allerede er sortert. I dette tilfellet gjør vi en passering gjennom vektoren (for å sjekke om den er sortert), men bytt ikke noe, og så kommer vi tilbake. Så det beste tilfellet kjøretid effektivitet er \(O (n)\).

  • det verste fallet er en matrise som er sortert i synkende rekkefølge. Hvert element må «boble» hele avstanden til sitt rette sted, så vi vil aldri gå ut tidlig (på grunn av sorted) og tilstanden i if – setningen vil være sant hver gang, så vi skal utføre så mange swaps som nødvendig. Hvis vi trener summen, får vi

    $$\sum_{j = 1}^n (n – j) = n – \sum_{j = 1}^n j$$

    hvor den andre summen utvides til \(\frac{n (n+1)}{2}\), gir oss en ordre av \(O (n)\).

Korrekthet av boblesortering

hvis vi vil bevise korrektheten av boblesortering, kommer det som vanlig ned til å velge riktig invariant (er). Her er det nyttig hvis vi har to, en avhver sløyfe:

template<typename T>void bubble_sort(vector<T>& data) { for(int j = 1; j < data.size(); ++j) { bool sorted = true; for(int i = 0; i < data.size() - j; ++i) if(data.at(i) > data.at(i + 1)) { swap(data.at(i), data.at(i + 1)); // INVARIANT: every element in data to data is *smaller* // than data. sorted = false; } // INVARIANT: every element of data to data is smaller // than data, and every element of data to // data is larger than data. (That is, // data is in the right place.) if(sorted) return; }}

Innsetting sort

Anta at vi deler inngangen i to «seksjoner», sortert og usortert. Den sorterte delen er i utgangspunktet tom. For hvert element i usortert seksjon, setter vi det inn i den sorterte delen, i riktig, sortert posisjon. Fordidette er en matrise / vektor, å sette inn et element krever å skifte alle elementeneetter det opp ett trinn. Selv om vi kan bygge en versjon av dette som opererer»på plass», på en enkelt array (fordi når den sorterte regionen vokser med 1, krymper den usorterte regionen med 1, så den totale størrelsen er alltid n), vil det være lettere å forstå om vi skriver det som en funksjon som beveger elementer fra anusortert vektor til en sortert vektor, som deretter returneres.

Innsettingssortering er stabil.

template<typename T>vector<T> insertion_sort(vector<T>& data) { vector<T> sorted; for(int i = 0; i < data.size(); ++i) { T& item = data.at(i); // Find the proper place for item in sorted int pos = sorted.size(); // Defaults to the end for(int j = 0; j < sorted.size(); ++j) if(sorted.at(j) >= item) { pos = j; break; } // Insert the item at pos, by shifting everything forward // (Increases the size of sorted by 1) sorted.insert(sorted.begin() + pos, item); }}

Hva er de beste og verste tilfellene for denne algoritmen? Det er litt trickyto finne ut fordi kompleksiteten til insert er proporsjonal medantall elementer flyttet (det vil si til sorted.size() - pos). Så mens theloop å finne posisjonen kan gå ut tidlig (selv i den første iterasjonen), thisis dårlig for innsatsen, da det innebærer at pos vil være liten og dermed er tiden for insert ganske dårlig. På den annen side, hvis den indre sløyfen går helt til slutten (pos = sorted.size()), så insert effektivtgjør ikke noe mer enn en push_back.

faktisk balanserer den indre sløyfen og insert alltid hverandre, slik at det totale mellom dem er sorted.size(). Og sorted.size() øker med enhver gang gjennom ytre sløyfen, så igjen har vi vår «trekantede» sløyfe.

Vi kan skrive en rekursiv versjon ved hjelp av en verktøyfunksjon:

  • insert plasserer et element på riktig sted i den sorterte regionen, igjen ved å skifte alt opp.

med disse to på plass blir den rekursive implementeringen

template<typename Iterator>void insertion_sort(Iterator start, Iterator unsorted, Iterator finish) { if(start == finish - 1) return; // One element else { // Insert first unsorted element into sorted region insert(start, unsorted, *unsorted); // Recursively sort the remainder of the unsorted region. insertion_sort(start, unsorted+1, finish); }}

Legg igjen en kommentar

Din e-postadresse vil ikke bli publisert.