[Algorytmy] Algorytm wrażliwy i niewrażliwy

sinnervo · Post autor: **sinnervo** » 13 gru 2011, o 23:19

Mówi się, że algorytm jest naturalny jeżeli dla bardziej uporządkowanych danych szybciej porądkuje te dane (w przypadku algorytmów sortujących).

Co to znaczy, że algorytm jest wrażliwy/niewrażliwy? Mówi się,że algorym QuickSort jest wrażliwy. Czy chodzi o znaczną różnicę w złożonościach obliczeniowych pesymistycznych/optymistycznych/średnich?

Pozdrawiam,

Kartezjusz · Post autor: **Kartezjusz** » 14 gru 2011, o 10:07

Nie znam się,ale Quicksort ma to do siebie,że jeżeli dane są prawie uporządkowane,na przykład \(\displaystyle{ {1,2,3,4,10,5,6,7}}\)nie przeniesie dziesiątki na koniec,ale ,robałagani nam te ciąg do reszty.,Czyli algorytm jest niewrażliwy,jeśli z tego,że powinien mieć mało do zrobienia powinno wynikać,że mało robi...Nie wyrażę tego naukowo...

sinnervo · Post autor: **sinnervo** » 14 gru 2011, o 10:32

A więc o to chodzi, dzięki.