跳至內容

CKE Matura (Poland) Informatyka

Matura Poland · CKEInformatyka19 則筆記,位於 5 個資料夾,60 KB

cookie 製作的 CKE Matura Poland Informatyka 考試準備筆記,共 19 篇,分為 5 個部分,依照課程主題編排。

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.

內容

第一則筆記

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.

還有 18 個:可以從上方清單開啟任何一個。

評分

還沒有文字評論。把這些筆記加到自己的筆記中,就能成為第一個留下評論的人。