Algoritmer For Dummies Cheat Sheet - dummies - Personlig finansiering 2024

Af John Paul Mueller, Luca Massaron

Algoritmer behøver ikke at være kedelige eller svære at bruge. Faktisk omgiver algoritmer dig på mange måder, som du måske ikke har tænkt på, og du bruger dem hver dag til at udføre vigtige opgaver. Du skal dog være i stand til at bruge algoritmer uden at blive matematiker.

Programmeringssprog giver dig mulighed for at beskrive de trin, der bruges til at oprette en algoritme. Nogle sprog er bedre end andre til at udføre denne opgave på en måde, som folk kan forstå uden at blive computerforskere. Python gør brug af algoritmer lettere, fordi det kommer med en masse indbygget og udvidet support (gennem brug af pakker, datasæt og andre ressourcer). Dette Cheat Sheet hjælper dig med at få adgang til de mest nødvendige tips til at gøre din brug af algoritmer hurtig og nem.

Find algoritmen, du har brug for

I nedenstående tabel beskrives algoritmer og algoritmtyper, som du måske finder nyttige til forskellige typer dataanalyse. (Du kan finde diskussioner af alle disse algoritmer i algoritmer til dummier.)

Algoritme	Beskrivelse	Nyttige link
A * Søgning	Algoritmen sporer omkostningerne til noder, da den udforsker dem ved hjælp af ligning: f (n) = g (n) + h (n), hvor: n er knudepunktsidentifikatoren g (n) kostprisen for at nå knuden indtil nu h (n) er den anslåede pris for at nå frem til Målet fra knuden f (n) er den anslåede pris for stien fra n til målet Ideen er at søge de mest lovende stier først og undgå dyre stier.	Standford. edu
Balanced Tree	En slags træ, der opretholder en afbalanceret struktur gennem omorganisering, så den kan give reducerede adgangstider. Antallet af elementer på venstre side adskiller sig fra tallet på højre side af højst.	Webdocs
Tovejsøgning	Denne teknik søger samtidigt fra rodknuden og målnoden, indtil de to søgestier møder i midten. En fordel ved denne tilgang er, at den er tidseffektiv, fordi den finder løsningen hurtigere end mange andre brute-force løsninger. Derudover bruger hukommelsen mere effektivt end andre tilgange og finder altid en løsning. Den største ulempe er implementeringens kompleksitet.	Planlægning. cs
Binærtræ	Dette er en type træ, der indeholder knuder, der forbinder til nul (bladknudepunkter), en eller to (grenknudepunkter) andre knuder. Hver node definerer de tre elementer, som den skal indeholde for at give forbindelse og gemme data: datalagring, venstre tilslutning og højre forbindelse.	cs. CMU. edu
Breadth-First Search	Denne teknik begynder ved rodknuden, undersøger hver af børnelyderne først og går først derefter ned til næste niveau. Den skrider frem efter niveau, indtil den finder en løsning. Ulempen ved denne algoritme er, at den skal lagre hver node i hukommelsen, hvilket betyder at den bruger en betydelig mængde hukommelse til et stort antal noder. Denne teknik kan tjekke for dubletter, hvilket sparer tid, og det kommer altid op med en løsning.	Khan Academcy
Brute Force	Dette er en teknik til problemløsning, hvor nogen forsøger enhver mulig løsning og søger den bedste problemløsning. Brute-force teknikker garanterer en bedst egnet løsning, når man eksisterer, men er så tidskrævende at implementere, at de fleste mennesker undgår dem.	IgM. univ
Dybde-første søgning	Denne teknik begynder ved rodknuden og udforsker et sæt tilsluttede børne noder, indtil det når et bladknude. Det skrider frem til filialen, indtil den finder en løsning. Ulempen ved denne algoritme er, at den ikke kan tjekke for dubletter, hvilket betyder, at den kan krydse de samme nodeveje mere end én gang. Faktisk kan denne algoritme slet ikke finde en løsning, hvilket betyder at du skal definere et cutoff-punkt for at holde algoritmen fra at søge uendeligt. En fordel ved denne tilgang er, at den er hukommelseseffektiv.	Hacker Earth
Divide and Conquer	Dette er en problemløsningsproces, hvor problemet er opdelt i de mindste mulige stykker og løst ved hjælp af den enkleste tilgang. Denne teknik sparer betydelig tid og ressourcer i forhold til andre tilgange, såsom brute force. Det garanterer dog ikke altid et bedst egnet resultat.	Khan Academy
Dijikstra	Dette er en algoritme, der bruges til at finde den korteste vej i en rettet vægtet grafik (med positiv vægt).	Geeks for Geeks
Graf	En graf er en slags træforlængelse. Som med træer har du noder, der forbinder hinanden for at skabe relationer. I modsætning til binære træer kan en graf imidlertid have mere end en eller to forbindelser. Faktisk har grafnoder ofte en lang række forbindelser. Du kan se grafer, der bruges på steder som kort til GPS og alle andre steder, hvor top-down-tilgangen til et træ ikke virker.	Tutorials
Greedy Algorithms	Thistechnique af en af problemløsning, hvor løsningen er afhængig af det bedste svar for hvert trin i problemløsningsprocessen. Greedy algoritmer gør generelt to antagelser: Det er muligt at foretage et enkelt optimalt valg ved et givet trin. Ved at vælge det optimale valg ved hvert trin, er det muligt at finde en optimal løsning til det samlede problem.	Tutorials
Greedy Best-First Search (BFS)	Algoritmen vælger altid den sti, der er tættest på målet ved hjælp af ligningen: f (n) = h n). Denne særlige algoritme kan finde løsninger ret hurtigt, men det kan også sidde fast i sløjfer, så mange anser det ikke for en optimal tilgang til at finde en løsning.	Centurion2
Hashing	Dette er en metode til at forudsige placeringen af et bestemt datapunkt i datastrukturen (uanset hvilken struktur der måtte være), før du faktisk leder efter det. Denne fremgangsmåde afhænger af brugen af nøgler, der er placeret i et indeks. En hash-funktion gør nøglen til en numerisk værdi, som algoritmen placeres i et hashbord. Et hashbord giver midlerne til at oprette et indeks, der peger på elementer i en datastruktur, således at en algoritme nemt kan forudsige placeringen af dataene.	Tutorials
Heap	Dette er et sofistikeret træ, der tillader dataindsættelse i træstrukturen. Anvendelsen af dataindsættelse gør sorteringen hurtigere. Du kan yderligere klassificere disse træer som maxhøje og minhopper afhængigt af træets evne til straks at give den maksimale eller minimale værdi i træet.	Tutorials
Heuristics	Dette er en problemløsningsproces, der er afhængig af selvopdagelse og producerer tilstrækkeligt nyttige resultater (ikke nødvendigvis optimalt, men godt nok) til at løse et problem godt nok, at en bedre løsning ikke er ' t nødvendigt. Selvopdagelse er processen med at lade algoritmen vise dig en potentielt nyttig vej til en løsning (men du skal stadig regne med menneskets intuition og forståelse for at vide, om løsningen er den rigtige).	Northwest. edu
MapReduce	Dette er en ramme for, at algoritmer kan arbejde ved hjælp af beregninger parallelt (ved hjælp af flere computere, der er tilsluttet sammen i et netværk), hvilket gør det muligt for algoritmer at færdiggøre deres løsninger hurtigere.	Hadoop Apache
Mergesort	Mergesort er en generelle sammenligningsbaseret metode til sortering af data. Det afhænger af en divide-and-conquer tilgang til at udføre sin opgave.	Geeks for Geeks
Nash Equilibrium	Dette er en spilteori, hvor de andre spillere kender ligevægtsstrategien for de andre spillere, så ingen har noget at vinde ved at ændre sin personlige strategi. Denne teori ser anvendelse i enhver fjendtlig situation, hvor spilleren skal tage højde for de beslutninger, som alle andre spillere har truffet for at vinde spillet.	Khan Academy
PageRank	PageRank er en algoritme til måling af vigtigheden af en node i en graf. Denne algoritme er kernen i Googles kernealgoritmer til at drive relevante søgninger til brugere.	Princeton. edu
Pure Heuristic Search	Denne algoritme udvider knuder i rækkefølge af deres omkostninger. Den opretholder to lister. Den lukkede liste indeholder de noder, den allerede har udforsket, og den åbne liste indeholder de noder, den endnu må undersøge. I hver iteration udvider algoritmen knuden med den lavest mulige pris. Alle dens børne noder er placeret i den lukkede liste, og de individuelle barneknutekostnader beregnes. Algoritmen sender barnetoderne med en lav pris tilbage til den åbne liste og sletter børnelodene med en høj pris. Algoritmen udfører derfor en intelligent, omkostningsbaseret søgning efter løsningen.	Verden af computing
Quicksort	Dette er en generel sorteringsstrategi baseret på partitionering af data i mindre arrays.Det afhænger af en divide-and-conquer tilgang til at udføre sin opgave.	Tutorials
Ubalanceret træ	Dette er et træ, der placerer nye dataelementer, hvor det er nødvendigt i træet uden hensyntagen til balance. Denne metode til at tilføje elementer gør bygningen hurtigere, men reducerer adgangshastigheden, når du søger eller sorterer.	Quora

Differentierende algoritmer fra andre matematiske strukturer

Hvis du er som de fleste, finder du ofte dig selv ved at skrabe dit hoved når det kommer til matematiske strukturer, fordi ingen synes at vide, hvordan man bruger vilkårene korrekt. Det er som om folk forsætligt forsøger at gøre tingene hårde! Hvad er en ligning, og hvorfor er den forskellig fra en algoritme? Nå, frygt ikke mere: Den følgende tabel giver den endelige vejledning til matematiske strukturer, som du måske støder på, men har været bange for at spørge om.

Struktur	Beskrivelse
Ligning	Tall og symboler, der, når de tages som en helhed, svarer til en bestemt værdi. En ligning indeholder altid et ligestegn, så du ved, at tallene og symbolerne repræsenterer den specifikke værdi på den anden side af ligestegnet. Ligninger indeholder generelt variable data, der præsenteres som et symbol, men de er ikke forpligtet til at bruge variabler.
Formel	En kombination af tal og symboler, der bruges til at udtrykke information eller ideer. En formel præsenterer normalt matematiske eller logiske begreber, såsom at definere den største fælles divisor (GCD) af to heltal (videoen på Khan Academy fortæller hvordan dette virker). Generelt viser en formel forholdet mellem to eller flere variabler. De fleste mennesker ser en formel som en særlig form for ligning.
Algoritme	En række trin, der bruges til at løse et problem. Sekvensen præsenterer en unik metode til at løse et problem ved at give en særlig løsning. En algoritme behøver ikke repræsentere matematiske eller logiske begreber, selvom præsentationerne i denne bog ofte falder ind i den kategori, fordi folk oftest bruger algoritmer på denne måde. Nogle specielle formler er også algoritmer, såsom den kvadratiske formel. For en proces, der repræsenterer en algoritme, skal den være følgende: Finite: Algoritmen skal til sidst løse problemet. Veldefineret: Trækkerne skal være præcise og nuværende trin, der er forståelige, især ved computere, som skal kunne skabe en brugbar algoritme. Effektiv: En algoritme skal løse alle tilfælde af det problem, som nogen definerede det. En algoritme bør altid løse det problem, den skal løse. Selvom du bør forudse nogle fejl, er forekomsten af fiasko sjælden og forekommer kun i situationer, der er acceptable for den tilsigtede algoritmebrug.

Fantastiske måder at bruge algoritmer på

Folk bruger faktisk algoritmer hele tiden. For eksempel er at lave toast et eksempel på en algoritme, som forklaret i dette blogindlæg. At lave toast er ikke en fantastisk algoritme, men dem i den følgende tabel, som bruger en computer til at udføre opgaver, er.

Opgave	Hvorfor er det forbløffende
Kryptografi	At holde data sikkert er et løbende kamp mod hackere, som konstant angriber datakilder. Algoritmer giver dig mulighed for at analysere data, sætte det i en anden form, og returnere den derefter til sin oprindelige form senere.
Grafanalyse	Muligheden for at bestemme den korteste linje mellem to punkter finder alle mulige anvendelser. I et ruteflyvning kunne din GPS muligvis ikke fungere uden denne særlige algoritme, fordi den aldrig kunne lede dig langs bygader ved hjælp af den korteste rute fra punkt A til punkt B.
Pseudorandom talegenerering	Forestil dig at spille spil der aldrig varieret. Du starter på samme sted og udfører de samme trin på samme måde hver gang du spiller. Kedelig! Uden evnen til at generere tilsyneladende tilfældige tal, bliver mange computeropgaver meningsløse eller umulige.
Planlægning	At gøre brug af ressourcer retfærdige for alle involverede er en anden måde, hvorpå algoritmer gør deres tilstedeværelse kendt på en stor måde. For eksempel er timinglys ved korsninger ikke længere enkle enheder, der tæller sekunderne mellem lysændringer. Moderne enheder overvejer alle mulige problemer, såsom tid på dagen, vejrforhold og trafikstrøm. Planlægning kommer imidlertid i mange former. Overvej hvordan din computer kører flere opgaver på samme tid. Uden en planlægningsalgoritme kan operativsystemet få fat i alle tilgængelige ressourcer og holde din ansøgning fra at gøre noget nyttigt arbejde.
Søgning	Find oplysninger eller verificere, at de oplysninger, du ser, er de ønskede oplysninger, er en vigtig opgave. Uden denne evne vil mange opgaver du udfører online ikke være mulige, f.eks. At finde hjemmesiden på internettet, der sælger den perfekte kaffekande til dit kontor.
Sortering	Bestemmelse af rækkefølgen for at præsentere oplysninger er vigtig, fordi de fleste mennesker i dag lider af overbelastning af informationer og skal reducere dataets forstyrrelse. Forestil dig at gå til Amazon, finde mere end tusind kaffekande til salg, og alligevel ikke at kunne sortere dem efter pris eller mest positive anmeldelse. Desuden kræver mange komplekse algoritmer data i den rigtige rækkefølge at arbejde pålideligt, så sortering er en vigtig forudsætning for at løse flere problemer.
Transformere	Konvertering af en slags data til en anden slags data er afgørende for at forstå og bruge dataene effektivt. For eksempel kan du forstå imperialvægte helt fint, men alle dine kilder bruger metriske systemer. Konvertering mellem de to systemer hjælper dig med at forstå dataene. På samme måde konverterer Fast Fourier Transform (FFT) signaler mellem tidsdomænet og frekvensdomænet, så ting som din WiFi-router kan fungere.

Håndtering af algoritmkompleksitet

Du ved allerede, at algoritmer er komplekse. Men du skal vide, hvor kompleks en algoritme er, fordi jo mere kompliceret en er, desto længere tid tager det at køre. Den følgende tabel hjælper dig med at forstå de forskellige niveauer af kompleksitet, der præsenteres i løbet af løbstid (fra hurtigste til langsomste).

Kompleksitet	Beskrivelse
Konstant kompleksitet O (1)	Giver en uendelig eksekveringstid, uanset hvor meget input du giver. Hver indgang kræver en enkelt enhed for udførelsestid.
Logaritmisk kompleksitet O (log n)	Antallet af operationer vokser ved en langsommere hastighed end inputen, hvilket gør algoritmen mindre effektiv med små indgange og mere effektiv med større. En typisk algoritme for denne klasse er binær søgning.
Lineær kompleksitet O (n)	Operationer vokser med input i et 1: 1 forhold. En typisk algoritme er iteration, når du scanner input en gang og bruger en operation til hvert element af det.
Linearitmisk kompleksitet O (n log n)	Kompleksitet er en blanding mellem logaritmisk og lineær kompleksitet. Det er typisk for nogle smarte algoritmer, der bruges til at bestille data, såsom Mergesortsort, Heapsort og Quicksort.
Kvadratisk kompleksitet O (n ² )	Operationer vokser som et firkant af antallet af input. Når du har en iteration inde i en anden iteration (kaldet indlejrede iterationer i datalogi), har du kvadratisk kompleksitet. For eksempel har du en liste over navne, og for at finde de mest lignende, sammenligner du hvert navn med alle de andre navne. Nogle mindre effektive ordningsalgoritmer præsenterer sådan kompleksitet: boble sortering, valg sortering og insertion sortering. Dette niveau af kompleksitet betyder, at dine algoritmer kan løbe i timer eller endda dage, før de når en løsning.
Kubisk kompleksitet O (n ³ )	Operationer vokser endnu hurtigere end kvadratisk kompleksitet, fordi nu har du flere indlejrede iterationer. Når en algoritme har denne rækkefølge af kompleksitet, og du skal behandle en beskeden mængde data (100.000 elementer), kan din algoritme løbe i årevis. Når du har en række operationer, der er en effekt af input, er det almindeligt at henvise til algoritmen som kørende i polynomisk tid.
Eksponentiel kompleksitet O (2 ⁿ )	Algoritmen tager to gange antallet af tidligere operationer for hvert nyt element tilføjet. Når en algoritme har denne kompleksitet, kan selv små problemer tage for evigt. Mange algoritmer gør udtømmende søgninger har eksponentiel kompleksitet. Det klassiske eksempel på dette niveau af kompleksitet er imidlertid beregningen af Fibonacci-tal.
Faktorisk kompleksitet O (n!)	Denne algoritme præsenterer et ægte mareridt af kompleksitet på grund af det store antal mulige kombinationer mellem elementerne. Bare forestil dig: Hvis din indgang er 100 objekter, og en operation på din computer tager 10 ^-6 sekunder (en rimelig hastighed for hver computer i dag), skal du bruge omkring 10 ¹⁴⁰ år at fuldføre opgaven med succes (en umulig tid, fordi universets alder skønnes at være 10 ₁₄ år). Et kendte factorial kompleksitetsproblem er det rejseforhandlerproblem, hvor en sælger skal finde den korteste rute for at besøge mange byer og komme tilbage til startbyen.