Algoritmer for Dummies Cheat Sheet - dummies

Av John Paul Mueller, Luca Massaron

Algoritmer trenger ikke å være kjedelig eller vanskelig å bruke. Faktisk omgir algoritmer deg på mange måter som du kanskje ikke har tenkt på, og du bruker dem hver dag til å utføre viktige oppgaver. Du må imidlertid kunne bruke algoritmer uten å bli matematiker.

Programmeringsspråk lar deg beskrive trinnene som brukes til å opprette en algoritme. Noen språk er bedre enn andre til å utføre denne oppgaven på en måte som folk kan forstå uten å bli datavitenskapere. Python gjør bruk av algoritmer enklere fordi det kommer med mye innebygd og utvidet støtte (ved bruk av pakker, datasett og andre ressurser). Dette Cheat Sheet hjelper deg med å få tilgang til de mest nødvendige tipsene for å gjøre bruk av algoritmer raskt og enkelt.

Finne algoritmen du trenger

Følgende tabell beskriver algoritmer og algoritmetyper som du kan finne nyttige for ulike typer dataanalyse. (Du finner diskusjoner av alle disse algoritmer i Algoritmer for Dummies.)

Algoritme	Beskrivelse	Nyttig link
A * Søk	Algoritmen sporer kostnadene for noder da den utforsker dem ved hjelp av ligning: f (n) = g (n) + h (n), hvor: n er nodenavnet g (n) kostnaden for å nå noden så langt h (n) er den anslåtte kostnaden for å nå Målet fra noden f (n) er den anslåtte kostnaden for banen fra n til målet Tanken er å søke de mest lovende stiene først og unngå dyre stier.	Standford. edu
Balanced Tree	En slags tre som opprettholder en balansert struktur gjennom omorganisering slik at den kan gi reduserte tilgangstider. Antallet elementer på venstre side avviger fra tallet på høyre side av en på de fleste.	Webdocs
Toveiset søk	Denne teknikken søker samtidig fra rotnoden og målnoden til de to søkebanene møtes i midten. En fordel ved denne tilnærmingen er at det er tidseffektivt fordi det finner løsningen raskere enn mange andre brute-force løsninger. I tillegg bruker det minne mer effektivt enn andre tilnærminger, og finner alltid en løsning. Den største ulempen er implementeringens kompleksitet.	Planning. cs
Binær Tree	Dette er en type tre som inneholder noder som knytter seg til null (blad noder), en eller to (gren noder) andre noder. Hver node definerer de tre elementene som den må inkludere for å gi tilkobling og lagre data: datalagring, venstre tilkobling og riktig tilkobling.	cs. CMU. edu
Bredde-første søk	Denne teknikken begynner ved rotnoden, undersøker hver av barnnoderne først, og beveger seg bare ned til neste nivå. Den utvikler seg nivå etter nivå til det finner en løsning. Ulempen med denne algoritmen er at den må lagre hver node i minnet, noe som betyr at den bruker en betydelig mengde minne for et stort antall noder. Denne teknikken kan sjekke for dupliserte noder, noe som sparer tid, og det kommer alltid opp med en løsning.	Khan Academcy
Brute Force	Dette er en teknikk for problemløsing der noen prøver alle mulige løsninger, på jakt etter den beste problemløsningen. Brute-force teknikker garanterer en best egnet løsning når man eksisterer, men er så tidkrevende å implementere at de fleste mennesker unngår dem.	IgM. univ
Dybde-første søk	Denne teknikken begynner på rotnoden og utforsker et sett med tilkoblede barnnoder til det når et bladknutepunkt. Den utvikler grenen etter grenen til den finner en løsning. Ulempen med denne algoritmen er at den ikke kan se etter dupliserte noder, noe som betyr at den kan krysse de samme nodebanene mer enn en gang. Faktisk kan denne algoritmen kanskje ikke finne en løsning i det hele tatt, noe som betyr at du må definere et cutoff-punkt for å holde algoritmen fra å søke uendelig. En fordel ved denne tilnærmingen er at den er minneeffektiv.	Hacker Earth
Divide and Conquer	Dette er en teknikk for problemløsing der problemet brytes inn i de minste mulige bitene og løses ved hjelp av den enkleste tilnærmingen som er mulig. Denne teknikken sparer betydelig tid og ressurser i forhold til andre tilnærminger, som brute force. Det garanterer imidlertid ikke alltid et best egnet resultat.	Khan Academy
Dijikstra	Dette er en algoritme som brukes til å finne den korteste banen i en rettet vektet grafikk (med positive vekter).	Geeks for Geeks
Graf	En graf er en slags treforlengelse. Som med trær, har du noder som kobler til hverandre for å skape relasjoner. I motsetning til binære trær kan en graf imidlertid ha mer enn en eller to tilkoblinger. Faktisk har grafnoder ofte en rekke tilkoblinger. Du ser grafer som brukes på steder som kart for GPS og alle andre steder som topp-ned-tilnærmingen til et tre ikke vil fungere.	Tutorials
Greedy Algorithms	Thistechnique av en av problemløsning der løsningen er avhengig av det beste svaret for hvert trinn i problemløsingsprosessen. Greedy algoritmer gjør vanligvis to forutsetninger: Det er mulig å foreta et enkelt, optimalt valg ved et gitt trinn. Ved å velge det optimale valget i hvert trinn, er det mulig å finne en optimal løsning for det totale problemet.	Tutorials
Greedy Best-First Search (BFS)	Algoritmen velger alltid banen som er nærmest målet ved å bruke ligningen: f (n) = h n). Denne spesielle algoritmen kan finne løsninger ganske raskt, men det kan også bli sittende fast i sløyfer, så mange anser det ikke som en optimal tilnærming til å finne en løsning.	Centurion2
Hashing	Dette er en metode for å forutsi plasseringen av et bestemt datapunkt i datastrukturen (hva den strukturen kan være) før du faktisk ser etter den. Denne tilnærmingen er avhengig av bruk av nøkler plassert i en indeks. En hashfunksjon gjør nøkkelen til en numerisk verdi som algoritmen plasserer i et hashbord. Et hashbord gir midler til å opprette en indeks som peker på elementer i en datastruktur, slik at en algoritme lett kan forutsi at dataene er plassert.	Tutorials
Heap	Dette er et sofistikert tre som gjør det mulig å sette inn data i trestrukturen. Bruken av datainnsetting gjør sorteringen raskere. Du kan videre klassifisere disse trærne som makshøyder og minhunder, avhengig av treets evne til umiddelbart å gi den maksimale eller minsteverdien som er tilstede i treet.	Tutorials
Heuristics	Dette er en teknikk for problemløsing som bygger på selvoppdagelse og gir tilstrekkelig nyttige resultater (ikke nødvendigvis optimal, men god nok) for å løse et problem godt nok at en bedre løsning ikke er " t nødvendig. Selvoppdagelse er prosessen med å la algoritmen vise deg en potensielt nyttig vei til en løsning (men du må fortsatt stole på menneskelig intuisjon og forståelse for å vite om løsningen er den rette).	Northwest. edu
MapReduce	Dette er et rammeverk for å lage algoritmer som arbeider ved å bruke beregninger parallelt (ved hjelp av flere datamaskiner koblet sammen i et nettverk), slik at algoritmer kan fullføre sine løsninger raskere.	Hadoop Apache
Mergesort	Mergesort er en allsidig, sammenligningsbasert metode for sortering av data. Det avhenger av en splittelse og erobre tilnærming til å utføre sin oppgave.	Geeks for Geeks
Nash Equilibrium	Dette er en spillteori hvor de andre spillerne kjenner likevektsstrategien for de andre spillerne, så ingen har noe å vinne ved å endre sin personlige strategi. Denne teorien ser bruk i en hvilken som helst fiendtlig situasjon der spilleren må ta hensyn til de beslutningene som er tatt av alle de andre spillerne for å vinne spillet.	Khan Academy
PageRank	PageRank er en algoritme for å måle viktigheten av en node i en graf. Denne algoritmen er grunnen til Googles kjernealgoritmer for å drive relevante søk til brukere.	Princeton. edu
Pure Heuristic Search	Denne algoritmen utvider nodene i rekkefølge av kostnadene. Den opprettholder to lister. Den lukkede listen inneholder noder som den allerede har utforsket, og den åpne listen inneholder noder som den ennå må utforske. I hver iterasjon utvider algoritmen node med lavest mulig pris. Alle dens barnnoder er plassert i den lukkede listen, og de individuelle barneknutekostnadene beregnes. Algoritmen sender barnnoder med lav pris tilbake til den åpne listen og sletter barnnoder med høy pris. Algoritmen utfører derfor en intelligent, kostnadsbasert søk etter løsningen.	World of Computing
Quicksort	Dette er en generell sorteringsstrategi basert på partisjoneringsarrayer av data til mindre arrays.Det avhenger av en splittelse og erobre tilnærming til å utføre sin oppgave.	Tutorials
Ubalansert Tree	Dette er et tre som plasserer nye dataelementer hvor det er nødvendig i treet uten hensyn til balanse. Denne metoden for å legge til elementer gjør det mulig å bygge treet raskere, men reduserer tilgangshastigheten når du søker eller sorterer.	Quora

Differensierende algoritmer fra andre matematiske strukturer

Hvis du er som de fleste, finner du ofte deg selv når du skal skrape hodet når det gjelder matematikkstrukturer fordi ingen synes å vite hvordan man bruker vilkårene riktig. Det er som om folk forsiktig forsøker å gjøre ting vanskelig! Tross alt, hva er en ligning og hvorfor er det forskjellig fra en algoritme? Vel, vær ikke redd: Følgende tabell gir den endelige veiledningen til matematikkstrukturer som du kanskje støter på, men har vært redd for å spørre om.

Struktur	Beskrivelse
Ligning	Tall og symboler som, når de er tatt som helhet, tilsvarer en bestemt verdi. En ligning inneholder alltid et like tegn slik at du vet at tallene og symbolene representerer den spesifikke verdien på den andre siden av likestegnet. Likninger inneholder generelt variabel informasjon som presenteres som et symbol, men de er ikke pålagt å bruke variabler.
Formel	En kombinasjon av tall og symboler som brukes til å uttrykke informasjon eller ideer. En formel presenterer vanligvis matematiske eller logiske begreper, for eksempel å definere den største felles divisor (GCD) av to heltall (videoen på Khan Academy forteller hvordan dette fungerer). Generelt viser en formel forholdet mellom to eller flere variabler. De fleste ser en formel som en spesiell type ligning.
Algoritme	En sekvens av trinn som brukes til å løse et problem. Sekvensen presenterer en unik metode for å løse et problem ved å gi en bestemt løsning. En algoritme trenger ikke representere matematiske eller logiske begreper, selv om presentasjonene i denne boken ofte faller inn i den kategorien fordi folk oftest bruker algoritmer på denne måten. Noen spesielle formler er også algoritmer, som den kvadratiske formelen. For en prosess for å representere en algoritme må den være følgende: Endelig: Algoritmen må til slutt løse problemet. Godt definert: Trinnene må være presise og nåværende trinn som er forståelige, spesielt ved datamaskiner, som må kunne lage en brukbar algoritme. Effektiv: En algoritme må løse alle tilfeller av problemet som noen definerte det for. En algoritme bør alltid løse problemet det må løse. Selv om du bør forutse noen feil, er forekomsten av fiasko sjelden og forekommer bare i situasjoner som er akseptable for den tiltenkte algoritmen.

Utrolige måter å bruke algoritmer på

Folk bruker faktisk algoritmer hele tiden. For eksempel er å lage toast et eksempel på en algoritme, som forklart i dette blogginnlegget. Å lage toast er ikke en fantastisk algoritme, men de i følgende tabell, som bruker en datamaskin til å utføre oppgaver, er.

Oppgave	Hvorfor det er utrolig
Kryptografi	Å holde data trygt er et pågående kamp med hackere som stadig angriper datakilder. Algoritmer gjør at du kan analysere data, sette den inn i en annen form, og deretter returnere den til sin opprinnelige form senere.
Grafanalyse	Muligheten til å bestemme seg for den korteste linjen mellom to punkter, finner alle bruksområder. For eksempel, i et ruteproblem kunne GPS ikke fungere uten denne spesifikke algoritmen fordi den aldri kunne lede deg langs bygater ved å bruke den korteste ruten fra punkt A til punkt B.
Pseudorandom nummergenerering	Tenk deg å spille spill som aldri varierte. Du starter på samme sted og utfører de samme trinnene på samme måte hver gang du spiller. Kjedelig! Uten muligheten til å generere tilsynelatende tilfeldige tall, blir mange datoperasjoner meningsløse eller umulige.
Planlegging	Å gjøre bruk av ressurser rettferdig for alle involverte, er en annen måte hvor algoritmer gjør at deres tilstedeværelse er kjent på en stor måte. For eksempel er timinglysene ved kryssene ikke lenger enkle enheter som teller ned sekunder mellom lysendringer. Moderne enheter vurderer alle slags problemer, for eksempel tidspunktet på dagen, værforholdene og trafikkstrømmen. Planlegging kommer imidlertid i mange former. Vurder hvordan datamaskinen din kjører flere oppgaver på samme tid. Uten en planleggingsalgoritme kan operativsystemet gripe alle tilgjengelige ressurser og holde søknaden din fra å gjøre noe nyttig arbeid.
Søker	Finne informasjon eller verifisere at informasjonen du ser er den informasjonen du vil ha er en viktig oppgave. Uten denne egenskapen vil mange oppgaver du utfører online ikke være mulig, for eksempel å finne nettstedet på Internett som selger den perfekte kaffekannen til kontoret.
Sortering	Bestemme rekkefølgen for å presentere informasjon er viktig fordi de fleste i dag lider av overbelastning av informasjon, og trenger å redusere dataene. Tenk deg å gå til Amazon, finne mer enn tusen kaffekasser til salgs, og likevel ikke kunne sortere dem etter pris eller mest positiv vurdering. Videre krever mange komplekse algoritmer data i riktig rekkefølge for å fungere pålitelig, så sortering er en viktig forutsetning for å løse flere problemer.
Transformere	Konvertere en slags data til en annen type data er avgjørende for å forstå og bruke dataene effektivt. For eksempel kan du forstå imperiale vekter helt fint, men alle kildene dine bruker metriske systemet. Konvertering mellom de to systemene hjelper deg med å forstå dataene. På samme måte konverterer Fast Fourier Transform (FFT) signaler mellom tidsdomene og frekvensdomene, slik at ting som din WiFi-ruter kan fungere.

Håndtere algoritmkompleksitet

Du vet allerede at algoritmer er komplekse. Men du må vite hvor komplisert en algoritme er fordi jo mer komplisert man er, desto lengre tid det tar å løpe. Følgende tabell hjelper deg å forstå de ulike nivåene av kompleksitet som presenteres i rekkefølge av kjøretid (fra raskeste til langsommere).

Kompleksitet	Beskrivelse
Konstant kompleksitet O (1)	Gir en uvanlig utførelsestid, uansett hvor mye input du oppgir. Hver inngang krever en enkelt enhet med kjøretid.
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, 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 Mergesortsort, 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 (kalt nestede 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.
Faktorisk kompleksitet O (n!)	Denne algoritmen presenterer 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 fordi 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.