Apakah fungsi dengan pertumbuhan lebih lambat daripada Ackermann terbalik muncul dalam batas runtime?

Beberapa algoritma yang rumit ( union-find ) memiliki fungsi Ackermann terbalik yang hampir konstan yang muncul dalam kompleksitas waktu asimptotik, dan waktu terburuk optimal jika istilah Ackermann terbalik yang hampir konstan diabaikan.

Adakah contoh algoritma yang dikenal dengan waktu berjalan yang melibatkan fungsi yang secara fundamental tumbuh lebih lambat daripada inversi Ackermann (mis. Invers fungsi yang tidak setara dengan Ackermann dalam transformasi polinomial atau eksponensial dll.), Yang memberikan waktu kasus terburuk yang paling dikenal kompleksitas untuk memecahkan masalah yang mendasarinya?

reference-request algorithm-analysis time-complexity runtime-analysis pengguna2566092
sumber

O (1)

$O(1)$ algoritma waktu? Anda bertanya tentang masalah yang diketahui yang algoritma paling terkenal adalah dan ? Pertama, Anda perlu menemukan fungsi yang tumbuh "secara fundamental lebih cepat" daripada , seperti TREE , dan kemudian mengambil kebalikannya, dan kemudian menemukan masalah yang cocok!

ω (1)

$\omega(1)$

o (α (n))

$o(\alpha(n))$

A (n)

$A(n)$

(n)

$(n)$

Pål GD

ada algoritma yang dibuat sewenang-wenang dibangun dari hierarki waktu thm

vzn

@vzn: Apa pun tidak dapat dikonstruksikan dengan waktu (yang meliputi ). Jadi teorema hierarki waktu tidak dapat digunakan di sini.

f (n) = o (n)

$f(n) = o(n)$

α (n)

$\alpha(n)$

mdxn

@ MDX senang seseorang menunjukkan hal itu, hanya menguji Anda mengedipkan mata. ya akhir-akhir ini telah berpikir mungkin ada generalisasi hierarki waktu untuk sub- fungsi. tetapi toh batas adalah karena TM yang dapat dikonstruksi waktu harus membaca semua input, tetapi apakah kita mengatakan algoritme lain ini misalnya dengan kompleksitas waktu Ackermann terbalik, bukan? kesulitan memvisualisasikan ini! rasakan pertanyaannya lebih lanjut tentang keberadaan sub- bahasa .... mungkinkah ada semacam survei atau deskripsi di suatu tempat ....

o (n)

$o(n)$

o (n)

$o(n)$

o (n)

$o(n)$

vzn

@vzn: OP benar-benar perlu mengklarifikasi model perhitungan apa yang mereka pikirkan. dan perlu didefinisikan pada TM akses acak (atau yang setara). Saat menentukan mekanika kita, kita mungkin secara tidak sengaja menambahkan terlalu banyak tenaga. Bahkan mungkin sampai pada tingkat di mana gagasan kompleksitas komputasi tidak membuahkan hasil. Dalam istilah yang paling dasar, kita harus mengubah gagasan kita tentang kompleksitas waktu (yang merupakan apa yang dilakukan runtime diamortisasi) dengan risiko definisi seperti itu menjadi sangat dibuat-buat (hal yang sama berlaku untuk model perhitungan).

DLOGTIME

$\text{DLOGTIME}$

LH

$\text{LH}$

mdxn

Jawaban:

Seth Pettie datang dengan algoritma untuk menghitung sensitivitas pohon spanning minimum dalam waktu , meningkatkan algoritma Tarjan yang menghitung sama dalam waktu . (Bandingkan ini dengan algoritma Chazelle untuk menghitung pohon spanning minimum itu sendiri.) Masalah sensitivitas meminta untuk menghitung, untuk grafik yang diberikan dan pohon spanning minimum yang diberikan, dengan seberapa banyak setiap bobot sisi dapat berubah tanpa mengubah pohon rentang minimum. $O(m\log \alpha(m,n))$ $O(m\alpha(m,n))$ $O(m\alpha(m,n))$

(Terima kasih kepada Tsvi Kopelowitz untuk referensi ini.)

Yuval Filmus
sumber

Saya tidak tahu apakah log inverse Ackermann "secara fundamental lebih lambat" dari pada inverse Ackermann, tetapi saya menemukan waktu berjalan seperti ini mengejutkan.

Yuval Filmus

Fungsi yang paling lambat berkembang secara komikal yang pernah secara serius saya lihat digunakan dalam makalah adalah , berapa kali Anda harus menerapkan invers Ackermann untuk menjatuhkan ke beberapa konstanta tetap. Ini digunakan dalam makalah ini pada dugaan deque pada pohon splay . $\alpha^*(n)$ $n$

templatetypedef
sumber

-1

Ketika Alan Turing menemukan komputer, dulu ada beberapa model untuk komputer yang diusulkan. Turing membuktikan bahwa beberapa (3) dari model-model ini dapat mensimulasikan satu sama lain DAN menghitung fungsi Ackermann, sedangkan model lain dapat mensimulasikan satu sama lain tetapi tidak fungsi Ackermann (sehingga mereka tidak dapat mensimulasikan 3). Oleh karena itu, 3 model ini (Turing Machine, von Neumann dan yang saya tidak tahu), dipilih sebagai arsitektur untuk komputer. Ini tidak berarti fungsi Ackermann adalah batas komputer, tapi saya kira itu sains yang sulit. Saya tidak mengetahui adanya fungsi komputasi yang tumbuh lebih cepat daripada fungsi Ackermann.

Sekarang, saya tidak berpikir ada masalah praktis yang cocok dengan pertanyaan Anda, tapi mungkin kita bisa membuat satu. Kita perlu memberi batasan pada input. Karena kami tidak dapat menggunakan O (n), kami tidak dapat memeriksa seluruh input. Bahkan, kita bahkan tidak dapat memeriksa panjang input karena itu akan menjadi O (log n). Jadi, pertama kita perlu parameter representasi panjang sisa input, misalnya c sehingga Ackermann (c) adalah panjang input. Karena ini juga tidak cocok, kami meminta sebagai nilai pertama dalam input kami parameter c, sehingga bb (c) adalah tentang panjang input, di mana bb adalah fungsi berang-berang yang sibuk. Fungsi ini tidak dapat dihitung tetapi pasti ada bb (c). Kemudian, algoritmenya seperti:

for (int i=0; i<c; i++) {
    if (input[i] == null) {
        return false;
    }
}
return true;

Tujuan dari algoritma ini adalah untuk memeriksa bahwa jika c adalah kebalikan dari bb, jika kemudian panjang input lebih besar dari bb (c).

Jika ada fungsi yang dapat dihitung yang tumbuh lebih cepat dari fungsi Ackermann, saya pikir kita bisa menggunakannya terbalik untuk membuat algoritma yang menjawab pertanyaan Anda pada input apa pun.

Albert Hendriks
sumber

Pasti ada fungsi yang tumbuh lebih cepat daripada fungsi Ackermann seperti yang ditunjukkan dalam komentar (TREE (n)). Bagian rumit dari pertanyaan adalah membangun algoritma dengan batas run-time dari kebalikan dari fungsi itu. Mesin seperti itu tidak memiliki cukup waktu untuk menghitung kebalikan dari fungsi di tempat pertama, sehingga konstruksi TM yang mencapai ini tidak lurus ke depan.

mdxn