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算法的複雜性

回答

相關問題