Hej! Dagens lektion kommer att skilja sig något från resten. Det kommer att skilja sig åt genom att det bara är indirekt relaterat till Java. Som sagt, detta ämne är mycket viktigt för alla programmerare. Vi ska prata om algoritmer . Vad är en algoritm? Enkelt uttryckt är det en sekvens av åtgärder som måste slutföras för att uppnå ett önskat resultat . Vi använder ofta algoritmer i vardagen. Till exempel, varje morgon har du en specifik uppgift: gå till skolan eller jobbet, och samtidigt vara:
- Klädd
- Rena
- Fed
- Vakna med en väckarklocka.
- Ta en dusch och tvätta dig.
- Gör frukost och lite kaffe eller te.
- Äta.
- Om du inte strök dina kläder kvällen innan, stryk dem.
- Klä på sig.
- Lämna huset.
- Köp eller ladda ner 1961 års upplaga av Webster's Third New International Dictionary.
- Hitta alla namn från vår lista i den här ordboken.
- På ett papper skriver du sidan i ordboken där namnet finns.
- Använd papperslapparna för att sortera namnen.
for
slinga som utför denna uppgift
int[] numbers = new int[100];
// ...fill the array with numbers
for (int i: numbers) {
System.out.println(i);
}
Vad är komplexiteten i denna algoritm? Linjär, dvs O(n). Antalet åtgärder som programmet måste utföra beror på hur många nummer som skickas till det. Om det finns 100 nummer i arrayen kommer det att finnas 100 åtgärder (påståenden för att visa strängar på skärmen). Om det finns 10 000 nummer i arrayen måste 10 000 åtgärder utföras. Kan vår algoritm förbättras på något sätt? Nej. Oavsett vad kommer vi att behöva göra N passerar genom arrayen och exekvera N satser för att visa strängar på konsolen. Tänk på ett annat exempel.
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
i vilken vi infogar flera siffror. Vi måste utvärdera den algoritmiska komplexiteten för att infoga ett enstaka nummer i LinkedList
vårt exempel, och hur det beror på antalet element i listan. Svaret är O(1), dvs konstant komplexitet . Varför? Observera att vi lägger in varje nummer i början av listan. Dessutom kommer du ihåg att när du infogar en siffra i en LinkedList
flyttar elementen inte någonstans. Länkarna (eller referenserna) uppdateras (om du har glömt hur LinkedList fungerar, titta på en av våra gamla lektioner ). Om den första siffran i vår lista är x
, och vi infogar siffran y längst fram i listan, behöver vi bara göra följande:
x.previous = y;
y.previous = null;
y.next = x;
När vi uppdaterar länkarna bryr vi oss inte om hur många nummer som redan finns i ,LinkedList
om en eller en miljard. Algoritmens komplexitet är konstant, dvs O(1).