fibonacci serileri ph ile php arasında O (log N)

Question

Karmaşıklık kodunun O(log N) olduğu bir çözüm aranır. space complexity, O(1)

Ben

function fib($a, $b, $N) { 

    $c = ""; 
    if ($N == 0) { 
     return intval($a); 
    } else if ($N == 1) { 
     return intval($b); 
    } else { 
     for ($i = 1; $i <= $N - 1; $a = $b, $b = $c, $i++) { 
      $c = ($a) + ($b); 
     } 
    } 
    return intval($c); 
} 

Orijinal sorunun O(1) ait

Answer 1

Yani kod ilişkin, sen elde ettik uzay karmaşıklığı ancak zaman karmaşıklığı hala O(n) aşağıdaki çalıştı olacaktır n'th numarasını bulmak için for döngüsünün n yürütmelerini almaya devam edecektir. İkinci olarak, yaratmaya çalıştığınız işlev, fibonacci dizisini üretebilir, ancak aynı ilkeyi kullanarak ancak farklı sayılardan başlayarak başka diziler de üretebilir.

Biz soldaki matrisi oluşturabilirsiniz: Lineer zamanda daha az bu sorunu çözmek için yapmanız gerekir

ilk şey, bu yüzden gibi matrisler kullanılarak diziyi temsil etmek İlk iki sayıdan. Ardından, n-1 güce yükseltebiliriz ve istenen numarayı sonuç matrisinin sol üst köşesinde alacağız. muhtemelen görebileceğiniz gibi biz hala O(n) bir zaman karmaşıklık var, yani biz hala döngü kurtulmak yok,

/** 
* Takes two 2x2 matrices as parameters, multiplies them and returns the result. 
*/ 
function multiply_matrix(array $a, array $b) { 
    return [ 
     [ 
      $a[0][0]*$b[0][0] + $a[0][1]*$b[1][0], 
      $a[0][0]*$b[0][1] + $a[0][1]*$b[1][1] 
     ], 
     [ 
      $a[1][0]*$b[0][0] + $a[1][1]*$b[1][0], 
      $a[1][0]*$b[0][1] + $a[1][1]*$b[1][1] 
     ] 
    ]; 
} 

/** 
* Multiplies a 2x2 matrix to the n'th power 
*/ 
function power_of_matrix(array $matr, $n) { 
    $result = $matr; 

    for ($i = 1; $i < $n; ++$i) { 
     $result = multiply_matrix($result, $matr); 
    } 

    return $result; 
} 

function gf($a, $b, $n) { 
    if ($n == 0) { 
     return $a; 
    } 

    $result = power_of_matrix([[$a+$b, $b], [$b, $a]], $n - 1); 

    return $result[0][0]; 
} 

Ama: PHP

Basit uygulama aşağıdaki gibi görünebilir. Sonunda doğrusal sürenin altına inmek için, power_of_matrix()'u optimize etmemiz gerekecek.

Şu anda matrisler n kat çarpıyoruz. Ama bunu gerçekten yapmak zorunda mıyız? Basit bir denklem yıkmak edelim: bize çarpma adımları bir çok tasarruf,

2^8 = 256 = 2^4 * 2^4 = 2^4 * 2^2 * 2^2 = 2^4 * 2^2 * 2 * 2 

güç inci' n/2 hesaplayarak, biz sonuca saklayabilir ve onun tarafından çarpın. Sadece, güç bile olmazsa, sonucu bir kez daha fazla çarptığımızdan emin olmalıyız.

Aynı mantık matrisleri için geçerlidir ve böylece gibi power_of_matrix optimize için kullanabilirsiniz:

function power_of_matrix(array $matr, $n) { 
    if ($n == 0 || $n == 1) { 
     return $matr; 
    } 

    $result = power_of_matrix($matr, intval($n/2)); 
    $result = multiply_matrix($result, $result); 

    if ($n % 2 != 0) { 
     return multiply_matrix($result, $matr); 
    } 

    return $result; 
} 

Şimdi çözüm O(log n) bir zaman karmaşıklığını vardır. Ancak, burada yineleme kullandığımız için ve PHP dizilerinin yapısı nedeniyle, bu yöntemin O(1) alan karmaşıklığı yoktur.

Bunu başarmak için, her seferinde yeni bir sonuç matrisini döndürmek yerine, matrisi referans alarak değiştirip değiştirmek zorundayız.

Umarım bu, sorunu anlamanıza ve çözmenize yardımcı olur.