Czy w rzeczywistych aplikacjach jest konkretna korzyść z używania algorytmów zamiast algorytmów ?
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.
Biorąc pod uwagę, że osobiście wolę BST niż drzewa VEB, co myślisz?
Można łatwo wykazać, że:
algorithms
complexity-theory
binary-trees
algorithm-analysis
search-trees
Ghassen Hamrouni
źródło
źródło
Odpowiedzi:
Nie zapominaj, że wciąż rośnie wykładniczo (w ) szybciej niż !logn log( n ) log( logn )
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 ⋅ log( n ) re⋅ 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.
źródło
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.
źródło
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ą
size
wstawki z losowymi liczbami w przedziale[0, bound]
, a następniesize
wyszukują, a następniesize
usuwają, a następnie ponowniesize
wyszukują. 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: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 przypadkulogn 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ć.
źródło