Czy występują problemy, których najbardziej znany algorytm ma czas działania

Nigdy wcześniej nie widziałem algorytmu z logiem w mianowniku i zastanawiam się, czy w tym formularzu są jakieś przydatne algorytmy?

Rozumiem wiele rzeczy, które mogą powodować mnożenie współczynnika logu w czasie wykonywania, np. Algorytmy sortowania lub oparte na drzewach, ale co może powodować dzielenie przez współczynnik log?

Zwykła odpowiedź na „co może spowodować podział przez log?” to połączenie dwóch rzeczy:

1. model obliczeń, w którym dozwolone są operacje arytmetyczne o stałym czasie na liczbach całkowitych wielkości słowa, ale w których chcesz zachować ostrożność co do długości słów, więc przyjmij $O(\log n)$ bitów na słowo (ponieważ dowolne mniej niż to a nawet nie można było zająć się całą pamięcią, a także dlatego, że algorytmy korzystające z wyszukiwania tabel zajęłyby zbyt dużo czasu na ustawienie tabel, gdyby słowa były dłuższe), i
2. algorytm, który kompresuje dane poprzez upakowanie bitów na słowa, a następnie działa na nich.

Myślę, że istnieje wiele przykładów, ale klasycznym przykładem jest algorytm Czterech Rosjan dla najdłuższych typowych podsekwencji itp. W rzeczywistości kończy się na , ponieważ wykorzystuje ideę pakowania bitów, ale następnie oszczędza sekundę Współczynnik logowania przy użyciu innego pomysłu: zastąpienie bloków operacji bitowych O ( log 2 n ) pojedynczym przeglądaniem tabeli.$O(n^2/\log^2 n)$$O(\log^2 n)$

Kostka Rubika jest bardzo naturalnym (i dla mnie nieoczekiwanym) przykładem. $n\times n\times n$ kostki wymagają $\Theta(n^2/\log n)$ kroki w celu rozwiązania. (Zauważ, że jest to notacja theta, więc jest to ciasna górna i dolna granica).

Jest to pokazane w tym artykule [1].

Warto wspomnieć, że złożoność rozwiązywania określonych przypadków kostki Rubika jest otwarta, ale przypuszcza się, że jest NP-twarda (omówione tutaj na przykład) NP twarda [2]. $\Theta(n^2/\log n)$ algorytm zapewnia rozwiązanie, a to zapewnia, że wszystkie roztwory są asymptotycznie optymalny, ale może nie rozwiązywać konkretne przykłady optymalnie. Twoja definicja przydatności może tutaj obowiązywać, ale nie, ponieważ kostki Rubika na ogół nie są rozwiązywane za pomocą tego algorytmu (algorytm Kociemby jest ogólnie stosowany w przypadku małych kostek, ponieważ daje szybkie, optymalne rozwiązania w praktyce).

[1] Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Anna Lubiw i Andrew Winslow. Algorytmy rozwiązywania kostek Rubika. Materiały z 19. dorocznego europejskiego sympozjum na temat algorytmów (ESA 2011), 5–9 września 2011 r., Strony 689–700

[2] Erik D. Demaine, Sarah Eisenstat i Michaił Rudoy. Optymalne rozwiązanie Kostki Rubika jest zakończone NP. Materiały z 35. międzynarodowego sympozjum na temat teoretycznych aspektów informatyki (STACS 2018), 28 lutego – 3 marca 2018 r., Strony 24: 1-24: 13.

Przykładem pokazującym się w mianowniku bez sztuczek upakowania bitów jest niedawny artykuł Agarwal, Ben Avraham, Kaplan i Sharir na temat obliczania dyskretnej odległości Frécheta między dwoma łańcuchami wielokątnymi w czasie O ( n 2 log log n / log n ) . Chociaż nie znam szczegółów algorytmu, jedną ogólną sztuczką jest podzielenie danych wejściowych na względnie małe kawałki, a następnie sprytne połączenie odpowiedzi (oczywiście brzmi to jak dzielenie i podbijanie, ale nie dostajesz log n w mianowniku z kilkoma sprytnymi sztuczkami)$\log n$$O(n^2\log\log n/\log n)$

Nie do końca to, o co prosiłeś, ale sytuacją „na wolności”, w której w mianowniku pojawia się współczynnik logarytmiczny, jest artykuł „ Kamyki i programy rozgałęziające do oceny drzew” Stephen Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman i ” i Rahul Santhanam.

Problem oceny drzewo (TEP) wynosi: otrzymuje -ary drzewo uwagami z wartościami w { 1 , ... , k } na liście i funkcji { 1 , ... , k } d → { 1 , ... , k } na węzłach wewnętrznych oceń drzewo. Tutaj każdy węzeł wewnętrzny pobiera wartość swojej funkcji z adnotacjami do wartości swoich potomków. Jest to prosty problem, a chodzi o to, aby pokazać, że nie można go rozwiązać w przestrzeni logarytmicznej (gdy wysokość drzewa jest częścią danych wejściowych). W tym celu jesteśmy zainteresowani rozmiarem programów rozgałęziających rozwiązujących TEP.$d$$\{1,\ldots,k\}$$\{1,\ldots,k\}^d \to \{1,\ldots,k\}$

W rozdziale 5 przedstawiono ścisłe ograniczenia dla drzew o wysokości 3, zarówno dla TEP, jak i dla pokrewnego problemu BEP, w którym dane wyjściowe są zwinięte do w dowolny arbitralny sposób. W przypadku TEP granica wynosi Θ ( k 2 d - 1 ) , podczas gdy dla BEP granica wynosi Θ ( k 2 d - 1 / log k ) , tzn. Uzyskuje się zapis log k .$\{0,1\}$$\Theta(k^{2d-1})$$\Theta(k^{2d-1}/\log k)$$\log k$

Mimo że nie chodzi o środowisko uruchomieniowe, pomyślałem, że warto wspomnieć o klasycznym wyniku Hopcroft, Paul i Valiant: [1], ponieważ wciąż jest w duch „co może spowodować, że uratujesz$\mathsf{TIME[t]} \subseteq \mathsf{SPACE}[t/\log t]$ współczynnik log”.

To daje wiele przykładów problemów, których najlepiej znana górna granica złożoności przestrzeni ma log w mianowniku. (W zależności od twojego punktu widzenia, uważam, że albo czyni ten przykład bardzo interesującym - co za niesamowite twierdzenie! - albo bardzo nieciekawym - prawdopodobnie nie jest „faktycznie przydatny”.)

[1] Hopcroft, Paul i Valiant. Na czas kontra przestrzeń . J. ACM 24 (2): 332–337, 1977.

$\Theta(n/\log n)$

• Problem z ważeniem monet ze skalą sprężynową.
• Mastermind z pozycją n i 2 kolorami.

The best known algorithm for computing the edit (a.k.a. Levenshtein) distance between two strings of length $n$ takes $O((n/\log n)^2)$ time:

William J. Masek, Mike Paterson: A Faster Algorithm Computing String Edit Distances. J. Comput. Syst. Sci. 20(1): 18-31 (1980).

$\Theta(n/\log n)$ pojawia się jako poprawna granica problemu rozpatrywanego przez Grega i Paula Valianta (brak połączenia z trikami bitowymi):

Gregory Valiant i Paul Valiant, Moc estymatorów liniowych, 2011. W 52. dorocznym sympozjum IEEE na temat podstaw informatyki, FOCS 2011.

Oto kolejny przykład ścisłego powiązania mającego współczynnik logarytmiczny. (To jest twierdzenie 6.17 z Boolean Function Complexity: Advances and Frontiers autorstwa Stasys Jukna.)

Rozmiar formuły (ponad pełną podstawę binarną lub podstawę De Morgana) problemu odróżnialności elementu wynosi $\Theta(n^2/\log n)$, where $n$ is the number of bits in the input.

The reason the log factor appears in the denominator is that representing $m$ integers between 1 and $\text{poly}(m)$ requires $n := O(m \log m)$ bits in total, since each integer requires $O(\log m)$ bits. So an upper bound that looks natural in terms of $m$, like $\Theta(m^2 \log m)$, becomes $\Theta(n^2/\log n)$ when expressed in terms of $n$, where $n$ is the number of bits in the input.

Finding the prime factors of n by trial division when the list of primes is already given. There are $\theta(\frac{n}{\log(n)})$ primes less than n so if these primes are given to you, then trial division of n by each of them takes $\theta(\frac{n}{\log(n)})$ time (assuming division is a constant-time operation)

somewhat similar to JG's answer & "thinking outside the box", this seems like a related/relevant/apropos/fundamental negative result. based on diagonalization with a universal TM, there exists a $O(f(n))$ DTIME language that cannot run in $O\left({f(n)\over{\log f(n)}}\right)$ DTIME, due to the time hierarchy theorem. so this applies to a linear DTIME algorithm that exists, $f(n)=n$, that runs impossibly in $O\left(n \over {\log n} \right)$ DTIME.