複雜度分析：積性函數的狄利克雷卷積

07-15

複雜度分析：積性函數的狄利克雷卷積

7 人贊了文章

根據狄利克雷卷積的基本概念，我們可以知道，對於兩個積性函數 $f(n)$ 與 $g(n)$ 和他們的卷積 $h=f*g$ ，當 $gcd(a,b)=1$ 時，

$egin{eqnarray} h(ab) & = & sum_{cd|ab} f(cd)g(frac{ab}{cd}) \ & = & sum_{c|a}f(c)g(frac a c) sum_{d|b}f(d)g(frac b d) \ & = & h(a)h(b) end{eqnarray}$

所以我們可以通過積性函數的方法計算在1~n內的函數值，程序化一點就有

$h(n) = left{ egin{array}{clclc} 1 & ext{if} & n = 1 \ sum_{d=0}^{k} f(p^d) g(p^{k-d}) & ext{if} & n = p^k \ h(p^k)h(m) & ext{else let} & n = p^k m & ext{where} & gcd(p^k, m) = 1 end{array} ight.$

第1部分是平凡的，第3部分可以在Euler篩法的時候處理且總代價是 $Theta(n)$ 的，重點是第2部分的花銷。

按照這個計算方法，對於 $p^k$ 的函數值會額外造成 $Theta(k)$ 次計算。我們可以依次列出總時間複雜度的式子：

$egin{eqnarray} T(n) & = & sum_{x=1}^{log_2 n} xpi left( leftlfloor sqrt[x]n ight floor ight) \ & approx & sum_{x=1}^{log_2 n} frac {xsqrt[x]n} {ln {sqrt[x]n}} \ & = & frac 1{ln n}sum_{x=1}^{log_2 n} x^2 sqrt[x]n end{eqnarray}$

這裡用到了 $lim_{n ightarrow +infty} frac{pi(n)}{n/ln n} = 1$ 的素數分布函數的極限。

這個式子怎麼判斷它的界呢？我們嘗試找一下 $x^2 sqrt[x]n$ 的極值。

$ewcommand{diff}{mathrm{d}} egin{eqnarray} frac{diff}{diff x} , x^2 sqrt[x]n & = & 2xsqrt[x]n -x^2 sqrt[x]n frac 1 {x^2} ln n \ & = & sqrt[x]n (2x - ln n) end{eqnarray}$

可以看到原函數是單峰且凹的函數，極值在兩邊取得，是 $x=1$ 時得 $n$ 。

用最大值的界可得：

$egin{eqnarray*} T(n) & leq & frac{log_2 n}{ln n} n \ T(n) & = & mathcal O(n) end{eqnarray*}$

因此，計算兩個積性函數的狄利克雷卷積的複雜度是 $Theta(n)$ 的。