CIAO! La lezione di oggi sarà leggermente diversa dalle altre. Differirà in quanto è solo indirettamente correlato a Java. Detto questo, questo argomento è molto importante per ogni programmatore. Parleremo di algoritmi . Cos'è un algoritmo? In termini semplici, è una sequenza di azioni che devono essere completate per ottenere un risultato desiderato . Utilizziamo algoritmi spesso nella vita di tutti i giorni. Ad esempio, ogni mattina hai un compito specifico: andare a scuola o al lavoro, e allo stesso tempo essere:
- Vestito
- Pulito
- Alimentato
- Svegliati usando una sveglia.
- Fatti una doccia e lavati.
- Prepara la colazione e un caffè o un tè.
- Mangiare.
- Se non hai stirato i vestiti la sera prima, stirali.
- Vestirsi.
- Uscire di casa.
- Acquista o scarica l'edizione 1961 del Webster's Third New International Dictionary.
- Trova tutti i nomi dalla nostra lista in questo dizionario.
- Su un pezzo di carta, scrivi la pagina del dizionario su cui si trova il nome.
- Usa i pezzi di carta per ordinare i nomi.
for
ciclo ordinario che esegue questa attività
int[] numbers = new int[100];
// ...fill the array with numbers
for (int i: numbers) {
System.out.println(i);
}
Qual è la complessità di questo algoritmo? Lineare, cioè O(n). Il numero di azioni che il programma deve eseguire dipende da quanti numeri gli vengono passati. Se ci sono 100 numeri nell'array, ci saranno 100 azioni (dichiarazioni per visualizzare stringhe sullo schermo). Se nell'array sono presenti 10.000 numeri, è necessario eseguire 10.000 azioni. Il nostro algoritmo può essere migliorato in qualche modo? No. Non importa cosa, dovremo fare N passaggi attraverso l'array ed eseguire N istruzioni per visualizzare le stringhe sulla console. Considera un altro esempio.
public static void main(String[] args) {
LinkedList<Integer> numbers = new LinkedList<>();
numbers.add(0, 20202);
numbers.add(0, 123);
numbers.add(0, 8283);
}
Abbiamo un vuoto LinkedList
in cui inseriamo diversi numeri. Dobbiamo valutare la complessità algoritmica dell'inserimento di un singolo numero nel LinkedList
nostro esempio e come dipende dal numero di elementi nell'elenco. La risposta è O(1), cioè complessità costante . Perché? Si noti che inseriamo ogni numero all'inizio dell'elenco. Inoltre, ricorderai che quando inserisci un numero in a LinkedList
, gli elementi non si spostano da nessuna parte. I link (o riferimenti) sono aggiornati (se hai dimenticato come funziona LinkedList, guarda una delle nostre vecchie lezioni ). Se il primo numero nella nostra lista è x
, e inseriamo il numero y all'inizio della lista, tutto quello che dobbiamo fare è questo:
x.previous = y;
y.previous = null;
y.next = x;
Quando aggiorniamo i collegamenti, non ci interessa quanti numeri ci sono già nelLinkedList
, se uno o un miliardo. La complessità dell'algoritmo è costante, cioè O(1).
GO TO FULL VERSION