Kompleksitas algoritma naif untuk menemukan substring Fibonacci terpanjang

Diberikan dua simbol dan , mari kita mendefinisikan string Fibonacci sebagai berikut:b $\text{a}$$\text{b}$$k$

$$F(k) = \begin{cases} \text{b} &\mbox{if } k = 0 \\ \text{a} &\mbox{if } k = 1 \\ F(k-1) \star F(k-2) &\mbox{else} \end{cases}$$

dengan menunjukkan penggabungan string.$\star$

Dengan demikian kita akan memiliki:

• $F(0) = \text{b}$
• $F(1) = \text{a}$
• $F(2) = F(1) \star F(0) = \text{ab}$
• $F(3) = F(2) \star F(1) = \text{aba}$
• $F(4) = F(3) \star F(2) = \text{abaab}$
• ...

Mengingat string yang dibentuk oleh simbol, kita mendefinisikan Fibonacci substring sebagai salah substring dari yang juga string Fibonacci untuk pilihan yang cocok dan .$S$$n$a $S$$\text{a}$$\text{b}$

Masalah

Diberikan , kami ingin menemukan substring Fibonacci terpanjang.$S$

Algoritma sepele

Untuk setiap posisi dari string , anggaplah bahwa mulai di sana (cukup untuk memeriksa bahwa simbol ke- dan -th berbeda). Jika itu masalahnya, periksa apakah dapat diperluas ke , lalu , dan seterusnya. Setelah itu, mulai lagi dari posisi . Ulangi sampai Anda mencapai posisi .S F ( 2 ) i ( i + 1 ) F ( 3 ) F ( 4 ) i + 1 $i$$S$$F(2)$$i$$(i+1)$$F(3)$$F(4)$$i+1$$n$

Kita harus melihat setiap simbol setidaknya sekali, jadi . Hanya ada dua untuk loop yang terlibat, sehingga kita dapat selanjutnya mengatakan bahwa itu adalah .O ( n 2$\Omega(n)$$O(n^2)$

Namun (agak tidak mengejutkan) algoritma naif ini berkinerja jauh lebih baik daripada algoritma kuadratik biasa (jika itu banyak bekerja pada posisi ke- , itu tidak akan melakukan banyak pekerjaan di posisi berikutnya).$i$

Bagaimana saya bisa menggunakan properti Fibonacci untuk menemukan batas yang lebih ketat untuk waktu eksekusi algoritma ini?

Katakan bahwa terjadi pada beberapa posisi jika substring yang dimulai pada posisi tersebut kompatibel dengan atau komplemenasinya. Seberapa dekat kejadian ? Ambil sebagai contoh . Jika terjadi pada posisi maka tidak dapat terjadi pada posisi atau$F(n)$ F ( n ) F ( 4 ) = a b a a b F ( 4 ) p p + 1 p + $F(n)$$F(n)$$F(4) = abaab$$F(4)$$p$$p+1$$p+2$ , tetapi dapat muncul pada posisi . Kita membiarkan ℓ ( n ) menjadi angka terkecil sehingga dua kejadian F ( ℓ ) dapat terjadi pada jarak $p+3$$\ell(n)$$F(\ell)$$\ell$. Anda dapat membuktikan dengan induksi bahwa untuk kita memiliki ℓ ( n ) = | F ( n - 1 ) | (misalnya, ℓ ( 4 ) = 3 ).$n \geq 4$$\ell(n) = |F(n-1)|$$\ell(4) = 3$

Diberikan string dengan panjang , untuk setiap n, biarkan P ( n ) menjadi himpunan posisi di mana F ( n ) terjadi. Kami atas dapat terikat waktu berjalan prosedur Anda kira-kira dengan Σ n | P ( n ) | | F ( n ) | , di mana jumlahnya melebihi semua n sehingga | F ( n - 1 ) | ≤ N (katakanlah). Sejak kemunculan F ( $N$$n$$P(n)$$F(n)$$\sum_n |P(n)| |F(n)|$$n$$|F(n-1)| \leq N$ dipisahkan oleh setidaknya | F ( n - 1 ) | , Kita melihat bahwa waktu berjalan dibatasi oleh urutan Σ n | F ( n ) | ( $F(n)$$|F(n-1)|$ Karena panjang kata-kata Fibonacci meningkat secara eksponensial,Σn| F(n)| =O(N). Istilah yang tersisa adalah∑nO(N)=O(NlogN), karena jumlah berisilogNbanyak istilah. Kami menyimpulkan bahwa waktu berjalan adalahO(Nlog

$$\sum_n |F(n)| \left(\frac{N}{|F(n-1)|} + 1\right).$$ $\sum_n |F(n)| = O(N)$$\sum_n O(N) = O(N\log N)$$\log N$ .$O(N\log N)$

Sebaliknya, waktu berjalan pada adalah Ω ( | F n | log | F n | ) , sebagaimana dapat dibuktikan dengan induksi. Kami menyimpulkan bahwa case run time terburuk pada string panjang N adalah Θ ( N log N ) .$F_n$$\Omega(|F_n|\log|F_n|)$$N$$\Theta(N\log N)$