AiSD: lista 7, zadanie 4

Paweł Laskoś-Grabowski

nr indeksu 169827

29 maja 2006

1

Treść

n-elementowym ciągiem o jednym zaburzeniu nazywamy dowolny ciąg, który może być
otrzymany z ciągu {1, 2, . . . , n} poprzez wykonanie jednej transpozycji. Załóżmy, że al-
gorytm InsertSort będzie uruchamiany jedynie na ciągach o jednym takim zaburzeniu.
Zbadaj średnią złożoność algorytmu przy założeniu, że dla każdego n wszystkie takie ciągi
n-elementowe są jednakowo prawdopodobne.

2

Rozwiązanie

Przeanalizujmy przebieg działania algorytmu na ciągu

1, 2, . . . , i − 1, j, i + 1, . . . , j − 1, i, j + 1, . . . , n − 1, n,

zauważając, że działa on w czterech „fazach”:

1. Sortowanie elementów 1, 2, . . . , i−1, j. Ponieważ każdy kolejny rozpatrywany element

jest większy od poprzedniego, wykonuje się i − 1 porównań (pierwszego elementu nie
porównujemy z niczym).

2. Wsortowanie elementów i + 1, . . . , j − 1. Każdy z nich porównywany jest ze stoją-

cym na początku listy j, od którego jest mniejszy, a następnie ze stojącym za nim,
od którego jest większy, zatem dla każdego z j − i − 1 elementów wykonuje się 2
porównania.

3. Wsortowanie elementu i. Wstawiany element jest mniejszy od stojących na początku

listy i + 1, . . . , j − 1, j (j − i porównań), ale większy od stojącego za nimi i − 1 –
ogółem j − i + 1 porównań.

4. Dosortowanie elementów j + 1, . . . , n − 1, n. Tu znów na początku listy zawsze stoi

element mniejszy od wsortowywanego, zatem wykonuje się po 1 porównaniu dla
każdego z n − j elementów.

Po zsumowaniu dostajemy koszt T (i, j) = n + 2(j − i − 1).

Subtelnie inny wynik otrzymamy, gdy i = 1. Tu fazy działania algorytmu są nastę-

pujące:

1. Wstawienie j. 0 porównań.

2. Wsortowanie elementów i + 1, . . . , j − 1. Pierwszy z nich porównywany jest raz (tylko

z j), następne – po 2 razy (z j oraz następnym na liście, na którym się „zatrzymują”).
Razem – 2(j − 3) + 1 porównań.

1

3. Wsortowanie elementu i. Porównujemy go ze wszystkimi już znajdującymi się na

liście, gdyż są od niego większe – j − 1 porównań.

4. Dosortowanie pozostałych elementów. Tak jak poprzednio, wykonuje się n − j po-

równań.

Koszt sumaryczny wynosi teraz T (1, j) = n + 2(j − 3). Ostatecznie zatem

T (i, j) =

(

n + 2(j − i − 1)

dla i>1,

n + 2(j − i − 1) − 2 dla i=1.

(1)

Aby policzyć średnią złożoność algorytmu, należy teraz zsumować wszystkie T (i, j) dla
1 ¬ i < j ¬ n (z równymi wagami, bo każdy ciąg – czyli każdą parę transponowanych
indeksów i, j – uznajemy za równo prawdopodobną), i podzielić przez ilość różnych ciągów,
czyli

n

2

. Zatem

S =

n−1

X

i=1

n

X

j=i+1

T (i, j) =

n

X

j=2

(n + 2(j − 1 − 1) − 2) +

n−1

X

i=2

n

X

j=i+1

(n + 2(j − i − 1)) =

=

n−1

X

i=1

n

X

j=i+1

(n + 2(j − i − 1)) − 2(n − 1) =

=

n−1

X

i=1





(n − 2i − 2)(n − i) + 2

n

X

j=i+1

j





− 2(n − 1) =

=

n−1

X

i=1



(n − 2i − 2)(n − i) + 2

(n + i + 1)(n − i)

2



− 2(n − 1) =

=

n−1

X

i=1

((n − i)(2n − i − 1)) − 2(n − 1) =

=

n−1

X

i=1

(2n

2

− n + i(1 − 3n) + i

2

) − 2(n − 1) =

= (2n

2

− n)(n − 1) + (1 − 3n)

n−1

X

i=1

i +

n−1

X

i=1

i

2

− 2(n − 1) =

= (2n

2

− n)(n − 1) + (1 − 3n)

(n − 1)n

2

+

(n − 1)n(2n − 1)

6

− 2(n − 1) =

=

5

6

n

3

−

3

2

n

2

−

4

3

n + 2.

(2)

Średnia złożoność wynosi zatem

S(n) =

2S

n(n + 1)

'

5

3

n,

(3)

gdzie pominęliśmy wyrazy niższych rzędów.

2