Jestem dość pewny, że autor komiksu jest w błędzie. Poniżej znajduje się bardziej formalna analiza algorytmu.
Na początek będziemy musieli ustalić podstawowe zasady dotyczące tego, jak żaby jedzą muchy. Zakładam, że wszystkie żaby mogą jeść muchy w stałym tempie r. Oznacza to, że żaba potrzebuje sekund, aby zjeść jedną muchę, 10 sekund dla żaby, aby zjeść dziesięć much itp. Następnie, zróbmy (rozsądne) założenie, że wszystkie żaby jedzą równolegle. Przyjmiemy również, że potrzeba czasu j, aby żaba wyskoczyła z pustego pudełka.
Musimy również uwzględnić czas konfiguracji. Załóżmy, że mamy pod ręką nieograniczony zapas much, żab i pudełek, i powiedzmy, że potrzeba czasu b, aby uzyskać pudełko i czas na włożenie jednej muchy do pudełka. Na koniec zakładamy, że potrzeba czasu na umieszczenie żaby w pudełku. Dla uproszczenia przyjmiemy, że żaby nie zaczynają jeść much, dopóki wyraźnie tego nie zalecimy, aby żaby umieszczone w pudełkach przed innymi żabami nie stały się strzałem w dziesiątkę.
Jeden ostatni szczegół - załóżmy, że potrzeba czasu na zapisanie numeru.
W tym przypadku środowisko wykonawcze tego algorytmu jest podane w następujący sposób. Przypuśćmy, że nasza lista numerów do sortowania to x , x , ..., x n. W takim przypadku ilość czasu potrzebna do skonfigurowania wszystkich skrzynek będzie wynosić n (b + f) + y (Σ x i). Powodem tego jest to, że musimy uzyskać n boksów i umieścić jedną żabę w każdym pudełku (stąd pierwszy termin) plus jednostki czasu dla każdej z much (stąd drugi termin).
W ramach algorytmu, musimy zapisać każdy numer dokładnie raz, gdy żaba wyskakuje z pudełka. Oznacza to, że w całym algorytmie wykonamy pracę zapisując posortowaną sekwencję.
Wreszcie, musimy zastanowić się, jak długo trwają wszystkie żaby. Ponieważ wszystkie żaby jedzą równolegle, wszystko, co musimy zadbać, to żaba, która ma najwięcej much do zjedzenia. Ta żaba będzie miała muchy do zjedzenia, gdzie x maks. jest maksymalną liczbą na liście wejściowej. Dlatego czas spędzany przez żaby na robienie jedzenia jest określony przez r x max. Factoring w skoku podjętym przez ostatnią żabę, wszystkie żaby pracują równolegle, będą wspólnie kończyć w rx max + j czas.
Oznacza to, że całkowity czas dla algorytmu jest przez
n (f + b) + Y Σ x i + NW + RX maks + J.
Jeśli teraz przyjmiemy, że "jedna jednostka pracy" wystarczy, aby wykonać jedną z indywidualnych operacji (żaba może zjeść muchę, wyskoczyć z pudełka lub umieścić żabę w pudełku, itd.), przy czym całkowity czas wymagany jest co najwyżej
n + Σ (x i) + x maks + 1
Stwierdzając, że x maks ≤ Σ x i, otrzymujemy, że całkowity czas pracy tego algorytmu jest Θ (n + Σ x i). Innymi słowy, środowisko wykonawcze jest proporcjonalne zarówno do liczby liczb do posortowania, jak i całkowitego rozmiaru sortowanych liczb.
Zauważ, że to środowisko wykonawcze nie ma żadnych logarytmy w nim, więc od razu możemy stwierdzić, że analiza Runtime autora jest błędna.
Na koniec zauważ, że jest to naprawdę zły algorytm sortowania. Algorytm counting sort może sortować n liczb naturalnych w czasie O (n + U), gdzie U jest maksymalną wartością do posortowania, która jest asymptotycznie lepsza niż FrogSort. Algorytm radix sort mógłby to zrobić w czasie O (n lg U), który jest lepszy dla dużych wartości U. Potem znowu oba algorytmy wymagają wyrafinowanych mechanizmów, które prawdopodobnie nie istniałyby w otoczeniu opisanym przez komiks.
Mam nadzieję, że to pomoże!
Jeśli masz duży stopień paralelizmu, pobudzenie O (n) do sortowania może być teoretycznie możliwe dzięki Sortowanie snu – templatetypedef
W szczególności: Ponieważ sieci sortujące (http: //en.wikipedia .org/wiki/Sorting_network) istnieją z głębokością O (log n), powinno być możliwe sortowanie n liczb w czasie O (log n), jeśli masz n procesorów wszystkich działa równolegle. – templatetypedef
Sortowanie snu także przyszło mi do głowy, kiedy czytałem historię. +1 –