Poprawność algorytmu: niezmienniki, własność stopu

Przez poprawność algorytmu rozumiemy to, że daje on takie odpowiedzi, jakich oczekujemy. Oczywiście algorytm musi być poprawny, aby miało sens rozpatrywanie jego złożoności.

Pojęcie niezmiennika

Poprawność algorytmu sprowadza się do spełniania określonych niezmienników na różnych etapach wykonywania tego algorytmu. Rozważmy kilka przykładów pozwalających zrozumieć znaczenie niezmiennika.

Załóżmy, że mamy zbiór \( S \) składający się z \( n \) przedmiotów. Niektóre z przedmiotów są czarne, a niektóre białe. Zakładamy, że liczba czarnych przedmiotów jest nieparzysta.

Algorytm Biało-czarne1

  while |S|> 1 do begin
    pobierz dwa przedmioty z S; 
    if przedmioty są różnego koloru then wstaw z powrotem czarny 
  end;
  return kolor ostatniego przedmiotu w S;

Załóżmy, że mamy 10000001 czarnych przedmiotów i 1000000001 białych, jaki jest ostatni przedmiot? Rozpatrzmy niezmiennik: parzystość liczby czarnych przedmiotów.

Ponieważ na początku mamy nieparzystą liczbę czarnych przedmiotów, zatem wynikiem jest kolor czarny.

Rozpatrzmy modyfikację tego algorytmu, zakładamy że \( n \) jest niezerowe.

Algorytm Biało-czarne2

  while   |S|> 1 do begin 
    pobierz dwa przedmioty z S; 
    if co najmniej jeden jest biały then wstaw z powrotem jeden biały; 
  end; 
  return kolor ostatniego przedmiotu w S;

Załóżmy, że mamy 10000001 czarnych przedmiotów i 1000000001 białych, jaki jest ostatni przedmiot? Tym razem rozważmy niezmiennik: znak liczby białych przedmiotów. (Znak liczby jest równy 0, jeśli jest ona równa zeru, 1 - jeśli jest większa od zera.) Zatem ostatnim przedmiotem jest przedmiot biały.

Własność stopu

Jednym z podstawowych elementów poprawności algorytmu jest własność stopu: dla poprawnych danych wejściowych algorytm zatrzymuje się w skończonym czasie.
Na przykładzie czterech krótkich algorytmów pokażemy, że sprawdzanie własności stopu może nie być czynnością trywialną.

Algorytm Suma-Kwadratów-Cyfr

  while ((n <>4) and (n <> 1)) do
    n:= suma kwadratów cyfr liczby n;

Algorytm 6174

// n jest czterocyfrową liczbą naturalną niepodzielną przez 1111 
// pierwszymi cyframi n mogą być zera 
  while (n<>6174) do
       n1:= największa liczba czterocyfrowa, której cyfry są permutacją cyfr liczby n; 
       n2:= najmniejsza liczba czterocyfrowa, której  cyfry są permutacją cyfr liczby n; 
       n:= n1 - n2

W przypadku liczb trzycyfrowych rolę liczby 6174 pełni liczba 495. W przypadku liczb pięciocyfrowych nie ma takiej pojedyńczej liczby.

Rozpatrzmy następujący algorytm (zaprojektowany podobno przez
Fibonacciego) na rozkład ułamka na sumę parami różnych ułamków Egipskich,

tzn. ułamków postaci \( \frac{1}{q_i} \).

Rozkład Egipski jest postaci \( \hspace{0.4cm} \frac{p}{q}\ =\ \frac{1}{q_1}+\frac{1}{q_2}+\frac{1}{q_3}+\frac{1}{q_4}+\ldots , \hspace{0.4cm} \) gdzie \( q_1 < q_2 < q_3 < \ldots \) są liczbami naturalnymi:

Każdy ułamek ma rozkład Egipski, oto przykład takiego rozkładu:

\( 31/311\ =\ 1/12 + 1/63 + 1/2799 + 1/8708 \)

Niech \( DolnyEgipt(x) \) oznacza najwięszy ułamek Egipski (tzn. postaci \( \frac{1}{q} \)) nie przekraczający x.

Przykłady:
\( DolnyEgipt(2/3)=1/2,\ DolnyEgipt(4/5)=1/2,\ \)
\( DolnyEgipt(2/5)=1/3,\ DolnyEgipt(2/7)=1/4. \)

Niech \( 1\le p < q \) będą dwiema względnie pierwszymi liczbami naturalnymi. Następujący algorytm oblicza rozkład (niekoniecznie najkrótszy) nieskracalnego ułamka \( \frac{p}{q} \) na ułamki Egipskie.

Algorytm Rozkład-Egipski\( (p,q) \)

(algorytm Fibonacciego) 
  x:=p/q; 
  while (x>0) do
      y:=DolnyEgipt (x); output y; 
      x:=x-y;

Nasz algorytm dla wejścia (31,311), tzn. \( x=31/311 \), wyprodukuje 10 składników w rozkładzie Egipskim.

Dla wejścia \( \frac{7}{15} \) otrzymamy jako wynik następujący ciąg ułamków Egispskich: \( \hspace{0.5cm} \frac{1}{3},\ \frac{1}{8},\ \frac{1}{120}. \)

Algorytm ma własność stopu ponieważ liczniki kolejnych dodatnich wartości \( x \) (przedstawionych jako nieskracalne ułamki) maleją
(pozostawiamy dowód tego faktu jako ćwiczenie).
Oto przykład ciągu kolejnych wartości \( x \): 4/5 -> 3/10 -> 1/10. Liczniki maleją: \( 4>3>1 \).
W pewnym momencie licznik liczby \( x \) dochodzi do jedynki, wtedy następna wartość \( x \) staje się zerem i algorytm zatrzymuje się.
Zatem algorytm wykonuje co najwyżej \( p \) iteracji dla wejścia \( p/q \).

Innym przykładem związanym z ułamkami jest następujący algorytm.
Mamy zbiór ułamków \(X\;=\; \{1/1,\; 1/2,\; 1/3,\; \ldots 1/100\}\).
dopóki zbiór ma co najmniej 2 elementy wykonaj
pobierz dwa różne elementy \(a,b\) z tego zbioru i włóż \(f(a,b)\).
return(ostatni jedyny element).

Jaki będzie wynik jeśli \(f(a,b)\,=\,ab/(a+b)\),
a jaki jeśli \(f(a,b)\,=\,ab+a+b.\) ?

W pierwszym przypadku niezmiennikiem jest wartość sumy odwrotności elementów zbioru X,
w drugim przypadku jeśli do odwrotności każdego elementu dodamy 1, to wartość iloczynu
otrzymanych liczb jest niezmiennikiem.

Rozpatrzmy jeszcze jeden ciekawy przykład związany z własnością stopu. Załóżmy, że mamy ciąg cykliczny liczb całkowitych zadany przez tablicę \(A[0..n-1]\), czyli pozycja \(0\) jest następną po pozycji \(n-1\)..
Nasz obecny algorytm jednocześnie dla każdej pozycji zmieniai jej wartość na wartość różnicy między wartością na danej pozycji i cyklicznie następnej. Pytamy się dla jakich \( n\) algorytm ten zatrzymuje się dla każdych danych całkowitoliczbowych w tablicy długości \(n+1\).

Algorytm Ciąg-cykliczny

 while ciąg nie składa się z samych zer do
  pom:= A[0]
  for i=0 to n-2 
    A[i]:=|A[i]-A[i+1|
  A[n-1]:=|A[n-1]-pom|

Pierwsze trzy algorytmy mają własność stopu. W pierwszym łatwo to sprawdzić, gdyż dla \( n>100 \) następna wartość jest istotnie mniejsza.

Pozostawiamy jako ćwiczenie znalezienie najkrótszego koncepcyjnie dowodu własności stopu dwu pierwszych algorytmów (nie chodzi nam tu o brutalny dowód polegający na sprawdzeniu wszystkich przypadków przez komputer). Algorytm Ciąg-cykliczny, pomimo swojej prostoty, ma nietrywialą własność stopu (dla ciągu o długości będącej potęgą dwójki).

Następny algorytm jest bardziej abstrakcyjny. Pochodzi on od Collatza (jak również od polskiego matematyka Ulama).

Algorytm Collatza

 while n \neq 1 do
    if    n parzyste then n := n div 2; else n := 3*n+1;

Algorytm Collatza jest bardzo zagadkowy. Nie wiadomo, czy dla każdej dodatniej liczby całkowitej \( n \) ma on własność stopu. Problem ten postawił L. Collatz w roku 1937, wiadomo, że własność stopu zachodzi dla każdego \( 1 \le n \le 10^{16} \).

Rozważmy jeszcze jeden bardzo dziwny algorytm. Niech \(x^R\) oznacza wartość liczby będącej odwróceniem zapisu dziesiętnego liczby x, np \(12^R=21\).

Algorytm Dziwny

 while x <> x^R do
    x := x+x^R;

Algorytm Dziwny jest również zagadkowy. Nie wiadomo, czy dla każdej dodatniej liczby całkowitej \( n \) ma on własność stopu W szczególności najciekawszy jest przypadek liczby 196.

Jeśli zamiast zapisu dziesiętnego weźmiemy binarny to algorytm nie zawsze ma własność stopu, np. dla liczby 22 zapisanej binarnie nigdy sie nie zatrzyma. W tym przypadku co kilka iteracji otrzymamy liczbę (zapisaną binarnie) typu \(10 1^k 01 0^k \) dla coraz większych k.

Opis algorytmu za pomocą niezmienników

Niezmienniki są często podstawową konstrukcji algorytmu na poziomie koncepcyjnym. Opisujemy jedynie co dana część algorytmu ma wykonać w sensie zachowania odpowiedniego niezmiennika. Reszta jest czasami prostą sprawą natury inżynieryjno-technicznej.

Zademonstrujemy to na następujacym przykładzie posegregowania tablicy liczbowej \( A[1..n] \) względem elementu \( x \). Dla zbiorów pozycji \( X,Y \) tablicy \( A \) piszemy \( X < Y \) gdy każda pozycja w X jest mniejsza od każdej pozycji w \( Y \). Piszemy \( A[X] < a \) gdy wartości na pozycjach X są mniejsze od a (podobnie z równością).

Zdefiniujmy następujący niezmiennik

Nazwy M,R,W biorą się od Mniejsze, Równe, Większe.

Naszym problemem jest poprzestawiać elementy tablicy tak aby dla pewnych zbiorów M,R,W dających w sumie cały zbiór pozycji zachodził niezmiennik \( \alpha(M,R,W) \) (algorytmy tego typu maja zastosowanie w implmentacji bardzo praktycznego algorytmu Quicksort).

Algorytm wykonuje swoje zadanie startując od zbiorów pustych i zwiększając zbiory. Chcemy aby algorytm działał w miejscu (dodatkowa pamięć stała) i w każdej iteracji wykonywał stałą liczbę operacji.

Algorytm PosegregujTablicę

  M:= ∅; R:= ∅; W:= ∅; 
  while |M|+|R|+|W| <n do 
    zwiększ o jeden sumę |M|+|R|+|W| zachowując niezmiennik alpha(M,R,W,x) 
    w czasie i dodatkowej pamięci  O(1)

Algorytm ten jest silnikiem algorytmu QuickSort, który jest praktycznie najszybszym algorytmem sortowania.

Możliwe są różne scenariusze tego algorytmu poprzez dospecyfikowanie niezmiennika. Na przykład możemy zażądąc aby zbiory M,R,W były sąsiednimi przedziałami, tworzącymi razem sufiks (lub prefiks) tablicy, lub aby M było prefiksem a W sufiksem tablicy. Otrzymamy różne algorytmy w pewnym sensie izomorficzne. Naturalnym jest aby zażądać, by każdy ze zbiorów M, R, W był przedziałem, nawet jeśli tego nie zażądamy to tak będzie po zakończeniu algorytmu. Jeśli zbiory są przedziałami to pojedyńcza iteracja polega na manipulacji w okolicy końców przedziałów.

Możemy problem ouogólnić i segregować tablicę względem większej liczby elementów, np. względem elementów \( x < y \). Teraz zamiast dwóch segmentów M, R, W tablicy A mamy pięć zbiorów pozycji, a niezmiennik zamienia się na

\( Z1 < Z2 < Z3 < Z4 < Z5,\ A[Z1] < x,\ A[Z2]=x, \)

\( x < A[Z3] < y,\ A[Z4]=y,\ A[Z5]>y. \)

Poprawność i złożoność 10 prostych algorytmów

Poniżej dokonamy pobieżnej analizy złożoności obliczeniowej dziesięciu prostych algorytmów i wykażemy, że ich złożoności są lepsze od złożoności kwadratowej rozwiązań naiwnych, chociaż nasze algorytmy będą niewiele bardziej skomplikowane od naiwnych.

Poza dwoma z nich (działającymi w czasie czas \( O(n \log n), \)) wszystkie algorytmy działają w czasie liniowym.

Dokładne analizy pozostawiamy jako ćwiczenia.

Algorytm 1. Przywódca ciągu

Przywódcą ciągu jest element, który występuje w ciągu więcej razy niż połowa długości tego ciągu. Naszym problemem jest policzenie przywódcy ciągu danego w tablicy \( A[1..n] \). Dla uproszczenia przyjmijmy, że w tym ciągu jest przywódca. Łatwo zmodyfikować algorytm tak, by sprawdzał istnienie przywódcy.

Algorytm Liczenie-Przywódcy

ile := 0;
for i := 1 to n do 
  if (ile = 0) then 
    ile:= ile+1 ; j := i;
  else if (A[i]=A[j]) then ile:=ile+1;
  else ile :=ile-1; 
return A[j];

Przyspieszenie wynika z następującej własności problemu: jeśli mamy dwa różne elementy w tablicy, to możemy je usunąć i przywódca pozostanie taki sam.

Algorytm można zmodyfikować tak, aby w czasie liniowym liczył słabego przywódcę: element, który występuje w tablicy więcej niż \( n/5 \) razy. W tym przypadku potrzebne są cztery liczniki odpowiadające czterem kandydatom na słabego przywódcę. Algorytm liczy element, który jest kandydatem na słabego przywódcę (jeśli istnieje taki przywódca, to na pewno jest nim wyliczony element). Jeśli istnieje słaby przywódca i mamy pięć różnych elementów, to można je usunąć bez zmiany wyniku. Pozostawiamy napisanie odpowiedniego algorytmu jako ćwiczenie.

Problem można rozwiązać inaczej, sortując tablicę, wtedy mamy złożoność \( O(n log n) \). Podamy potem również rozwiązanie metodą "dziel i zwyciężaj".

W animacji kolorem żółtym na końcu jest zaznaczony licznik słabego przywódcy, a jego nazwa jest umieszczona w niebieskim kwadraciku.

Algorytm 2. Szukanie sumy

Mamy dane dwie tablice posortowane rosnąco \( A,B \) i liczbę \( x \), pytamy, czy istnieją \( a \in A,\ b \in B \) takie, że \( x=a+b \).

Algorytm Szukanie Sumy

i := 1; j := n;
while (i  < = n and j > 0) do
  if (A[i]+B[j]=x) then  return true; 
  else if (A[i]+B[j] < x) then i:=i+1;
  else j:=j-1;
return false;

Przyspieszenie jest możliwe dzięki odpowiedniej kolejności sprawdzania \( i,j \) i pominięciu zbędnych sprawdzeń.

Algorytm 3. Maksymalny segment

Dla tablicy \( A[1..n] \, \) liczymy maksymalną wartość z zera i ze wszystkich liczb \( \sum_{k=i}^j\ A[k] \), gdzie \( 1\le i\le j\le n \).

wynik := 0; sufiks := 0;
for i := 1 to n do
    sufiks:= max(A[i]+sufiks,0); wynik:= max(wynik,sufiks);

Przyspieszenie w stosunku do algorytmu kwadratowego następuje dzięki wprowadzeniu dodatkowej zmiennej sufiks. Po każdym zakończeniu pętli "for" zachodzi: wynik jest maksymalną sumą przedziału zawierającego się w \( [1..i] \) oraz sufiks jest maksymalną sumą segmentu, który jest sufiksem przedziału \( [1..i] \).

Algorytm 4. Najbliższy mniejszy sąsiad w ciągu

Dla każdego \( i > 1 \) zdefiniujmy najbliższego mniejszego (lewego) sąsiada \( i \) jako

\( Lewy[i] =max \{j < i : A[j] < A[i] \} \).

Dla uproszczenia zakładamy, że \( A[i]> 0 \) dla \( i>0 \) oraz \( A[0]=0 \).

Algorytm Najbliższy-Mniejszy-Sąsiad

for i := 1 to n do
  j := i-1;
  while ( A[j] >= A[i]) do j := Lewy[j];
  Lewy[i] := j;

Przyspieszenie w stosunku do algorytmu naiwnego następuje dzięki temu, że nie ma potrzeby sprawdzania tablicy dla indeksów istotnie wewnątrz przedziału \( [Lewy[i-1]...(i-1)] \). Niech \( k_i \) będzie liczbą tych \( j \), dla których \( A[j]>=A[i] \) (w wierszu 3). Wystarczy pokazać, że suma wszystkich \( k_i \) jest liniowa ze względu na n. Może się zdarzyć, że niektóre \( k_i \) mają wartość liniową. Zauważmy jednak, że dany indeks \( j \) pojawia się co najwyżej raz w sytuacji, gdy \( A[j] >= A[i] \), potem będzie "przeskoczony".

Opiszemy teraz nieformalnie alternatywny algorytm korzystajacy ze stosu.
Zamiast indeksu lewego sasiada bedziemy teraz liczyc wartosc lewego sasiada, inaczej mowiac
liczymy pierwsza wartosc na lewo mniejsza od danej wartosci.
Niech y oznacza element na wierzcholku stosu.

Czytamy kolejne elementy.
Po wczytaniu kolejnego elementu x usuwamy elementy ze stosu dopoki x<y.
W tym momencie znajdujemy lewego sasiada x, jego wartoscia jest y.
Wrzucamy x na stos.

Zalozmy ze A jest permutacja liczb 1,2,..n. Wtedy mozliwy jest jeszcze inny algorytm liniowy.

Trzymamy elementy tablicy w liscie dwukierunkowej.

Dla k=n,n-1,..2 wykonujemy:
lewym sasiadem k zostaje jego poprzednik na liscie.
Nastepnie element k usuwamy z listy.

Algorytm 5. Najdalszy mniejszy sąsiad w permutacji

W tym algorytmie zakładamy że na wejściu jest permutacja A elementów od 1 do n.
Dla każdego \( i > 1 \) zdefiniujmy najdalszego mniejszego (prawego) sąsiada \( i \) jako
\( Najd\_Prawy[i] =max \{j>i : A[j] < A[i] \} \).

W trakcie algorytmu obliczamy tablicę Pozycja, będącą odwrotościa permutacji.
Załóżmy, że początkowo Najd_Prawy[i]=0, Pozycja[i]=0, dla każdego i.

Algorytm Najdalszy-Prawy-Mniejszy-Sąsiad

min:=1;
for i := 1 to n do
  Pozycja[A[i]]:=i;
  while min <= n and Pozycja[min] <> 0 do
     Najd_Prawy[Pozycja[min]]:=i;  min := min+1;

Algorytm ten dziła oczywiście w czasie liniowym. Jego wadą jest ograniczenie się do permutacji.

Algorytm 6. Najdłuższy malejący podciąg

Niech \( A[1], A[2],\ldots A[n] \) będzie ciągiem \( n \) dodatnich liczb.
Następujący algorytm oblicza długość najdłuższego malejącego podciągu (w kolejności od lewej do prawej strony).

Algorytm Najdłuższy-Malejący

wynik := 1;
for i := 1 to n do
  x := A[i]; A[i]:=0;
  k := min { j <= i : x  >= A[j]};
  A[k] := x; wynik := max(k, wynik);

Poprawność algorytmu nie jest całkowicie oczywista, uzasadnienie można znależć w rozwiązaniu stosownego zadania (patrz Ćwiczenia). Jeśli wejściem jest [5,2,1,3,7] to w momencie gdy algorytm kończy obliczenia, tablica A jest równa [7,3,1,0,0]. Zauważmy, że [7,3,1] wcale nie jest podciągiem (w kierunku od lewej do prawej strony) tablicy wejściowej. Niemniej wynik jest poprawny.

Złożoność alorytmu istotnie zależy od implementacji instrukcji:

\( k := min \{ j : x \ge A[j]\} \).

Ponieważ wszystko się odbywa w tablicy, możemy minimum policzyć łatwo w czasie logarytmicznym stosując szukanie binarne w posortowanej tablicy (segment tablicy \( A[1..i] \) jest posortowany). Zatem całkowity koszt algorytm jest \( O(n \log n) \) przy dosyć prostej implementacji.

Algorytm może, po niewielkim dodatkowym wysiłku procesora, podać najdłuższy malejący podciąg, albo też rozkład na minimalną liczbę podciągów niemalejących. Nie jest jasne, jak policzyć leksykograficznie minimalny i leksykograficznie maksymalny podciąg malejący o długości \( k \), gdzie \( k \) jest wynikiem powyższego algorytmu. Możemy się też zastanowić nad efektywnym algorytmem znajdowania liczby wszystkich takich ciągów długości \( k \).

Algorytm 7. Dwu-Pakowanie

Załóżmy, że mamy dowolnie dużą liczbę pudełek, każde o rozmiarze R, oraz n przedmiotów o rozmiarach \( r[1], r[2],\ldots r[n] \). Zakładamy, że \( R \ge r[1]\ge r[2]\ldots \ge r[n] \).

Mamy włożyć przedmioty do pudełek, co najwyżej dwa do jednego pudełka.

Pozostawiamy jako ćwiczenie analizę następującego algorytmu, który oblicza minimalną liczbę pudełek do zapełnienia.

Algorytm Dwu-Pakowanie

wynik := n;
for i := 1 to n do 
  if (i  <  wynik and r[i]+r[wynik] <= R) 
    wynik := wynik-1;

Algorytm 8. Równoważność cykliczna ciągów

Niech \( u,v \) będą całkowitoliczbowymi ciągami długości \( n \) zadanymi tablicami o zakresie [0..n-1]. Jest to wyjątek, z reguły poprzednio przyjmowaliśmy, że tablica zaczyna się od pozycji jeden.

Mówimy, że u, v sa cyklicznie równoważne gdy \( v\ =\ u[k+1.. n-1]u[0.. k] \) dla pewnego przesunięcia cyklicznego k.

Niech \( x \mod n \) oznacza resztę modulo n, np. dla \( n=9 \) mamy: \( 88 \mod n\ =\ 7 \) .

Naiwny algorytm sprawdzałby równość \( v\ =\ u[k+1.. n-1]u[0.. k] \) dla każego k, za każdym razem wykonując być może liniową liczbę operacji (w sumie kwadratową).

Następujący algorytm jest niewiele bardziej skomplikowany w porówaniu z naiwnym, działa w czasie liniowym i daje w wniku (zatrzymując się) wartość true wtedy i tylko wtedy gdy
ciągi są cyklicznie równoważne.

Algorytm Równoważność-Cykliczna

i:=-1; j:=-1;
while true do 
  if (i>n-1) or (j > n-1) then return false; k:=1; 
  while u[(i+ k) mod n]=v[(j+ k) mod n] and k <= n do k:=k+1;
  if k > n then return true;
  if u[(i+ k) mod n] > v[(j+ k) mod n] then i:=i+k else j:=j+k;

Problem poprawności jest tutaj znacznie bardziej skomplikowany niż dosyć oczywista złóżoność liniowa. Pozostawiamy to jako ćwiczenie.

Algorytm 9. Liczba inwersji permutacji

Niech \( P[0..n-1] \) będzie permutacją liczb \( 0,\ 1,\ 2\ ..n-1 \) zadaną tablicą o zakresie [0..n-1].
Liczbą inwersji jest liczba par \( i < j \) takich że \( P[i]>P[j] \).
Na przkład mamy 15 inwersji w permutacji

\( P[0..6]\ =\ [5,\ 4,\ 3,\ 6,\ 0,\ 1,\ 2] \)

Pomocniczą tablicą będzie \( Licz[0..n] \), załóżmy że początkowo zawiera ona same zera.
Funkcja logiczna \( odd() \) sprawdza czy liczba jest nieparzysta. Funkcja \( div \) jest dzieleniem całkowitoliczbowym, pomijamy resztę.
Funkcja \( \log( n) \) zwraca całkowitoliczbową część logarytmu przy podstawie 2, np. \( \log( 1025)\ =\ 10 \).

Końcową wartością zmiennej \( wynik \) jest liczba inwersji permutacji P.

Algorytm Liczba-Inwersji (algorytm Ryttera)

wynik:=0
repeat log n times
  for  i:=0  to  n-1 do
    if odd(P[i])  then Licz[P[i]]:=Licz[P[i]]+1  
      else wynik:=wynik+Licz[P[i]+1] ; 
  for i=0 to n-1 do
     Licz[i]:=0; P[i]:=P[i] div 2

Algorytm naiwny liczyłby wynik sprawdzając wszystkie pary \( i < j \), a więc w czasie kwadratowym.

Nasz algorytm liczy to w czasie \( O(n \log n) \). Złożoność jest oczywista, poprawność jest mniej oczywista.

Oznaczmy \( \delta(x)=x\ div\ 2,\ \ \delta^0(x)=x,\ \ \delta^{k+1}(x)=\delta(\delta^{k}(x)) \).
Poprawność algorytmu wynika z nastepujacego faktu:
dla każdych liczb naturalnych \( x < y \) istnieje dokladnie jedna liczba naturalna k taka że

\( \delta^k(x)+1=\delta^k(y)\ \ \textrm{oraz}\ \ odd(\delta^k(y)) \).

Funkcję dzielenia można łatwo wyeliminowac i pozostawić jedynie operacje arytmetyczne dodawania i odejmowania.

Przy okazji algorytmów sortowania można skonstruować kilka innych algorytmów dla tego samego probemu.
Możemy terza liczyć inwersję dla każdego ciągu elementów, niekoniecznie będącego permutacją.
Liczba zamian elementów w insertion-sort jest równa liczbie inwersji,
podobnie algorytm merge-sort możemy rozbudować tak aby liczył liczbę inwersji w czasie rzędu n log n.
Algorytmy inserion-sor, merge-sort poznamy w następnych modułach.
Ograniczymy się tutaj jedynie do algorytmu licznia inwersji między dwiema posortowanymi rosnąco tablicami \( A[1..n]\),\([1..n] \).

W poniższym algorytmie zakładamy że tablice A, B są posortowane rosnąco.
Wynikiem jest liczba par \( (i,j) \) taich,że \( A[i]>B[j] \).

Algorytm Inwersje-Między-AB

wynik:=0; i:=1; j:=1; ; 
while i  < = n do 
    if  j < =n and A[i] > B[j]  then j:=j+1; 
    else 
        wynik:=wynik+j-1; i:=i+1;

Algorytm 10. Generacja permutacji

Niech \( P[1..n] \) będzie permutacją liczb 1,2,..n. Oznaczmy przez \( P_0=[1,2,3\ldots n] \) permutację identycznościową.
Operacja \( rotacja(k,P) \) polega na rotacji cyklicznej pierwszych k elementów tablicy P: \( k \)-ty element wędruje na początek. Na przykład:

Następujący algorytm generuje wszystkie permutacje, każdą dokladnie raz.
Operacja \( wypisz \) wypisuje w kolejnym wierszu tablicę P.

Algorytm Generacja-Permutacji

P:= P_0;  j:=n; wypisz(P); 
while j > 1 do
  rotacja(j,P); 
  if  j <> P[j] 
        wypisz(P); j:=n;  
  else 
        j:=j-1

Algorytm ten ma następujacą ciekawą własność: jesli zdefiniujemy rotację jako operację odwrotna do tej którą mamy (pierwszy element wędruje
za \( k \)-ty element) to algorytm w dalszym ciągu jest poprawny: wypisuje dokładnie raz każdą permutację.

Mozna rozwazyc jeszcze prostsza operacje zmiany jednej permutacji w druga: wymiana elementu na pozycji 1-szej z elementem na pozyci k-tej.
Pokazac ze mozna wygenerowac wszystkie permutacje stosujac za kazdym razem pojedyncza operacje takiej zamiany.
Jednakze ten algorytm ma musi miec zupelnie inna strukture.
Na przyklad dla \( n=4 \) ciag pozycji k moze byc nastepujacy: 2 3 2 3 2 4 3 2 3 2 3 4 2 3 2 3 2 4 3 2 3 2 3 .

Rozważmy podobny algorytm do algorytmu Generacja-Permutacji generowania podzbiorów k-elemntowych (kombinacji)
zbioru n-elementowego, każda konfiguracja jest ciągiem K zerojedynkowym mającym dokładnie k jedynek.
Inaczej mowiąc chcemy wygenerowąc każdy taki ciąg dokładnie raz. K jest jednocześnie traktowane jako ciąg i jako tablica n-elementowa.

Oznaczmy przez SzukajWzorzec(01,K) długośc najkrótszego prefiksu ciągu K kończącego się na 01. Na przykład SzukajWzorzec(01,111100001001) = 9.

Algorytm Generacja-kombinacji

K := 1^k 0^(n-k);  j:=n-1; 
Załóżmy że 0 < k < n  
while  j < n  do 
  wypisz(K); rotacja(j+1,K); 
  j:= SzukajWzorzec(01,K)

Koszt zamortyzowany

Jeśli mamy ciąg operacji \( op_1,op_2,\ldots, op_n \), to koszt zamortyzowany jednej z nich jest sumarycznym kosztem wykonania wszystkich operacji podzielonym przez liczbę operacji. Inaczej mówiąc jest to, dla danego ciągu operacji, "średni" koszt jednej z nich. Zauważmy, że nie mówimy tu nic o prawdopodobieństwie - model jest deterministyczny. Na przykład w algorytmie Najbliższy-Mniejszy-Sąsiad rozważmy ciąg operacji

\( op_i \): while \( ( A[j] >= A[i])\ j = Lewy[j] \)

Koszt pojedynczej operacji może być liniowy, również sumaryczny koszt ciągu tych operacji \( op_1,op_2,\ldots, op_n \) jest liniowy. Zatem pesymistyczny koszt jednej operacji jest tutaj liniowy, natomiast zamortyzowany koszt jednej operacji jest ograniczony przez stałą. W tym przypadku wiemy, że każde sprawdzenie \( A[j]>=A[i]) \) z wynikiem negatywnym odbywa się tylko raz dla danej wartości \( j \). Możemy powiedzieć, że księgujemy koszt operacji elementom \( j \) o tej własności. Nieformalna metoda księgowania kosztów polega na rozdzielaniu (księgowaniu) kosztu, a następnie szacowaniu sumarycznej złożoności poprzez sumowanie wszystkich zaksięgowanych kosztów. Operacje pożyczają w pewnym sensie fundusze na pokrycie kosztów z różnych źródeł. Metoda ta będzie wykorzystana do analizy algorytmu dla interesującego problemu Find-Union.

Typowym przykładem liczenia kosztu w sposób zamortyzowany jest analiza generacji reprezentacji binarnych kolejnych liczb naturalnych od 0 do \( 2^n-1 \) przez dodawanie jedynki. W jednym kroku zastępujemy najdłuższy ciąg jedynek od końca zerami, następnie wstawiamy jedną jedynkę. Ponieważ w sumie wstawiliśmy \( 2^n-1 \) jedynek w ciągu \( 2^n- 1 \) operacji, to zamortyzowana liczba operacji zamiany zera na jedynkę wynosi 1.

Zasada magazynu. W ostatnim przykładzie możemy powiedzieć, że analizowaliśmy koszt tzw. metodą magazynu. W każdej operacji koszt jest proporcjonalny do liczby przedmiotów włożonych do magazynu lub do liczby przedmiotów wyjętych z magazynu. Magazyn początkowo jest pusty. Wtedy całkowity koszt jest proporcjonalny do liczby przedmiotów włożonych. W przypadku generowania liczb binarnych do magazynu wkładamy nowe jedynki, a wyjmujemy te jedynki, które zamieniamy na zera.

Potencjał - Fundusz Ubezpieczeń Kosztów Algorytmicznych

Metodę magazynu można uogólnić na tzw. metodę potencjału. Niech \( \Phi_i \) będzie pewną liczbą naturalną (włączając zero) odpowiadającą potencjałowi po wykonaniu \( i \)-tej operacji. Wyglądałoby to mniej tajemniczo, gdybyśmy zamiast \( \Phi(i) \) pisali \( Bilans(i) \).

Niech \( koszt(i) \) będzie rzeczywistym kosztem wykonania i-tej operacji.

Zakładamy, że potencjał jest początkowo zero, nigdy nie jest ujemny oraz że:

Wtedy całkowity koszt jest tego samego rzędu co \( \sum wplata(i) \). W naszych poprzednich przykładach rozmiar magazynu jest w tym sensie potencjałem.

Można powiedzieć obrazowo, że potencjał jest kapitałem Funduszu Ubezpieczeń Kosztów Algorytmicznych. Jeśli wszystkie wpłaty są takie same, to koszt zamortyzowany jednej operacji jest wpłatą (składką), którą ta operacja wpłaca do funduszu.

Operacja najpierw wpłaca swoją składkę, a następnie pobiera z funduszu tyle, żeby proporcjonalnie (być może z dokładnością do stałego współczynnika) zapłacić za swój koszt wykonania.

Dzięki temu, że wiele operacji pobiera z funduszu znacznie mniej niż wpłaca, niektóre operacje mogą jednorazowo pobrać dużą kwotę, którą płacą za koszt wykonania. Istotne jest jedynie, żeby Fundusz nie zbankrutował i kapitał nie zszedł poniżej zera. Możliwa jest również sytuacja, gdy Fundusz startuje z kapitałem początkowym. Wtedy kapitał ten wlicza się do całkowitego kosztu algorytmu, który się dodaje do sumy składek.

Rozważmy przykłady ilustrujące wykorzystanie potencjału. Najistotniejsze jest określenie składek.

Tablica dynamiczna

Przypuśćmy, że mamy dynamiczną tablicę. W każdym momencie wiemy, ile elementów w tablicy jest aktywnych, elementy nieaktywne zaznaczamy. W każdej operacji, jeśli liczba elementów nieaktywnych jest mniejsza od \( \frac{1}{4} \) wielkości tablicy, to tworzymy tablicę dwa razy mniejszą i tam przepisujemy elementy aktywne. Starą tablicę zwalniamy. W przeciwnym wypadku jeśli chcemy dodać element, który spowoduje przepełnienie tablicy, to całą tablicę kopiujemy do tablicy dwa razy większej. Początkowo tablica ma rozmiar 1. Zakładamy, że operacją dominującą jest kopiowanie aktywnego elementu do nowej tablicy. Jeśli mamy \( n \) operacji, to całkowity koszt kopiowania jest liniowy. Wystarczy w każdej operacji dać składkę 4 jednostek do Funduszu (potencjału). Wtedy koszt jednej dużej operacji przepisywania zamortyzuje się zmianą potencjału.

Zastąpienie kolejki dwoma stosami

Jedną kolejkę Q można zastąpić dwoma stosami \( S1,\ S2 \). Jeśli pierwszy element stosu lub kolejki w reprezentacji poziomej jest w ciągu na pierwszej pozycji (tzn. pobieramy \( e_1 \), stawiamy za \( e_n \)), oraz \( Q = (e_1,e_2,..,e_k) \), to dla pewnego \( j \) mamy:

\( S1 = (e_n,e_{n-1},...,e_j),\ S2 = (e_{1},e_{2}, ...,e_{j-1}) \).

Inaczej mówiąc, pierwszy element kolejki jest na wierzchołku drugiego stosu, a ostatni element kolejki jest na wierzchołku pierwszego stosu.

Operacja wstawiania do Q odpowiada wstawieniu elementu do \( S1 \), operacja pobrania z Q odpowiada pobraniu elementu z S2 z tym, że jeśli \( S2 \) jest pusty, to przepisujemy najpierw wszystkie elementy z S1 do S2. Niech operacją dominującą będzie jedna operacja stosowa (wstawienie lub pobranie pojedynczego elementu ze stosu). Wtedy ciąg \( n \) operacji kolejkowych, startujących od pustej kolejki, ma koszt liniowy w tej implementacji. Wystarczy, że każda operacja wkłada do Funduszu składkę 3 jednostek. Dowód tego pozostawiamy jako ćwiczenie.

Zastąpienie kolejki dwustronnej trzema stosami

Rozważmy podobny problem - z tym, że nasza kolejka jest dwustronna, możemy wkładać i pobierać element z każdego z dwóch końców kolejki. Wtedy możemy taką kolejkę zastąpić trzema stosami tak, że teraz również każda operacja kolejkowa będzie mieć zamortyzowany koszt stały. Elementy kolejki trzymamy w dwóch stosach S1, S2 tak, jak poprzednio. Niezmiennikiem jest to, że oba stosy są niepuste, lub mają w sumie co najwyżej jeden element. Zapewniamy zachodzenie niezmiennika wykorzystując trzeci stos. W momencie, gdy jeden ze stosów ma więcej niż jeden element, a drugi jest pusty, korzystając z trzeciego stosu, doprowadzamy do reprezentacji aktualnej kolejki przez stosy S1 i S2 tak, aby miały one tę samą liczbę elementów (z dokładnością do 1). Pozostawiamy jako ćwiczenie dowód (metodą potencjału) tego, że zamortyzowany koszt jest stały.

Ćwiczenia