Złożoność algorytmu tasowania Fishera-Yatesa

To pytanie dotyczy algorytmu Fishera-Yatesa służącego do zwracania losowego losowania danej tablicy. The Wikipedii mówi, że jego złożoność wynosi O (n), ale myślę, że jest to O (n log n).

W każdej iteracji i losowa liczba całkowita jest wybierana między 1 a i. Po prostu zapisywanie liczby całkowitej w pamięci to O (log i), a ponieważ istnieją iteracje, suma jest równa

O (log 1) + O (log 2) + ... + O (log n) = O (n log n)

co nie jest lepszym naiwnym algorytmem. Czy coś mi umyka?

Uwaga: Naiwnym algorytmem jest przypisanie każdemu elementowi losowej liczby w przedziale (0,1), a następnie posortowanie tablicy pod względem przypisanych liczb.

Podejrzewam, że tutaj, podobnie jak w przypadku większości algorytmów, zakłada się , że koszt odczytu i zapisu liczb bitów jest stały. To grzech niewielki, o ile nie da się ponieść emocjom i przypadkowo nie upaść P i PSPACE .$O(\log n)$

Standardowy model obliczeń zakłada, że ​​operacje arytmetyczne na liczbach całkowitych O (log n) mogą być wykonywane w stałym czasie, ponieważ operacje te są zwykle przekazywane sprzętowo. Tak więc w algorytmie Fishera-Yatesa „zapisanie liczby całkowitej i w pamięci” zajmuje tylko czas O (1).

Oczywiście analiza algorytmu pod kątem operacji bitowych jest całkowicie sensowna, ale model kosztów bitowych jest mniej przewidywalny dla rzeczywistych zachowań. Nawet prosta pętla for i = 1 to n: print(i)wymaga operacji bitowych O (n log n).

To odpowiedź na to, że „[algorytm Fishera-Yatesa] nie jest lepszy niż naiwny algorytm. Czy coś mi tu brakuje?” które zadałeś w pytaniu.

W twoim „naiwnym” algorytmie wykorzystującym liczby rzeczywiste: ile bitów dokładności używasz? Jeśli liczysz złożoność bitów (jak się wydaje robisz dla Fishera-Yatesa), a algorytm używa k losowych bitów dla liczb rzeczywistych, wówczas jego czas działania wyniósłby Ω (kn log n), ponieważ porównując dwa k- bitowe liczby rzeczywiste zajmują czas Ω (k). Ale k musi wynosić co najmniej Ω (log n), aby zapobiec odwzorowaniu dwóch elementów na tę samą liczbę rzeczywistą, co oznacza, że ​​algorytm przyjmuje Ω (n log ² n), który jest wolniejszy niż tasowanie Fishera-Yatesa o współczynnik log n.

Jeśli po prostu liczysz liczbę operacji arytmetycznych i porównawczych i ignorujesz ich złożoność bitów, to Fisher-Yates ma Θ (n), a twój algorytm to Θ (n log n), wciąż jest to współczynnik log n oddzielnie.

Dla tego problemu nie ma nic specjalnego w liczbach całkowitych.

Na przykład tabele skrótów (przechowujące dowolne wartości) nie mają czasu O (1) na dostęp, jeśli funkcja skrótu musi odczytać całą wartość, aby obliczyć swój skrót. n unikatowe elementy wymagają logarytmicznej reprezentacji każdego z bitów, bez względu na to, jak sprytna jest twoja reprezentacja, a każda funkcja haszująca, która odczytuje całe dane wejściowe, oblicza co najmniej tyle samo czasu. W praktyce są szybsze niż drzewa czerwono-czarne, ale asymptotycznie nie są lepsze.

Brouhaha, do którego odnosi się randomwalker, dotyczyło artykułu POPL 2008 ( http://portal.acm.org/citation.cfm?doid=1328438.1328460 ), omówionego tutaj: http://blog.computationalcomplexity.org/2009/05/shaving- logs-with-unit-cost.html

W tym poście Lance Fortnow opisuje, jak jako student skarżył się, że sortowanie naprawdę wymaga n log ^ 2 n czasu, jeśli musimy przeczytać wszystkie log n bity dwóch elementów, aby je porównać, co wydaje się rozsądnym zastrzeżeniem.

Strona Wikipedii mówi, że jego złożoność wynosi O (n), ale myślę, że jest to O (n log n).

W rzeczywistości O (n log n) stanowi dolną granicę tego problemu w modelach, w których sortowanie to O (n log n). Jeśli wszystkie permutacje są jednakowo prawdopodobne, to algorytm jako funkcja od losowych strumieni do permutacji musi być zaskakujący. Jest n! permutacje, więc w czymś takim jak model drzewa decyzyjnego istnieją gałęzie o długości co najmniej O (log n!) = O (n log n).

$1-\epsilon$$O(\epsilon)$

W TCS bierzemy pod uwagę - o ile nie zaznaczono inaczej - złożoność maszyny Turinga. Chociaż jest to przydatne do celów teoretycznych, wyniki nie są bardzo pomocne w praktyce, ponieważ wdrażamy różne modele maszyn (tj. Skończone przybliżenia) w sprzęcie. Jest zatem wykonalnym pytaniem o złożoność tych modeli. Na przykład zazwyczaj zakładamy, że maszyny rejestrów (podobne do rzeczywistych procesorów) mogą wykonywać operacje atomowe na dwóch rejestrach w stałym czasie - to mogło być tutaj zastosowane.

W skrócie: myślisz w kategoriach TM, autorzy artykułu w kategoriach RM. Oboje macie rację.