fooアルゴリズムの複雑さ

Question

私はこの問題を解決できません。この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）*私はそれがログ（だかはわからないループの内部のための何か..だと思いますn）または何..

それはlog^2（n）のシータですか？

Answer 1

これはマスター定理の大きなアプリケーションである：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）

Answer 2

「すばやく汚れた」方法があるかどうかはわかりませんが、古き良き数学を使うことができます。ファンシー定理はなく、単純な方程式です。

第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)となります。