Hej! Dagens lektion vil være lidt anderledes end resten. Det vil adskille sig ved, at det kun er indirekte relateret til Java. Når det er sagt, er dette emne meget vigtigt for enhver programmør. Vi skal tale om algoritmer . Hvad er en algoritme? Enkelt sagt er det en række handlinger, der skal udføres for at opnå et ønsket resultat . Vi bruger ofte algoritmer i hverdagen. For eksempel har du hver morgen en bestemt opgave: gå i skole eller arbejde, og samtidig være:
- Påklædt
- Ren
- Fed
- Vågn op ved hjælp af et vækkeur.
- Tag et brusebad og vask dig selv.
- Lav morgenmad og noget kaffe eller te.
- Spise.
- Hvis du ikke har stryget dit tøj den foregående aften, så stryg det.
- Få tøj på.
- Forlad huset.
- Køb eller download 1961-udgaven af Webster's Third New International Dictionary.
- Find hvert navn fra vores liste i denne ordbog.
- På et stykke papir skal du skrive den side i ordbogen, hvor navnet står.
- Brug stykkerne papir til at sortere navnene.
for
loop, der udfører denne opgave
int[] numbers = new int[100];
// ...fill the array with numbers
for (int i: numbers) {
System.out.println(i);
}
Hvad er kompleksiteten af denne algoritme? Lineær, dvs. O(n). Antallet af handlinger, som programmet skal udføre, afhænger af, hvor mange numre, der sendes til det. Hvis der er 100 tal i arrayet, vil der være 100 handlinger (udsagn til at vise strenge på skærmen). Hvis der er 10.000 numre i arrayet, skal der udføres 10.000 handlinger. Kan vores algoritme forbedres på nogen måde? Nej. Lige meget hvad, bliver vi nødt til at lave N passerer gennem arrayet og udføre N sætninger for at vise strenge på konsollen. Overvej et andet eksempel.
public static void main(String[] args) {
LinkedList<Integer> numbers = new LinkedList<>();
numbers.add(0, 20202);
numbers.add(0, 123);
numbers.add(0, 8283);
}
Vi har en tom LinkedList
, hvor vi indsætter flere tal. Vi er nødt til at evaluere den algoritmiske kompleksitet ved at indsætte et enkelt tal i LinkedList
vores eksempel, og hvordan det afhænger af antallet af elementer på listen. Svaret er O(1), altså konstant kompleksitet . Hvorfor? Bemærk, at vi indsætter hvert tal i begyndelsen af listen. Derudover vil du huske, at når du indsætter et tal i en LinkedList
, flytter elementerne sig ingen steder. Linkene (eller referencerne) er opdateret (hvis du har glemt, hvordan LinkedList fungerer, så kig på en af vores gamle lektioner ). Hvis det første tal på vores liste er x
, og vi indsætter tallet y foran på listen, skal vi kun gøre dette:
x.previous = y;
y.previous = null;
y.next = x;
Når vi opdaterer linkene, er vi ligeglade med, hvor mange tal der allerede er iLinkedList
, om en eller en milliard. Algoritmens kompleksitet er konstant, altså O(1).