Zum Inhalt springen

CKE Matura (Poland) Informatyka

Matura Poland · CKEInformatyka19 Notizen in 5 Ordnern, 60 KB

19 Lernnotizen für CKE Matura Poland Informatyka, von cookie erstellt, in 5 Abschnitten, die den Themen des Kurses folgen.

Notes for the CKE Matura computer science exam at extended level (Formuła 2023), in folders for the five content areas of the informator: algorithms and programming, number systems, databases and SQL, spreadsheets, and networks and the internet. Worked examples use their own numbers and were recomputed.

Was enthalten ist

Die erste Notiz

Algorytmy i programowanie / Złożoność algorytmów

Porównując dwa algorytmy rozwiązujące ten sam problem, nie mierzy się ich czasu w sekundach. Ten sam program działa różnie szybko na różnych komputerach i w różnych językach. Zamiast tego liczy się operacje dominujące, czyli te, których liczba najszybciej rośnie wraz z rozmiarem danych. Zwykle jest to porównanie elementów, przypisanie wartości do tablicy albo przesunięcie elementu. Liczbę takich operacji oznacza się przez nn, czyli rozmiar danych wejściowych.

Złożoność pesymistyczna i optymistyczna

Ta sama liczba elementów może dawać różną liczbę operacji, zależnie od tego, jakie dane dostaniemy. Złożoność pesymistyczna to największa możliwa liczba operacji dla danych najgorszych. Złożoność optymistyczna to najmniejsza liczba operacji dla danych najlepszych. Dla wyszukiwania liniowego dane najgorsze to szukana wartość na końcu ciągu albo jej brak, a dane najlepsze to szukana wartość na początku.

Zapis O

Zapis O(f(n))O(f(n)) oznacza, że liczba operacji nie rośnie szybciej niż stała razy f(n)f(n), gdy nn jest duże. Stałe mnożniki i składniki niższego rzędu pomija się. Operacji 3n+73n + 7 jest O(n)O(n), a operacji n2+100nn^2 + 100n jest O(n2)O(n^2). Najczęstsze rzędy, od najkorzystniejszego do najgorszego, to O(1)O(1), O(log⁡n)O(\log n), O(n)O(n), O(nlog⁡n)O(n \log n) i O(n2)O(n^2).

Przykładowo, dostęp do elementu tablicy przez indeks wymaga stałej liczby kroków, więc jest O(1)O(1). Wstawienie elementu na początek tablicy wymaga przesunięcia wszystkich pozostałych elementów, więc jest O(n)O(n). Wstawienie na początek listy jednokierunkowej, gdy znamy wskaźnik na jej początek, wymaga zmiany dwóch wskaźników, więc jest O(1)O(1).

Liczenie operacji w pętlach

Dwie pętle jedna po drugiej, każda po nn obiegów, dają 2n2n operacji, czyli O(n)O(n). Dwie pętle zagnieżdżone, z których wewnętrzna przebiega po nn elementach, dają n2n^2 operacji, czyli O(n2)O(n^2). Gdy wewnętrzna pętla przebiega i=1,…,ni = 1, \dots, n elementów, łączna liczba wykonań wynosi

∑i=1ni=n(n+1)2. \sum_{i=1}^{n} i = \frac{n(n+1)}{2}.

Przykład. Dla n=10n = 10 wewnętrzna instrukcja wykona się 10⋅112=55\frac{10 \cdot 11}{2} = 55 razy. Dla n=1000n = 1000 wynik to 500 500500\,500, czyli około pół miliona, a więc rząd n2n^2, a nie nn.

Jak zmienia się czas przy wzroście danych

Podwojenie nn przy złożoności O(n)O(n) podwaja liczbę operacji. Przy O(n2)O(n^2) liczba operacji rośnie czterokrotnie. Przy O(log⁡n)O(\log n) podwojenie nn dodaje zaledwie jedną operację, bo logarytm dwójkowy rośnie o jeden. Dlatego dla dużych zbiorów danych wybór algorytmu o niższym rzędzie ma większe znaczenie niż optymalizacja kodu.

Co zrobić przy analizie algorytmu

Najpierw wybiera się operację dominującą i wyjaśnia, dlaczego to ona wyznacza czas. Następnie liczy się, ile razy się wykona, osobno dla danych najgorszych i najlepszych. Na koniec sprawdza się wynik dla kilku małych przykładów, licząc ręcznie. Taki sprawdzian wyłapuje najczęstszy błąd, czyli pominięcie pętli albo źle ustawiony zakres indeksów.

Und 18 weitere: Öffne sie über die Liste oben.

Bewertungen

Noch keine schriftlichen Rezensionen. Füge diese Notizen zu deinen hinzu und du kannst die erste Rezension schreiben.