foo算法的复杂性

我有这个问题，我无法解决..什么是这个foo算法的复杂性？foo算法的复杂性

int foo(char A[], int n, int m){ 
    int i, a=0; 
    if (n>=m) 
    return 0; 
    for(i=n;i<m;i++) 
    a+=A[i] 
    return a + foo(A, n*2, m/2); 
}

foo的函数的调用方式：

foo(A,1,strlen(A));

所以...我想这是日志（N）*的东西内部for循环..这我不知道这是否是日志（ n）还是什么..

它可能是log^2（n）的θ？

来源

2011-02-04 luca

是这个家庭作业？ – Mike 2011-02-04 20:49:02

不，这是我今天完成的考试，我试图说服我是否做得对（我怀疑它..）请问，也许这不是很适合问这里，但我问过cstheory.stackexchange，他们说我应该问这里。 – luca 2011-02-04 20:53:20

这是主定理的一个很大的应用：在n个方面

重写和X = MN：

int foo(char A[], int n, int X){ 
    int i, a=0; 
    if (X < 0) return 0; 
    for(i=0;i<X;i++) 
    a+=A[i+n] 
    return a + foo(A, n*2, (X-3n)/2); 
}

所以复杂度

T(X, n) = X + T((X - 3n)/2, n*2)

注意到点球随X增加并随n减小，

T(X, n) < X + T(X/2, n)

因此，我们可以考虑复杂

U(X) = X + U(X/2)

，并插入到主定理这一发现U（X）= O（X） - >复杂度为O（M-N）

来源

2011-02-04 21:22:37

我不确定是否有'快捷和肮脏'的方式，但你可以使用旧的好数学。没有花哨的定理，只是简单的方程。

在第k级递归（k从零开始），循环将有~ n/(2^k) - 2^k迭代。因此，对于0 <= i <= l，循环迭代的总数将为S = sum(n/2^i) - sum(2^i)，其中l是递归的深度。

l将近似log(2, n)/2（证明它）。

分别将公式中的每个部分转换为S，我们得到。

S = (1 + 2 + .. + 2^l)*n/2^l - (2^(l + 1) - 1) ~= 2*n - 2^(l + 1) ~= 2*n - sqrt(n)

由于除循环相互语句将仅重复l次，我们知道l ~= log(2, n)，也不会影响的复杂性。

所以，最后我们得到O(n)。

来源

2011-02-04 21:08:57

foo算法的复杂性

回答

相关问题