Czasem chcemy coś zaimplementować bardzo efektywnie. Innym razem może nam zależeć na szybkości samego procesu implementacji, przy zachowaniu rozsądnej efektywności kodu. Jeśli chcemy posortować 5 liczb i nie mamy do dyspozycji wbudowanego algorytmu sortowania, możemy to zrobić np. tak:
void sort(int* a, int n) {
for (int i = 0; i < n; ++i)
for (int j = i; j < n; ++j)
if (a[i] > a[j])
swap(a[i], a[i]);
}
Chyba prościej się nie da. Dodatkowo, nie ma gdzie się tu pomylić – czy zaczniemy od j = i, czy od j = i+1, i tak będzie dobrze. Podczas tych zajęć pokażemy kilka przykładów na to, jak kosztem czynnika logarytmicznego lub pierwiastkowego można uzyskać dużo prostszy algorytm.
Kiedyś pojawią się tu notatki z prawdziwego zdarzenia. Na razie jest sporo odnośników do łatwo dostępnych źródeł.
Patrz metoda 2c w opisie rozwiązania zadania Żabka z III etapu XVII Olimpiady Informatycznej (Niebieska książeczka).
Patrz ostatni przykład z lekcji o sztuczkach algorytmicznych na MAIN-ie.
Patrz przedostatni przykład z lekcji o sztuczkach algorytmicznych na MAIN-ie oraz jedno z zadań domowych do tej lekcji.
Słownik to struktura danych, która pozwala wykonywać operacje: find(x) – test na występowanie elementu w strukturze, ewentualnie zwraca iterator na ten element; insert(x) – wstawienie elementu; delete(x) – usunięcie elementu. Jest wiele klasycznych słowników, umożliwiających wykonywanie powyższych operacji w czasie O(log(n)), przy czym n to liczba operacji wykonywanych na strukturze: np. w bibliotece STL mamy set i map, są to zrównoważone drzewa binarne, takie jak drzewa czerwono-czarne, AVL, są też drzewa Splay, B-drzewa itp. Można także używać haszowania. Tym razem pokażemy, jak zastosować tablice Younga do implementacji operacji słownikowych w czasie O(sqrt(n)).
Tablica Younga to tablica kwadratowa t[N][N] wypełniona elementami słownika i INFTY (nieskończoność), jeśli żadnego elementu na danej pozycji nie ma. Dodatkowo, zarówno wiersze, jak i kolumny tablicy są uporządkowane niemalejąco. To pozwala wykonać operację find(x) za pomocą jednego przejścia w dół i w lewo, w czasie O(N):
pair<int, int> find(int x) {
int i = 0, j = N - 1;
while (i < N) {
while (j ≥ 0 && t[i][j] > x)
--j;
if (t[i][j] == x) return make_pair(i, j);
++i;
}
return make_pair(-1, -1); // brak
}
W operacji insert(x) musimy przede wszystkim zamienić jakoś nieskończoność na x. Najłatwiej to zrobić w polu t[N-1][N-1], bo tam na pewno znajduje się nieskończoność, jeśli w ogóle tablica nie jest całkowicie zapełniona. Potem tylko musimy poprawić uporządkowanie, patrząc na dwa sąsiednie pola. Po tej poprawce możemy być zmuszeni poprawiać tak dalej, idąc w górę i w lewo. Poniższy kod jest jakiś paskudny, ale ma trywialną strukturę.
void insert(int x) {
int i = N - 1, j = N - 1;
t[i][j] = x;
while (1) {
if ((!i || t[i-1][j] ≤ x) && (!j || t[i][j-1] ≤ x)) break;
if (i && j) {
if (t[i-1][j] > t[i][j-1]) {
swap(t[i-1][j], t[i][j]);
--i;
} else {
swap(t[i][j-1], t[i][j]);
--j;
}
} else if (i) {
swap(t[i-1][j], t[i][j]);
--i;
} else {
swap(t[i][j-1], t[i][j]);
--j;
}
}
}
Wreszcie w operacji delete(x) najpierw znajdujemy element x za pomocą find(x), ustawiamy go na INFTY, po czym poprawiamy tablicę lokalnie podobnie jak powyżej, tylko idąc w dół i w prawo.
Koszt każdej operacji słownikowej to O(N) = O(sqrt(n)).
Omówiliśmy zadanie domowe. Notatki w tym IKO z Delty.
Zadanie domowe: zadanie Robot sortujący na ASD-SIO.