Nie bogobogosort
Sposób, w jaki zaimplementowałeś swojego bogobogosort, jest w rzeczywistości szybszy niż bogosort, ponieważ z kilku powodów:
-
Po pomyślnym posortowaniu elementów k od razu sprawdzasz, czy k+1 elementy są sortowane. Oznacza to, że jeśli podczas poprzedniego losowego tasowania zdarzyło Ci się pomieszać m elementy w kolejności, to po posortowaniu pierwszych dwóch elementów natychmiast dotrzesz do m.
Załóżmy na przykład, że osiągniesz 5 kart, a następnie przegrywasz. Tasujesz 5 kart, a następnie zaczynasz od nowa od 2. Jeśli zdarzy się, że te 5 kart będzie posortowanych, natychmiast osiągniesz 6, gdy tylko ułożysz pierwsze 2 karty w kolejności.
-
Ze względu na punkt 1, twój bogobogosort jest w rzeczywistości szybszy niż bogosort, ponieważ musi sortować tylko n-1 karty zamiast n . Po posortowaniu kart n-1 sprawdza kolejność kart n i może się nie powieść. Jednak w przypadku niepowodzenia przetasowuje karty n, tak że za każdym razem, gdy sortuje karty n-1, ma 1/n szansa na ostateczny sukces. Tak więc całkowita liczba tasowanych kart jest rzędu (n-1) * (n-1)! * n, co upraszcza do (n-1) * n!, w porównaniu z bogosortem, który tasuje n * n! karty.
Uważam, że ta sama zasada obowiązuje na każdym kroku, więc czas jest nawet krótszy niż (n-1) * n!. Nie jestem pewien dokładnej matematyki, ale po uruchomieniu programu wydaje się, że bogobogosort działa mniej więcej w tym samym czasie co bogosort z jedną mniejszą liczbą kart. Tj. Your_bogobogosort (n) = bogosort (n-1).
Właściwy bogobogosort
Przepisałem twoją funkcję bogobogosort tak, aby wyglądała następująco:
unsigned long bogobogosort(int *data, size_t n) { unsigned long c = 0; size_t b = 2; while (1) { if (sorted(data, b)) { if (b == n) break; b++; } else { b = 2; } c += b; shuffle(data, b); } return c; }
Kluczowa różnica polega na tym, że po każdym sukcesie, w którym zwiększa się b, przetasowuje talię, aby zapobiec wystąpieniu punktu 1 powyżej. Dzięki tej zmianie otrzymuję następujący wynik:
% ./a.out 6 bogosort shuffled 1044 cards in 0.000013 seconds. bogobogosort shuffled 54464568 cards in 0.500339 seconds.
Komentarze