计算理论 复杂度预备知识

符号

$f(n)=o(g(n))$ ：$\exists c$ ，当 $n$ 足够大时， $f(n)<cg(n)$ ；∑n→∞f(n)g(n)=0\\sum\\limits_{n\\to\\infty} \\frac{f(n)}{g(n)}=0n→∞∑​g(n)f(n)​=0 ；
$f(n)=O(g(n))$ ：$\exists c$ ，当 $n$ 足够大时， $f(n)\le cg(n)$ ；
$f(n)=\theta (g(n))$ ：∃c1,c2\\exists c_{1}, c_{2}∃c1​,c2​ ，当 $n$ 足够大时， c1g(n)<f(n)<c2g(n)c_{1}g(n)\\lt f(n) \\lt c_{2}g(n)c1​g(n)<f(n)<c2​g(n) ；
$f(n)=\omega (g(n))$ ：$\exists c$ ，当 $n$ 足够大时， $f(n)>cg(n)$ ；
$f(n)=\Omega (g(n))$ ：$\exists c$ ，当 $n$ 足够大时， $f(n)\ge cg(n)$ ；

递归表达式求解通项公式

① T(n)=4T(n2)+nT(n)=4T\\left( \\frac{n}{2} \\right)+nT(n)=4T(2n​)+n ：就直接展开，找到规律
T(n)=4T(n2)+n=4(4(T(n22)+n2)+n=4T(n22)+2n+n=4kT(n2k)+n(20+21+⋯+2k−1)\\begin{array}{l} \\quad T(n) \\\\ =4T(\\frac{n}{2})+n \\\\ =4(4(T(\\frac{n}{2^{2}})+\\frac{n}{2})+n \\\\ =4T(\\frac{n}{2^{2}})+2n+n \\\\ =4^{k}T(\\frac{n}{2^{k}})+n(2^0+2^1+\\dots+2^{k-1}) \\end{array} T(n)=4T(2n​)+n=4(4(T(22n​)+2n​)+n=4T(22n​)+2n+n=4kT(2kn​)+n(20+21+⋯+2k−1)​
假设 $n$ 是 2 的幂，则最后 $k$ 应该等于 log⁡2(n)\\log_{2}(n)log2​(n) ，故：
T(n)=T(1)n2+n∑i=1log⁡2(n)2i−1=T(1)n2+n(n−1)=O(n2)T(n)=T(1)n^{2}+n\\sum\\limits_{i=1}^{\\log_{2}(n)}2^{i-1}=T(1)n^{2}+n(n-1)=O(n^{2}) T(n)=T(1)n2+ni=1∑log2​(n)​2i−1=T(1)n2+n(n−1)=O(n2)
② T(n)=2T(n2)+n=nT(1)+nlog⁡2(n)=O(nlog⁡n)T(n)=2T(\\frac{n}{2})+n=nT(1)+n\\log_{2}(n)=O(n\\log{n})T(n)=2T(2n​)+n=nT(1)+nlog2​(n)=O(nlogn)
③ T(n)=4T(n2)+n2=n2T(1)+n2log⁡2n=O(n2log⁡n)T(n)=4T(\\frac{n}{2})+n^{2}=n^{2}T(1)+n^{2}\\log_{2}{n}=O(n^{2}\\log{n})T(n)=4T(2n​)+n2=n2T(1)+n2log2​n=O(n2logn)
④ T(n)=2T(n2)+n2=nT(1)+2n2=O(n2)T(n)=2T(\\frac{n}{2})+n^2=nT(1)+2n^{2}=O(n^{2})T(n)=2T(2n​)+n2=nT(1)+2n2=O(n2)
⑤ T(n)=4T(n2)+n2log⁡nT(n)=4T(\\frac{n}{2})+\\frac{n^{2}}{\\log{n}}T(n)=4T(2n​)+lognn2​
T(n)=4T(n2)+n2log⁡n=n2T(1)+n2log⁡n+n2log⁡n−1+⋯+n2log⁡1=θ(n2log⁡log⁡n)\\begin{array}{l} \\quad T(n) \\\\ =4T(\\frac{n}{2})+\\frac{n^{2}}{\\log{n}} \\\\ =n^{2}T(1)+\\frac{n^{2}}{\\log{n}}+\\frac{n^{2}}{\\log{n-1}}+\\dots+\\frac{n^{2}}{\\log{1}} \\\\ =\\theta(n^{2}\\log{\\log{n}}) \\end{array} T(n)=4T(2n​)+lognn2​=n2T(1)+lognn2​+logn−1n2​+⋯+log1n2​=θ(n2loglogn)​
因为这个级数可以看成积分：
1x+1x−1+1x−2+⋯=∫1xdx=ln⁡x\\frac{1}{x}+\\frac{1}{x-1}+\\frac{1}{x-2}+\\dots=\\int_{1}^x \\, dx=\\ln{x} x1​+x−11​+x−21​+⋯=∫1x​dx=lnx

主方法

Th：设 $a\ge 1$ ，$b\ge 1$ ，$f(n)$ 为一定义在非负整数上的函数，T(n)=aT(nb)+f(n)T(n)=aT(\\frac{n}{b})+f(n)T(n)=aT(bn​)+f(n) （当 nb\\frac{n}{b}bn​ 不为整数时代表 ⌈nb⌉\\lceil \\frac{n}{b} \\rceil⌈bn​⌉ 或 ⌊nb⌋\\lfloor \\frac{n}{b} \\rfloor⌊bn​⌋ ），则：

1. 若 $\exists \epsilon >0$ ，使得 f(n)=O(nlog⁡ba−ε)f(n)=O(n^{\\log_{b}{a}-\\varepsilon})f(n)=O(nlogb​a−ε) ，则 T(n)=Θ(nlog⁡ba)T(n)=\\Theta(n^{\\log_{b}{a}})T(n)=Θ(nlogb​a)
2. 若 $\exists k\ge 0$ ，使得 f(n)=Θ(nlog⁡balgkn)f(n)=\\Theta(n^{\\log_{b}{a}\\,lg^k{n}})f(n)=Θ(nlogb​algkn) ，则 T(n)=Θ(nlog⁡balgk+1n)T(n)=\\Theta(n^{\\log_{b}{a}}\\,lg^{k+1}{n})T(n)=Θ(nlogb​algk+1n)
3. 若 $\exists \epsilon >0$ ，使得 f(n)=Ω(nlog⁡ba+ε)f(n)=\\Omega(n^{\\log_{b}{a}+\\varepsilon})f(n)=Ω(nlogb​a+ε) ，且存在 $0<c<1$ 以及正整数 N0N_{0}N0​ ，使得当 n>N0n>N_{0}n>N0​ 时，有 af(nb)≤cf(n)af(\\frac{n}{b})\\leq cf(n)af(bn​)≤cf(n) ，则 $T(n)=\Theta (f(n))$
   证明：首先展开，得到：

T(n)=aT(nb)+f(n)=a(aT(nb2)+f(nb))+f(n)a2T(nb2)+af(nb)+f(n)=…=alog⁡bnT(1)+∑i=0log⁡bn−1aif(nbi)\\begin{array}{l} \\quad T(n) \\\\ =aT(\\frac{n}{b})+f(n) \\\\ =a(aT(\\frac{n}{b^2})+f(\\frac{n}{b}))+f(n) \\\\ a^2T(\\frac{n}{b^{2}})+af(\\frac{n}{b})+f(n) \\\\ =\\dots \\\\ =a^{\\log_{b}{n}}T(1)+\\sum\\limits_{i=0}^{\\log_{b}{n}-1}a^if(\\frac{n}{b^i}) \\end{array} T(n)=aT(bn​)+f(n)=a(aT(b2n​)+f(bn​))+f(n)a2T(b2n​)+af(bn​)+f(n)=…=alogb​nT(1)+i=0∑logb​n−1​aif(bin​)​

其中 alog⁡bn=blog⁡balog⁡bn=nlog⁡baa^{\\log_{b}{n}}=b^{\\log_{b}a\\log_{b}n}=n^{\\log_{b}a}alogb​n=blogb​alogb​n=nlogb​a ；如果把 $f(n)$ 看成多项式的话，只需要比较 $f(n)$ 的次数与 log⁡ba\\log_{b}alogb​a 的相对大小；
① 若 $\exists \epsilon >0$ ，使得 f(n)=O(nlog⁡ba−ε)f(n)=O(n^{\\log_{b}{a}-\\varepsilon})f(n)=O(nlogb​a−ε) ，则 T(n)=Θ(nlog⁡ba)T(n)=\\Theta(n^{\\log_{b}{a}})T(n)=Θ(nlogb​a)
∑i=0log⁡bn−1aif(nbi)=∑ai(nb)log⁡ba−ε=∑nlog⁡ba−ε−biεai=nlog⁡ba−ε∑biε=nlog⁡ba−ε1−nε1−bε=O(nlog⁡ba)\\begin{array}{l} \\quad\\sum\\limits_{i=0}^{\\log_{b}{n}-1}a^if\\left( \\frac{n}{b^i} \\right) \\\\ =\\sum\\limits a^i\\left( \\frac{n}{b} \\right)^{\\log_{b}a-\\varepsilon} \\\\ =\\sum\\limits \\frac{n^{\\log_{b}a-\\varepsilon}-b^{i\\varepsilon}}{a^i} \\\\ =n^{\\log_{b}a-\\varepsilon}\\sum\\limits b^{i\\varepsilon} \\\\ =n^{\\log_{b}a-\\varepsilon} \\frac{1-n^{\\varepsilon}}{1-b^{\\varepsilon}} \\\\ =O(n^{\\log_{b}a}) \\end{array} i=0∑logb​n−1​aif(bin​)=∑ai(bn​)logb​a−ε=∑ainlogb​a−ε−biε​=nlogb​a−ε∑biε=nlogb​a−ε1−bε1−nε​=O(nlogb​a)​
② 若 $\exists k\ge 0$ ，使得 f(n)=Θ(nlog⁡balgkn)f(n)=\\Theta(n^{\\log_{b}{a}\\,lg^k{n}})f(n)=Θ(nlogb​algkn) ，则 T(n)=Θ(nlog⁡balgk+1n)T(n)=\\Theta(n^{\\log_{b}{a}}\\,lg^{k+1}{n})T(n)=Θ(nlogb​algk+1n)
我们就假设 f(n)=nlog⁡balg⁡knf(n)=n^{\\log_{b}a}\\lg^k{n}f(n)=nlogb​algkn ，则：
∑i=0log⁡bn−1aif(nbi)=∑ai(nbi)log⁡balg⁡k(nbi)=∑ainlog⁡baai(lg⁡n−ilg⁡b)k\\begin{array}{l} \\quad\\sum\\limits_{i=0}^{\\log_{b}{n}-1}a^if\\left( \\frac{n}{b^i} \\right) \\\\ =\\sum\\limits a^{i}(\\frac{n}{b^{i}})^{\\log_{b}{a}}\\lg^k{(\\frac{n}{b^i})} \\\\ =\\sum\\limits a^{i}\\frac{n^{\\log_{b}a}}{a^{i}}(\\lg{n}-i\\lg{b})^k \\end{array} i=0∑logb​n−1​aif(bin​)=∑ai(bin​)logb​algk(bin​)=∑aiainlogb​a​(lgn−ilgb)k​
这个 (lg⁡n−ilg⁡b)k(\\lg{n}-i\\lg{b})^k(lgn−ilgb)k 二项展开的话会发现，次数肯定是 lg⁡kn\\lg^k{n}lgkn 决定的，则：
≈∑nlogbalg⁡kn=log⁡bn⋅nlogbalg⁡kn=nlog⁡balgk+1n\\begin{array}{l} \\approx \\sum\\limits n^{\\\\log_{b}a}\\lg^k{n} \\\\ =\\log_{b}{n} \\cdot n^{\\\\log_{b}a}\\lg^k{n} \\\\ =n^{\\log_{b}{a}}\\,lg^{k+1}{n} \\end{array} ≈∑nlogb​algkn=logb​n⋅nlogb​algkn=nlogb​algk+1n​
③ 若 $\exists \epsilon >0$ ，使得 f(n)=Ω(nlog⁡ba+ε)f(n)=\\Omega(n^{\\log_{b}{a}+\\varepsilon})f(n)=Ω(nlogb​a+ε) ，且存在 $0<c<1$ 以及正整数 N0N_{0}N0​ ，使得当 n>N0n>N_{0}n>N0​ 时，有 af(nb≤cf(n))af(\\frac{n}{b}\\leq cf(n))af(bn​≤cf(n)) ，则 $T(n)=\Theta (f(n))$
当满足条件时，有 cf(n)≥af(nb)cf(n)\\geq af(\\frac{n}{b})cf(n)≥af(bn​) ，得到：
f(n)≥acf(nb)≥a2c2f(nb2)≥⋯≥aicif(nbi)f(n)\\geq \\frac{a}{c}f(\\frac{n}{b}) \\geq \\frac{a^{2}}{c^{2}}f(\\frac{n}{b^{2}})\\geq\\dots\\geq\\frac{a^{i}}{c^{i}}f(\\frac{n}{b^{i}}) f(n)≥ca​f(bn​)≥c2a2​f(b2n​)≥⋯≥ciai​f(bin​)
故 f(n)≥aicif(nbi)f(n)\\geq\\frac{a^{i}}{c^{i}}f(\\frac{n}{b^{i}})f(n)≥ciai​f(bin​) ；需要满足所有大于等于的条件，发现只需要最后一个大于等于满足即可，即 nbi>N0⟹i<log⁡bn−log⁡bN0+1\\frac{n}{b^{i}}\\gt N_{0}\\implies i< \\log_{b}n-\\log_{b}{N_{0}}+1bin​>N0​⟹i<logb​n−logb​N0​+1
∑i=0log⁡bn−1aif(nbi)=∑i=0log⁡bn−log⁡bN0aif(nbi)+∑i=log⁡bn−log⁡bN0+1log⁡bn−1aif(nbi)\\begin{array}{l} \\quad\\sum\\limits_{i=0}^{\\log_{b}{n}-1}a^if\\left( \\frac{n}{b^i} \\right) \\\\ =\\sum\\limits_{i=0}^{\\log_{b}^n-\\log_{b}^{N_{0}}} a^if\\left( \\frac{n}{b^i} \\right)+\\sum\\limits_{i=\\log_{b}^n-\\log_{b}^{N_{0}}+1}^{\\log_{b}n-1}a^if\\left( \\frac{n}{b^i} \\right) \\end{array} i=0∑logb​n−1​aif(bin​)=i=0∑logbn​−logbN0​​​aif(bin​)+i=logbn​−logbN0​​+1∑logb​n−1​aif(bin​)​
左项是满足 i<log⁡bn−log⁡bN0+1i< \\log_{b}n-\\log_{b}{N_{0}}+1i<logb​n−logb​N0​+1 的条件，有：
≤∑i=0log⁡bn−log⁡bN0cif(n)=O(f(n))\\leq \\sum\\limits_{i=0}^{\\log_{b}^n-\\log_{b}^{N_{0}}}c^if(n)=O(f(n)) ≤i=0∑logbn​−logbN0​​​cif(n)=O(f(n))
右项是 $O(1)$ ，展开也看不出来（直接把 $f(n)$ 看作 O(nlog⁡ba+ε)O(n^{\\log_{b}a+{\\varepsilon}})O(nlogb​a+ε)）：
=∑ai(nbi)log⁡ba+ε=∑ainlog⁡ba+εai⋅biε=nlog⁡ba+ε∑1biε=1−(1bε)log⁡bN0−11−1bε⋅1bε(log⁡bn−log⁡bN0+1)⋅nlog⁡ba+ε\\begin{array}{l} =\\sum\\limits a^i\\left( \\frac{n}{b^i} \\right)^{\\log_{b}a+\\varepsilon} \\\\ =\\sum\\limits a^i\\frac{n^{\\log_{b}a+\\varepsilon}}{a^i\\cdot b^{i\\varepsilon}} \\\\ =n^{\\log_{b}a+\\varepsilon}\\sum\\limits\\frac{1}{b^{i\\varepsilon}} \\\\ =\\frac{1-(\\frac{1}b^{\\varepsilon})^{\\log_{b}N_{0}-1}}{1-\\frac{1}{b^{\\varepsilon}}}\\cdot \\frac{1}{b^{\\varepsilon(\\log_{b}n-\\log_{b}N_{0}+1)}} \\cdot n^{\\log_{b}a+\\varepsilon} \\end{array} =∑ai(bin​)logb​a+ε=∑aiai⋅biεnlogb​a+ε​=nlogb​a+ε∑biε1​=1−bε1​1−(b1​ε)logb​N0​−1​⋅bε(logb​n−logb​N0​+1)1​⋅nlogb​a+ε​
第一项是常数，后边两项乘起来看着像个常数

Akra-Bazzi 定理

Th：设 $g(x)$ 为一非负函数，T(x)={Θ(1),1≤x≤X0∑i=1kaiT(xbi)+g(x),n>X0T(x)=\\left\\{\\begin{array}{ll}\\Theta(1) & ,1\\leq x \\leq X_{0} \\\\ \\sum\\limits_{i=1}^k a_{i}T(\\frac{x}{b_{i}})+g(x)& ,n>X_{0} \\end{array}\\right.T(x)=⎩⎨⎧​Θ(1)i=1∑k​ai​T(bi​x​)+g(x)​,1≤x≤X0​,n>X0​​ （其中 $k\ge 1$ ，ai>0a_{i}>0ai​>0 ，bi>1b_{i}>1bi​>1，X0X_{0}X0​ 满足对任意 $1\le i\le k$ 有 X0>biX_{0}>b_{i}X0​>bi​ 且 X0>bibi−1X_{0}>\\frac{b_{i}}{b_{i}-1}X0​>bi​−1bi​​ ），若 $g(x)$ 满足多项式增长条件，$p$ 为方程 ∑i=1kaibip=1\\sum\\limits_{i=1}^k\\frac{a_{i}}{b_{i}^p}=1i=1∑k​bip​ai​​=1 的实数解，则：
T(x)=Θ(xp(1+∫1xg(x)xp+1dx))T(x)=\\Theta\\left( x^p\\left( 1+\\int_{1}^x \\frac{g(x)}{x^{p+1}}dx \\right) \\right) T(x)=Θ(xp(1+∫1x​xp+1g(x)​dx))
例：T(n)=2T(n4+3T(n6)+nlg⁡n)T(n)=2T(\\frac{n}{4}+3T(\\frac{n}{6})+n\\lg{n})T(n)=2T(4n​+3T(6n​)+nlgn)
解 24p+36p=1\\frac{2}{4^p}+\\frac{3}{6^p}=14p2​+6p3​=1 得 $p=1$
T(n)=Θ(n(1+∫1nxlg⁡xx2dx))=Θ(n(1+12lg⁡2n))=Θ(nlg⁡2n)\\begin{array}{l} \\quad T(n) \\\\ =\\Theta(n(1+\\int_{1}^n \\frac{x\\lg{x}}{x^{2}} dx)) \\\\ =\\Theta(n(1+\\frac{1}{2}\\lg^2{n})) \\\\ =\\Theta(n\\lg^2{n}) \\end{array} T(n)=Θ(n(1+∫1n​x2xlgx​dx))=Θ(n(1+21​lg2n))=Θ(nlg2n)​