- c - 在位数组中找到第一个零
- linux - Unix 显示有关匹配两种模式之一的文件的信息
- 正则表达式替换多个文件
- linux - 隐藏来自 xtrace 的命令
此问题的时间复杂度不同于已提出的类似问题。这是来自 Zauba 开发人员招聘挑战( Activity 于一个月前结束)的问题:
f(0) = p
f(1) = q
f(2) = r
for n > 2
f(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
一样大。
在上面的链接中,没有指定时间复杂度,我已经在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;
}
请注意,我在原始代码中的适当位置使用模 10^9 + 7
来处理溢出,在必要时处理适当的边缘情况,并且我使用了 java long 数据类型(如果它有帮助).
但由于这仍然需要 O(n)
时间,我期待一个更好的解决方案来处理 n ~ 10^18
。
编辑
正如用户 גלעד ברקן 提到它与矩阵求幂的关系一样,我尝试这样做并停留在一个特定的点,我不确定在矩阵的第 4 行第 3 列中放置什么。请提出任何建议和更正。
| 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
最佳答案
矩阵求幂确实是正确的方法,但还有一些工作要做。
自 g(n)
不是常量值,无法有效(O(log n)
而不是 O(n)
)对当前形式的递归关系应用矩阵求幂。
需要为 g(n)
找到类似的递推关系只有一个常数项尾随。自 g(n)
是立方的,需要 3 个递归项:
g(n) = x*g(n-1) + y*g(n-2) + z*g(n-3) + w
展开它们每个的三次表达式:
n³ + n² = x(n³-2n²+n) + y(n³-5n²+8n-4) + z*(n³-8n²+21n-18) + w
= n³(x+y+z) + n²(-2x-5y-8z) + n(x+8y+21z) + (w-4y-18z)
匹配系数以获得 x, y, z
的三个联立方程加上另一个来计算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
方便的是,这些系数也是整数*,这意味着可以直接对递归进行模运算。
* 我怀疑这是巧合 - 这很可能是招聘考官的意图。
因此矩阵递推方程为:
| 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 |
(每个操作都隐含地对 10^9 + 7
或提供的任何此类数字进行模数。)
请注意 Java 的 %
运算符是余数,它不同于负数的模数。示例:
-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;
}
模矩阵函数:
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)
);
}
以下是上述两种算法的一些示例基准。
原始迭代算法:
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 多秒来计算 n = 10^9
,而新算法仅用了 0.6 毫秒秒(加速了 150,000 倍)!
原始算法的时间复杂度显然是线性的(正如预期的那样); n = 10^10
花了太长时间才完成,所以我没有继续。
新算法的时间复杂度显然是对数的 - 是 n
的两倍数量级。导致执行时间加倍(同样,由于平方求幂,正如预期的那样)。
对于 n
的“小”值( < 100
) 矩阵分配和操作的开销掩盖了算法本身,但很快就变得微不足道了 n
增加。
关于java - 在小于 O(N) 的时间内找到序列的第 n 项,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56959409/
这个问题在这里已经有了答案: Different ways of loading a file as an InputStream (6 个答案) 关闭 8 年前。 在我的 gradle java
给定一个 User 类: class User end 我想使用 .class_eval 定义一个新常量.所以: User.class_eval { AVOCADO = 'fruit' } 如果我尝试
这可能听起来很奇怪,但我正在开发一个需要查找 div 内的元素或 div 本身的插件。 脚本根据用户选择查找元素,但内容(包括标记)是可变的。因此脚本将按如下方式查找元素: $('.block').f
关闭。此题需要details or clarity 。目前不接受答案。 想要改进这个问题吗?通过 editing this post 添加详细信息并澄清问题. 已关闭 7 年前。 Improve th
我需要在按我自己的函数排序的对的多集中查找并删除一个值。显然, .find 总是将迭代器返回到末尾,而不是返回到搜索到的值。有小费吗?这是函数: struct cmp { bool operato
求助!我将如何通过遍历查看字符并计算有效字符出现之前的下划线数量来查找和删除前导下划线。以及从字符串末尾向后迭代以查找任何尾随下划线。 我可以使用下面的方法来删除下划线,但是如何迭代才能找到下划线。
如果你在 $(xml) 中有下面的 xml,你会变得懒惰: $(xml).find("animal").find("dog").find("beagle").text() 在 jQuery 中是否有类
你如何找到4个文件的交集? 我用了grep -Fx -f 1.txt 2.txt 3.txt 4.txt ,但它似乎只适用于 2 个文件。同样comm -12 1.txt 2.txt无法扩展为 4 个
我已经完成了标记的姿势估计并获得了 rvec 和 tvec 值。我不知道如何找到它的中心,因为我需要绘制一个需要中心值的圆柱体。 我该怎么做? 最佳答案 标记的 tvec 是标记从原点的平移 (x,y
我有一个任务,我需要找到 2 个单链接(单对单)列表的交集。我还必须为 2 个双向链接(双重 vs 双重)列表执行此操作: 对于单链表,我使用 mergeSort() 对两个列表进行排序,然后逐项比较
我是 R 的新手,我有一个 100x100 的方阵。我想找到这个矩阵的最大特征值。我试过了 is.indefinite(x) 但是它写 is.indefinite(x) : argument x is
您好,我是 svg 和 JavaScript 的新手,当鼠标位于 svg 上方时,我试图使一些 svg 元素弹出(通过缩放),反之亦然,当鼠标离开 svg 元素时。 我已经能够通过使用转换使 svg
我正在尝试为 scala 项目编写一个类,但在多个地方使用 class、def、while 等关键字出现此错误。 它发生在这样的地方: var continue = true while (conti
我有两个 pandas 数据框,它们只取自一列并将日期列设置为索引,所以现在我有两个 Series。我需要找到这些系列的相关性。 这里有几行来自dfd: index change 2018-
我正在尝试调整我的 Vagrantfile,因此如果它丢失,它会自动在项目根目录中创建一个文件夹。创建文件夹没问题,但我无法找到创建该文件夹的位置。 我发现此信息可在 Vagrant::Environ
我正在尝试在 jquery 中找到 Test3 的位置,请有人引导我走上正确的道路。 我需要jquery来显示5 Test7 Test2 Test6 Test5 Test3 Test8 谢谢 最佳
大家早上好 我有一个像这样的图像列表: 使用 jQuery 如何查找 ul#preload 中包含特定字符串(例如“green”)的所有图像 src 类似... var new_src = j
我正在开发一个修改 Excel 文件的应用程序。 如何找到任意行中最后使用的单元格? 示例:行号 => 5 中最后使用的单元格 最佳答案 要找到一行中的最后一个单元格,您需要 Range 的 End
我刚刚陷入 react native ,需要一些帮助才能在找到 token 时导航到 protected 屏幕。我应该在哪里寻找应用程序加载时的 token ?如何在不多次调用导航的情况下导航用户一次
非常奇怪...此页面是 protected 内容还是我不知道的内容?我尝试单击下一页 anchor 。 参见this page first. 我试图用这个来抓取元素 var buttonNext =
我是一名优秀的程序员,十分优秀!