Share
Ik neem aan dat je een computerprogrammeur bent. Misschien ben je een nieuwe student van de informatica of misschien ben je een ervaren software-ingenieur. Ongeacht waar je bent in dat spectrum, algoritmen en datastructuren zijn van belang. Niet alleen als theoretische concepten, maar als bouwstenen die worden gebruikt om oplossingen te vinden voor zakelijke problemen.
Natuurlijk weet u misschien hoe u de C # moet gebruiken Lijst of stack klas, maar begrijp je wat er gebeurt onder de dekens? Zo niet, maakt u echt de beste beslissingen over welke algoritmen en gegevensstructuren u gebruikt?
Betekenisvol begrip van algoritmen en datastructuren begint met het hebben van een manier om hun relatieve kosten tot uitdrukking te brengen en te vergelijken.
Wanneer we het hebben over het meten van de kosten of complexiteit van een algoritme, hebben we het eigenlijk over het uitvoeren van een analyse van het algoritme wanneer de invoersets erg groot zijn. Analyse van wat er gebeurt als het aantal inputs erg groot wordt, wordt asymptotische analyse genoemd. Hoe verandert de complexiteit van het algoritme bij toepassing op tien of duizend of tien miljoen items? Als een algoritme in vijf milliseconden met duizend items wordt uitgevoerd, wat kunnen we dan zeggen over wat er gebeurt als het met een miljoen wordt uitgevoerd? Gaat het vijf seconden of vijf jaar duren? Zou je dit liever niet voor je klant uitzoeken??
Dit spul is belangrijk!
Snelheid van groei beschrijft hoe de complexiteit van een algoritme verandert naarmate de invoer groter wordt. Dit wordt meestal weergegeven met de Big-O-notatie. Big-O notatie gebruikt een hoofdletter O ("volgorde") en een formule die de complexiteit van het algoritme uitdrukt. De formule kan een variabele n hebben, die de grootte van de invoer vertegenwoordigt. Hier volgen enkele veelgebruikte bestelfuncties die we in dit boek zullen zien, maar deze lijst is zeker niet compleet.
Een O (1) -algoritme is een algoritme waarvan de complexiteit constant is, ongeacht hoe groot de invoergrootte is. De "1" betekent niet dat er maar één handeling is of dat de bewerking een kleine hoeveelheid tijd kost. Het kan een microseconde duren of het kan een uur duren. Het punt is dat de grootte van de invoer geen invloed heeft op de tijd die de operatie in beslag neemt.
openbare int GetCount (int [] items) return items.Length;
Een O (n) -algoritme is een algoritme waarvan de complexiteit lineair groeit met de grootte van de invoer. Het is redelijk om te verwachten dat als een ingangsgrootte van één vijf milliseconden in beslag neemt, een invoer met duizend items vijf seconden in beslag zal nemen.
U kunt vaak een O (n) -algoritme herkennen door te zoeken naar een lusmechanisme dat toegang biedt tot elk lid.
openbare lange GetSum (int [] items) lange som = 0; foreach (int i in items) sum + = i; teruggave som;
Een O (log n) -algoritme is een algoritme waarvan de complexiteit logaritmisch is met de omvang ervan. Veel algoritmen voor verdelen en veroveren vallen in deze emmer. De binaire zoekboom bevat methode implementeert een O (log n) algoritme.
Een linearitmisch algoritme, of loglineair, is een algoritme met een complexiteit van O (n log n). Sommige verdeel en heers algoritmen vallen in deze emmer. We zullen twee voorbeelden zien wanneer we naar merge sort en quick sort kijken.
Een O (n ^ 2) algoritme is een algoritme waarvan de complexiteit kwadratisch is ten opzichte van de grootte. Hoewel niet altijd te vermijden, is het gebruik van een kwadratisch algoritme een mogelijk teken dat u uw algoritme of datastructuurkeuze opnieuw moet overwegen. Kwadratische algoritmen schalen niet goed naarmate de invoer groter wordt. Een array met 1000 gehele getallen zou bijvoorbeeld 1.000.000 bewerkingen vereisen. Een invoer met een miljoen items zou één biljoen (1.000.000.000.000) bewerkingen kosten. Om dit in perspectief te plaatsen, duurt het bijna 32 jaar voordat een bewerking één milliseconde in beslag neemt. Een algoritme O (n ^ 2) dat een invoer van één miljoen items ontvangt, duurt bijna 32 jaar. Dat algoritme 100 keer sneller maken zou nog steeds 84 dagen duren.
We zullen een voorbeeld van een kwadratisch algoritme zien als we bellen met bellen bekijken.
Als we zeggen dat een algoritme O (n) is, wat zeggen we dan eigenlijk? Zeggen we dat het algoritme gemiddeld O (n) is? Of beschrijven we het beste of slechtste scenario?
We bedoelen meestal het worstcasescenario tenzij het gewone en het slechtste geval totaal anders zijn. We zullen bijvoorbeeld voorbeelden in dit boek zien waarbij een algoritme gemiddeld O (1) is, maar wordt periodiek O (n) (zie ArrayList.Add). In deze gevallen zal ik het algoritme gemiddeld als O (1) beschrijven en vervolgens uitleggen wanneer de complexiteit verandert.
Het belangrijkste punt is dat het zeggen van O (n) niet betekent dat het altijd n operaties zijn. Het is misschien minder, maar het zou niet meer moeten zijn.
Wanneer we algoritmen en gegevensstructuren meten, hebben we meestal het over een van de twee dingen: de hoeveelheid tijd die de operatie in beslag neemt (operationele complexiteit), of de hoeveelheid bronnen (geheugen) die een algoritme gebruikt (resourcecomplexiteit).
Een algoritme dat tien keer sneller werkt maar tien keer zoveel geheugen gebruikt, kan perfect acceptabel zijn in een serveromgeving met enorme hoeveelheden beschikbaar geheugen, maar is mogelijk niet geschikt in een ingesloten omgeving waar het beschikbare geheugen ernstig wordt beperkt.
In dit boek zal ik me vooral richten op operationele complexiteit, maar in de sectie Sorteeralgoritmen zullen we enkele voorbeelden van resource-complexiteit zien.
Enkele specifieke voorbeelden van dingen die we kunnen meten zijn onder meer:
In de context van de bewerking die wordt uitgevoerd, wordt meestal aangegeven welk type meting wordt uitgevoerd.
Wanneer we bijvoorbeeld de complexiteit bespreken van een algoritme dat zoekt naar een item in een datastructuur, hebben we vrijwel zeker het over vergelijkende bewerkingen. Zoeken is over het algemeen een alleen-lezen-bewerking, dus het is niet nodig om opdrachten uit te voeren of geheugen toe te wijzen.
Als we het echter hebben over het sorteren van gegevens, kan het logisch zijn om aan te nemen dat we het kunnen hebben over vergelijkingen, toewijzingen of toewijzingen. In gevallen waar er ambiguïteit kan zijn, zal ik aangeven naar welk type meting de complexiteit feitelijk verwijst.
Hiermee is het eerste deel over algoritmen en gegevensstructuren voltooid. Vervolgens gaan we verder met de gelinkte lijst.
Accentsconagua