Video: Yves Morieux: As work gets more complex, 6 rules to simplify 2024
Deel van Algorithms For Dummies Cheat Sheet
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 2 ) | 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 3 ) | 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 n ) | 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 140 jaar nodig om de taak met succes te voltooien (een onmogelijke hoeveelheid tijd omdat de ouderdom van het universum wordt geschat op 10 14 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. |
