Algorytmika i złożoność
Zapis algorytmów (schematy blokowe, pseudokod), podstawowe algorytmy sortowania (bąbelkowe, przez wstawianie, szybkie) i wyszukiwania (liniowe, binarne), złożoność obliczeniowa (O-notacja), struktury danych (tablice, listy, stosy, kolejki, drzewa).
Wstęp: dział, w którym liczy się jedna rzecz — liczba kroków
Algorytmika w INF.04 rzadko wygląda jak pytanie „czym jest algorytm". Wygląda tak: masz schemat blokowy i musisz podać, co wypisze dla podanych danych. Albo: masz tablicę pięciu liczb i musisz zapisać jej stan po drugim przebiegu sortowania bąbelkowego. Albo: która metoda wyszukiwania wymaga wcześniejszego posortowania danych. To są zadania na dokładność, nie na erudycję — trzeba umieć odtworzyć algorytm krok po kroku na kartce i znać złożoności z pamięci.
📋 Spis treści
Podstawy i zapis
1
Pojęcie algorytmu i jego cechy
Algorytm to skończony, uporządkowany ciąg jednoznacznych czynności, który dla poprawnych danych wejściowych prowadzi do rozwiązania zadania. Przepis na naleśniki algorytmem nie jest — „smaż, aż będą gotowe" nie jest jednoznaczne, a „szczypta soli" nie jest wielkością mierzalną. Egzamin pyta o cechy algorytmu wprost, więc warto znać je z nazwy.
Dla każdego dopuszczalnego zestawu danych wejściowych algorytm zwraca wynik zgodny ze specyfikacją. Algorytm liczący średnią z pustej tablicy dzieli przez zero — jest niepoprawny, dopóki nie obsłuży tego przypadku.
Algorytm kończy się po skończonej liczbie kroków. Pętla, w której warunek nigdy nie przestaje być prawdziwy, łamie tę cechę — to pętla nieskończona, a nie algorytm.
Każdy krok jest opisany tak, że nie da się go zinterpretować na dwa sposoby, a wykonanie na tych samych danych zawsze daje ten sam wynik (determinizm). „Weź dużą liczbę" to krok niejednoznaczny.
- Ogólność (uniwersalność) — algorytm rozwiązuje całą klasę zadań, a nie jeden konkretny przypadek. Algorytm liczący NWD działa dla dowolnej pary liczb, nie tylko dla 24 i 36.
- Efektywność — rozwiązuje zadanie przy rozsądnym nakładzie czasu i pamięci. Dwa poprawne algorytmy mogą różnić się czasem działania o wiele rzędów wielkości.
- Sprawność — ma określone dane wejściowe i wyjściowe, czyli coś przyjmuje i coś zwraca.
Elementy każdego algorytmu: dane wejściowe, zbiór operacji do wykonania, wynik (dane wyjściowe). Do opisu dołącza się specyfikację: co jest dane, co jest szukane i jakie warunki muszą spełniać dane.
Zadanie: znajdź największy element w tablicy liczb całkowitych.
Dane wejściowe: liczba naturalna n ≥ 1 oraz tablica A złożona
z n liczb całkowitych.
Dane wyjściowe: liczba max równa największemu z elementów
tablicy A.
Warunek dla danych: tablica nie może być pusta — dla n = 0
zadanie nie ma rozwiązania.
Trzy zdania, a dają punkt w zadaniach otwartych. Bez określenia warunku dla
danych brzegowych opis algorytmu jest niepełny.
2
Sposoby zapisu i schemat blokowy
Ten sam algorytm można zapisać na cztery sposoby. Egzamin najczęściej daje schemat blokowy i każe go „wykonać" na kartce albo odwrotnie — daje listę kroków i pyta, który schemat jej odpowiada. Symbole graficzne trzeba znać na pamięć, bo od nich zależy odczytanie całego rysunku.
Opis słowny to zwykłe zdania. Czytelny dla człowieka, ale łatwo o niejednoznaczność, więc nadaje się tylko do prostych zadań.
Lista kroków to ponumerowane, krótkie polecenia. Numery pozwalają odwoływać się do konkretnego miejsca („wróć do kroku 3"), dzięki czemu da się zapisać pętlę i rozgałęzienie.
Pseudokod wygląda jak kod, ale nie należy do żadnego języka. Używa słów typu jeżeli, dopóki, dla i operatora przypisania. Nie kompiluje się i nie musi.
Schemat blokowy (sieć działań) to rysunek z figur połączonych strzałkami. Najbardziej czytelny dla prostych algorytmów, nieczytelny dla długich.
| Figura | Nazwa bloku | Znaczenie | Liczba wyjść |
|---|---|---|---|
| owal | graniczny (terminalny) | START albo STOP | 1 dla START, 0 dla STOP |
| równoległobok | wejścia/wyjścia | czytaj dane, wypisz wynik | 1 |
| prostokąt | operacyjny | obliczenie, przypisanie wartości | 1 |
| romb | warunkowy (decyzyjny) | pytanie o wartość logiczną | 2 — TAK i NIE |
| strzałka | połączenie | kolejność wykonywania bloków | — |
Zasada, o którą pytają najczęściej: tylko romb ma dwa wyjścia, a blok STOP nie ma żadnego. Każdy schemat ma dokładnie jeden blok START i może mieć kilka bloków STOP.
Zadanie: wczytaj liczbę i wypisz, czy jest parzysta.
LISTA KROKÓW PSEUDOKOD SCHEMAT BLOKOWY
1. Start czytaj n (owal) START
2. Czytaj n jeżeli n mod 2 = 0 to |
3. Oblicz r = n mod 2 pisz "parzysta" (r-bok) czytaj n
4. Jeżeli r = 0, idź do 5, w przeciwnym razie |
w przeciwnym razie do 6 pisz "nieparzysta" (romb) n mod 2 = 0 ?
5. Pisz "parzysta", idź do 7 koniec jeżeli / \
6. Pisz "nieparzysta" TAK NIE
7. Stop (r-bok) (r-bok)
"parzysta" "nieparzysta"
\ /
(owal) STOPOperator mod (reszta z dzielenia) i div (dzielenie całkowite) wracają w tym dziale bez przerwy: parzystość, liczby pierwsze, konwersje systemów liczbowych, wyciąganie cyfr liczby. Warto mieć je w palcach.
3
Złożoność obliczeniowa i notacja O
Złożoność czasowa mówi, ile operacji dominujących wykona algorytm dla danych rozmiaru n. Złożoność pamięciowa — ile dodatkowej pamięci zajmie. Notacja O opisuje tempo wzrostu, więc pomija stałe i składniki niższego rzędu: 3n² + 5n + 100 to po prostu O(n²).
| Klasa | Nazwa | Co ma taką złożoność | Operacje dla n = 1000 |
|---|---|---|---|
| O(1) | stała | odczyt elementu tablicy po indeksie, operacja push na stosie | 1 |
| O(log n) | logarytmiczna | wyszukiwanie binarne, szukanie w zrównoważonym drzewie BST | około 10 |
| O(n) | liniowa | wyszukiwanie liniowe, suma elementów, szukanie maksimum | 1 000 |
| O(n log n) | liniowo-logarytmiczna | sortowanie szybkie i przez scalanie | około 10 000 |
| O(n²) | kwadratowa | sortowanie bąbelkowe, przez wybór, przez wstawianie | 1 000 000 |
| O(2ⁿ) | wykładnicza | naiwna rekurencja Fibonacciego, przegląd wszystkich podzbiorów | liczba o ponad 300 cyfrach |
| O(n!) | wykładnicza (silnia) | przegląd wszystkich permutacji, naiwny problem komiwojażera | liczba o ponad 2500 cyfrach |
Skala robi wrażenie dopiero w zestawieniu. Dla n = 1000 algorytm O(n log n) wykonuje około 10 tysięcy operacji, a O(n²) — milion, czyli sto razy więcej. Dwie ostatnie klasy dają liczby, których nie da się policzyć na żadnym sprzęcie — dlatego algorytmy wykładnicze uznaje się za praktycznie nieużywalne dla dużych danych.
1. Pojedyncza pętla po n elementach to O(n). Nie ma
znaczenia, ile instrukcji jest w środku, o ile jest ich stała liczba.
2. Pętla w pętli, obie po n, to O(n²). Zagnieżdżenie mnoży,
nie dodaje. Trzy zagnieżdżone pętle to O(n³).
3. Podział zakresu na pół w każdym kroku to O(log n). Jeżeli
w pętli zmienna dzieli się przez 2 albo mnoży przez 2, masz logarytm.
Dwie pętle jedna po drugiej to O(n) + O(n) = O(2n) = O(n) —
stałe odrzucamy. Odrzucamy też składniki niższego rzędu: O(n² + n) = O(n²).
Logarytm w notacji O jest zawsze o podstawie 2, ale podstawy się nie pisze,
bo zmiana podstawy to tylko mnożenie przez stałą.
- Optymistyczny (najlepszy) — dane ułożone najkorzystniej. Dla wyszukiwania liniowego: szukany element stoi na pierwszej pozycji, czyli O(1).
- Średni (oczekiwany) — uśrednienie po wszystkich możliwych układach danych. Dla wyszukiwania liniowego: około n/2 porównań, czyli nadal O(n).
- Pesymistyczny (najgorszy) — dane ułożone najgorzej. Dla wyszukiwania liniowego: element na ostatniej pozycji albo w ogóle go nie ma, czyli n porównań, O(n).
Gdy w zadaniu nie napisano, o który przypadek chodzi, przyjmuje się pesymistyczny — bo tylko on daje gwarancję czasu wykonania.
4
Algorytmy sortowania
Pięć algorytmów, które trzeba umieć opisać i prześledzić na małej tablicy. Trzy proste mają złożoność kwadratową, dwa zaawansowane — liniowo-logarytmiczną. Zadanie „podaj zawartość tablicy po pierwszym przebiegu" to najczęstsza forma pytania z tego zakresu.
Bubble sort. Porównuje sąsiednie elementy i zamienia je miejscami, jeśli stoją w złej kolejności. Po pierwszym przebiegu największy element „wypływa" na koniec tablicy — stąd nazwa. Każdy kolejny przebieg może być krótszy o jedną pozycję.
Selection sort. Szuka najmniejszego elementu w nieposortowanej części i zamienia go z pierwszym elementem tej części. Wykonuje najwyżej n − 1 zamian — najmniej ze wszystkich metod, więc opłaca się, gdy przenoszenie danych jest kosztowne.
Insertion sort. Bierze kolejny element i wsuwa go w odpowiednie miejsce już posortowanego początku tablicy — dokładnie jak układanie kart w ręce. Dla danych prawie posortowanych działa w czasie bliskim O(n).
Metoda dziel i zwyciężaj. Wybiera element osiowy (pivot), przestawia dane tak, by po lewej stronie znalazły się elementy mniejsze, a po prawej większe od pivota, a potem wywołuje się rekurencyjnie dla obu części. Średnio O(n log n), ale przy fatalnie dobranym pivocie (na przykład zawsze pierwszy element w tablicy już posortowanej) degeneruje się do O(n²). Sortuje w miejscu — dodatkowa pamięć idzie tylko na stos wywołań rekurencyjnych.
Też dziel i zwyciężaj, ale podział jest zawsze na dwie równe połowy, niezależnie od zawartości danych. Dzieli tablicę aż do fragmentów jednoelementowych, a potem scala je parami, zachowując porządek. Dzięki temu O(n log n) w każdym przypadku, także pesymistycznym. Cena: wymaga dodatkowej tablicy o rozmiarze n, czyli pamięci O(n).
| Algorytm | Optymistyczny | Średni | Pesymistyczny | Pamięć | Stabilny |
|---|---|---|---|---|---|
| bąbelkowe | O(n) | O(n²) | O(n²) | O(1) | tak |
| przez wybór | O(n²) | O(n²) | O(n²) | O(1) | nie |
| przez wstawianie | O(n) | O(n²) | O(n²) | O(1) | tak |
| szybkie (QuickSort) | O(n log n) | O(n log n) | O(n²) | O(log n) | nie |
| przez scalanie (MergeSort) | O(n log n) | O(n log n) | O(n log n) | O(n) | tak |
Stabilność oznacza, że elementy o równych kluczach zachowują
swoją pierwotną kolejność względem siebie. Ma znaczenie przy sortowaniu
rekordów po jednym polu — na przykład gdy porządkujesz listę uczniów po
ocenie, zachowując alfabetyczny porządek wewnątrz każdej oceny.
Złożoność O(n) w przypadku optymistycznym dla sortowania bąbelkowego dotyczy
wersji z flagą wykrywającą brak zamian. Bez tej flagi
algorytm zawsze wykonuje pełne n − 1 przebiegów i ma O(n²) także dla danych
już posortowanych.
// A - tablica indeksowana od 0 do n-1, sortowanie rosnąco
// wersja z flagą: kończy pracę, gdy w przebiegu nie było ani jednej zamiany
sortowanie_babelkowe(A, n):
powtarzaj
zamiana = FALSZ
dla i = 0 do n - 2 wykonuj:
jeżeli A[i] > A[i + 1] to
pom = A[i]
A[i] = A[i + 1]
A[i + 1] = pom
zamiana = PRAWDA
koniec jeżeli
koniec dla
n = n - 1 // największy element jest już na swoim miejscu
dopóki zamiana = PRAWDA
zwróć AZamiana dwóch wartości zawsze wymaga zmiennej pomocniczej. Zapis A[i] = A[i+1] bez zapamiętania starej wartości nadpisuje dane — to klasyczny błąd punktowany na minus w zadaniach otwartych.
Treść: Podaj zawartość tablicy [5, 1, 4, 2, 8] po każdym pełnym przebiegu sortowania bąbelkowego rosnąco.
start: 5 1 4 2 8
przebieg 1: porównania par (5,1) (5,4) (5,2) (5,8)
1 4 2 5 8 <- 5 dopłynęło na pozycję 3, 8 zostało na końcu
przebieg 2: porównania par (1,4) (4,2) (4,5)
1 2 4 5 8 <- tablica jest już posortowana
przebieg 3: porównania par (1,2) (2,4) - żadnej zamiany, algorytm kończy pracęUwaga na pułapkę: „przebieg" to przejście przez całą tablicę, a nie pojedyncze porównanie. Jeśli zadanie prosi o stan po pierwszym przebiegu, odpowiedź brzmi 1, 4, 2, 5, 8 — a nie 1, 5, 4, 2, 8, czyli stan po pierwszej zamianie.
5
Wyszukiwanie liniowe i binarne
Dwa algorytmy i jedno pytanie, które pojawia się prawie zawsze: który z nich wymaga uprzedniego posortowania danych. Odpowiedź: binarne. Na nieposortowanej tablicy wyszukiwanie binarne nie działa wolniej — działa błędnie.
| Cecha | Liniowe (sekwencyjne) | Binarne (przez połowienie) |
|---|---|---|
| Wymaga posortowania | nie | tak, bezwzględnie |
| Zasada działania | sprawdza po kolei element po elemencie | porównuje ze środkiem i odrzuca połowę zakresu |
| Przypadek optymistyczny | O(1) — element pierwszy | O(1) — element w środku |
| Przypadek pesymistyczny | O(n) | O(log n) |
| Tablica 1 000 elementów | do 1 000 porównań | do 10 porównań |
| Tablica 1 000 000 elementów | do 1 000 000 porównań | do 20 porównań |
| Wymagana struktura | tablica, lista, plik — cokolwiek | dostęp swobodny po indeksie, czyli tablica |
Skąd te 10 i 20: liczba kroków wyszukiwania binarnego to logarytm o podstawie 2 z liczby elementów. 2¹⁰ = 1024, więc dla tysiąca elementów wychodzi około 10 kroków. 2²⁰ = 1 048 576, więc dla miliona — około 20. Tysiąckrotny wzrost ilości danych kosztuje zaledwie dziesięć dodatkowych kroków. Na tym polega cała siła logarytmu i dlatego opłaca się najpierw posortować dane, jeśli zamierzasz szukać w nich wielokrotnie.
// WARUNEK KONIECZNY: tablica A musi być posortowana rosnąco
// zwraca indeks elementu x albo -1, gdy elementu nie ma w tablicy
wyszukiwanie_binarne(A, n, x):
lewy = 0
prawy = n - 1
dopóki lewy <= prawy wykonuj:
srodek = (lewy + prawy) div 2 // dzielenie całkowite
jeżeli A[srodek] = x to
zwróć srodek // znaleziono
w przeciwnym razie jeżeli A[srodek] < x to
lewy = srodek + 1 // odrzuć lewą połowę
w przeciwnym razie
prawy = srodek - 1 // odrzuć prawą połowę
koniec jeżeli
koniec dopóki
zwróć -1 // elementu nie ma w tablicy
// dla porównania - wyszukiwanie liniowe:
wyszukiwanie_liniowe(A, n, x):
dla i = 0 do n - 1 wykonuj:
jeżeli A[i] = x to zwróć i
koniec dla
zwróć -1Tablica: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91], czyli n = 10, indeksy od 0 do 9.
krok 1: lewy=0 prawy=9 srodek=(0+9) div 2=4 A[4]=16 16 < 23 -> lewy=5
krok 2: lewy=5 prawy=9 srodek=(5+9) div 2=7 A[7]=56 56 > 23 -> prawy=6
krok 3: lewy=5 prawy=6 srodek=(5+6) div 2=5 A[5]=23 trafienie -> zwróć 5
wynik: 3 kroki
wyszukiwanie liniowe potrzebowałoby w tym samym przypadku 6 porównańZwróć uwagę na dzielenie całkowite przy wyznaczaniu środka: (5 + 6) div 2 = 5, a nie 5,5. To najczęstsze źródło błędu przy śledzeniu tego algorytmu na kartce.
6
Struktury danych: stos, kolejka, drzewo
Struktura danych to sposób organizacji danych w pamięci wraz z zestawem operacji, które można na nich wykonywać. Egzamin sprawdza tu dwie rzeczy: czy znasz skróty LIFO i FIFO oraz czy potrafisz podać przykład zastosowania każdej struktury.
Last In, First Out — ostatni przyszedł, pierwszy wychodzi. Dane dodaje się i zdejmuje z tego samego końca, zwanego wierzchołkiem. Model do zapamiętania: stos talerzy — bierzesz ten z góry.
Operacje: push (odłóż na wierzch),
pop (zdejmij z wierzchu),
top (podejrzyj wierzch bez zdejmowania). Każda w czasie O(1).
Zastosowania: stos wywołań funkcji (w tym rekurencji), funkcja „cofnij" w edytorach, sprawdzanie poprawności nawiasów w wyrażeniu, obliczanie wyrażeń w odwrotnej notacji polskiej (ONP), przechodzenie grafu w głąb (DFS).
First In, First Out — pierwszy przyszedł, pierwszy wychodzi. Dane dodaje się na końcu, a pobiera z początku. Model do zapamiętania: kolejka do kasy.
Operacje: enqueue (dodaj na koniec),
dequeue (pobierz z przodu). Obie w czasie O(1).
Zastosowania: kolejka wydruku, bufor klawiatury, kolejka procesów w systemie operacyjnym, kolejki komunikatów, przechodzenie grafu wszerz (BFS). Odmiana: kolejka priorytetowa, z której wychodzi element o najwyższym priorytecie, a nie najstarszy.
Wkładamy po kolei: A, B, C, D
STOS (LIFO) KOLEJKA (FIFO)
[D] <- wierzch wejście -> D C B A -> wyjście
[C]
[B] kolejność pobierania:
[A] <- dno A, B, C, D
kolejność pobierania: czyli dokładnie taka,
D, C, B, A w jakiej wkładaliśmy
czyli ODWROTNA do wkładaniaKlasyczne zadanie: „na stos wstawiono kolejno 1, 2, 3, po czym wykonano dwie operacje pop. Co znajduje się na wierzchu?" — zdjęto 3, potem 2, więc na wierzchu zostaje 1.
- Tablica — ciągły obszar pamięci, elementy tego samego typu, dostęp po indeksie w czasie O(1). Rozmiar zwykle stały; wstawienie elementu w środek wymaga przesunięcia całej reszty, czyli O(n).
- Lista jednokierunkowa — węzły rozrzucone po pamięci, każdy zawiera dane i wskaźnik na następny węzeł. Ostatni wskazuje na wartość pustą. Dostęp do k-tego elementu wymaga przejścia od początku, czyli O(n), ale wstawienie w znanym miejscu to O(1).
- Lista dwukierunkowa — każdy węzeł ma wskaźnik na następny oraz na poprzedni, więc można iść w obie strony i łatwiej usuwać element. Kosztem jest dodatkowy wskaźnik w każdym węźle.
- Lista cykliczna — ostatni węzeł wskazuje na pierwszy zamiast na wartość pustą.
- Drzewo — struktura hierarchiczna: korzeń, węzły, liście (węzły bez potomków). Każdy węzeł ma dokładnie jednego rodzica, poza korzeniem, który nie ma żadnego.
- Drzewo binarne — każdy węzeł ma co najwyżej dwóch potomków: lewego i prawego.
- Drzewo BST (wyszukiwań binarnych) — w lewym poddrzewie leżą wartości mniejsze od węzła, w prawym większe. Wyszukiwanie w drzewie zrównoważonym to O(log n), ale w drzewie zdegenerowanym do „patyka" — O(n).
- Graf — zbiór wierzchołków połączonych krawędziami. Skierowany (krawędzie mają zwrot) lub nieskierowany, ważony (krawędzie mają koszt) lub nie. Reprezentacje: macierz sąsiedztwa albo lista sąsiedztwa. Drzewo to szczególny przypadek grafu: spójny i pozbawiony cykli.
7
Rekurencja: silnia i Fibonacci
Rekurencja to sytuacja, w której funkcja wywołuje samą siebie dla mniejszego podproblemu. Każda funkcja rekurencyjna musi mieć warunek zakończenia (przypadek bazowy) — bez niego wywołania nigdy się nie kończą i program przerywa pracę z przepełnieniem stosu.
// definicja matematyczna: 0! = 1 oraz n! = n * (n-1)!
WERSJA REKURENCYJNA WERSJA ITERACYJNA
silnia(n): silnia(n):
jeżeli n <= 1 to wynik = 1
zwróć 1 // baza dla i = 2 do n wykonuj:
w przeciwnym razie wynik = wynik * i
zwróć n * silnia(n - 1) koniec dla
koniec jeżeli zwróć wynik
rozwinięcie dla n = 5:
silnia(5) = 5 * silnia(4) = 5 * 4 * silnia(3) = 5 * 4 * 3 * silnia(2)
= 5 * 4 * 3 * 2 * silnia(1) = 5 * 4 * 3 * 2 * 1 = 120
obie wersje: złożoność czasowa O(n)
pamięć: rekurencyjna O(n) - stos wywołań; iteracyjna O(1)// F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)
// ciąg: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
fib(n):
jeżeli n <= 1 to
zwróć n
w przeciwnym razie
zwróć fib(n - 1) + fib(n - 2)
koniec jeżeli
drzewo wywołań dla fib(5) - zwróć uwagę na powtórzenia:
fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \
fib(2) fib(1) fib(3) liczone 2 razy, fib(2) liczone 3 razyNaiwna rekurencja dla Fibonacciego ma złożoność wykładniczą, w przybliżeniu O(2ⁿ), bo te same wartości liczone są wielokrotnie od nowa. Wersja iteracyjna, która pamięta tylko dwie ostatnie wartości, działa w czasie O(n) i pamięci O(1). To sztandarowy przykład na to, że algorytm poprawny może być praktycznie bezużyteczny z powodu złożoności.
Rekurencja kontra iteracja — jak odpowiadać
Rekurencja daje krótszy i czytelniejszy zapis dla problemów z natury
rekurencyjnych: drzewa, metoda dziel i zwyciężaj, Wieże Hanoi. Iteracja jest
szybsza i nie zużywa stosu wywołań, więc nie grozi jej przepełnienie. Każdy
algorytm rekurencyjny da się przepisać iteracyjnie — czasem kosztem jawnego
użycia stosu w kodzie.
8
Algorytmy klasyczne z egzaminu
Cztery algorytmy, które w tym dziale wracają najczęściej. Warto umieć odtworzyć je zarówno jako schemat blokowy, jak i jako pseudokod, oraz prześledzić na konkretnych liczbach.
WERSJA Z ODEJMOWANIEM WERSJA Z RESZTĄ (mod) - szybsza
nwd(a, b): nwd(a, b):
dopóki a <> b wykonuj: dopóki b <> 0 wykonuj:
jeżeli a > b to r = a mod b
a = a - b a = b
w przeciwnym razie b = r
b = b - a koniec dopóki
koniec jeżeli zwróć a
koniec dopóki
zwróć a
Przykład dla a = 48, b = 18 (wersja z resztą):
a=48 b=18 -> r = 48 mod 18 = 12 -> a=18 b=12
a=18 b=12 -> r = 18 mod 12 = 6 -> a=12 b=6
a=12 b=6 -> r = 12 mod 6 = 0 -> a=6 b=0
b = 0, pętla się kończy, więc NWD(48, 18) = 6
NWW liczymy ze wzoru: NWW(a, b) = a * b / NWD(a, b)
NWW(48, 18) = 864 / 6 = 144Wersja z odejmowaniem jest znacznie wolniejsza — dla pary (1000, 1) wykona 999 obiegów pętli, podczas gdy wersja z resztą zakończy się po jednym. Zapamiętaj też, że algorytm Euklidesa działa na liczbach naturalnych dodatnich; wersja z odejmowaniem zapętli się, gdy podasz jej zero.
Liczba pierwsza to liczba naturalna większa od 1, która ma dokładnie dwa dzielniki: 1 i samą siebie. Liczba 1 nie jest pierwsza, a 2 jest jedyną parzystą liczbą pierwszą — to dwa najczęściej mylone fakty.
czy_pierwsza(n):
jeżeli n < 2 to
zwróć FALSZ
dla i = 2 do pierwiastek(n):
jeżeli n mod i = 0 to
zwróć FALSZ
koniec dla
zwróć PRAWDASprawdzanie dzielników tylko do pierwiastka z n skraca złożoność z O(n) do O(√n). Powód: jeśli n = a · b, to co najmniej jeden z czynników jest nie większy niż pierwiastek z n.
Znajduje wszystkie liczby pierwsze mniejsze lub równe n, wykreślając wielokrotności kolejnych liczb pierwszych. Złożoność O(n log log n), czyli praktycznie liniowa.
sito(n):
utwórz tablicę T o indeksach 2..n
wypełnij ją wartością PRAWDA
dla i = 2 do pierwiastek(n):
jeżeli T[i] = PRAWDA to
j = i * i
dopóki j <= n wykonuj:
T[j] = FALSZ
j = j + i
// indeksy z PRAWDA to liczby pierwszeDla n = 30 zostaną: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 — dziesięć liczb.
DZIESIĘTNY -> BINARNY: dziel przez 2, zapisuj reszty, czytaj OD DOŁU
156 : 2 = 78 reszta 0 wynik czytamy od ostatniej reszty do pierwszej:
78 : 2 = 39 reszta 0 156(10) = 10011100(2)
39 : 2 = 19 reszta 1
19 : 2 = 9 reszta 1 pseudokod:
9 : 2 = 4 reszta 1 dopóki n > 0 wykonuj:
4 : 2 = 2 reszta 0 dopisz_z_lewej(n mod 2)
2 : 2 = 1 reszta 0 n = n div 2
1 : 2 = 0 reszta 1 koniec dopóki
BINARNY -> DZIESIĘTNY: suma bitów pomnożonych przez potęgi dwójki
10011100(2) = 1*128 + 0*64 + 0*32 + 1*16 + 1*8 + 1*4 + 0*2 + 0*1 = 156(10)
BINARNY <-> SZESNASTKOWY: grupuj bity po CZTERY, licząc od prawej strony
1001 1100 -> 9 C -> 9C(16) bo 9 = 1001, C = 12 = 1100
BINARNY <-> ÓSEMKOWY: grupuj bity po TRZY, licząc od prawej strony
010 011 100 -> 2 3 4 -> 234(8)
Cyfry szesnastkowe: 0-9, dalej A=10, B=11, C=12, D=13, E=14, F=15Grupowanie po cztery bity działa, bo 16 = 2⁴, a po trzy — bo 8 = 2³. Brakujące bity z lewej strony uzupełniamy zerami. To najszybsza metoda na egzaminie: zamiana liczby szesnastkowej na dziesiętną przez zapis binarny jest krótsza i mniej podatna na błąd niż liczenie potęg szesnastki.
- Wyszukiwanie binarne na nieposortowanej tablicy. To nie jest „wolniejsze" — to jest błędne. Algorytm odrzuci połowę zakresu, w której leży szukany element, i zwróci informację, że elementu nie ma.
- Mylenie LIFO z FIFO. Stos to LIFO (ostatni wchodzi, pierwszy wychodzi), kolejka to FIFO. Zapamiętaj przez model: stos talerzy kontra kolejka do kasy.
- Podawanie O(n log n) jako pesymistycznej złożoności QuickSorta. W najgorszym przypadku QuickSort ma O(n²). Gwarantowane O(n log n) we wszystkich trzech przypadkach ma tylko sortowanie przez scalanie — kosztem pamięci O(n).
- Liczenie „przebiegu" jako pojedynczej zamiany. Jeden przebieg sortowania bąbelkowego to przejście przez całą tablicę, czyli n − 1 porównań, a nie jedno.
- Traktowanie 1 jako liczby pierwszej. Liczby pierwsze zaczynają się od 2, bo 1 ma tylko jeden dzielnik. Dodatkowo 2 jest jedyną parzystą liczbą pierwszą.
- Odczytywanie reszt konwersji od góry. Przy zamianie na system binarny wynik czyta się od ostatniej reszty do pierwszej. Odwrotna kolejność to gwarantowany zły wynik.
- Pomijanie warunku zakończenia rekurencji. Funkcja bez przypadku bazowego nie jest algorytmem — łamie cechę skończoności i kończy się przepełnieniem stosu.
- Rysowanie dwóch wyjść z prostokąta. W schemacie blokowym dwa wyjścia ma wyłącznie romb. Blok operacyjny i blok wejścia/wyjścia mają zawsze dokładnie jedno.
Algorytmiki nie da się nauczyć samym czytaniem. Weź kartkę, prześledź sortowanie bąbelkowe na pięciu liczbach i policz NWD algorytmem Euklidesa — a potem sprawdź się na pytaniach z tego działu.