我需要帮助找到递归算法的复杂性;我知道为了解决这个问题,我必须找到线性递归,然后应用主定理。据我所知,如果只考虑一个参数,就可以很容易地找到递归;
在这种情况下,有两个参数(i,j)。考虑以下调用的函数(A,1,n):
integer stuff(integer [] A, integer i, integer j){
if i ≥ j then return i – j
integer h ← 0
for integer k ← 1 to floor((j – i + 1)/3) do {
在T(n) = T(n-1) +2+ T(n+1)以下是否存在递推关系?
我只是计算中间变量赋值和最后一行,因为所有的if语句都排除了其他语句.这个方法正确吗?
/*
* V is sorted
* V.size() = N
* The function is initially called as searchNumOccurrence(V, k, 0, N-1)
*/
int searchNumOccurrence(vector<int> &V, int k, int start, int end) {
if (start > end) ret
我对递推方程概念很陌生,需要以下算法的帮助
G(n)
Require: A positive integer n.
if n <= 1 then
return n
else
return 5*g(n - 1) - 6* g(n- 2)
end if
我给出了以下关于上述问题的重现公式:
T(n) = n,如果n<=1
T(n) = 5*T(n-1) - 6.T(n-2),若n>1
如果这是正确的,我还必须设置一个重复次数的乘法执行这个算法。请帮帮忙。
我很难为算法建立递归关系。这是我得到的算法:
int result = silly (n);
public static int silly (int n)
{
if (n <= 1)
{
return -100;
}
int sum = 0;
for (int i = 0; i < n; i++)
{
sum += i;
}
return sum + silly (n-2);
}
我知道大小写是T(1) = 1,但不知道T(n)是什么。会不会是
T(n) = n[T(n-2) + 1]
所以,我有一个psuedocode,我必须分析一个类。我试着用θ来计算最好的和最坏的情况。我想出了最好的办法,但最坏的情况我有麻烦了。我认为最坏的情况其实和最好的情况是一样的,但我想自己再想一想,如果最坏的情况实际上是不一样的话,如何恰当地发展它们的重现性,我想得到一些反馈。
代码:
function max-element(A)
if n = 1
return A[1]
val = max-element(A[2...n]
if A[1] > val
return A[1]
else
return val
有fnc的:
bool ISINTREE( int x, BinTree<int> t)
{
bool b = false
if (!t.isEmpty())
{
if (x == t.getRoot())
{ b = true }
else
{
if (ISINTREE(x,t.leftTree()))
{ b = true }
if (ISINTREE(x,t.rightTree()))
{ b = true }
}
}
r
T(n) = { 0 If n = 0
{ T(square root n) + 1 If n > 0
我正试图用替换来解决这个问题。
我猜:O(lg lg n)
通过归纳
T(n) = c lg lg n
T(n) =< c (lg lg square root n) + 1
自square root n = n^1/2 =< c(1/2 lg lg n) + 1以来
我无法继续这个部分来获得lg lg n,我看到了许多使用权力的解决方案。还有别的路吗?
有人能画一棵递归树来帮助我理解吗?
1
||
n^1/2
||
我很难理解如何发展循环关系。我得到的代码是
int result = bizarre(n, n);
public static int bizarre (int first, int second)
{
if (second <= 1)
{
int temp = 0;
for (int i = 0; i < first; i++)
temp += i;
return temp;
}
return bizarre (first, second-1);
}
据我所知,
T(n) = n + 1
T(1)
T(n)=T(n^1/4)+n^1/2+n T(n^1/8)+n^1/4+n^1/2+n。。
T(n^1/2^k)+n^1/k-1+n^1/k-2......+n
I got k= loglog(n) but i am not able to solve the series by putting this k value into above series.
我现在正在学习关于重复关系的知识。我可以解决它们并计算出它们的界限,但我不确定的是如何为一个特定的算法求出一个递归关系。下面是我书中的一个例子:
// Sort array A[] between indices p and r inclusive.
SampleSort (A, p, r) {
// Base Case: use HeapSort
//
if (r - p < 12) {
HeapSort(A, p, r) ;
}
// Break the array into 1st quarter, 2nd
考虑元素唯一性问题,其中给出了一个范围,i,i+ 1,。。。,j,数组的索引,A,我们想确定这个范围的元素,Ai,Ai+1,。。。,Aj,都是唯一的,也就是说,在这组数组条目中没有重复元素。考虑下面的递归算法(ineffi)。
public static boolean isUnique(int[] A, int start, int end) {
if (start >= end) return true; // the range is too small for repeats
// check recursively if first part of array A
今年10月,我开始攻读生物信息学硕士学位,因为一位前生物学家很难从一段代码中找到一个递归方程。如果有人能向我解释这件事,我将非常感激。
如何从这段代码中找到递归方程?
procedure DC(n)
if n<1 then return
for i <- 1 to 8 do DC(n/2)
for i <- 1 to n³ do dummy <- 0
我猜T(n) =c+ 8T(n/2),因为第一个if条件需要常数时间c,第一个for循环是递归情况,从1到8执行,因此8*T(n/2),但我不知道如何将最后一行代码添加到我的方程中。
关于使用递归关系分析时间复杂性,我有两个问题。
问题1.如何在使用回忆录时形成算法的递归关系?这可能吗?
例如,考虑计算Fibonacci序列的第n个项。算法如下:
fib(n)
if n < 2
return n
else
return fib(n-1)+fib(n-2)
这段代码的递归关系是:
T(n) = T(n-1) + T(n-2) + c,时间复杂度约为2^n。
这一守则的回忆录版本如下:
MemFib(n)
if n < 2
return n
else
if F[n] is
我可以计算一阶线性递推方程的矩阵表示。并利用快速矩阵指数进行高阶计算。我是从本教程学到的。
但是,在计算二阶线性递推方程的矩阵表示时,我遇到了一些问题。例如-
S(n) = a * (S(n - 1))^2 + b * S(n - 1) + c
where S(0) = d
你能帮我找出上述方程的矩阵表示或给我一些见解吗?提前谢谢。
根据运算次数,找出重复关系!
a = N;
var = 0;
while (a > 1)
{
var = var + a;
num = 2 * var;
a = a / 2;
}
我认为将形成的重复关系是:(不计算赋值操作)
T(n)= (from a=1 to N)Σ(3)
我说的对吗??
现在利用这个递推关系,如何找出它的复杂性。