Prosty i praktyczny algorytm deterministyczny, skomplikowany czas działania

18

Bardzo często, jeśli czas działania algorytmu jest skomplikowanym wyrażeniem, sam algorytm jest również skomplikowany i niepraktyczny. Każdy z pierwiastek sześcienny i czynników w czasie biegu asymptotycznej tendencję, aby dodać złożoności algorytmu, a także ukryte czynniki stałe do czasu pracy. $\log \log n$

Czy mamy uderzające przykłady, w których zawodzi ta praktyczna zasada?

Oczywiście łatwo jest znaleźć przykłady algorytmów, które są bardzo trudne do wdrożenia, nawet jeśli mają bardzo prosty najgorszy czas działania. A co z rozmową?

Czy mamy przykłady bardzo prostych i praktycznych deterministycznych algorytmów, które są łatwe do wdrożenia, ale zdarzają się bardzo skomplikowane wyrażenia jako najgorszy przypadek asymptotycznego czasu działania?

Zwróć uwagę na słowa kluczowe „deterministyczny” i „najgorszy przypadek”; analiza prostych randomizowanych algorytmów dość łatwo prowadzi do skomplikowanych wyrażeń.

Oczywiście to, co „skomplikowane”, jest kwestią gustu. W każdym razie wolałbym, aby wyrażenie było zbyt brzydkie, aby umieścić je w tytule twojego artykułu. Wolałbym skomplikowaną funkcję jednego naturalnego parametru (wielkość wejściowa, liczba węzłów itp.).

PS. Myślałem, że nie uczynię tego „pytaniem z dużej listy”, a nie CW. Chciałbym znaleźć jeden doskonały przykład (jeśli w ogóle istnieje). Dlatego proszę zamieścić inną odpowiedź tylko wtedy, gdy uważasz, że jest ona „lepsza” niż jakakolwiek z dotychczasowych odpowiedzi.

ds.algorithms soft-question recreational

— Jukka Suomela
źródło

2

Czy algorytm testowania pierwotności AKS kwalifikuje się jako odpowiedź? Waham się, ponieważ „komplikacja” jego przebiegu jest w pewnym sensie wynikiem pseudolosowości rozkładu liczb pierwszych ...

— arnab

Mam wrażenie, że najgorszym przypadkiem jest w większości przypadków coś, co powoduje „bieganie po wszystkim” i wszystko jest tym, w czym mierzymy środowisko uruchomieniowe. Naturalnie, proste algorytmy mają łatwe środowiska wykonawcze WC. Skomplikowane środowiska wykonawcze pojawiają się, gdy próbujemy zgolić odrobinę przy pomocy jakiegoś triku. Ale twoje pytanie jest interesujące; Z pewnością jestem ciekawa, czy moje uczucie jest słuszne.

— Raphael

@arnab: Dzięki, AKS to dobry pomysł. Ale nie jestem pewien, czy możemy to nazwać „praktycznym”?

— Jukka Suomela

Czy schematy przekazywania wiadomości, takie jak propagacja ankiety, propagacja ograniczeń lub sekwencyjne TRW, są liczone jako „algorytmy”? Łatwy do wdrożenia, czas działania jest trudny do przewidzenia

— Jarosław Bułatow

Ups, zawsze podoba mi się metoda rho Pollarda, jest prosta i praktyczna, a analiza jest naprawdę trudna, ale losowość algorytmu czyni go niekwalifikowanym jako odpowiedź na post ...

— Hsien-Chih Chang 張顯之

20

Najlepszym przykładem, jaki mogę wymyślić, jest algorytm (opisany poniżej) do obliczenia poziomu w układzie linii w płaszczyźnie, tj. Linii wielokątnej utworzonej przez punkty, które mają dokładnie linii w pionie nad nią. To nie jest najbardziej wydajny algorytm znany z problemu. Istnieją wydajniejsze algorytmy o prostszych złożonościach, ale uważam, że ten jest bardziej praktyczny niż większość (jeśli nie wszystkie) z nich. Analiza prawdopodobnie nie jest ścisła, ponieważ wykorzystuje złożoność poziomu , która jest znanym otwartym problemem (myślę, że wszystkie inne terminy w analizie są ścisłe). Mimo to wątpię, czy poprawione granice dla poziomu poziom znacznie uprościłyby czas działania. Zakładam, że $k$ $n$ $k$ $k$ $k$ aby zapisać złożoność jako funkcjęsamego . $k=n/2$ $n$

Algorytm oparty jest na paradygmacie przemiatania linii i wykorzystuje dwa -aryjne turnieje kinetyczne jako kinetyczne kolejki priorytetowe. Wstawienia i usunięcia są wykonywane, gdy linia przechodzi powyżej lub poniżej poziomu , przenosząc linię z jednego turnieju kinetycznego do drugiego. W związku z tym, istnieje insercje i delecje (przy użyciu granicę dla Dey w -level złożoność). Każde zdarzenie jest przetwarzane w czasu i istnieją $(\log n)$ $k$ $O(n^{4/3})$ $k$ $O(\log n)$ zdarzenia ( pochodzi ze złożoności górnej obwiedni układów segmentów linii, podczas gdy pochodzi z wysokościdrzewa -ary ). Całkowity czas działania wynosi $O(n^{4/3} \alpha(n) \log n / \log \log n)$ $\alpha(n)$ $\log n / \log \log n$ $(\log n)$

O (n^{4 / 3} α (n) \log^{2} n / \log \log n) .

$O(n^{4/3} \alpha(n) \log^2 n / \log \log n).$

Sprawdź manuskrypt Timothy Chana http://www.cs.uwaterloo.ca/~tmchan/lev2d_7_7_99.ps.gz, aby uzyskać więcej informacji i odniesień. Współczynnik można usunąć za pomocą binarnego (intead -ary) turnieju kinetycznego, ale w rzeczywistości przyspiesza on kolejkę priorytetów kinetycznych w testach, które przeprowadziłem. Złożoność powinna stać się nieco brzydsza i gorsza (podczas gdy algorytm nadal będzie praktyczny), jeśli zamiast turnieju kinetycznego zostanie użyta kupka kinetyczna ( powinien pojawić się wewnątrz pierwiastka kwadratowego). $1/\log \log n$ $(\log n)$ $\log$

— Guilherme D. da Fonseca
źródło

Doskonały przykład, dzięki! To nie będzie łatwe do pokonania. :)

— Jukka Suomela

1

Algorytm ten jest w praktyce wolniejszy niż algorytmy randomizowane, które są dość łatwe do wdrożenia (jak ktoś, kto zaimplementował jeden z tych algorytmów (patrz mój artykuł „Spacerując w układzie planarnym”.)

— Sariel Har-Peled,

Przyjąłem tę odpowiedź, ponieważ wydaje się ona być najbliższa temu, co miałem na myśli. Ale jeśli ktoś ma jakieś świeże pomysły, chętnie to usłyszę!

— Jukka Suomela

24

Operacje struktury danych znajdowania związku wydają się spełniać twoje kryteria:

http://en.wikipedia.org/wiki/Disjoint-set_data_structure

— Kevin Wortman
źródło

2

Rzeczywiście, opublikowałem tę samą odpowiedź, ale usunąłem ją, gdy zauważyłem, że mnie pobiłaś. :) Prosty i elegancki algorytm, który może nie-teoretyk mógłby nawet odkryć, ale odwrotność Ackermanna amortyzowała złożoność.

— Warren Schudy,

Cóż,

czas nie wygląda, że "skomplikowane", jeśli porównać go do

w odpowiedzi Guilherme za. :)

O (α (n))

$O(\alpha(n))$

O (n^{4 / 3} α (n) \log^{2} n / \log \log n)

$O(n^{4/3} \alpha(n) \log^2 n / \log \log n)$

— Jukka Suomela

Stosunek długości algorytmu do złożoności dowodu dla znalezienia związku jest prawdopodobnie nie do pobicia - wszystkie trzy operacje są, dziewięć linii kodu?

— Neel Krishnaswami,

1

Nie sądzę, aby pytanie dotyczyło prostego i praktycznego algorytmu ze złożoną analizą . Myślę, że pytanie dotyczy prostego i praktycznego algorytmu o złożonym czasie działania , to znaczy rzeczywistego wyrażenia uzyskanego dla górnej granicy.

— Guilherme D. da Fonseca

6

Algorytm simpleksowy. Łatwy do wdrożenia i działa doskonale w praktyce, ale jest bałagan do analizy teoretycznej.

— Mohit Singh
źródło

n

$n$

w rzeczywistości wiadomo, że simplex zajmuje najgorszy czas w najgorszym przypadku dzięki konstrukcji Klee-Minty. Myślę, że nie jest to przykład tego, o co pyta Jukka

— Suresh Venkat,

1

Może powinienem był powiedzieć metodę simpleks zamiast algorytmu simpleks. Kostka Klee-Minty i jej odmiany działają w przypadku niektórych zasad obracania wanilii. Ale na przykład reguła losowego obracania aspektu ma szaloną górną i (ostatnią) dolną granicę. Gil Kalai miał fajny wpis na blogu na temat ostatnich wyników. gilkalai.wordpress.com/2010/11/09/…

— Mohit Singh

dobra uwaga, Mohit. Byłem również zdezorientowany.

— Suresh Venkat

2

Nie jestem pewien, czy uważasz to za „praktyczne”, ale jest to znany otwarty problem. Paul Erdos powiedział o przypuszczeniu Collatza: „Matematyka nie jest jeszcze gotowa na takie problemy”

$x=1$

— Mohammad Al-Turkistany
źródło

A jaki problem rozwiązuje ten algorytm ...?

— Jukka Suomela

Sugeruje to poszukiwanie nowych technik analizy w czasie wykonywania.

— Mohammad Al-Turkistany

2

można wtedy powiedzieć, że brutalne poszukiwanie dowodu hipotezy Collatza również motywuje „nowatorskie techniki analizy w czasie wykonywania”; w obu przypadkach algorytm bezmyślnie bada digrafa. Hipoteza Collatza jest fajna, ale nie sądzę, że jest to interesujący przykład „algorytmu”.

— Niel de Beaudrap,

2

Ten przykład, mimo że nie spełnia listu twojej prośby, może być interesujący, ponieważ zawiera pewne duchowe powinowactwo. W szczególności kwestia sortowania stosów naleśników i przypalonych naleśników według zamiany.

http://en.wikipedia.org/wiki/Pancake_sorting

Jednym z obszarów zastosowania jest biologia obliczeniowa (genetyka), w której można postawić pytania dotyczące przestawienia genomu pod względem odległości między permutacjami przy użyciu odwrócenia części permutacji podlegających różnym regułom.

— Joseph Malkevitch
źródło