Fibonacci dizisine benzer dizilerin n’inci elemanın O(logn) zamanda hesaplanması

Fibonacci sayıları şu şekilde tanımlanabilir:

F_0 = 1, F_1 = 1, F_n = F_{n-1} + F_{n-2}

Bu tanımı kullanarak kendine yinelemeli bir kod yazmak oldukça kolaydır

int fib(int n){
    if(n == 0) return 1;
    if(n == 1) return 1;
    return fib(n-1) + fib(n-2);
}

Bu algoritmanın zaman karmaşıklığı O(2^n)’dir. Küçük bir optimizasyonla zaman karmaşıklığı linear hale getirilebilir.

#define MAXN 1000
int fibo[MAXN];
int fib(int n){
    if(fibo[n] != 0) return fibo[n];
    if(n == 0) return fibo[n] = 1;
    if(n == 1) return fibo[n] = 1;
    return fibo[n] = fib(n-1) + fib(n-2);
}

Bir dizide daha önce hesapladığımız fibonacci sayılarını tutarak aynı değerin birden fazla hesaplanmasını engelleriz ve zaman karmaşılığımız O(n) olur. Algoritmamızı değiştirerek zaman karmaşıklığımızı düşürebiliriz.

Matris çarpımının özelliklerinden yararlanarak.

(\begin{matrix}a &b \end{matrix}) *( \begin{matrix}0&1\\1&1 \end{matrix}) = (\begin{matrix}b &a+b \end{matrix})  , yani

(\begin{matrix}F_{n-1} & F_{n} \end{matrix}) *( \begin{matrix}0&1\\1&1 \end{matrix}) = (\begin{matrix}F_n &F_{n+1} \end{matrix})

Bu işlemi tekrar tekrar yaptığımızda en son durumda elde edeceğimiz ifade

(\begin{matrix}F_{0} & F_{1} \end{matrix}) *( \begin{matrix}0&1\\1&1 \end{matrix})^n = (\begin{matrix}F_n &F_{n+1} \end{matrix}) ‘dir.

( \begin{matrix}0&1\\1&1 \end{matrix})^n , http://bilimolimpiyatları.com/2019/04/02/bir-sayinin-ussunu-ologn-zamanda-hesaplamak/ da bahsettiğimiz yöntem kullanılarak O(logn) de hesaplanabilir.

#include <bits/stdc++.h>
using namespace std;

//matris' yı b'ye kopyalayan fonksiyon
void same(int matris[3][3], int b[3][3]){
    for(int i = 0; i < 2; ++i)
        for(int j = 0; j < 2; ++j)
            b[i][j] = matris[i][j]; 
}

//matris çarpımı, sonuç matris'ya kopyalanır
void mult(int a[3][3], int b[3][3]){
    int a1 = a[0][0]*b[0][0] + a[1][0]*b[1][0];
    int a2 = a[0][0]*b[0][1] + a[1][0]*b[1][1];
    int a3 = a[1][0]*b[0][0] + a[1][1]*b[1][0];
    int a4 = a[1][0]*b[0][1] + a[1][1]*b[1][1];
    a[0][0] = a1;
    a[0][1] = a2;
    a[1][0] = a3;
    a[1][1] = a4;
}
int fib(int n){
    //Üssünü alacağımız matris
    int matris[3][3] = {{0, 1}, {1, 1}};

    //Bu matris, çarpımlarda etkisiz elemandır
    int result[3][3] = {{1,0},{0,1}};

    //önceki bloglarda gösterilen üs fonksiyonun
    //matrislere uyarlaması
    while(n > 0){
        if(n % 2){
            mult(result, matris);
            --n;
        }
        mult(matris, matris);
        n /= 2;
    }

    //Üs alındıktan sonra (F0, F1) matrisi
    //ile çarpım
    return result[1][0] + result[0][0];
}

int main(){
    //Program F8'i çıktılar
    cout << fib(8) << endl;
}

Bu yöntem, Fibonacci sayılarından farklı dizileri hesaplamak için de kullanılabir. Mesela Pell sayılarında :

P_0 = 0, P_1 = 1, P_n = 2*P_{n-1} + P_{n-2}

Bu sayıları hesaplamak için sadece matrisimizi değiştirmemiz yeterli olacaktır.

(\begin{matrix}a &b \end{matrix}) *( \begin{matrix}0&1\\1&2 \end{matrix}) = (\begin{matrix}b &a+2*b \end{matrix}) böylece

(\begin{matrix}P_{n-1} & P_{n} \end{matrix}) *( \begin{matrix}0&1\\1&2 \end{matrix}) = (\begin{matrix}P_n &P_{n+1} \end{matrix}) ve

(\begin{matrix}P_{0} & P_{1} \end{matrix}) *( \begin{matrix}0&1\\1&2 \end{matrix})^n = (\begin{matrix}P_n &P_{n+1} \end{matrix}) ‘dir.

Kodumuzda sadece matrisimizin ilk değerini ve P0’ı değiştirirsek :


#include <bits/stdc++.h>
using namespace std;

void same(int matris[3][3], int b[3][3]){
    for(int i = 0; i < 2; ++i)
        for(int j = 0; j < 2; ++j)
            b[i][j] = matris[i][j]; 
}

void mult(int a[3][3], int b[3][3]){
    int a1 = a[0][0]*b[0][0] + a[1][0]*b[1][0];
    int a2 = a[0][0]*b[0][1] + a[1][0]*b[1][1];
    int a3 = a[1][0]*b[0][0] + a[1][1]*b[1][0];
    int a4 = a[1][0]*b[0][1] + a[1][1]*b[1][1];
    a[0][0] = a1;
    a[0][1] = a2;
    a[1][0] = a3;
    a[1][1] = a4;
}
int pell(int n){
    //Yeni matrisimiz
    int matris[3][3] = {{0, 1}, {1, 2}};

    int result[3][3] = {{1,0},{0,1}};

    while(n > 0){
        if(n % 2){
            mult(result, matris);
            --n;
        }
        mult(matris, matris);
        n /= 2;
    }

    // F0 = 0 iken P0 = 0 olduğu için
    // result[0][0] hesaplamaya katılmaz
    return result[1][0] ;
}

int main(){
    //Program P8'i çıktılar
    cout << pell(8) << endl;
}

Add a Comment

Your email address will not be published. Required fields are marked *