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

Prosty i praktyczny algorytm deterministyczny, skomplikowany czas działania

Odpowiedzi: