Rasio emas atau Pi dalam waktu berjalan

21

Ada banyak tempat di mana angka dan muncul. Saya ingin tahu tentang algoritma yang waktu berjalannya mengandung rasio emas atau dalam eksponen. $\pi$ $(1+\sqrt5)/2$ $\pi$

reference-request big-list Plummer
sumber

4

Apakah ada alasan komputasi tertentu untuk menduga bahwa itu mungkin? Dan tanpa mengetahui di mana itu muncul, apakah Anda pikir ada wawasan khusus yang bisa diperoleh jika itu terjadi?

Niel de Beaudrap

13

Rasio emas muncul dalam analisis kompleksitas program yang serupa dalam struktur rekursif dengan rekursi yang terlibat dalam angka-angka Fibonacci : .

F_{n + 2} = F_{n + 1} + F_{n}

$F_{n+2} = F_{n+1} + F_n$

Martin Berger

11

The Fortnow dan Melkebeek waktu / ruang yang lebih rendah-terikat untuk SAT solvabilitas yang terkandung rasio emas ( waktu dan ruang); tetapi eksponen telah diperbaiki kemudian oleh Ryan Williams.

n^{ϕ - ϵ}

$n^{\phi - \epsilon}$

n^{o (1)}

$n^{o(1)}$

Marzio De Biasi

2

@MarzioDeBiasi Saya pikir komentar Anda membuat jawaban yang baik, bahkan jika hasilnya ditingkatkan. Yang menarik adalah bahwa ada analisis yang menghasilkan rasio emas dalam eksponen

Sasho Nikolov

1

@NieldeBeaudrap Saya berharap untuk melihat beberapa pola di antara contoh-contoh. Misalnya, eksponen e muncul di banyak tempat dalam algoritma acak. Saya tidak terkejut dengan hal itu karena saya tahu bahwa jenis kegiatan bola-dan-sampah mengarah ke jawaban yang melibatkan e. Saya bertanya-tanya apakah sesuatu seperti itu dapat dikatakan tentang algoritma yang memiliki rasio emas dalam waktu berjalan.

Plummer

22

Ini basis daripada eksponen, tapi ada FPT terikat waktu $O(\varphi^k n^2)$

" Algoritma Tractable Parameter Tetap Efisien untuk Minimisasi Penyeberangan 1-Sisi ", Vida Dujmovic, Sue Whitesides, Algorithmica 40: 15–31, 2004.

Selain itu, batas bawah bukan batas atas, tetapi:

" Sebuah menurunkan terikat pada waktu untuk mensimulasikan satu antrian atau dua pushdown toko oleh satu tape $n^{1.618}$ ", Paul MB Vitányi, Inf. Proc Lett. 21: 147–152, 1985.

Akhirnya, yang saya coba temukan ketika saya berlari melintasi dua yang lain: ham sandwich tree, struktur data yang sekarang usang dalam geometri komputasi untuk kueri rentang segitiga, memiliki waktu kueri . Jadi rasio emas tepat dalam eksponen, tetapi dengan log daripada sebagai dirinya sendiri. Struktur data adalah partisi hierarki pesawat menjadi sel-sel cembung, dengan struktur keseluruhan pohon biner, di mana setiap sel dan saudara kandungnya di pohon dipartisi dengan potongan sandwich ham. Waktu kueri ditentukan oleh perulangan , yang memiliki solusi di atas. Ini dijelaskan (dengan nama yang lebih membosankan) oleh $O(n^{\log_2\varphi})\approx O(n^{0.695})$ $Q(n)=Q(\frac{n}{2})+Q(\frac{n}{4})+O(\log n)$

" Pencarian rentang Halfplanar dalam ruang linear dan waktu permintaan $O(n^{0.695})$ ", Herbert Edelsbrunner, Emo Welzl, Inf. Proc Lett. 23: 289–293, 1986.

David Eppstein
sumber

1

Saya tidak yakin saya akan merasa nyaman dengan mengatakan bahwa

memiliki

dalam eksponen.

n^{\log_{2} φ} = φ^{\log_{2} n}

$n^{\log_2\varphi}=\varphi^{\log_2n}$

φ

$\varphi$

Emil Jeřábek mendukung Monica

18

(dari komentar saya di atas)

The Fortnow dan Melkebeek waktu / ruang yang lebih rendah-terikat untuk SAT solvabilitas ( waktu dan spasi) yang terdapat rasio emas di eksponen; tetapi kemudian diperbaiki oleh Ryan Williams . $n^{\phi - \epsilon}$ $n^{o(1)}$

Marzio De Biasi
sumber

5

Sementara Ryan Williams merusak contoh Fortnow dan Melkebeek Anda, ia juga menyediakan satu lagi di bidang yang sama: di cs.cmu.edu/ ~ryanw/automated-lbs.pdf , ia menunjukkan bahwa tidak ada bukti perdagangan-pergantian

.

c o N T I M E [n] ⊈ N T I M E S P A C E [n^{ϕ + o (1)}, n^{o (1)}]

$\mathrm{coNTIME}[n]\nsubseteq\mathrm{NTIMESPACE}[n^{\phi+o(1)},n^{o(1)}]$

Emil Jeřábek mendukung Monica

15

Juga di pangkalan daripada eksponen: algoritma Monien-Speckenmeyer untuk 3-SAT memiliki waktu berjalan . Itu adalah batas atas non-trivial pertama untuk 3-SAT. $\varphi^n\cdot O(n)$

Jan Johannsen
sumber

10

Contoh lain dari di pangkalan adalah algoritma oleh Andreas Björklund dan Thore Husfeldt untuk menghitung paritas dari jumlah siklus Hamiltonian yang diarahkan, yang berjalan dalam waktu . $\varphi$ $O(\varphi^n)$

http://arxiv.org/abs/1301.7250

Tyson Williams
sumber

9

Juga di dasar: Algoritma penghapusan-kontraksi (Zykov, 1949) untuk menghitung jumlah pewarnaan grafik berjalan dalam waktu . Ini adalah contoh yang sangat kanonik tentang bagaimana rasio emas muncul dari pengulangan Fibonacci untuk waktu berjalan mengevaluasi formula rekursif alami; Saya yakin itu yang tertua. $O(\phi^{|E|+|V|})$

Mikko Koivisto menemukan algoritma untuk menghitung jumlah pencocokan sempurna (IWPEC 2009). $O(\phi^{|V|})$

Thore Husfeldt
sumber

8

Ransum emas di dasar: Algoritma FPT yang sangat baru oleh Kociumaka dan Pilipczuk, Umpan Balik deterministik yang lebih cepat Vertex Set menghitung FVS ukuran dalam waktu . (Mereka kemudian meningkatkan algoritme mereka untuk berjalan dalam waktu .) $k$ $O^*\left((2 + \phi)^k\right)$ $O^*(3.592^k)$

vb le
sumber

-2

untuk memperluas komentar Martin Bergers: algoritma GCD Euclidean kuno berjalan dalam waktu kasus terburuk pada dua elemen berturut-turut dari deret Fibonacci. lebih detail tentang wikipedia yang juga menyatakan:

Bukti ini, diterbitkan oleh Gabriel Lamé pada tahun 1844, merupakan awal dari teori kompleksitas komputasi, [93] dan juga aplikasi praktis pertama dari angka-angka Fibonacci. [91]

secara teknis algoritma GCD berjalan dalam waktu logaritmik tetapi rasio emas muncul dalam jumlah langkah algoritma. $O(\log(n))$

[1] berapa kompleksitas waktu dari algoritma Euclids, math.se

ay
sumber

Bagaimana perbedaan waktu dan jumlah langkah?

Nicholas Mancuso

maaf yang seharusnya membaca # operasi aritmatika

vzn

1

\log_{φ} N

$\log_{\varphi}N$

O ((\log N)^{2})

$O((\log N)^2)$

O (n^{2})

$O(n^2)$

T (a, b)

$T(a,b)$

T (a, b) = O (l o g_{ϕ} b)

$T(a,b)=O(log_\phi b)$

1

O (\log_{ϕ} b)

$O(\log_\phi b)$

O

$O$

Rasio emas atau Pi dalam waktu berjalan

Jawaban: