java - 最小跳转数组递归时间复杂度应为 O(n^n) 或 O(n!)
问题描述
我在 GeekforGeeks https://www.geeksforgeeks.org/minimum-number-of-jumps-to-reach-end-of-a-given-array/中检查“到达终点的最小跳跃次数”问题。我对那里提到的时间复杂度感到困惑,即 O(n^n)。
// Returns minimum number of
// jumps to reach arr[h] from arr[l]
static int minJumps(int arr[], int l, int h)
{
// Base case: when source
// and destination are same
if (h == l)
return 0;
// When nothing is reachable
// from the given source
if (arr[l] == 0)
return Integer.MAX_VALUE;
// Traverse through all the points
// reachable from arr[l]. Recursively
// get the minimum number of jumps
// needed to reach arr[h] from these
// reachable points.
int min = Integer.MAX_VALUE;
for (int i = l + 1; i <= h
&& i <= l + arr[l];
i++) {
int jumps = minJumps(arr, i, h);
if (jumps != Integer.MAX_VALUE && jumps + 1 < min)
min = jumps + 1;
}
return min;
}
如果我看到上面的代码块,就会从 i=l+1 调用 minJumps(arr, i, h) 递归调用。因此,在每个递归步骤中,l(start position) 都会增加 1。时间复杂度应计算如下。
T(N) = (n-1)*(n-2)*(n-3)...*1
= (n-1)!
我不明白为什么时间复杂度是 O(n^n)。在其他几个地方,我也看到这个递归解决方案的时间复杂度被提到为 O(n^n) 没有适当的解释。请帮我做一个简单的解释并指出我在这里遗漏的内容。
解决方案
我可以看到递归关系为T(n) = T(n-1) + T(n-2) + T(n-3) + T(n-4) + ... + T(0)
,因为循环是从 l 到 h (暂时忽略if
条件)。因此,对于一个区间,该区间中的[l,h]
每个值都将在最坏的情况下被调用,minJumps(l+1, h), minJumps(l+2, h) ... minJumps(h, h)
并且可以注意到上述递归关系在这里成立。
现在,解决关系,我们可以把它T(n) = T(n-1) + T(n-1)
写成T(n-1) = T(n-2) + T(n-3) + T(n-4) + ... + T(0)
。因此T(n) = 2 * T(n-1)
归结为O(2^n)
。
上述算法的时间复杂度应该是O(2^n)
。
推荐阅读
- python - 从 Python 2.7 中的众多字典之一中获取价值?
- python - 以 write_only 模式打开现有电子表格
- bash - 调用 SVN 更新的 Cronjob 无法使用凭据
- javascript - 编译数据数组以传递给 Materialise 自动完成
- laravel - laravel 5.7 中用于管理员保护的电子邮件验证
- html - 导航菜单onclick滚动问题?
- vba - 调用从 Delphi ADO 组件调用模块中的 VBA 函数的 MS Access 查询
- laravel - Laravel:在 Model::all() 上将参数设置为模型方法
- python - 在redis中完全删除哈希键的问题
- sql-server - TSQL XML 存在带有命名空间和 IF-ELSE 条件的查询