Kompleksitas komputasi Urutan Fibonacci

Saya mengerti notasi Big-O, tapi saya tidak tahu bagaimana cara menghitungnya untuk banyak fungsi. Secara khusus, saya telah mencoba untuk mencari kompleksitas komputasi dari versi naif dari deret Fibonacci:

int Fibonacci(int n)
{
    if (n <= 1)
        return n;
    else
        return Fibonacci(n - 1) + Fibonacci(n - 2);
}

Apa kompleksitas komputasi dari deret Fibonacci dan bagaimana cara menghitungnya?

Anda memodelkan fungsi waktu untuk menghitung Fib(n)sebagai jumlah waktu untuk menghitung Fib(n-1)ditambah waktu untuk menghitung Fib(n-2)ditambah waktu untuk menambahkannya bersama-sama ( O(1)). Ini mengasumsikan bahwa evaluasi berulang yang sama Fib(n)membutuhkan waktu yang sama - yaitu tidak ada memoisasi yang digunakan.

T(n<=1) = O(1)

T(n) = T(n-1) + T(n-2) + O(1)

Anda memecahkan hubungan perulangan ini (menggunakan fungsi menghasilkan, misalnya) dan Anda akan berakhir dengan jawabannya.

Atau, Anda dapat menggambar pohon rekursi, yang akan memiliki kedalaman ndan secara intuitif mengetahui bahwa fungsi ini asimtotik . Anda kemudian dapat membuktikan dugaan Anda dengan induksi.O(2n)

Basis: n = 1sudah jelas

Asumsikan , oleh karena ituT(n-1) = O(2n-1)

T(n) = T(n-1) + T(n-2) + O(1) yang sama dengan

T(n) = O(2n-1) + O(2n-2) + O(1) = O(2n)

Namun, seperti disebutkan dalam komentar, ini bukan ikatan yang ketat. Fakta menarik tentang fungsi ini adalah bahwa T (n) asimtotik sama dengan nilai Fib(n)karena keduanya didefinisikan sebagai

f(n) = f(n-1) + f(n-2).

Daun dari pohon rekursi akan selalu kembali 1. Nilai Fib(n)adalah jumlah dari semua nilai yang dikembalikan oleh daun di pohon rekursi yang sama dengan jumlah daun. Karena setiap daun akan mengambil O (1) untuk menghitung, T(n)sama dengan Fib(n) x O(1). Akibatnya, batas ketat untuk fungsi ini adalah deret Fibonacci itu sendiri (~ ). Anda dapat menemukan ikatan ketat ini dengan menggunakan fungsi pembangkit seperti yang saya sebutkan di atas.θ(1.6n)

Cukup tanyakan pada diri sendiri berapa banyak pernyataan yang perlu dieksekusi untuk F(n)menyelesaikan.

Sebab F(1), jawabannya adalah 1(bagian pertama dari kondisi).

Sebab F(n), jawabannya adalah F(n-1) + F(n-2).

Jadi fungsi apa yang memenuhi aturan ini? Coba ⁿ (a> 1):

a ⁿ == a ^(n-1) + a ^(n-2)

Membagi melalui ^(n-2) :

a ² == a +1

Pecahkan untuk a dan Anda dapatkan (1+sqrt(5))/2 = 1.6180339887, atau dikenal sebagai rasio emas .

Jadi butuh waktu yang eksponensial.

Saya setuju dengan pgaur dan rickerbh, kompleksitas Recursive-fibonacci adalah O (2 ^ n).

Saya sampai pada kesimpulan yang sama dengan alasan yang agak sederhana tapi saya percaya masih valid.

Pertama, ini semua tentang mencari tahu berapa kali fungsi fibonacci recursive (F () dari sekarang) dipanggil ketika menghitung nomor Nth fibonacci. Jika dipanggil sekali per angka dalam urutan 0 hingga n, maka kita memiliki O (n), jika dipanggil n kali untuk setiap angka, maka kita mendapatkan O (n * n), atau O (n ^ 2), dan seterusnya.

Jadi, ketika F () dipanggil untuk bilangan n, jumlah kali F () dipanggil untuk bilangan tertentu antara 0 dan n-1 bertambah ketika kita mendekati 0.

Sebagai kesan pertama, menurut saya jika kita meletakkannya secara visual, menggambar unit per waktu F () disebut dengan angka tertentu, basah mendapatkan semacam bentuk piramida (yaitu, jika kita memusatkan unit secara horizontal ). Sesuatu seperti ini:

n              *
n-1            **
n-2           ****  
...
2           ***********
1       ******************
0    ***************************

Sekarang, pertanyaannya adalah, seberapa cepat dasar piramida ini membesar saat n tumbuh?

Mari kita ambil contoh nyata, misalnya F (6)

F(6)                 *  <-- only once
F(5)                 *  <-- only once too
F(4)                 ** 
F(3)                ****
F(2)              ********
F(1)          ****************           <-- 16
F(0)  ********************************    <-- 32

Kita melihat F (0) dipanggil 32 kali, yaitu 2 ^ 5, yang untuk kasus sampel ini adalah 2 ^ (n-1).

Sekarang, kita ingin tahu berapa kali F (x) dipanggil sama sekali, dan kita dapat melihat berapa kali F (0) dipanggil hanya sebagian saja.

Jika kita secara mental memindahkan semua baris * dari F (6) ke F (2) menjadi garis F (1), kita melihat bahwa garis F (1) dan F (0) sekarang memiliki panjang yang sama. Yang berarti, total kali F () dipanggil ketika n = 6 adalah 2x32 = 64 = 2 ^ 6.

Sekarang, dalam hal kompleksitas:

O( F(6) ) = O(2^6)
O( F(n) ) = O(2^n)

Ada diskusi yang sangat bagus tentang masalah khusus ini di MIT . Pada halaman 5, mereka menyatakan bahwa, jika Anda menganggap bahwa penambahan membutuhkan satu unit komputasi, waktu yang diperlukan untuk menghitung Fib (N) sangat terkait erat dengan hasil Fib (N).

Sebagai hasilnya, Anda dapat melompat langsung ke perkiraan yang sangat dekat dari seri Fibonacci:

Fib(N) = (1/sqrt(5)) * 1.618^(N+1) (approximately)

dan mengatakan, oleh karena itu, bahwa kinerja kasus terburuk dari algoritma naif adalah

O((1/sqrt(5)) * 1.618^(N+1)) = O(1.618^(N+1))

PS: Ada diskusi tentang ekspresi bentuk tertutup dari angka Fibonacci ke- lebih di Wikipedia jika Anda menginginkan informasi lebih lanjut.

Anda dapat mengembangkannya dan melakukan visualisasi

     T(n) = T(n-1) + T(n-2) <
     T(n-1) + T(n-1) 

     = 2*T(n-1)   
     = 2*2*T(n-2)
     = 2*2*2*T(n-3)
     ....
     = 2^i*T(n-i)
     ...
     ==> O(2^n)

Itu dibatasi pada ujung bawah oleh 2^(n/2)dan pada ujung atas oleh 2 ^ n (seperti yang disebutkan dalam komentar lain). Dan fakta yang menarik dari implementasi rekursif adalah bahwa ia memiliki ikatan Fib (n) asimptotik yang ketat. Fakta-fakta ini dapat diringkas:

T(n) = Ω(2^(n/2))  (lower bound)
T(n) = O(2^n)   (upper bound)
T(n) = Θ(Fib(n)) (tight bound)

Ikatan yang rapat dapat dikurangi lebih jauh menggunakan bentuk tertutup jika diinginkan.

Jawaban buktinya bagus, tetapi saya selalu harus melakukan beberapa iterasi dengan tangan untuk meyakinkan diri saya sendiri. Jadi saya menggambar pohon panggilan kecil di papan tulis saya, dan mulai menghitung node. Saya membagi jumlah saya menjadi simpul total, simpul daun, dan simpul interior. Inilah yang saya dapatkan:

IN | OUT | TOT | LEAF | INT
 1 |   1 |   1 |   1  |   0
 2 |   1 |   1 |   1  |   0
 3 |   2 |   3 |   2  |   1
 4 |   3 |   5 |   3  |   2
 5 |   5 |   9 |   5  |   4
 6 |   8 |  15 |   8  |   7
 7 |  13 |  25 |  13  |  12
 8 |  21 |  41 |  21  |  20
 9 |  34 |  67 |  34  |  33
10 |  55 | 109 |  55  |  54

Yang segera terjadi adalah jumlah simpul daun fib(n). Apa yang memerlukan beberapa iterasi lagi untuk diperhatikan adalah jumlah node interior fib(n) - 1. Oleh karena itu jumlah total node adalah 2 * fib(n) - 1.

Karena Anda menjatuhkan koefisien ketika mengklasifikasikan kompleksitas komputasi, jawaban akhirnya adalah θ(fib(n)).

Kompleksitas waktu algoritma rekursif dapat diperkirakan dengan lebih baik dengan menggambar pohon rekursi, Dalam hal ini relasi perulangan untuk menggambar pohon rekursi adalah T (n) = T (n-1) + T (n-2) + O (1) perhatikan bahwa setiap langkah membutuhkan O (1) yang berarti waktu yang konstan, karena hanya melakukan satu perbandingan untuk memeriksa nilai n dalam jika blok. Pohon Pengembalian akan terlihat seperti

          n
   (n-1)      (n-2)
(n-2)(n-3) (n-3)(n-4) ...so on

Di sini katakanlah setiap tingkat pohon di atas dilambangkan oleh i karenanya,

i
0                        n
1            (n-1)                 (n-2)
2        (n-2)    (n-3)      (n-3)     (n-4)
3   (n-3)(n-4) (n-4)(n-5) (n-4)(n-5) (n-5)(n-6)

katakanlah pada nilai tertentu dari i, ujung pohon, kasus itu adalah ketika ni = 1, maka i = n-1, yang berarti bahwa ketinggian pohon adalah n-1. Sekarang mari kita lihat berapa banyak pekerjaan yang dilakukan untuk masing-masing dari n lapisan dalam pohon. Perhatikan bahwa setiap langkah membutuhkan O (1) waktu seperti yang dinyatakan dalam relasi perulangan.

2^0=1                        n
2^1=2            (n-1)                 (n-2)
2^2=4        (n-2)    (n-3)      (n-3)     (n-4)
2^3=8   (n-3)(n-4) (n-4)(n-5) (n-4)(n-5) (n-5)(n-6)    ..so on
2^i for ith level

karena i = n-1 adalah ketinggian pekerjaan pohon yang dilakukan pada setiap level

i work
1 2^1
2 2^2
3 2^3..so on

Maka total pekerjaan yang dilakukan akan menjumlahkan pekerjaan yang dilakukan pada setiap level, maka itu akan menjadi 2 ^ 0 + 2 ^ 1 + 2 ^ 2 + 2 ^ 3 ... + 2 ^ (n-1) karena i = n-1. Dengan deret geometri jumlah ini adalah 2 ^ n, maka kompleksitas waktu total di sini adalah O (2 ^ n)

Nah, menurut saya untuk itu O(2^n)karena dalam fungsi ini hanya rekursi yang mengambil waktu yang cukup lama (bagi dan taklukkan). Kita melihat bahwa, fungsi di atas akan berlanjut di pohon sampai daun mendekati ketika kita mencapai tingkat F(n-(n-1))yaitu F(1). Jadi, di sini ketika kita mencatat kompleksitas waktu yang dihadapi di setiap kedalaman pohon, seri penjumlahan adalah:

1+2+4+.......(n-1)
= 1((2^n)-1)/(2-1)
=2^n -1

itu adalah urutan 2^n [ O(2^n) ].

Versi rekursi naif dari Fibonacci adalah eksponensial dengan desain karena pengulangan dalam perhitungan:

Pada dasarnya Anda menghitung:

F (n) tergantung pada F (n-1) dan F (n-2)

F (n-1) tergantung pada F (n-2) lagi dan F (n-3)

F (n-2) tergantung pada F (n-3) lagi dan F (n-4)

maka Anda mengalami setiap panggilan tingkat 2 rekursif yang membuang banyak data dalam perhitungan, fungsi waktu akan terlihat seperti ini:

T (n) = T (n-1) + T (n-2) + C, dengan konstanta C

T (n-1) = T (n-2) + T (n-3)> T (n-2)

T (n)> 2 * T (n-2)

...

T (n)> 2 ^ (n / 2) * T (1) = O (2 ^ (n / 2))

Ini hanya batas bawah yang untuk keperluan analisis Anda harus cukup tetapi fungsi real time adalah faktor konstanta dengan rumus Fibonacci yang sama dan bentuk tertutup diketahui eksponensial dari rasio emas.

Selain itu, Anda dapat menemukan versi Fibonacci yang dioptimalkan menggunakan pemrograman dinamis seperti ini:

static int fib(int n)
{
    /* memory */
    int f[] = new int[n+1];
    int i;

    /* Init */
    f[0] = 0;
    f[1] = 1;

    /* Fill */
    for (i = 2; i <= n; i++)
    {
        f[i] = f[i-1] + f[i-2];
    }

    return f[n];
}

Itu dioptimalkan dan hanya melakukan n langkah tetapi juga eksponensial.

Fungsi biaya ditentukan dari ukuran Input hingga jumlah langkah untuk menyelesaikan masalah. Saat Anda melihat versi dinamis Fibonacci ( n langkah untuk menghitung tabel) atau algoritma termudah untuk mengetahui apakah bilangan prima ( sqrt (n) untuk menganalisis pembagi angka yang valid). Anda mungkin berpikir bahwa algoritma ini adalah O (n) atau O (sqrt (n)) tetapi ini tidak benar karena alasan berikut: Input ke algoritma Anda adalah angka: n , menggunakan notasi biner ukuran input untuk suatu integer n adalah log2 (n) kemudian melakukan perubahan variabel

m = log2(n) // your real input size

mari cari tahu jumlah langkah sebagai fungsi dari ukuran input

m = log2(n)
2^m = 2^log2(n) = n

maka biaya algoritma Anda sebagai fungsi dari ukuran input adalah:

T(m) = n steps = 2^m steps

dan inilah mengapa biayanya eksponensial.

Sangat mudah untuk menghitung dengan membuat diagram panggilan fungsi. Cukup tambahkan pemanggilan fungsi untuk setiap nilai n dan lihat bagaimana jumlahnya tumbuh.

Big O adalah O (Z ^ n) di mana Z adalah rasio emas atau sekitar 1,62.

Baik angka Leonardo dan angka Fibonacci mendekati rasio ini saat kami meningkatkan n.

Tidak seperti pertanyaan Big O lainnya, tidak ada variabilitas dalam input dan algoritma dan implementasi algoritma didefinisikan dengan jelas.

Tidak perlu banyak matematika yang rumit. Cukup gambarkan fungsi panggilan di bawah ini dan paskan fungsi dengan angka.

Atau jika Anda terbiasa dengan rasio emas, Anda akan mengenalinya.

Jawaban ini lebih benar daripada jawaban yang diterima yang mengklaim akan mendekati f (n) = 2 ^ n. Tidak akan pernah. Ini akan mendekati f (n) = golden_ratio ^ n.

2 (2 -> 1, 0)

4 (3 -> 2, 1) (2 -> 1, 0)

8 (4 -> 3, 2) (3 -> 2, 1) (2 -> 1, 0)
            (2 -> 1, 0)


14 (5 -> 4, 3) (4 -> 3, 2) (3 -> 2, 1) (2 -> 1, 0)
            (2 -> 1, 0)

            (3 -> 2, 1) (2 -> 1, 0)

22 (6 -> 5, 4)
            (5 -> 4, 3) (4 -> 3, 2) (3 -> 2, 1) (2 -> 1, 0)
                        (2 -> 1, 0)

                        (3 -> 2, 1) (2 -> 1, 0)

            (4 -> 3, 2) (3 -> 2, 1) (2 -> 1, 0)
                        (2 -> 1, 0)

http://www.ics.uci.edu/~eppstein/161/960109.html

waktu (n) = 3F (n) - 2