Spis treści
Przedmowa do nowego wydania . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
Przedmowa do pierwszego wydania . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
1 Podstawowe zasady analizy algorytmów . . . . . . . . . . . . . . . . . . . . . . .
15
1.1. Złożoność obliczeniowa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2. Równania rekurencyjne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3. Funkcje tworzące . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4. Poprawność semantyczna . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5. Podstawowe struktury danych . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5.1. Lista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5.2. Zbiór . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5.3. Graf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5.4. Notacja funkcyjna dla atrybutów obiektów . . . . . . . . . . . . . . . . . . . . 1.5.5. Drzewo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.6. Eliminacja rekursji . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.7. Koszt zamortyzowany operacji w strukturze danych . . . . . . . . . . . . . . . . . . . 1.8. Metody układania algorytmów . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.8.1. Metoda „dziel i zwyciężaj” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.8.2. Programowanie dynamiczne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.8.3. Metoda zachłanna . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.8.4. Inne metody . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Zadania . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15 22 23 24 26 27 29 30 35 35 38 40 42 42 42 43 44 44
2 Sortowanie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
51
2.1. Selectionsort – sortowanie przez selekcję . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2. Insertionsort – sortowanie przez wstawianie . . . . . . . . . . . . . . . . . . . . . . . . . 2.3. Quicksort – sortowanie szybkie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4. Dolne ograniczenie na złożoność problemu sortowania . . . . . . . . . . . . . . . . . 2.5. Sortowanie pozycyjne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.6. Kolejki priorytetowe i algorytm heapsort . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.7.. Drzewa turniejowe i zadania selekcji . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52 53 54 64 68 72 79
algorytmy_00.indd 5
2017-11-09 12:37:31