Logarytmiczna vs podwójna logarytmiczna złożoność czasu

Czy w rzeczywistych aplikacjach jest konkretna korzyść z używania algorytmów zamiast algorytmów ?$\mathcal{O}(\log(\log(n))$$\mathcal{O}(\log(n))$

Dzieje się tak, gdy na przykład używa się drzew van Emde Boasa zamiast bardziej tradycyjnych implementacji drzewa wyszukiwania binarnego. Ale na przykład, jeśli weźmiemy to w najlepszym przypadku podwójny algorytm logarytmiczny przewyższa algorytm logarytmiczny (około) współczynnik . A także ogólnie wdrożenie jest trudniejsze i bardziej złożone.$n < 10^6$$5$

Biorąc pod uwagę, że osobiście wolę BST niż drzewa VEB, co myślisz?

Można łatwo wykazać, że:

$\qquad \displaystyle \forall n < 10^6.\ \frac{\log n}{\log(\log(n))} < 5.26146$

Nie zapominaj, że wciąż rośnie wykładniczo (w ) szybciej niż !$\log n$$\log(n)$$\log(\log n)$

Rzeczywiście, jeśli spojrzymy na iloraz i , to nie jest zbyt imponujące, aby zobaczyć:$\log(n)$$\log(\log(n))$

^{[ źródło ]}

Ale nadal dostajesz współczynnik od pięciu do sześciu dla rozmiarów do . Zauważ, że większe rozmiary nie są rzadkie w praktyce, a przyspieszenie przez ten czynnik jest niesamowite ! Może mieć znaczenie różnica między uzyskaniem wyników po obiedzie a dopiero jutro. Pamiętaj, że część przyspieszenia może zostać pochłonięta przez wyższe stałe implementacji drzewa; musisz wykreślić (lub przeanalizować) i pomocą rzeczywistych stałych środowiska uruchomieniowego, aby uzyskać prawdziwy obraz.$100000$$c\cdot \log(n)$$d\cdot \log(\log(n))$$c,d$

Dodatkowo ważne jest to, o czym wspomina Dave: jeśli tak przyspieszona operacja jest wykonywana, powiedzmy, liniowo, stałe przyspieszenia stają się przyspieszeniami liniowymi, tzn. Możesz zmniejszyć wiodącą stałą całego algorytmu! Jak powiedziałem powyżej, to jest niesamowite. Wystarczy spojrzeć na to, co się stanie, jeśli uruchomisz operację razy:$n$

^{[ źródło ]}

Teraz, jeśli to nie jest warte kłopotu, nie wiem co.

Można sobie wyobrazić, że różnica w złożoności naprawdę nie ma tak wielkiego znaczenia, a faktyczny czas pracy jest ważniejszy. Ale jeśli algorytm jest rdzeniem innego algorytmu, różnica ta może być ważna.

Z czysto teoretycznego celu różnica oczywiście ma znaczenie, szczególnie jeśli algorytm jest częścią innego. Może umieścić większy algorytm w innej klasie złożoności.

Właściwie to kiedyś sam porównałem drzewo van Emde-Boasa. Porównałem to z drzewem AA, mapą skrótów i tablicą bitów.

Testy wykonują sizewstawki z losowymi liczbami w przedziale [0, bound], a następnie sizewyszukują, a następnie sizeusuwają, a następnie ponownie sizewyszukują. Usuwania są również wykonywane na liczbach losowych, więc najpierw musisz dowiedzieć się, czy w ogóle są w strukturze.

Oto wyniki ( size= 2000000, bound= 10000000) w sekundach:

AATreeLookup - O(n log n)
Inserting... 3.3652452
Searching... 5.2280724
Deleting...  7.3457427
Searching... 9.1462039
HashLookup - O(n) expected
Inserting... 0.3369505
Searching... 0.6223035
Deleting...  0.9062163
Searching... 1.1718223
VanEmdeBoasTree - O(n log log n)
Inserting... 0.7007531
Searching... 1.1775800
Deleting...  1.7257065
Searching... 2.2147703
ArrayLookup - O(n)
Inserting... 0.0681897
Searching... 0.1720300
Deleting...  0.2387776
Searching... 0.3413800

Jak widać, drzewa van Emde-Boasa są około dwa razy wolniejsze niż mapy haszujące, dziesięć razy wolniejsze niż tablice bitów i 5 razy szybsze niż drzewa wyszukiwania binarnego.

Oczywiście powyższe wymaga wyłączenia odpowiedzialności: testy są sztuczne, możesz ulepszyć kod lub użyć innego języka w kompilatorze, którego dane wyjściowe są szybsze, i tak dalej.

To wyłączenie odpowiedzialności stanowi sedno powodu, dla którego wykorzystujemy analizę asymptotyczną w projektowaniu algorytmów: ponieważ nie masz pojęcia, jakie są stałe, a ponieważ stałe mogą się zmieniać w zależności od czynników środowiskowych, najlepszą rzeczą, jaką możemy zrobić, jest analiza asymptotyczna.

Teraz w przypadku $\log n$ przeciw $\log \log n$: w powyższym przykładzie moje drzewo van Emde-Boasa jest w stanie pomieścić $2^{32}$ elementy. $\log 2^{32} = 32$, i $\log 32 = 5$, co stanowi poprawę współczynnika 6, co w praktyce jest dość duże. Dodatkowo drzewa van Emde-Boasa mają dobre stałe czynniki (w praktyce chodzi o stałe czynniki w przypadku tak małych różnic), ponieważ nie muszą się równoważyć.