Algoritma deterministik sederhana dan praktis, waktu berjalan yang rumit

18

Sangat sering, jika waktu berjalan suatu algoritma adalah ekspresi yang rumit, algoritma itu sendiri juga rumit dan tidak praktis. Setiap akar pangkat tiga dan faktor dalam waktu berjalan asimptotik cenderung menambah kompleksitas pada algoritma dan juga menyembunyikan faktor konstan pada waktu berjalan. $\log \log n$

Apakah kita memiliki contoh mencolok di mana aturan praktis ini gagal?

Tentu saja mudah untuk menemukan contoh - contoh algoritma yang sangat sulit diimplementasikan walaupun mereka memiliki waktu berjalan terburuk yang sangat sederhana. Tapi bagaimana dengan yang sebaliknya?

Apakah kita memiliki contoh algoritma deterministik yang sangat sederhana dan praktis yang mudah diterapkan tetapi kebetulan memiliki ekspresi yang sangat rumit sebagai waktu berjalan asimptotik terburuknya?

Harap perhatikan kata kunci "deterministik" dan "kasus terburuk"; analisis algoritma acak sederhana cukup mudah menyebabkan ekspresi rumit.

Tentu saja apa yang "rumit" adalah masalah selera. Lagi pula, saya lebih suka melihat ekspresi yang terlalu jelek untuk dimasukkan ke dalam judul makalah Anda. Dan saya lebih suka fungsi rumit dari satu parameter alami (ukuran input, jumlah node, dll.).

PS. Saya pikir saya tidak akan menjadikan ini "daftar pertanyaan besar", dan bukan CW. Saya ingin menemukan satu contoh bagus (jika ada sama sekali). Karena itu tolong posting jawaban lain hanya jika Anda berpikir itu "lebih baik" daripada jawaban sejauh ini.

ds.algorithms soft-question recreational Jukka Suomela
sumber

2

Apakah algoritma pengujian primality AKS memenuhi syarat sebagai jawaban? Saya ragu-ragu karena "kerumitan" waktu berjalannya, dalam beberapa hal, adalah hasil dari pseudorandomness dari distribusi bilangan prima ...

arnab

Perasaan saya adalah bahwa kasus terburuk dalam banyak kasus adalah sesuatu yang menyebabkan "berjalan di atas segalanya" dan semuanya adalah hal yang kita ukur runtime. Jadi, secara alami, algoritma yang mudah memiliki WC-runtime yang mudah. Runtimes yang rumit muncul jika kita mencoba mencukur sedikit demi sedikit dengan beberapa trik. Tetapi pertanyaan Anda menarik; Saya tentu ingin tahu apakah perasaan saya benar.

Raphael

@arnab: Terima kasih, AKS adalah ide yang bagus. Tetapi saya tidak yakin apakah kita dapat menyebutnya "praktis"?

Jukka Suomela

Apakah skema penyampaian pesan seperti propagasi survei, propagasi kendala atau TRW berurutan dianggap sebagai "algoritma"? Mudah diimplementasikan, runtime sulit diprediksi

Yaroslav Bulatov

Ups, saya selalu suka metode Pollard rho, sederhana dan praktis, dan analisisnya sangat sulit, tetapi keacakan algoritme membuatnya tidak memenuhi syarat sebagai jawaban untuk pos ...

Hsien-Chih Chang 張顯之

20

Contoh terbaik yang dapat saya pikirkan adalah sebuah algoritma (dijelaskan di bawah) untuk menghitung tingkat- dalam susunan garis dalam bidang, yaitu garis poligon yang dibentuk oleh titik-titik yang memiliki garis persis secara vertikal di atasnya. Ini bukan algoritma paling efisien yang dikenal untuk masalah ini. Ada algoritma yang lebih efisien dengan kompleksitas yang lebih sederhana, tetapi saya percaya ini lebih praktis daripada kebanyakan (jika tidak semua). Analisisnya mungkin tidak ketat, karena menggunakan kompleksitas level , yang merupakan masalah terbuka yang terkenal (saya pikir semua istilah lain dalam analisis ini ketat). Meski begitu, saya ragu peningkatan batasan untuk -level akan membuat waktu berjalan lebih sederhana. Saya akan menganggap $k$ $n$ $k$ $k$ $k$ untuk menulis kompleksitas sebagai fungsi dari sendiri. $k=n/2$ $n$

Algoritma ini didasarkan pada paradigma garis menyapu dan menggunakan dua turnamen kinetikary sebagai antrian prioritas kinetik. Penyisipan dan penghapusan dilakukan ketika garis berjalan di atas atau di bawah tingkat , memindahkan garis dari satu turnamen kinetik ke yang lain. Oleh karena itu, ada sisipan dan penghapusan (menggunakan terikat untuk Dey kompleksitas -tingkat). Setiap acara diproses di waktu dan ada $(\log n)$ $k$ $O(n^{4/3})$ $k$ $O(\log n)$ peristiwa ( berasal dari kompleksitas amplop atas pengaturan segmen garis, sedangkan berasal dari ketinggianpohon ). Total waktu berjalan adalah $O(n^{4/3} \alpha(n) \log n / \log \log n)$ $\alpha(n)$ $\log n / \log \log n$ $(\log n)$

HAI (n^{4 / 3} α (n) {catatan}^{2} n / catatan catatan n) .

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

Silakan periksa manuskrip Timothy Chan http://www.cs.uwaterloo.ca/~tmchan/lev2d_7_7_99.ps.gz untuk rincian dan referensi lebih lanjut. Faktor dapat dihapus dengan menggunakan turnamen kinetik biner (intead of -ary), tetapi sebenarnya mempercepat antrian prioritas kinetik dalam tes yang saya lakukan. Kompleksitas harus menjadi sedikit lebih buruk dan lebih buruk (sementara algoritme akan tetap praktis) jika tumpukan kinetik digunakan sebagai pengganti turnamen kinetik ( di dalam akar kuadrat akan muncul). $1/\log \log n$ $(\log n)$ $\log$

Guilherme D. da Fonseca
sumber

Contoh yang bagus, terima kasih! Ini tidak akan mudah dikalahkan. :)

Jukka Suomela

1

Algoritma ini lebih lambat dalam praktiknya daripada algoritma acak, yang cukup mudah untuk diimplementasikan (sebagai seseorang yang menerapkan salah satu dari algoritma ini (lihat makalah saya "Berjalan-jalan dalam pengaturan planar".)

Sariel Har-Peled

Saya telah menerima jawaban ini karena tampaknya paling dekat dengan apa yang ada dalam pikiran saya. Tetapi jika ada yang punya ide segar, saya akan senang mendengarnya!

Jukka Suomela

24

Operasi struktur data union-find tampaknya memenuhi kriteria Anda:

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

Kevin Wortman
sumber

2

Memang, saya memposting jawaban yang sama tetapi menghapusnya setelah saya perhatikan Anda mengalahkan saya untuk itu. :) Algoritma sederhana dan elegan yang mungkin ditemukan oleh non-ahli teori, tetapi sebaliknya Ackermann diamortisasi kompleksitasnya.

Warren Schudy

Nah,

waktu tidak terlihat yang "rumit" jika Anda membandingkannya dengan

dalam jawaban Guilherme ini. :)

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

Rasio panjang algoritme dengan kompleksitas bukti untuk menemukan-serikat mungkin tidak terkalahkan - ketiga operasi itu apa, sembilan baris kode?

Neel Krishnaswami

1

Saya tidak berpikir pertanyaannya adalah tentang algoritma yang sederhana dan praktis dengan analisis yang kompleks . Saya pikir pertanyaannya adalah tentang algoritma yang sederhana dan praktis dengan waktu berjalan yang kompleks , yaitu, ekspresi aktual yang diperoleh untuk batas atas.

Guilherme D. da Fonseca

6

Algoritma simpleks. Mudah diimplementasikan dan bekerja luar biasa dalam praktik tetapi berantakan untuk dianalisis secara teoritis.

Mohit Singh
sumber

n

$n$

sebenarnya simplex diketahui membutuhkan waktu yang eksponensial dalam kasus terburuk melalui konstruksi Klee-Minty. Saya kira, itu bukan contoh dari apa yang ditanyakan Jukka

Suresh Venkat

1

Mungkin saya seharusnya mengatakan metode simpleks daripada algoritma simpleks. Kubus Klee-Minty dan variasinya berfungsi untuk beberapa aturan berputar vanili. Tapi, misalnya, aturan pivot facet acak memiliki batas bawah gila dan baru-baru ini. Gil Kalai memiliki entri blog yang bagus tentang hasil terakhir. gilkalai.wordpress.com/2010/11/09/...

Mohit Singh

Poin bagus, Mohit. Saya juga bingung.

Suresh Venkat

2

Saya tidak yakin apakah Anda menganggap ini "praktis" tetapi ini adalah masalah terbuka yang terkenal. Paul Erdos berkata tentang dugaan Collatz: "Matematika belum siap untuk masalah seperti itu"

$x=1$

Mohammad Al-Turkistany
sumber

Dan apa masalahnya dengan algoritma ini ...?

Jukka Suomela

Ini menyarankan mencari teknik analisis run-time baru.

Mohammad Al-Turkistany

2

Anda kemudian bisa mengatakan bahwa pencarian dengan kekerasan untuk membuktikan dugaan Collatz juga memotivasi "teknik analisis run-time baru"; dalam kedua kasus, algoritma hanya menjelajahi digraf tanpa berpikir. Dugaan Collatz memang menyenangkan, tapi saya rasa ini bukan contoh yang menarik dari "sebuah algoritma".

Niel de Beaudrap

2

Contoh ini, walaupun tidak memenuhi surat permintaan Anda, mungkin menarik karena itu memiliki kedekatan spiritual. Secara khusus, pertanyaan tentang menyortir tumpukan pancake dan pancake yang dibakar dengan pembalikan.

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

Salah satu bidang aplikasi adalah untuk biologi komputasi (genetika) di mana pertanyaan tentang penyusunan kembali genom dapat ditulis dalam hal jarak antara permutasi menggunakan pembalikan potongan permutasi yang tunduk pada berbagai aturan.

Joseph Malkevitch
sumber

Algoritma deterministik sederhana dan praktis, waktu berjalan yang rumit

Jawaban: