這個(gè)問題的時(shí)間復(fù)雜度不同于被問到的類似問題。這是來自 Zauba 開發(fā)人員招聘挑戰(zhàn)（活動(dòng)于一個(gè)月前結(jié)束）的問題：f(0) = pf(1) = qf(2) = rfor n > 2f(n) = a*f(n-1) + b*f(n-2) + c*f(n-3) + g(n)where g(n) = n*n*(n+1)p, q, r, a, b, c, n給出。n可以大到10^18.鏈接到類似的問題在上面的鏈接中，沒有指定時(shí)間復(fù)雜度，我已經(jīng)在 中解決了這個(gè)問題O(n)，下面是偽代碼（只是一種方法，所有可能的邊界和邊緣情況都在比賽中處理）。if(n == 0) return p;if(n == 1) return q;if(n == 2) return r;for(long i=3;i<=n;i++){ now = a*r + b*q + c*p + i*i*(i+1); p = q; q = r; r = now;}請(qǐng)注意，我10^9 + 7在原始代碼中的適當(dāng)位置使用模數(shù)來處理溢出，在必要時(shí)處理適當(dāng)?shù)倪吘壡闆r，并且我使用了 java long 數(shù)據(jù)類型（如果它有幫助）。但由于這仍然需要O(n)時(shí)間，我期待一個(gè)更好的解決方案來處理n ~ 10^18.編輯正如用戶 ???? ???? 提到它與矩陣求冪的關(guān)系一樣，我嘗試這樣做并停留在一個(gè)特定的點(diǎn)，我不確定在矩陣的第 4 行第 3 列中放置什么。請(qǐng)?zhí)岢鋈魏谓ㄗh和更正。| a b c 1? | | f(n) | | f(n+1) || 1 0 0 0 | |f(n-1)| | f(n) || 0 1 0 0 | |f(n-2)| => | f(n-1) || 0 0 ?! 0 | | g(n) | | g(n+1) | M A B
1 回答
慕標(biāo)5832272
TA貢獻(xiàn)1966條經(jīng)驗(yàn) 獲得超4個(gè)贊
矩陣求冪確實(shí)是正確的方法，但還有一些工作要做。
由于g(n)不是常數(shù)值，因此無法有效地（O(log n)而不是O(n)）將矩陣求冪應(yīng)用于當(dāng)前形式的遞推關(guān)系。
需要找到類似的遞歸關(guān)系，g(n)只有一個(gè)常數(shù)項(xiàng)尾隨。由于g(n)是三次方，因此需要 3 個(gè)遞歸項(xiàng)：
g(n) = x*g(n-1) + y*g(n-2) + z*g(n-3) + w
展開它們每個(gè)的三次表達(dá)式：
n3 + n2 = x(n3-2n2+n) + y(n3-5n2+8n-4) + z*(n3-8n2+21n-18) + w
= n3(x+y+z) + n2(-2x-5y-8z) + n(x+8y+21z) + (w-4y-18z)
匹配系數(shù)以獲得三個(gè)聯(lián)立方程 加上x, y, z另一個(gè)來計(jì)算w：
x + y + z = 1
-2x - 5y - 8z = 1
x + 8y + 21z = 0
w - 4y - 18z = 0
解決它們得到：
x = 3 y = -3 z = 1 w = 6
方便的是，這些系數(shù)也是整數(shù)*，這意味著可以直接對(duì)遞歸進(jìn)行模運(yùn)算。
* 我懷疑這是巧合——這很可能是招聘考官的意圖。
因此，矩陣遞推方程為：
| a b c 1 0 0 0 | | f(n-1) | | f(n) |
| 1 0 0 0 0 0 0 | | f(n-2) | | f(n-1) |
| 0 1 0 0 0 0 0 | | f(n-3) | | f(n-2) |
| 0 0 0 3 -3 1 6 | x | g(n) | = | g(n+1) |
| 0 0 0 1 0 0 0 | | g(n-1) | | g(n) |
| 0 0 0 0 1 0 0 | | g(n-2) | | g(n-1) |
| 0 0 0 0 0 0 1 | | 1 | | 1 |
最終的矩陣求冪方程為：
[n-2]
| a b c 1 0 0 0 | | f(2) | | f(n) | | f(2) | | r |
| 1 0 0 0 0 0 0 | | f(1) | | f(n-1) | | f(1) | | q |
| 0 1 0 0 0 0 0 | | f(0) | | f(n-2) | | f(0) | | p |
| 0 0 0 3 -3 1 6 | x | g(3) | = | g(n+1) | , | g(3) | = | 36 |
| 0 0 0 1 0 0 0 | | g(2) | | g(n) | | g(2) | | 12 |
| 0 0 0 0 1 0 0 | | g(1) | | g(n-1) | | g(1) | | 2 |
| 0 0 0 0 0 0 1 | | 1 | | 1 | | 1 | | 1 |
（每個(gè)操作都是隱式模數(shù)10^9 + 7或提供的任何此類數(shù)字。）
請(qǐng)注意，Java 的%運(yùn)算符是remainder ，它與負(fù)數(shù)的模數(shù)不同。例子：
-1 % 5 == -1 // Java
-1 = 4 (mod 5) // mathematical modulus
解決方法很簡單：
long mod(long b, long a)
{
// computes a mod b
// assumes that b is positive
return (b + (a % b)) % b;
}
原始迭代算法：
long recurrence_original(
long a, long b, long c,
long p, long q, long r,
long n, long m // 10^9 + 7 or whatever
) {
// base cases
if (n == 0) return p;
if (n == 1) return q;
if (n == 2) return r;
long f0, f1, f2;
f0 = p; f1 = q; f2 = r;
for (long i = 3; i <= n; i++) {
long f3 = mod(m,
mod(m, a*f2) + mod(m, b*f1) + mod(m, c*f0) +
mod(m, mod(m, i) * mod(m, i)) * mod(m, i+1)
);
f0 = f1; f1 = f2; f2 = f3;
}
return f2;
}
模矩陣函數(shù)：
long[][] matrix_create(int n)
{
return new long[n][n];
}
void matrix_multiply(int n, long m, long[][] c, long[][] a, long[][] b)
{
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
long s = 0;
for (int k = 0; k < n; k++)
s = mod(m, s + mod(m, a[i][k]*b[k][j]));
c[i][j] = s;
}
}
}
void matrix_pow(int n, long m, long p, long[][] y, long[][] x)
{
// swap matrices
long[][] a = matrix_create(n);
long[][] b = matrix_create(n);
long[][] c = matrix_create(n);
// initialize accumulator to identity
for (int i = 0; i < n; i++)
a[i][i] = 1;
// initialize base to original matrix
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
b[i][j] = x[i][j];
// exponentiation by squaring
// there are better algorithms, but this is the easiest to implement
// and is still O(log n)
long[][] t = null;
for (long s = p; s > 0; s /= 2) {
if (s % 2 == 1) {
matrix_multiply(n, m, c, a, b);
t = c; c = a; a = t;
}
matrix_multiply(n, m, c, b, b);
t = c; c = b; b = t;
}
// write to output
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
y[i][j] = a[i][j];
}
最后，新算法本身：
long recurrence_matrix(
long a, long b, long c,
long p, long q, long r,
long n, long m
) {
if (n == 0) return p;
if (n == 1) return q;
if (n == 2) return r;
// original recurrence matrix
long[][] mat = matrix_create(7);
mat[0][0] = a; mat[0][1] = b; mat[0][2] = c; mat[0][3] = 1;
mat[1][0] = 1; mat[2][1] = 1;
mat[3][3] = 3; mat[3][4] = -3; mat[3][5] = 1; mat[3][6] = 6;
mat[4][3] = 1; mat[5][4] = 1;
mat[6][6] = 1;
// exponentiate
long[][] res = matrix_create(7);
matrix_pow(7, m, n - 2, res, mat);
// multiply the first row with the initial vector
return mod(m, mod(m, res[0][6])
+ mod(m, res[0][0]*r) + mod(m, res[0][1]*q) + mod(m, res[0][2]*p)
+ mod(m, res[0][3]*36) + mod(m, res[0][4]*12) + mod(m, res[0][5]*2)
);
}
以下是上述兩種算法的一些示例基準(zhǔn)。
原始迭代算法：
n time (μs)
-------------------
10^1 9.3
10^2 44.9
10^3 401.501
10^4 3882.099
10^5 27940.9
10^6 88873.599
10^7 877100.5
10^8 9057329.099
10^9 91749994.4
新矩陣算法：
n time (μs)
------------------
10^1 69.168
10^2 128.771
10^3 212.697
10^4 258.385
10^5 318.195
10^6 380.9
10^7 453.487
10^8 560.428
10^9 619.835
10^10 652.344
10^11 750.518
10^12 769.901
10^13 851.845
10^14 934.915
10^15 1016.732
10^16 1079.613
10^17 1123.413
10^18 1225.323
舊算法用了 90 多秒來計(jì)算n = 10^9，而新算法只用了 0.6多毫秒（150,000 倍的加速）！
原始算法的時(shí)間復(fù)雜度顯然是線性的（正如預(yù)期的那樣）；n = 10^10花了太長時(shí)間才完成，所以我沒有繼續(xù)。
新算法的時(shí)間復(fù)雜度顯然是對(duì)數(shù)的——將 的數(shù)量級(jí)加倍n導(dǎo)致執(zhí)行時(shí)間加倍（同樣，正如預(yù)期的那樣，由于平方求冪）。
n對(duì)于( )的“小”值，< 100矩陣分配和運(yùn)算的開銷掩蓋了算法本身，但隨著n增加而迅速變得微不足道。
添加回答
舉報(bào)
0/150
提交
取消