Hoi! De les van vandaag zal iets anders zijn dan de rest. Het zal verschillen doordat het slechts indirect gerelateerd is aan Java. Dat gezegd hebbende, dit onderwerp is erg belangrijk voor elke programmeur. We gaan het hebben over algoritmen . Wat is een algoritme? In eenvoudige bewoordingen is het een reeks acties die moeten worden voltooid om een gewenst resultaat te bereiken . We gebruiken algoritmen vaak in het dagelijks leven. Elke ochtend heb je bijvoorbeeld een specifieke taak: naar school of werk gaan, en tegelijkertijd zijn:
- Gekleed
- Schoon
- gevoed
- Wakker worden met een wekker.
- Neem een douche en was jezelf.
- Maak ontbijt en wat koffie of thee.
- Eten.
- Als je je kleren de vorige avond niet hebt gestreken, strijk ze dan.
- Aankleden.
- Verlaat het huis.
- Koop of download de editie uit 1961 van Webster's Third New International Dictionary.
- Vind elke naam uit onze lijst in dit woordenboek.
- Schrijf op een vel papier de pagina van het woordenboek waarop de naam staat.
- Gebruik de stukjes papier om de namen te sorteren.
for
lus die deze taak uitvoert
int[] numbers = new int[100];
// ...fill the array with numbers
for (int i: numbers) {
System.out.println(i);
}
Wat is de complexiteit van dit algoritme? Lineair, dwz O(n). Het aantal acties dat het programma moet uitvoeren, hangt af van het aantal getallen dat eraan wordt doorgegeven. Als er 100 getallen in de array zijn, zijn er 100 acties (statements om strings op het scherm weer te geven). Als er 10.000 nummers in de array staan, moeten er 10.000 acties worden uitgevoerd. Kan ons algoritme op enigerlei wijze worden verbeterd? Nee. Wat er ook gebeurt, we zullen N door de array moeten laten gaan en N statements moeten uitvoeren om strings op de console weer te geven. Overweeg een ander voorbeeld.
public static void main(String[] args) {
LinkedList<Integer> numbers = new LinkedList<>();
numbers.add(0, 20202);
numbers.add(0, 123);
numbers.add(0, 8283);
}
We hebben een lege ruimte LinkedList
waarin we verschillende nummers invoegen. We moeten de algoritmische complexiteit evalueren van het invoegen van een enkel getal in LinkedList
ons voorbeeld, en hoe dit afhangt van het aantal elementen in de lijst. Het antwoord is O(1), dwz constante complexiteit . Waarom? Merk op dat we elk nummer aan het begin van de lijst invoegen. Bovendien zult u zich herinneren dat wanneer u een getal invoegt in een LinkedList
, de elementen nergens heen bewegen. De links (of referenties) zijn bijgewerkt (als je bent vergeten hoe LinkedList werkt, bekijk dan een van onze oude lessen ). Als het eerste nummer in onze lijst is x
, en we voegen het nummer y vooraan in de lijst in, dan hoeven we alleen maar dit te doen:
x.previous = y;
y.previous = null;
y.next = x;
Wanneer we de links updaten, maakt het ons niet uit hoeveel nummers er al in de staanLinkedList
, of het nu een of een miljard is. De complexiteit van het algoritme is constant, namelijk O(1).
GO TO FULL VERSION