算法分析

Question

我有下面的僞代碼的算法：

R(n) 
if(n = 1) 
    return 1 
else 
    return(R(n-1) + 2 * n + 1) 

我需要設置爲通過該算法進行乘法運算的次數再次發生關係，並解決它。

下面是對的嗎？

R(1) = 0 
R(n) = R(n-1) + n^2 

Answer 1

您每步只執行一次乘法。因此，該關係將爲：

R(n) = R(n-1) + 1 

Answer 2

在所示的算法中，通過將R（n-1）與2 * n + 1相加來計算R（n）。如果使用乘法計算2 * n，則每個遞歸級別將有一個乘法，因此在R（n）的計算中有n-1次乘法。

要通過遞推計算，設M（n）是用於計算R（n）的乘法數。遞歸邊界條件是M（1）= 0，並且對於i> 1，遞歸關係是M（i）= M（i-1）+ 1。 （1）= 0; R（n）= R（n-1）+ n^2「作爲乘法次數的遞推包括：
•R（）已經在使用中作爲正在計算的函數，因此重新使用R乘法次數不正確
•算法中的每個遞歸級別都添加一次乘法，而不是n2次乘法。 R（n）= 1 + 5 + 7 + ... + 2n + 1 = 1 + 3 + 5 + 7 + ... + 2n + 1-3 = n 2 -3。即函數R（n）返回值n²-3。