Analiza złożoności czasu dla algorytmu UST-CONN Reingolda

Jaka jest dokładna złożoność czasowa niekierowanego algorytmu przestrzeni logów st-connectivity autorstwa Omer Reingold?

Wydaje się, że złożoność czasowa algorytmu Reingolda nie jest rozpatrywana ani w pracy Reingolda, ani w podręczniku Arora-Baraka. Wydawałoby się również, że analiza jest dość nużąca, ponieważ złożoność czasowa zależy od dokładnego wykresu ekspandera zastosowanego w konstrukcji oraz od niektórych stałych, które są wybierane jako „wystarczająco duże”.

Aby uzyskać ogólne pojęcie o złożoności czasowej, należy zauważyć, że algorytm Reingolda, biorąc pod uwagę wykres , przekształca go (domyślnie) w wykres ekspandera G ′ i przemierza każdy krok długości l = O ( log n ) . The O -notation ukrywa niektóre dość duże stałe tutaj. Wykres G ' ma stałą stopień d = 2 , b jakiegoś wystarczająco dużej B , co oznacza, że istnieje d L = O ( N C ) takie spacery jakiegoś dość dużą stałą$G$$G'$$l = O(\log n)$$O$$G'$$d = 2^b$$b$$d^l = O(n^c)$ . Przeglądając niektóre notatki z wykładu na ten temat, wydaje się, że c ≥ 10 9 b .$c$$c \ge 10^9b$