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

9

Czy w rzeczywistych aplikacjach jest konkretna korzyść z używania algorytmów zamiast algorytmów ?O(log(log(n))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<1065

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

Można łatwo wykazać, że:

n<106. lognlog(log(n))<5,26146

Ghassen Hamrouni
źródło
w zasadzie powinieneś spojrzeć na stałe zaangażowane w algorytm dla mniejszej wartości / wielkości danych wejściowych. Idealnie chcielibyśmy, aby były małe.
singhsumit
3
Zwróć uwagę, że wprowadzono wiele ulepszeń od drzew VEB, w wysokości w strukturach danych w pamięci RAM z złożonością wyszukiwania / wstawiania / usuwania bez randomizacji (deterministyczny) i z randomizacją. Zobacz Sortowanie deterministyczne w Czas i przestrzeń liniowa. autor: Han i Oczekiwany czas i przestrzeń liniowa. Han i Thorup. O(losol losol n)O(losol losol n)O(n losol losol n)O(losol losol n)
AT
W prawdziwym świecie współczynnik 5 jest dość znaczący, a liczba przedmiotów może często wynosić 10 ^ 9, a nawet 10 ^ 12.
RBarryYoung

Odpowiedzi:

10

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

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

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.100000dolog(n)relog(log(n))do,re

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

n * log (n) / (n * log (log (n)))
[ źródło ]

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

Raphael
źródło
6

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.

Dave Clarke
źródło
6

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 logn przeciw loglogn: w powyższym przykładzie moje drzewo van Emde-Boasa jest w stanie pomieścić 2)32 elementy. log2)32=32, i log32=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ć.

Alex ten Brink
źródło
Może wskocz do R (lub odpowiednika) i wygeneruje ładne wykresy (jak zrobił @Raphael).
Dave Clarke
1
Poprawi to twoją odpowiedź, jeśli powiążesz te algorytmy z pojęciami logn i loglogn
Dave Clarke
@DaveClarke: dzięki za sugestie. Niestety jestem dość kiepski w tworzeniu ładnych zdjęć - myślę, że moja edycja poprawiła czytelność moich wyników.
Alex ten Brink
Prawdopodobnie nie ma wystarczającej ilości danych do prawidłowego zdjęcia. Nie ważne ... ale nauka robienia dobrych zdjęć to przydatna umiejętność.
Dave Clarke