Kopiec dwumianowy - poszukiwanie błędu w implementacji

0

Hej,

Zaimplementowałem 3 kopce by porównać czasy ich działania na moim komputerze a przy okazji sprawdzenie na ile teoretyczna złożoność czasowa zgadza się z praktyką, i tu pojawia się problem.

Kopiec dwumianowy działa zdecydowanie wolniej od pozostałych, o ile przy niewielkich dych nie odstaje zbyt wiele od reszty, o tyle np przy 200 mb danych wejściowych, 20 000 wierzchołków, 10 000 000 połączeń, sytuacja przedstawia się tak:

Przy Dijkstrze:
Kopiec | Czas
Binarny | 0,782176s
Fibonacci | 1,020952s
Dwumianowy | 12,581656s

Usuwanie największej wartości z kopca wygląda tak:
Kopiec | Czas
Binarny | 0,011849s
Fibonacci | 0,048943s
Dwumianowy | 5,858372s

Pytanie jest następujące, czy takie rozbieżności są dopuszczalne, czy jest to efekt błędu w implementacji?

0

Odpal profiler i zobacz co zjada ci tyle czasu, bo rzędy wielkości różnicy zwykle oznaczają błąd (czasem głupi).

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0