Algoritmen Voor Dummy's Cheat Sheet - dummies - Persoonlijke financiën 2024

Door John Paul Mueller, Luca Massaron

Algoritmen hoeven niet saai of moeilijk te gebruiken te zijn. Sterker nog, algoritmen omringen je op vele manieren waar je misschien niet over hebt nagedacht en je gebruikt ze elke dag om belangrijke taken uit te voeren. U moet echter algoritmen kunnen gebruiken zonder een wiskundige te hoeven worden.

Met programmeertalen kunt u de stappen beschrijven die worden gebruikt om een algoritme te maken. Sommige talen zijn beter dan anderen in het uitvoeren van deze taak op een manier die mensen kunnen begrijpen zonder computerwetenschappers te worden. Python maakt het gebruik van algoritmen eenvoudiger omdat het wordt geleverd met veel ingebouwde en uitgebreide ondersteuning (door het gebruik van pakketten, gegevenssets en andere bronnen). Deze Cheat Sheet helpt u toegang te krijgen tot de meest gebruikelijke tips om uw algoritmen snel en gemakkelijk te gebruiken.

Lokaliseren van het algoritme dat u nodig hebt

De volgende tabel beschrijft algoritmen en algoritmetypen die u mogelijk handig vindt voor verschillende soorten gegevensanalyses. (U kunt discussies van al deze algoritmen vinden in Algorithms For Dummies.)

Algoritme	Beschrijving	Nuttige link
A * Zoeken	Het algoritme volgt de kosten van knooppunten terwijl het deze met behulp van de vergelijking: f (n) = g (n) + h (n), waarbij: n is het knooppunt-ID g (n) zijn de kosten van het bereiken van het knooppunt tot nu toe h (n) zijn de geschatte kosten om de doel vanaf het knooppunt f (n) is de geschatte kosten van het pad van n naar het doel Het idee is om eerst de meest veelbelovende paden te doorzoeken en dure paden te vermijden.	Standford. edu
Evenwichtige boom	Een soort boom die door middel van reorganisatie een evenwichtige structuur behoudt, zodat deze kortere toegangstijden biedt. Het aantal elementen aan de linkerkant verschilt maximaal één van de cijfers aan de rechterkant.	Webdocs
Bidirectioneel zoeken	Deze techniek zoekt gelijktijdig van het basisknooppunt en het doelknooppunt tot de twee zoekpaden elkaar in het midden ontmoeten. Een voordeel van deze aanpak is dat het tijd efficiënt is omdat het de oplossing sneller vindt dan vele andere brute-force oplossingen. Bovendien gebruikt het geheugen efficiënter dan andere benaderingen en vindt het altijd een oplossing. Het grootste nadeel is de complexiteit van de implementatie.	Planning. cs
Binary Tree	Dit is een type boom met knooppunten die verbinding maken met nul (bladknooppunten), één of twee (vertakkingsknooppunten) andere knooppunten. Elk knooppunt definieert de drie elementen die het moet bevatten om connectiviteit en opslaggegevens te bieden: gegevensopslag, linkse verbinding en juiste verbinding.	cs. cmu. edu
Breadth-First Search	Deze techniek begint bij het basisknooppunt, onderzoekt eerst elk van de onderliggende knooppunten en gaat dan alleen naar het volgende niveau. Het gaat niveau voor niveau verder totdat het een oplossing vindt. Het nadeel van dit algoritme is dat het elk knooppunt in het geheugen moet opslaan, wat betekent dat het een aanzienlijke hoeveelheid geheugen gebruikt voor een groot aantal knooppunten. Deze techniek kan controleren op dubbele knooppunten, wat tijd bespaart, en het komt altijd met een oplossing.	Khan Academcy
Brute Force	Dit is een techniek van probleemoplossing waarin iemand elke mogelijke oplossing uitprobeert, op zoek naar de beste probleemoplossing. Brute-force technieken garanderen een best passende oplossing wanneer er een bestaat, maar zijn zo tijdrovend om te implementeren dat de meeste mensen ze vermijden.	Igm. univ
Diepte-eerst zoeken	Deze techniek begint bij het wortelknooppunt en onderzoekt een reeks verbonden onderliggende knooppunten totdat deze een bladknooppunt bereikt. Het vordert van tak tot tak tot het een oplossing vindt. Het nadeel van dit algoritme is dat het niet op dubbele knooppunten kan controleren, wat betekent dat het meer dan één keer dezelfde knooppaden kan doorlopen. In feite vindt dit algoritme mogelijk helemaal geen oplossing, wat betekent dat u een afkappunt moet definiëren om te voorkomen dat het algoritme oneindig zoekt. Een voordeel van deze aanpak is dat het geheugen efficiënt is.	Hacker Earth
Divide and Conquer	Dit is een techniek van probleemoplossing waarbij het probleem wordt opgesplitst in de kleinst mogelijke stukjes en opgelost met behulp van de eenvoudigste benadering mogelijk. Deze techniek bespaart veel tijd en middelen in vergelijking met andere benaderingen, zoals brute kracht. Het garandeert echter niet altijd een optimaal resultaat.	Khan Academy
Dijikstra	Dit is een algoritme dat wordt gebruikt om het kortste pad te vinden in een gerichte, gewogen grafiek (met positieve gewichten).	Geeks voor geeks
Grafiek	Een grafiek is een soort boomextensie. Net als bij bomen, hebt u knooppunten die met elkaar verbonden zijn om relaties te creëren. In tegenstelling tot binaire bomen kan een grafiek echter meer dan een of twee verbindingen hebben. Grafiekknooppunten hebben vaak een veelvoud aan verbindingen. U ziet grafieken die worden gebruikt in plaatsen zoals kaarten voor GPS en allerlei andere plaatsen waarvoor de top-down benadering van een boom niet zal werken.	Tutorials
Greedy Algorithms	De techniek om problemen op te lossen waarbij de oplossing vertrouwt op het beste antwoord voor elke stap van het probleemoplossingsproces. Greedy-algoritmen doen over het algemeen twee aannames: Het maken van een optimale keuze bij een bepaalde stap is mogelijk. Door bij elke stap de optimale selectie te kiezen, is het vinden van een optimale oplossing voor het algehele probleem mogelijk.	Zelfstudies
Greedy Best-First Search (BFS)	Het algoritme kiest altijd het pad dat het dichtst bij het doel ligt met behulp van de vergelijking: f (n) = h (n). Dit specifieke algoritme kan vrij snel oplossingen vinden, maar het kan ook vastlopen in loops, dus veel mensen beschouwen het niet als een optimale benadering om een oplossing te vinden.	Centurion2
hashing	Dit is een methode om de locatie van een bepaald gegevensitem in de datastructuur te voorspellen (wat die structuur ook mag zijn) voordat u ernaar op zoek gaat. Deze benadering is afhankelijk van het gebruik van sleutels die in een index zijn geplaatst. Een hashfunctie verandert de sleutel in een numerieke waarde die door het algoritme in een hashtabel wordt geplaatst. Een hashtabel biedt de mogelijkheid om een index te maken die verwijst naar elementen in een gegevensstructuur, zodat een algoritme de locatie van de gegevens gemakkelijk kan voorspellen.	Tutorials
Heap	Dit is een geavanceerde structuur waarmee gegevens kunnen worden ingevoegd in de boomstructuur. Het gebruik van gegevensinvoer maakt het sorteren sneller. Je kunt deze bomen verder classificeren als max. Heaps en min-heaps, afhankelijk van de mogelijkheid van de boom om onmiddellijk de maximale of minimale waarde in de boom te geven.	Tutorials
Heuristieken	Dit is een techniek van probleemoplossing die berust op zelfontdekking en voldoende nuttige resultaten oplevert (niet noodzakelijkerwijs optimaal, maar goed genoeg) om een probleem goed genoeg aan te pakken zodat een betere oplossing niet mogelijk is. ' t noodzakelijk. Zelfontdekking is het proces waarbij het algoritme je een potentieel bruikbaar pad naar een oplossing laat zien (maar je moet nog steeds rekenen op menselijke intuïtie en begrip om te weten of de oplossing de juiste is).	Northwest. edu
MapReduce	Dit is een raamwerk om algoritmen te laten werken door parallel berekeningen te gebruiken (met behulp van meerdere computers die met elkaar zijn verbonden in een netwerk), waardoor algoritmen hun oplossingen sneller kunnen voltooien.	Hadoop Apache
Mergesort	Mergesort is een op algemene doeleinden gebaseerde, vergelijkingsmethode voor het sorteren van gegevens. Het hangt af van een verdeel-en-heers aanpak om zijn taak uit te voeren.	Geeks voor geeks
Nash Equilibrium	Dit is een speltheorie waarin de andere spelers de evenwichtsstrategie kennen voor de andere spelers, dus niemand heeft er iets aan te winnen door zijn of haar persoonlijke strategie te veranderen. Deze theorie ziet gebruik in elke vijandige situatie waarin de speler rekening moet houden met de beslissingen die door alle andere spelers worden genomen om het spel te winnen.	Khan Academy
PageRank	PageRank is een algoritme voor het meten van het belang van een knooppunt in een grafiek. Dit algoritme vormt de basis van de kernalgoritmen van Google om relevante zoekopdrachten naar gebruikers te sturen.	Princeton. edu
Pure Heuristic Search	Dit algoritme breidt nodes uit in volgorde van hun kosten. Het onderhoudt twee lijsten. De gesloten lijst bevat de knooppunten die al zijn onderzocht en de open lijst bevat de knooppunten die nog moeten worden onderzocht. In elke iteratie breidt het algoritme het knooppunt uit met de laagst mogelijke kosten. Alle onderliggende knooppunten worden in de gesloten lijst geplaatst en de kosten van de afzonderlijke kindknooppunten worden berekend. Het algoritme stuurt de onderliggende knooppunten met lage kosten terug naar de open lijst en verwijdert de onderliggende knooppunten met hoge kosten. Bijgevolg voert het algoritme een intelligente, op kosten gebaseerde zoekopdracht naar de oplossing uit.	World of Computing
Quicksort	Dit is een sorteerstrategie voor algemeen gebruik die is gebaseerd op het partitioneren van arrays van gegevens in kleinere arrays.Het hangt af van een verdeel-en-heers aanpak om zijn taak uit te voeren.	Zelfstudies
Ongebalanceerde structuur	Dit is een structuur die nieuwe gegevensitems plaatst waar nodig in de structuur zonder rekening te houden met de balans. Deze methode voor het toevoegen van items maakt het bouwen van de boom sneller maar vermindert de toegangssnelheid bij het zoeken of sorteren.	Quora

Differentiërende algoritmen van andere wiskundige structuren

Als je zoals de meeste mensen bent, merk je vaak dat je je hoofd krabt als het gaat om wiskundige structuren, omdat niemand weet hoe de termen correct moeten worden gebruikt. Het is alsof mensen opzettelijk proberen dingen moeilijk te maken! Wat is tenslotte een vergelijking en waarom is het anders dan een algoritme? Nou, wees niet bang: de volgende tabel biedt de definitieve gids voor wiskundige structuren die je misschien tegenkomt, maar waarover je niet durft te vragen.

Structuur	Beschrijving
Vergelijking	Getallen en symbolen die, als ze als geheel worden beschouwd, overeenkomen met een specifieke waarde. Een vergelijking bevat altijd een gelijkteken, zodat u weet dat de cijfers en symbolen de specifieke waarde aan de andere kant van het gelijkteken vertegenwoordigen. Vergelijkingen bevatten over het algemeen variabele informatie gepresenteerd als een symbool, maar ze zijn niet verplicht om variabelen te gebruiken.
Formule	Een combinatie van cijfers en symbolen die worden gebruikt om informatie of ideeën uit te drukken. Een formule presenteert normaal gesproken wiskundige of logische concepten, zoals het definiëren van de grootste gemene deler (GCD) van twee gehele getallen (de video op Khan Academy vertelt hoe dit werkt). Over het algemeen geeft een formule de relatie weer tussen twee of meer variabelen. De meeste mensen zien een formule als een speciaal soort vergelijking.
Algoritme	Een reeks stappen die is gebruikt om een probleem op te lossen. De sequentie biedt een unieke methode om een probleem aan te pakken door een bepaalde oplossing te bieden. Een algoritme hoeft geen wiskundige of logische concepten te vertegenwoordigen, ook al vallen de presentaties in dit boek vaak in die categorie omdat mensen op deze manier meestal algoritmen gebruiken. Sommige speciale formules zijn ook algoritmen, zoals de kwadratische formule. Voor een proces dat een algoritme vertegenwoordigt, moet dit het volgende zijn: Eindig: Het algoritme moet het probleem uiteindelijk oplossen. Goed gedefinieerd: De reeks stappen moet nauwkeurig zijn en de huidige stappen zijn begrijpelijk, vooral door computers, die een bruikbaar algoritme moeten kunnen maken. Effectief: Een algoritme moet alle problemen oplossen waarvoor iemand het heeft gedefinieerd. Een algoritme moet altijd het probleem oplossen dat het moet oplossen. Hoewel u op een aantal fouten moet anticiperen, is de incidentie van falen zeldzaam en treedt deze alleen op in situaties die acceptabel zijn voor het beoogde gebruik van het algoritme.

Verbluffende manieren om algoritmen te gebruiken

Mensen gebruiken de algoritmen altijd. Bijvoorbeeld: toast maken is een voorbeeld van een algoritme, zoals uitgelegd in deze blogpost. Toast maken is geen geweldig algoritme, maar die in de volgende tabel, die een computer gebruiken om taken uit te voeren, zijn.

Taak	Waarom het geweldig is
Cryptografie	Gegevens veilig houden, is een voortdurende strijd met hackers die voortdurend gegevensbronnen aanvallen. Met algoritmen kunt u gegevens analyseren, in een andere vorm plaatsen en deze later in de oorspronkelijke vorm terugbrengen.
Grafiekanalyse	De mogelijkheid om te beslissen over de kortste lijn tussen twee punten vindt allerlei soorten gebruik. In een routeringsprobleem kan uw GPS bijvoorbeeld niet werken zonder dit specifieke algoritme, omdat het u nooit langs stadsstraten zou kunnen leiden met de kortste route van punt A naar punt B.
Pseudorandoomgeneratie	Stel u voor dat u games speelt dat veranderde nooit. Je begint op dezelfde plaats en voert dezelfde stappen uit op dezelfde manier elke keer dat je speelt. Saai! Zonder de mogelijkheid om schijnbaar willekeurige getallen te genereren, worden veel computertaken zinloos of onmogelijk.
Planning	Het gebruik van bronnen eerlijk maken voor alle betrokkenen is een andere manier waarop algoritmen hun aanwezigheid op een grote manier kenbaar maken. Timingverlichting op kruispunten zijn bijvoorbeeld niet langer eenvoudige apparaten die de seconden aftellen tussen lichtveranderingen. Moderne apparaten houden rekening met allerlei problemen, zoals het tijdstip, de weersomstandigheden en de verkeersstroom. Planning is echter in vele vormen mogelijk. Overweeg hoe uw computer meerdere taken tegelijkertijd uitvoert. Zonder een planningsalgoritme zou het besturingssysteem alle beschikbare bronnen kunnen grijpen en voorkomen dat uw toepassing nuttig werk doet.
Zoeken	Informatie zoeken of controleren of de informatie die u ziet de gewenste informatie is, is een essentiële taak. Zonder deze mogelijkheid zijn veel taken die u online uitvoert niet mogelijk, zoals het vinden van de website op internet die de perfecte koffiepot voor uw kantoor verkoopt.
Sorteren	Het bepalen van de volgorde waarin informatie moet worden gepresenteerd, is belangrijk omdat de meeste mensen tegenwoordig last hebben van overbelasting van informatie en de gegevensstroom moeten verminderen. Stel je voor dat je naar Amazon gaat, meer dan duizend koffiepotten te koop vindt en toch niet in staat bent om ze te sorteren op prijs of meest positieve beoordeling. Bovendien vereisen veel complexe algoritmen dat gegevens in de juiste volgorde betrouwbaar werken, dus sorteren is een belangrijke vereiste voor het oplossen van meer problemen.
Transformeren	Het omzetten van één soort gegevens in een ander soort gegevens is van cruciaal belang voor een goed begrip en gebruik van de gegevens. U zou imperiale gewichten bijvoorbeeld prima kunnen begrijpen, maar al uw bronnen gebruiken het metrische systeem. Het converteren tussen de twee systemen helpt u de gegevens te begrijpen. Op dezelfde manier converteert de Fast Fourier-transformatie (FFT) signalen tussen het tijdsdomein en het frequentiedomein, waardoor dingen zoals uw WiFi-router kunnen werken.

Omgaan met complexiteit van algoritmen

U weet al dat algoritmen complex zijn. U moet echter weten hoe ingewikkeld een algoritme is, want hoe ingewikkelder een algoritme is, hoe langer het duurt om het uit te voeren. De volgende tabel helpt u de verschillende complexiteitsniveaus te begrijpen die worden gepresenteerd in volgorde van looptijd (van snelste tot langzaamste).

Complexiteit	Beschrijving
Constante complexiteit O (1)	Biedt een onveranderlijke uitvoeringstijd, ongeacht de hoeveelheid invoer die u levert. Elke ingang vereist een enkele uitvoeringstermijn.
Logaritmische complexiteit O (log n)	Het aantal bewerkingen groeit langzamer dan de invoer, waardoor het algoritme minder efficiënt is met kleine invoer en efficiënter met grotere. Een typisch algoritme van deze klasse is de binaire zoekopdracht.
Lineaire complexiteit O (n)	De bewerkingen nemen toe met de invoer in een verhouding van 1: 1. Een typisch algoritme is iteratie, wanneer u de invoer eenmaal scant en een bewerking toepast op elk element ervan.
Lineairithmische complexiteit O (n log n)	Complexiteit is een mix tussen logaritmische en lineaire complexiteit. Het is typerend voor enkele slimme algoritmen die worden gebruikt om gegevens te ordenen, zoals Mergesort, Heapsort en Quicksort.
Kwadratische complexiteit O (n ² )	Bewerkingen groeien als een vierkant van het aantal ingangen. Wanneer je één iteratie hebt binnen een andere iteratie (geneste iteraties in de informatica genoemd), heb je een kwadratische complexiteit. U hebt bijvoorbeeld een lijst met namen en om de meest vergelijkbare te vinden, vergelijkt u elke naam met alle andere namen. Sommige minder efficiënte ordeningsalgoritmen vertonen een dergelijke complexiteit: bubbelsortering, selectiesortering en invoegtypen. Dit niveau van complexiteit betekent dat uw algoritmen uren of zelfs dagen kunnen duren voordat ze een oplossing bereiken.
Kubieke complexiteit O (n ³ )	Bewerkingen groeien zelfs sneller dan kwadratische complexiteit omdat u nu meerdere geneste iteraties hebt. Wanneer een algoritme deze volgorde van complexiteit heeft en u een bescheiden hoeveelheid gegevens (100, 000 elementen) moet verwerken, kan uw algoritme jaren duren. Wanneer u een aantal bewerkingen hebt die de input zijn, is het gebruikelijk om te verwijzen naar het algoritme dat wordt uitgevoerd in polynomiale tijd.
Exponentiële complexiteit O (2 ⁿ )	Het algoritme neemt tweemaal het aantal vorige bewerkingen voor elk toegevoegd nieuw element. Wanneer een algoritme deze complexiteit heeft, kunnen zelfs kleine problemen voor altijd duren. Veel algoritmen die uitputtend zoeken, hebben een exponentiële complexiteit. Het klassieke voorbeeld voor dit niveau van complexiteit is echter de berekening van Fibonacci-getallen.
Factorische complexiteit O (n!)	Dit algoritme biedt een echte nachtmerrie van complexiteit vanwege het grote aantal mogelijke combinaties tussen de elementen. Stelt u zich eens voor: als uw invoer 100 objecten is en een bewerking op uw computer 10 ^-6 seconden kost (een redelijke snelheid voor elke computer tegenwoordig), heeft u ongeveer 10 ¹⁴⁰ jaar nodig om de taak met succes te voltooien (een onmogelijke hoeveelheid tijd omdat de ouderdom van het universum wordt geschat op 10 ₁₄ jaar). Een beroemd facetcomplexiteitsprobleem is het reizende verkoopprobleem, waarbij een verkoper de kortste route moet vinden om vele steden te bezoeken en terug te komen naar de startstad.