Dla danych wejściowych o rozmiarze n, dla których wartości n powoduje wstawianie-sortowanie bitowe-sortowanie?

Question

W książce Wprowadzenie do algorytmów (Corman) ćwiczenie 1.2-2 zadaje następujące pytanie dotyczące porównywania implementacji sortowania i scalania sortowania. W przypadku danych wejściowych o rozmiarze n sortowanie w trybie wstawiania odbywa się w krokach 8n^2, podczas gdy sortowanie w trybie scalonym przebiega w odstępach 64 ng n; dla których wartości n sortowanie sortowania bitowego sortuje sortowanie?

Mimo że jestem zainteresowany odpowiedzią, jestem bardziej zainteresowany tym, jak znaleźć odpowiedź krok po kroku (tak, że mogę powtórzyć proces, aby porównać dwa dowolne algorytmy, jeśli to w ogóle możliwe).

Na pierwszy rzut oka ten problem wydaje się podobny do znalezienia punktu zerowego w biznesie-rachunku, klasie, którą zabrałem ponad 5 lat temu, ale nie jestem pewien, więc każda pomoc byłaby doceniona.

Dziękuję

P/S Jeśli moje tagi są błędne, to pytanie jest błędnie sklasyfikowane, lub jakaś inna konwencja jest nadużywane są tu proszę ograniczyć chastising do minimum, jak to jest mój pierwszy raz, kiedy publikuję pytanie.

Answer 1

Ponieważ jesteś znaleźć podczas uderzeń Sortowanie przez wstawianie sortowanie przez scalanie

8n^2<=64nlogn 
n^2<=8nlogn 
n<=8logn 

na rozwiązywaniu n-8logn = 0 masz

n = 43.411 

Więc dla n<=43 Sortowanie przez wstawianie działa lepiej niż seryjnej rodzaju.