Pytania otagowane jako analysis-of-algorithms

3
Wykorzystanie złożoności Kołmogorowa jako wejściowego „rozmiaru”
SSSI(n)={w∈S:|w|=n}I(n)={w∈S:|w|=n}I(n) = \{w \in S : |w| = n\}nnnT(w)T(w)T(w)AAAwwwAAAfn=maxw∈I(n)T(w).fn=maxw∈I(n)T(w). f_n = \max_{w \in I(n)} T(w). Zdefiniujmy teraz zbiory wszystkich danych wejściowych o złożoności Kołmogorowa , i zdefiniujmy sekwencję Tutaj jest średnią sekwencją czasu pracy dla , z wyjątkiem przypadków, gdy „rozmiar” danych wejściowych jest złożonością Kołmogorowa, a nie ich długością.n …
1
Przyspieszenia wielomianowe z algorytmami opartymi na programowaniu półfinałowym
Jest to kontynuacja ostatniego pytania zadanego przez A. Pala: Rozwiązywanie programów półfinałowych w czasie wielomianowym . Nadal zastanawiam się nad faktycznym czasem działania algorytmów obliczających rozwiązanie programu półfinałowego (SDP). Jak zauważył Robin w swoim komentarzu do powyższego pytania, SDP-ów nie można ogólnie rozwiązać w czasie wielomianowym. Okazuje się, że jeśli …
6
Kiedy znaleźliśmy lepsze granice dla znanych algorytmów?
Czy istnieją interesujące przypadki algorytmów, które zostały opublikowane ze sprawdzonymi granicami i gdzie opublikowano później ściśle lepsze ograniczenia? Nie lepsze algorytmy z lepszymi granicami - oczywiście tak się stało! Ale lepsza analiza prowadząca do lepszego powiązania z istniejącym algorytmem Myślałem, że mnożenie macierzy jest tego przykładem, ale sam sobie z …
2
Losowy spacer i średni czas trafienia na prostym niekierowanym wykresie
Niech będzie prostym nieukierowanym wykresem na wierzchołkach i krawędziach.n mG=(V,E)sol=(V.,mi)G=(V,E)nnnmmm Próbuję określić czas oczekiwany prowadzeniem algorytmu Wilsona do generowania losowych rozpinające drzewo . Tam pokazano, że to , gdzie to średni czas uderzenia : gdzie:O ( τ ) τGsolGO(τ)O(τ)O(\tau)ττ\tauτ=∑v∈Vπ(v)⋅H(u,v),τ=∑v∈V.π(v)⋅H.(u,v),\tau = \sum_{v \in V} \pi(v) \cdot H(u, v), ππ\pi to rozkład …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.