Cześć! Dzisiejsza lekcja będzie nieco inna niż pozostałe. Różni się tym, że jest tylko pośrednio powiązany z Javą. To powiedziawszy, ten temat jest bardzo ważny dla każdego programisty. Będziemy rozmawiać o algorytmach . Co to jest algorytm? Mówiąc najprościej, jest to pewna sekwencja działań, które należy wykonać, aby osiągnąć pożądany rezultat . Algorytmów używamy często w życiu codziennym. Na przykład każdego ranka masz określone zadanie: iść do szkoły lub pracy, a jednocześnie być:
- Ubrany
- Czysty
- Karmiony
- Obudź się za pomocą budzika.
- Weź prysznic i umyj się.
- Zrób śniadanie i kawę lub herbatę.
- Jeść.
- Jeśli poprzedniego wieczoru nie wyprasowałeś ubrań, wyprasuj je.
- Ubrać się.
- Opuścić dom.
- Kup lub pobierz wydanie Webster's Third New International Dictionary z 1961 roku.
- Znajdź każde imię z naszej listy w tym słowniku.
- Napisz na kartce stronę słownika, na której znajduje się nazwa.
- Użyj kawałków papieru, aby posortować nazwy.
for
pętlę, która wykonuje to zadanie
int[] numbers = new int[100];
// ...fill the array with numbers
for (int i: numbers) {
System.out.println(i);
}
Jaka jest złożoność tego algorytmu? Liniowy, tj. O(n). Liczba akcji, które program musi wykonać, zależy od liczby przekazanych mu liczb. Jeśli w tablicy jest 100 liczb, będzie 100 akcji (instrukcji do wyświetlenia napisów na ekranie). Jeśli w tablicy jest 10 000 liczb, należy wykonać 10 000 akcji. Czy nasz algorytm można w jakikolwiek sposób ulepszyć? Nie. Bez względu na wszystko, będziemy musieli wykonać N przejść przez tablicę i wykonać N instrukcji, aby wyświetlić ciągi znaków na konsoli. Rozważ inny przykład.
public static void main(String[] args) {
LinkedList<Integer> numbers = new LinkedList<>();
numbers.add(0, 20202);
numbers.add(0, 123);
numbers.add(0, 8283);
}
Mamy puste miejsce LinkedList
, w które wstawiamy kilka liczb. Musimy ocenić złożoność algorytmiczną wstawiania pojedynczej liczby do liczby LinkedList
w naszym przykładzie i jak zależy to od liczby elementów na liście. Odpowiedzią jest O(1), czyli stała złożoność . Dlaczego? Zauważ, że wstawiamy każdy numer na początku listy. Ponadto przypomnisz sobie, że po wstawieniu liczby do LinkedList
, elementy nigdzie się nie przesuwają. Linki (lub odniesienia) są aktualizowane (jeśli zapomniałeś, jak działa LinkedList, spójrz na jedną z naszych starych lekcji ). Jeśli pierwszą liczbą na naszej liście jest x
, a my wstawimy liczbę y na początku listy, to wszystko, co musimy zrobić, to:
x.previous = y;
y.previous = null;
y.next = x;
Kiedy aktualizujemy linki, nie obchodzi nas, ile liczb jest już wLinkedList
, czy to jeden, czy miliard. Złożoność algorytmu jest stała, tj. O(1).
GO TO FULL VERSION