斐波納契系列在PHP中的第n個數字與O（日誌N）

-1

尋找複雜代碼爲O(log N)的解決方案。 space complexity將O(1)斐波納契系列在PHP中的第n個數字與O（日誌N）

我嘗試以下

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); 
}

將原問題

來源

2016-03-31 Kapil Sharma

的O(1)所以，關於你的代碼，你已經實現空間複雜度，但你的時間複雜度仍然O(n)，因爲它仍然會執行for循環的n以查找n'th數字。其次，您嘗試創建的函數可以生成斐波那契序列，但也可以使用相同的原理生成其他序列，但是從不同的數字開始。

我們需要做的，在不到線性的時間來解決這個問題的第一件事，就是用矩陣來表示序列，像這樣：

我們可以在左側創建矩陣從兩個最初的數字。然後我們可以將它提升到n-1的能力，我們將在結果矩陣的左上角得到我們想要的數字。

在PHP簡單實現看起來是這樣的：

/** 
* 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]; 
}

但是，你很可能會看到，我們仍然沒有得到for循環擺脫的，這意味着我們仍然有一個O(n)時間複雜度。爲了最終獲得線性時間，我們需要優化power_of_matrix()。

現在，我們將矩陣乘以n次。但是我們真的必須這樣做嗎？讓我們打破一個簡單的等式：

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

通過計算n/2「次方，我們可以存儲結果，並通過其大量繁殖，爲我們節省了大量的乘法運算步驟。我們只需要確保，如果權力不是平均的，我們會將結果乘以一個額外的時間。

同樣的邏輯也適用於矩陣，我們可以用它來優化power_of_matrix像這樣：

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; 
}

現在，該溶液具有O(log n)時間複雜度。但是，因爲我們在這裏使用遞歸，並且由於PHP數組的性質，因此此方法不具有空間複雜性。

爲了達到這個目的，我們必須通過引用傳遞矩陣並修改它，而不是每次都返回一個新的結果矩陣。

我希望這可以幫助您理解和解決問題。

來源

2016-03-31 13:34:30

斐波納契系列在PHP中的第n個數字與O（日誌N）

回答

相關問題