[Teoria złożoności] Złożoność quicksort

[moniac91]

1. Podaj i udowodnij oszacowanie górne na pesymistyczny czas działania algorytmu quicksort

2. Sformułuj twierdzenie o ograniczeniu dolnym na złożoność pesymistyczną algorytmu sortującego za pomocą porównań i podaj szkic dowodu.

Czy w przypadku 1 to \(\displaystyle{ O(n^{2})}\) ?
Jak jest zatem w przypadku 2? Nie mogę znaleźć nigdzie ani twierdzenia ani dowodu.

[norwimaj]

2. Załóżmy, że mamy do posortowania liczby \(\displaystyle{ x_1,x_2,\ldots,x_n}\). Ograniczmy rozważania jedynie do ciągów różnowartościowych. Na algorytm sortujący przez porównania można patrzeć jak na drzewo binarne. Na początku algorytm zadaje jakieś pytanie, na przykład "czy \(\displaystyle{ x_3>x_6}\)?". To jest pytanie w korzeniu drzewa. W zależności od odpowiedzi algorytm przechodzi do jednego albo drugiego poddrzewa. Na przykład jedna gałąź w drzewie dla \(\displaystyle{ n=3}\) może wyglądać tak:

Czy \(\displaystyle{ x_1<x_2}\)? T
Czy \(\displaystyle{ x_2<x_3}\)? N
Czy \(\displaystyle{ x_1<x_3}\)? T
Odp: \(\displaystyle{ x_1<x_3<x_2}\).

Możliwych odpowiedzi (czyli liści w drzewie) jest \(\displaystyle{ n!}\). Jaka więc musi być co najmniej wysokość drzewa?

[Afish]

1. Tak.
2. Twierdzenie i dowód jest w Cormenie, zapewne w sieci też da się go znaleźć.