新闻详情

之前我们讲了主定理，用来解决： <span class="katex"><span class="katex-mathml">�(�)=��(�/�)+�(�)<span class="katex-html"><span class="base"><span class="strut"><span class="mord mathnormal">T<span class="mopen">(<span class="mord mathnormal">n<span class="mclose">)<span class="mspace"><span class="mrel">=<span class="mspace"><span class="base"><span class="strut"><span class="mord mathnormal">a<span class="mord mathnormal">T<span class="mopen">(<span class="mord mathnormal">n<span class="mord">/<span class="mord mathnormal">b<span class="mclose">)<span class="mspace"><span class="mbin">+<span class="mspace"><span class="base"><span class="strut"><span class="mord mathnormal">f<span class="mopen">(<span class="mord mathnormal">n<span class="mclose">)&nbsp;的复杂度

但现实里的递归，往往没有这么整齐。比如每个子问题的规模不同：

 

�(�)=�(�/2)+�(�/3)+�T(n)=T(n/2)+T(n/3)+n

 

这时候，主定理就不能直接用了。这篇我们讲一个更强的工具：Akra–Bazzi 定理。

主定理的扩展

很多算法的递归是这样的：

 

�(�)=�(�/3)+�(2�/3)+�(�)T(n)=T(n/3)+T(2n/3)+O(n)

 

或者：

 

�(�)=�(�/5)+�(7�/10)+�(�)T(n)=T(n/5)+T(7n/10)+O(n)

 

这些递归的特点是：子问题规模不同、递归分支不均匀。主定理无法直接套。这时候就需要 Akra–Bazzi 定理。

Akra–Bazzi 定理处理什么

Akra–Bazzi 定理处理的是：

 

�(�)=�(�)+∑�=1����(�/��)T(n)=f(n)+i=1∑k​ai​T(n/bi​)

 

其中：

• <span class="katex"><span class="katex-mathml">��<span class="katex-html"><span class="base"><span class="strut"><span class="mord"><span class="mord mathnormal">a<span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist"><span><span class="pstrut"><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight">i<span class="vlist-s">​<span class="vlist-r"><span class="vlist"><span>&nbsp;表示第&nbsp;<span class="math inline"><span class="katex"><span class="katex-mathml">�<span class="katex-html"><span class="base"><span class="strut"><span class="mord mathnormal">i&nbsp;类子问题有多少个
• <span class="katex"><span class="katex-mathml">�/��<span class="katex-html"><span class="base"><span class="strut"><span class="mord mathnormal">n<span class="mord">/<span class="mord"><span class="mord mathnormal">b<span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist"><span><span class="pstrut"><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight">i<span class="vlist-s">​<span class="vlist-r"><span class="vlist"><span>&nbsp;表示第&nbsp;<span class="math inline"><span class="katex"><span class="katex-mathml">�<span class="katex-html"><span class="base"><span class="strut"><span class="mord mathnormal">i&nbsp;类子问题的规模
• <span class="katex"><span class="katex-mathml">�(�)<span class="katex-html"><span class="base"><span class="strut"><span class="mord mathnormal">f<span class="mopen">(<span class="mord mathnormal">n<span class="mclose">)&nbsp;表示递归之外的额外工作

它是主定理的扩展。主定理是它的特殊情况。

计算核心：先求一个 <span class="katex"><span class="katex-mathml">�<span class="katex-html"><span class="base"><span class="strut"><span class="mord mathnormal">p

Akra–Bazzi 的第一步，是找到 <span class="katex"><span class="katex-mathml">�<span class="katex-html"><span class="base"><span class="strut"><span class="mord mathnormal">p，使得：

 

∑�=1�����−�=1i=1∑k​ai​bi−p​=1

 

这个 <span class="katex"><span class="katex-mathml">�<span class="katex-html"><span class="base"><span class="strut"><span class="mord mathnormal">p&nbsp;可以理解为递归结构本身的增长指数。为什么？假设&nbsp;<span class="math inline"><span class="katex"><span class="katex-mathml">�(�)<span class="katex-html"><span class="base"><span class="strut"><span class="mord mathnormal">T<span class="mopen">(<span class="mord mathnormal">n<span class="mclose">)&nbsp;大概像&nbsp;<span class="math inline"><span class="katex"><span class="katex-mathml">��<span class="katex-html"><span class="base"><span class="strut"><span class="mord"><span class="mord mathnormal">n<span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist"><span><span class="pstrut"><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight">p，代入递归：

 

��≈∑�=1���(�/��)�np≈i=1∑k​ai​(n/bi​)p

 

整理得：

 

��≈��∑�=1�����−�np≈npi=1∑k​ai​bi−p​

 

所以必须有：

 

∑�=1�����−�=1i=1∑k​ai​bi−p​=1

 

这就是 Akra–Bazzi 定理的灵魂。

结论

求出 <span class="katex"><span class="katex-mathml">�<span class="katex-html"><span class="base"><span class="strut"><span class="mord mathnormal">p&nbsp;之后，有：

 

�(�)=Θ(��(1+∫1��(�)��+1��))T(n)=Θ(np(1+∫1n​up+1f(u)​du))

 

这个公式可以拆成两部分看：

• <span class="katex"><span class="katex-mathml">��<span class="katex-html"><span class="base"><span class="strut"><span class="mord"><span class="mord mathnormal">n<span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist"><span><span class="pstrut"><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight">p：递归结构本身的复杂度
• 积分：每一层额外工作 <span class="katex"><span class="katex-mathml">�(�)<span class="katex-html"><span class="base"><span class="strut"><span class="mord mathnormal">f<span class="mopen">(<span class="mord mathnormal">n<span class="mclose">)&nbsp;的累计影响

因此，使用 Akra–Bazzi 定理计算复杂度分为三步：

第一步，解方程求出 p：

 

∑�=1�����−�=1i=1∑k​ai​bi−p​=1

 

第二步，计算积分：

 

∫1��(�)��+1��∫1n​up+1f(u)​du

 

第三步，乘回 <span class="katex"><span class="katex-mathml">��<span class="katex-html"><span class="base"><span class="strut"><span class="mord"><span class="mord mathnormal">n<span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist"><span><span class="pstrut"><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight">p：

 

�(�)=Θ(��(1+∫1��(�)��+1��))T(n)=Θ(np(1+∫1n​up+1f(u)​du))

 

例子

主定理无法处理的递归

考虑：

 

�(�)=�(�/2)+�(�/3)+�T(n)=T(n/2)+T(n/3)+n

 

这里有两个子问题，规模分别是 <span class="katex"><span class="katex-mathml">�/2<span class="katex-html"><span class="base"><span class="strut"><span class="mord mathnormal">n<span class="mord">/2&nbsp;和&nbsp;<span class="math inline"><span class="katex"><span class="katex-mathml">�/3<span class="katex-html"><span class="base"><span class="strut"><span class="mord mathnormal">n<span class="mord">/3。

所以：<span class="katex"><span class="katex-mathml">(1/2)�+(1/3)�=1<span class="katex-html"><span class="base"><span class="strut"><span class="mopen">(<span class="mord">1/2<span class="mclose"><span class="mclose">)<span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist"><span><span class="pstrut"><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight">p<span class="mspace"><span class="mbin">+<span class="mspace"><span class="base"><span class="strut"><span class="mopen">(<span class="mord">1/3<span class="mclose"><span class="mclose">)<span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist"><span><span class="pstrut"><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight">p<span class="mspace"><span class="mrel">=<span class="mspace"><span class="base"><span class="strut"><span class="mord">1，这个方程的解大约是：<span class="math inline"><span class="katex"><span class="katex-mathml">�&asymp;0.79<span class="katex-html"><span class="base"><span class="strut"><span class="mord mathnormal">p<span class="mspace"><span class="mrel">&asymp;<span class="mspace"><span class="base"><span class="strut"><span class="mord">0.79

又因为 <span class="katex"><span class="katex-mathml">�(�)=�<span class="katex-html"><span class="base"><span class="strut"><span class="mord mathnormal">f<span class="mopen">(<span class="mord mathnormal">n<span class="mclose">)<span class="mspace"><span class="mrel">=<span class="mspace"><span class="base"><span class="strut"><span class="mord mathnormal">n，所以：<span class="math inline"><span class="katex"><span class="katex-mathml">�(�)=&Theta;(��(1+&int;1����+1��))<span class="katex-html"><span class="base"><span class="strut"><span class="mord mathnormal">T<span class="mopen">(<span class="mord mathnormal">n<span class="mclose">)<span class="mspace"><span class="mrel">=<span class="mspace"><span class="base"><span class="strut"><span class="mord">&Theta;<span class="mspace"><span class="minner"><span class="mopen delimcenter"><span class="delimsizing size1">(<span class="mord"><span class="mord mathnormal">n<span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist"><span><span class="pstrut"><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight">p<span class="mspace"><span class="minner"><span class="mopen delimcenter"><span class="delimsizing size1">(<span class="mord">1<span class="mspace"><span class="mbin">+<span class="mspace"><span class="mop"><span class="mop op-symbol small-op">&int;<span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist"><span><span class="pstrut"><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">1<span><span class="pstrut"><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight">n<span class="vlist-s">​<span class="vlist-r"><span class="vlist"><span><span class="mspace"><span class="mord"><span class="mopen nulldelimiter"><span class="mfrac"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist"><span><span class="pstrut"><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight"><span class="mord mathnormal mtight">u<span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist"><span><span class="pstrut"><span class="sizing reset-size3 size1 mtight"><span class="mord mtight"><span class="mord mathnormal mtight">p<span class="mbin mtight">+<span class="mord mtight">1<span><span class="pstrut"><span class="frac-line"><span><span class="pstrut"><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathnormal mtight">u<span class="vlist-s">​<span class="vlist-r"><span class="vlist"><span><span class="mclose nulldelimiter"><span class="mord mathnormal">d<span class="mord mathnormal">u<span class="mclose delimcenter"><span class="delimsizing size1">)<span class="mclose delimcenter"><span class="delimsizing size1">)

积分部分为：<span class="katex"><span class="katex-mathml">&int;1��&minus;���=&Theta;(�1&minus;�)<span class="katex-html"><span class="base"><span class="strut"><span class="mop"><span class="mop op-symbol small-op">&int;<span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist"><span><span class="pstrut"><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">1<span><span class="pstrut"><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight">n<span class="vlist-s">​<span class="vlist-r"><span class="vlist"><span><span class="mspace"><span class="mord"><span class="mord mathnormal">u<span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist"><span><span class="pstrut"><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">&minus;<span class="mord mathnormal mtight">p<span class="mord mathnormal">d<span class="mord mathnormal">u<span class="mspace"><span class="mrel">=<span class="mspace"><span class="base"><span class="strut"><span class="mord">&Theta;<span class="mopen">(<span class="mord"><span class="mord mathnormal">n<span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist"><span><span class="pstrut"><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">1<span class="mbin mtight">&minus;<span class="mord mathnormal mtight">p<span class="mclose">)

因此：<span class="katex"><span class="katex-mathml">�(�)=&Theta;(��&sdot;�1&minus;�)=&Theta;(�)<span class="katex-html"><span class="base"><span class="strut"><span class="mord mathnormal">T<span class="mopen">(<span class="mord mathnormal">n<span class="mclose">)<span class="mspace"><span class="mrel">=<span class="mspace"><span class="base"><span class="strut"><span class="mord">&Theta;<span class="mopen">(<span class="mord"><span class="mord mathnormal">n<span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist"><span><span class="pstrut"><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight">p<span class="mspace"><span class="mbin">&sdot;<span class="mspace"><span class="base"><span class="strut"><span class="mord"><span class="mord mathnormal">n<span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist"><span><span class="pstrut"><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">1<span class="mbin mtight">&minus;<span class="mord mathnormal mtight">p<span class="mclose">)<span class="mspace"><span class="mrel">=<span class="mspace"><span class="base"><span class="strut"><span class="mord">&Theta;<span class="mopen">(<span class="mord mathnormal">n<span class="mclose">)

不均匀分治

快速排序不可能每次都选到最中间的枢纽。假设快速排序每次都把数组分成 <span class="katex"><span class="katex-mathml">1/4<span class="katex-html"><span class="base"><span class="strut"><span class="mord">1/4&nbsp;和&nbsp;<span class="math inline"><span class="katex"><span class="katex-mathml">3/4<span class="katex-html"><span class="base"><span class="strut"><span class="mord">3/4&nbsp;两部分。递归为：

 

�(�)=�(�/4)+�(3�/4)+�(�)T(n)=T(n/4)+T(3n/4)+O(n)

 

求 <span class="katex"><span class="katex-mathml">�<span class="katex-html"><span class="base"><span class="strut"><span class="mord mathnormal">p：<span class="math inline"><span class="katex"><span class="katex-mathml">(1/4)�+(3/4)�=1<span class="katex-html"><span class="base"><span class="strut"><span class="mopen">(<span class="mord">1/4<span class="mclose"><span class="mclose">)<span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist"><span><span class="pstrut"><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight">p<span class="mspace"><span class="mbin">+<span class="mspace"><span class="base"><span class="strut"><span class="mopen">(<span class="mord">3/4<span class="mclose"><span class="mclose">)<span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist"><span><span class="pstrut"><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight">p<span class="mspace"><span class="mrel">=<span class="mspace"><span class="base"><span class="strut"><span class="mord">1。显然&nbsp;<span class="math inline"><span class="katex"><span class="katex-mathml">�=1<span class="katex-html"><span class="base"><span class="strut"><span class="mord mathnormal">p<span class="mspace"><span class="mrel">=<span class="mspace"><span class="base"><span class="strut"><span class="mord">1。

于是：<span class="katex"><span class="katex-mathml">�(�)=&Theta;(�(1+&int;1���2��))<span class="katex-html"><span class="base"><span class="strut"><span class="mord mathnormal">T<span class="mopen">(<span class="mord mathnormal">n<span class="mclose">)<span class="mspace"><span class="mrel">=<span class="mspace"><span class="base"><span class="strut"><span class="mord">&Theta;<span class="mspace"><span class="minner"><span class="mopen delimcenter"><span class="delimsizing size1">(<span class="mord mathnormal">n<span class="mspace"><span class="minner"><span class="mopen delimcenter"><span class="delimsizing size1">(<span class="mord">1<span class="mspace"><span class="mbin">+<span class="mspace"><span class="mop"><span class="mop op-symbol small-op">&int;<span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist"><span><span class="pstrut"><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">1<span><span class="pstrut"><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight">n<span class="vlist-s">​<span class="vlist-r"><span class="vlist"><span><span class="mspace"><span class="mord"><span class="mopen nulldelimiter"><span class="mfrac"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist"><span><span class="pstrut"><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight"><span class="mord mathnormal mtight">u<span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist"><span><span class="pstrut"><span class="sizing reset-size3 size1 mtight"><span class="mord mtight">2<span><span class="pstrut"><span class="frac-line"><span><span class="pstrut"><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathnormal mtight">u<span class="vlist-s">​<span class="vlist-r"><span class="vlist"><span><span class="mclose nulldelimiter"><span class="mord mathnormal">d<span class="mord mathnormal">u<span class="mclose delimcenter"><span class="delimsizing size1">)<span class="mclose delimcenter"><span class="delimsizing size1">)

最终 <span class="katex"><span class="katex-mathml">�(�)=&Theta;(�log⁡�)<span class="katex-html"><span class="base"><span class="strut"><span class="mord mathnormal">T<span class="mopen">(<span class="mord mathnormal">n<span class="mclose">)<span class="mspace"><span class="mrel">=<span class="mspace"><span class="base"><span class="strut"><span class="mord">&Theta;<span class="mopen">(<span class="mord mathnormal">n<span class="mspace"><span class="mop">log<span class="mspace"><span class="mord mathnormal">n<span class="mclose">)

这和快速排序的直觉一致：只要划分不是极端不平衡，快速排序仍然是 <span class="katex"><span class="katex-mathml">�(�log⁡�)<span class="katex-html"><span class="base"><span class="strut"><span class="mord mathnormal">O<span class="mopen">(<span class="mord mathnormal">n<span class="mspace"><span class="mop">log<span class="mspace"><span class="mord mathnormal">n<span class="mclose">)。事实上，只要每层总工作量是线性的，并且问题按固定比例缩小，总复杂度通常还是&nbsp;<span class="math inline"><span class="katex"><span class="katex-mathml">�log⁡�<span class="katex-html"><span class="base"><span class="strut"><span class="mord mathnormal">n<span class="mspace"><span class="mop">log<span class="mspace"><span class="mord mathnormal">n&nbsp;级别。

BFPRT 选择算法

BFPRT，也就是线性时间选择算法，会出现类似递归：

 

�(�)=�(�/5)+�(7�/10)+�(�)T(n)=T(n/5)+T(7n/10)+O(n)

 

其中：

• <span class="katex"><span class="katex-mathml">�(�/5)<span class="katex-html"><span class="base"><span class="strut"><span class="mord mathnormal">T<span class="mopen">(<span class="mord mathnormal">n<span class="mord">/5<span class="mclose">)&nbsp;来自递归寻找中位数的中位数
• <span class="katex"><span class="katex-mathml">�(7�/10)<span class="katex-html"><span class="base"><span class="strut"><span class="mord mathnormal">T<span class="mopen">(<span class="mord">7<span class="mord mathnormal">n<span class="mord">/10<span class="mclose">)&nbsp;来自递归处理剩下的一侧
• <span class="katex"><span class="katex-mathml">�(�)<span class="katex-html"><span class="base"><span class="strut"><span class="mord mathnormal">O<span class="mopen">(<span class="mord mathnormal">n<span class="mclose">)&nbsp;来自分组、找中位数和 partition

求 <span class="katex"><span class="katex-mathml">(1/5)�+(7/10)�=1<span class="katex-html"><span class="base"><span class="strut"><span class="mopen">(<span class="mord">1/5<span class="mclose"><span class="mclose">)<span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist"><span><span class="pstrut"><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight">p<span class="mspace"><span class="mbin">+<span class="mspace"><span class="base"><span class="strut"><span class="mopen">(<span class="mord">7/10<span class="mclose"><span class="mclose">)<span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist"><span><span class="pstrut"><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight">p<span class="mspace"><span class="mrel">=<span class="mspace"><span class="base"><span class="strut"><span class="mord">1

由于当 <span class="katex"><span class="katex-mathml">�=1<span class="katex-html"><span class="base"><span class="strut"><span class="mord mathnormal">p<span class="mspace"><span class="mrel">=<span class="mspace"><span class="base"><span class="strut"><span class="mord">1&nbsp;时：<span class="math inline"><span class="katex"><span class="katex-mathml">1/5+7/10=9/10&lt;1<span class="katex-html"><span class="base"><span class="strut"><span class="mord">1/5<span class="mspace"><span class="mbin">+<span class="mspace"><span class="base"><span class="strut"><span class="mord">7/10<span class="mspace"><span class="mrel">=<span class="mspace"><span class="base"><span class="strut"><span class="mord">9/10<span class="mspace"><span class="mrel">&lt;<span class="mspace"><span class="base"><span class="strut"><span class="mord">1。所以真正的&nbsp;<span class="math inline"><span class="katex"><span class="katex-mathml">�&lt;1<span class="katex-html"><span class="base"><span class="strut"><span class="mord mathnormal">p<span class="mspace"><span class="mrel">&lt;<span class="mspace"><span class="base"><span class="strut"><span class="mord">1。

代入 Akra–Bazzi 公式后，这就和例子一完全一样了。最终 <span class="katex"><span class="katex-mathml">�(�)=&Theta;(�)<span class="katex-html"><span class="base"><span class="strut"><span class="mord mathnormal">T<span class="mopen">(<span class="mord mathnormal">n<span class="mclose">)<span class="mspace"><span class="mrel">=<span class="mspace"><span class="base"><span class="strut"><span class="mord">&Theta;<span class="mopen">(<span class="mord mathnormal">n<span class="mclose">)

递归结构本身占主导

考虑：

 

�(�)=2�(�/2)+�(�/4)+�(�)T(n)=2T(n/2)+T(n/4)+O(n)

 

求 <span class="katex"><span class="katex-mathml">�<span class="katex-html"><span class="base"><span class="strut"><span class="mord mathnormal">p：<span class="math inline"><span class="katex"><span class="katex-mathml">2(1/2)�+(1/4)�=1<span class="katex-html"><span class="base"><span class="strut"><span class="mord">2<span class="mopen">(<span class="mord">1/2<span class="mclose"><span class="mclose">)<span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist"><span><span class="pstrut"><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight">p<span class="mspace"><span class="mbin">+<span class="mspace"><span class="base"><span class="strut"><span class="mopen">(<span class="mord">1/4<span class="mclose"><span class="mclose">)<span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist"><span><span class="pstrut"><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight">p<span class="mspace"><span class="mrel">=<span class="mspace"><span class="base"><span class="strut"><span class="mord">1

当 <span class="katex"><span class="katex-mathml">�=1<span class="katex-html"><span class="base"><span class="strut"><span class="mord mathnormal">p<span class="mspace"><span class="mrel">=<span class="mspace"><span class="base"><span class="strut"><span class="mord">1&nbsp;时：<span class="math inline"><span class="katex"><span class="katex-mathml">2&sdot;12+14=54&gt;1<span class="katex-html"><span class="base"><span class="strut"><span class="mord">2<span class="mspace"><span class="mbin">&sdot;<span class="mspace"><span class="base"><span class="strut"><span class="mord"><span class="mopen nulldelimiter"><span class="mfrac"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist"><span><span class="pstrut"><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">2<span><span class="pstrut"><span class="frac-line"><span><span class="pstrut"><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">1<span class="vlist-s">​<span class="vlist-r"><span class="vlist"><span><span class="mclose nulldelimiter"><span class="mspace"><span class="mbin">+<span class="mspace"><span class="base"><span class="strut"><span class="mord"><span class="mopen nulldelimiter"><span class="mfrac"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist"><span><span class="pstrut"><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">4<span><span class="pstrut"><span class="frac-line"><span><span class="pstrut"><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">1<span class="vlist-s">​<span class="vlist-r"><span class="vlist"><span><span class="mclose nulldelimiter"><span class="mspace"><span class="mrel">=<span class="mspace"><span class="base"><span class="strut"><span class="mord"><span class="mopen nulldelimiter"><span class="mfrac"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist"><span><span class="pstrut"><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">4<span><span class="pstrut"><span class="frac-line"><span><span class="pstrut"><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">5<span class="vlist-s">​<span class="vlist-r"><span class="vlist"><span><span class="mclose nulldelimiter"><span class="mspace"><span class="mrel">&gt;<span class="mspace"><span class="base"><span class="strut"><span class="mord">1

当 <span class="katex"><span class="katex-mathml">�=2<span class="katex-html"><span class="base"><span class="strut"><span class="mord mathnormal">p<span class="mspace"><span class="mrel">=<span class="mspace"><span class="base"><span class="strut"><span class="mord">2&nbsp;时：<span class="math inline"><span class="katex"><span class="katex-mathml">2&sdot;14+116=916&lt;1<span class="katex-html"><span class="base"><span class="strut"><span class="mord">2<span class="mspace"><span class="mbin">&sdot;<span class="mspace"><span class="base"><span class="strut"><span class="mord"><span class="mopen nulldelimiter"><span class="mfrac"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist"><span><span class="pstrut"><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">4<span><span class="pstrut"><span class="frac-line"><span><span class="pstrut"><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">1<span class="vlist-s">​<span class="vlist-r"><span class="vlist"><span><span class="mclose nulldelimiter"><span class="mspace"><span class="mbin">+<span class="mspace"><span class="base"><span class="strut"><span class="mord"><span class="mopen nulldelimiter"><span class="mfrac"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist"><span><span class="pstrut"><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">16<span><span class="pstrut"><span class="frac-line"><span><span class="pstrut"><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">1<span class="vlist-s">​<span class="vlist-r"><span class="vlist"><span><span class="mclose nulldelimiter"><span class="mspace"><span class="mrel">=<span class="mspace"><span class="base"><span class="strut"><span class="mord"><span class="mopen nulldelimiter"><span class="mfrac"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist"><span><span class="pstrut"><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">16<span><span class="pstrut"><span class="frac-line"><span><span class="pstrut"><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">9<span class="vlist-s">​<span class="vlist-r"><span class="vlist"><span><span class="mclose nulldelimiter"><span class="mspace"><span class="mrel">&lt;<span class="mspace"><span class="base"><span class="strut"><span class="mord">1

所以：

 

1<�<21<p<2

 

这里递归结构本身增长得比 <span class="katex"><span class="katex-mathml">�<span class="katex-html"><span class="base"><span class="strut"><span class="mord mathnormal">n&nbsp;更快。

因此：<span class="katex"><span class="katex-mathml">�(�)=&Theta;(��)<span class="katex-html"><span class="base"><span class="strut"><span class="mord mathnormal">T<span class="mopen">(<span class="mord mathnormal">n<span class="mclose">)<span class="mspace"><span class="mrel">=<span class="mspace"><span class="base"><span class="strut"><span class="mord">&Theta;<span class="mopen">(<span class="mord"><span class="mord mathnormal">n<span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist"><span><span class="pstrut"><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight">p<span class="mclose">)。其中&nbsp;<span class="math inline"><span class="katex"><span class="katex-mathml">�<span class="katex-html"><span class="base"><span class="strut"><span class="mord mathnormal">p&nbsp;是方程&nbsp;<span class="math inline"><span class="katex"><span class="katex-mathml">2(1/2)�+(1/4)�=1<span class="katex-html"><span class="base"><span class="strut"><span class="mord">2<span class="mopen">(<span class="mord">1/2<span class="mclose"><span class="mclose">)<span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist"><span><span class="pstrut"><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight">p<span class="mspace"><span class="mbin">+<span class="mspace"><span class="base"><span class="strut"><span class="mopen">(<span class="mord">1/4<span class="mclose"><span class="mclose">)<span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist"><span><span class="pstrut"><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight">p<span class="mspace"><span class="mrel">=<span class="mspace"><span class="base"><span class="strut"><span class="mord">1&nbsp;的解。

和主定理的关系

主定理处理：

 

�(�)=��(�/�)+�(�)T(n)=aT(n/b)+f(n)

 

这是 Akra–Bazzi 的特殊情况。

此时只有一类子问题，所以方程变成：<span class="katex"><span class="katex-mathml">��&minus;�=1<span class="katex-html"><span class="base"><span class="strut"><span class="mord mathnormal">a<span class="mord"><span class="mord mathnormal">b<span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist"><span><span class="pstrut"><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">&minus;<span class="mord mathnormal mtight">p<span class="mspace"><span class="mrel">=<span class="mspace"><span class="base"><span class="strut"><span class="mord">1

解得：<span class="katex"><span class="katex-mathml">�=log⁡��<span class="katex-html"><span class="base"><span class="strut"><span class="mord mathnormal">p<span class="mspace"><span class="mrel">=<span class="mspace"><span class="base"><span class="strut"><span class="mop"><span class="mop">log<span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist"><span><span class="pstrut"><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight">b<span class="vlist-s">​<span class="vlist-r"><span class="vlist"><span><span class="mspace"><span class="mord mathnormal">a

这正好就是主定理里的关键指数。

所以：

 

主定理=Akra–Bazzi 在等规模子问题下的特例主定理=Akra–Bazzi 在等规模子问题下的特例

 

关于 <span class="katex"><span class="katex-mathml">�(�)<span class="katex-html"><span class="base"><span class="strut"><span class="mord mathnormal">f<span class="mopen">(<span class="mord mathnormal">n<span class="mclose">)&nbsp;的条件

Akra–Bazzi 定理要求 <span class="katex"><span class="katex-mathml">�(�)<span class="katex-html"><span class="base"><span class="strut"><span class="mord mathnormal">f<span class="mopen">(<span class="mord mathnormal">n<span class="mclose">)&nbsp;不能太奇怪。直观地说，<span class="math inline"><span class="katex"><span class="katex-mathml">�(�)<span class="katex-html"><span class="base"><span class="strut"><span class="mord mathnormal">f<span class="mopen">(<span class="mord mathnormal">n<span class="mclose">)&nbsp;要比较平滑，不能剧烈震荡。就常见的函数来说：

 

�(�)=Θ(��log⁡��)f(n)=Θ(nαlogβn)

 

都是可以的。但像 <span class="katex"><span class="katex-mathml">�(�)=2�<span class="katex-html"><span class="base"><span class="strut"><span class="mord mathnormal">f<span class="mopen">(<span class="mord mathnormal">n<span class="mclose">)<span class="mspace"><span class="mrel">=<span class="mspace"><span class="base"><span class="strut"><span class="mord"><span class="mord">2<span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist"><span><span class="pstrut"><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight">n&nbsp;这种就不可用。

 

 

 

 

https://2shou.guilinlife.com/classad-302-6273685.html
https://2shou.guilinlife.com/classad-302-6273640.html
https://2shou.guilinlife.com/classad-302-6273606.html
https://2shou.guilinlife.com/classad-302-6273562.html
https://2shou.guilinlife.com/classad-302-6273519.html
https://2shou.guilinlife.com/classad-302-6273482.html
https://2shou.guilinlife.com/classad-302-6273446.html
https://2shou.guilinlife.com/classad-302-6273409.html
https://2shou.guilinlife.com/classad-302-6273372.html
https://2shou.guilinlife.com/classad-302-6273335.html
https://2shou.guilinlife.com/classad-302-6273297.html
https://2shou.guilinlife.com/classad-302-6273259.html
https://2shou.guilinlife.com/classad-302-6273225.html
https://2shou.guilinlife.com/classad-302-6273183.html
https://2shou.guilinlife.com/classad-302-6273147.html
https://2shou.guilinlife.com/classad-302-6273112.html
https://2shou.guilinlife.com/classad-302-6273076.html
https://2shou.guilinlife.com/classad-302-6273040.html
https://2shou.guilinlife.com/classad-302-6273005.html
https://2shou.guilinlife.com/classad-302-6272968.html
https://2shou.guilinlife.com/classad-302-6272933.html
https://2shou.guilinlife.com/classad-302-6272898.html
https://2shou.guilinlife.com/classad-302-6272854.html
https://2shou.guilinlife.com/classad-302-6260616.html
https://2shou.guilinlife.com/classad-302-6260586.html
https://2shou.guilinlife.com/classad-302-6260553.html
https://2shou.guilinlife.com/classad-302-6260522.html
https://2shou.guilinlife.com/classad-302-6260490.html
https://2shou.guilinlife.com/classad-302-6260458.html
https://2shou.guilinlife.com/classad-302-6260428.html
https://2shou.guilinlife.com/classad-302-6260397.html
https://2shou.guilinlife.com/classad-302-6260368.html
https://2shou.guilinlife.com/classad-302-6260339.html
https://2shou.guilinlife.com/classad-302-6260310.html
https://2shou.guilinlife.com/classad-302-6260281.html
https://2shou.guilinlife.com/classad-302-6260254.html
https://2shou.guilinlife.com/classad-302-6260225.html
https://2shou.guilinlife.com/classad-302-6260198.html
https://2shou.guilinlife.com/classad-302-6260169.html
https://2shou.guilinlife.com/classad-302-6260140.html
https://2shou.guilinlife.com/classad-302-6260112.html
https://2shou.guilinlife.com/classad-302-6260081.html
https://2shou.guilinlife.com/classad-302-6260054.html
https://2shou.guilinlife.com/classad-302-6260026.html
https://2shou.guilinlife.com/classad-302-6259997.html
https://2shou.guilinlife.com/classad-302-6259969.html
https://2shou.guilinlife.com/classad-302-6259939.html
https://2shou.guilinlife.com/classad-302-6259910.html
https://2shou.guilinlife.com/classad-302-6275768.html
https://2shou.guilinlife.com/classad-302-6275734.html
https://2shou.guilinlife.com/classad-302-6275700.html
https://2shou.guilinlife.com/classad-302-6275658.html
https://2shou.guilinlife.com/classad-302-6275620.html
https://2shou.guilinlife.com/classad-302-6275581.html
https://2shou.guilinlife.com/classad-302-6273785.html
https://2shou.guilinlife.com/classad-302-6273746.html
https://2shou.guilinlife.com/classad-302-6273701.html
https://2shou.guilinlife.com/classad-302-6273661.html
https://2shou.guilinlife.com/classad-302-6273619.html
https://2shou.guilinlife.com/classad-302-6273578.html
https://2shou.guilinlife.com/classad-302-6273537.html
https://2shou.guilinlife.com/classad-302-6273497.html
https://2shou.guilinlife.com/classad-302-6273460.html
https://2shou.guilinlife.com/classad-302-6273422.html
https://2shou.guilinlife.com/classad-302-6273386.html
https://2shou.guilinlife.com/classad-302-6273348.html
https://2shou.guilinlife.com/classad-302-6273313.html
https://2shou.guilinlife.com/classad-302-6273274.html
https://2shou.guilinlife.com/classad-302-6273238.html
https://2shou.guilinlife.com/classad-302-6273202.html
https://2shou.guilinlife.com/classad-302-6273161.html
https://2shou.guilinlife.com/classad-302-6273125.html
https://2shou.guilinlife.com/classad-302-6273089.html
https://2shou.guilinlife.com/classad-302-6273055.html
https://2shou.guilinlife.com/classad-302-6273019.html
https://2shou.guilinlife.com/classad-302-6272983.html
https://2shou.guilinlife.com/classad-302-6272947.html
https://2shou.guilinlife.com/classad-302-6272914.html
https://2shou.guilinlife.com/classad-302-6272871.html
https://2shou.guilinlife.com/classad-302-6260627.html
https://2shou.guilinlife.com/classad-302-6260599.html
https://2shou.guilinlife.com/classad-302-6260566.html
https://2shou.guilinlife.com/classad-302-6260535.html
https://2shou.guilinlife.com/classad-302-6260502.html
https://2shou.guilinlife.com/classad-302-6260472.html
https://2shou.guilinlife.com/classad-302-6260440.html
https://2shou.guilinlife.com/classad-302-6260410.html
https://2shou.guilinlife.com/classad-302-6260380.html
https://2shou.guilinlife.com/classad-302-6260352.html
https://2shou.guilinlife.com/classad-302-6260323.html
https://2shou.guilinlife.com/classad-302-6260293.html
https://2shou.guilinlife.com/classad-302-6260265.html
https://2shou.guilinlife.com/classad-302-6260237.html
https://2shou.guilinlife.com/classad-302-6260208.html
https://2shou.guilinlife.com/classad-302-6260180.html
https://2shou.guilinlife.com/classad-302-6260151.html
https://2shou.guilinlife.com/classad-302-6260124.html
https://2shou.guilinlife.com/classad-302-6260093.html
https://2shou.guilinlife.com/classad-302-6260065.html
https://2shou.guilinlife.com/classad-302-6260036.html
https://2shou.guilinlife.com/classad-302-6260008.html
https://2shou.guilinlife.com/classad-302-6259979.html
https://2shou.guilinlife.com/classad-302-6259951.html
https://2shou.guilinlife.com/classad-302-6259921.html
https://2shou.guilinlife.com/classad-302-6249369.html
https://2shou.guilinlife.com/classad-302-6275780.html
https://2shou.guilinlife.com/classad-302-6275745.html
https://2shou.guilinlife.com/classad-302-6275710.html
https://2shou.guilinlife.com/classad-302-6275672.html
https://2shou.guilinlife.com/classad-302-6275635.html
https://2shou.guilinlife.com/classad-302-6275594.html
https://2shou.guilinlife.com/classad-302-6273799.html
https://2shou.guilinlife.com/classad-302-6273759.html
https://2shou.guilinlife.com/classad-302-6273715.html
https://2shou.guilinlife.com/classad-302-6273674.html
https://2shou.guilinlife.com/classad-302-6273631.html
https://2shou.guilinlife.com/classad-302-6273596.html
https://2shou.guilinlife.com/classad-302-6273551.html
https://2shou.guilinlife.com/classad-302-6273511.html
https://2shou.guilinlife.com/classad-302-6273472.html
https://2shou.guilinlife.com/classad-302-6273436.html
https://2shou.guilinlife.com/classad-302-6273398.html
https://2shou.guilinlife.com/classad-302-6273363.html
https://2shou.guilinlife.com/classad-302-6273325.html
https://2shou.guilinlife.com/classad-302-6273286.html
https://2shou.guilinlife.com/classad-302-6273250.html
https://2shou.guilinlife.com/classad-302-6273214.html
https://2shou.guilinlife.com/classad-302-6273174.html
https://2shou.guilinlife.com/classad-302-6273138.html
https://2shou.guilinlife.com/classad-302-6273101.html
https://2shou.guilinlife.com/classad-302-6273067.html
https://2shou.guilinlife.com/classad-302-6273031.html
https://2shou.guilinlife.com/classad-302-6272996.html
https://2shou.guilinlife.com/classad-302-6272960.html
https://2shou.guilinlife.com/classad-302-6272925.html
https://2shou.guilinlife.com/classad-302-6272888.html
https://2shou.guilinlife.com/classad-302-6260639.html
https://2shou.guilinlife.com/classad-302-6260608.html
https://2shou.guilinlife.com/classad-302-6260578.html
https://2shou.guilinlife.com/classad-302-6260544.html
https://2shou.guilinlife.com/classad-302-6260512.html
https://2shou.guilinlife.com/classad-302-6260483.html
https://2shou.guilinlife.com/classad-302-6260449.html
https://2shou.guilinlife.com/classad-302-6260421.html
https://2shou.guilinlife.com/classad-302-6260389.html
https://2shou.guilinlife.com/classad-302-6260361.html
https://2shou.guilinlife.com/classad-302-6260332.html
https://2shou.guilinlife.com/classad-302-6260303.html
https://2shou.guilinlife.com/classad-302-6260274.html
https://2shou.guilinlife.com/classad-302-6260247.html
https://2shou.guilinlife.com/classad-302-6260218.html
https://2shou.guilinlife.com/classad-302-6260190.html
https://2shou.guilinlife.com/classad-302-6260163.html
https://2shou.guilinlife.com/classad-302-6260134.html
https://2shou.guilinlife.com/classad-302-6260102.html
https://2shou.guilinlife.com/classad-302-6260074.html
https://2shou.guilinlife.com/classad-302-6260046.html
https://2shou.guilinlife.com/classad-302-6260017.html
https://2shou.guilinlife.com/classad-302-6259991.html
https://2shou.guilinlife.com/classad-302-6259961.html
https://2shou.guilinlife.com/classad-302-6259932.html
https://2shou.guilinlife.com/classad-302-6249386.html
https://2shou.guilinlife.com/classad-302-6275777.html
https://2shou.guilinlife.com/classad-302-6275743.html
https://2shou.guilinlife.com/classad-302-6275707.html
https://2shou.guilinlife.com/classad-302-6275669.html
https://2shou.guilinlife.com/classad-302-6275632.html
https://2shou.guilinlife.com/classad-302-6275591.html
https://2shou.guilinlife.com/classad-302-6273794.html
https://2shou.guilinlife.com/classad-302-6273757.html
https://2shou.guilinlife.com/classad-302-6273710.html
https://2shou.guilinlife.com/classad-302-6273669.html
https://2shou.guilinlife.com/classad-302-6273627.html
https://2shou.guilinlife.com/classad-302-6273590.html
https://2shou.guilinlife.com/classad-302-6273549.html
https://2shou.guilinlife.com/classad-302-6273508.html
https://2shou.guilinlife.com/classad-302-6273470.html
https://2shou.guilinlife.com/classad-302-6273432.html
https://2shou.guilinlife.com/classad-302-6273395.html
https://2shou.guilinlife.com/classad-302-6273360.html
https://2shou.guilinlife.com/classad-302-6273320.html
https://2shou.guilinlife.com/classad-302-6273283.html
https://2shou.guilinlife.com/classad-302-6273246.html
https://2shou.guilinlife.com/classad-302-6273210.html
https://2shou.guilinlife.com/classad-302-6273171.html
https://2shou.guilinlife.com/classad-302-6273135.html
https://2shou.guilinlife.com/classad-302-6273098.html
https://2shou.guilinlife.com/classad-302-6273063.html
https://2shou.guilinlife.com/classad-302-6273029.html
https://2shou.guilinlife.com/classad-302-6272991.html
https://2shou.guilinlife.com/classad-302-6272955.html
https://2shou.guilinlife.com/classad-302-6272921.html
https://2shou.guilinlife.com/classad-302-6272886.html
https://2shou.guilinlife.com/classad-302-6260636.html
https://2shou.guilinlife.com/classad-302-6260605.html
https://2shou.guilinlife.com/classad-302-6260575.html
https://2shou.guilinlife.com/classad-302-6260541.html
https://2shou.guilinlife.com/classad-302-6260509.html
https://2shou.guilinlife.com/classad-302-6260479.html
https://2shou.guilinlife.com/classad-302-6260446.html
https://2shou.guilinlife.com/classad-302-6260419.html
https://2shou.guilinlife.com/classad-302-6260387.html
https://2shou.guilinlife.com/classad-302-6260358.html
https://2shou.guilinlife.com/classad-302-6260330.html
https://2shou.guilinlife.com/classad-302-6260301.html
https://2shou.guilinlife.com/classad-302-6260272.html
https://2shou.guilinlife.com/classad-302-6260244.html
https://2shou.guilinlife.com/classad-302-6260215.html
https://2shou.guilinlife.com/classad-302-6260187.html
https://2shou.guilinlife.com/classad-302-6260158.html
https://2shou.guilinlife.com/classad-302-6260130.html
https://2shou.guilinlife.com/classad-302-6260100.html
https://2shou.guilinlife.com/classad-302-6260072.html
https://2shou.guilinlife.com/classad-302-6260043.html
https://2shou.guilinlife.com/classad-302-6260014.html
https://2shou.guilinlife.com/classad-302-6259986.html
https://2shou.guilinlife.com/classad-302-6259958.html
https://2shou.guilinlife.com/classad-302-6259928.html
https://2shou.guilinlife.com/classad-302-6249382.html
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6275793
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6275758
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6275725
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6275686
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6275647
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6275610
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6275570
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273774
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273729
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273690
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273647
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273609
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273565
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273524
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273485
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273449
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273413
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273375
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273339
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273301
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273263
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273227
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273188
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273149
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273114
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273079
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273043
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273008
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6272972
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6272937
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6272902
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6272857
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260619
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260590
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260556
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260525
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260493
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260462
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260430
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260399
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260371
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260342
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260313
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260284
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260257
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260229
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260200
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260172
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260142
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260115
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260084
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260057
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260029
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260000
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6259971
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6259941
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6259912
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6275788
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6275754
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6275721
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6275681
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6275642
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6275602
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6275566
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273768
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273723
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273683
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273639
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273605
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273559
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273517
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273479
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273444
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273406
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273370
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273333
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273293
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273258
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273222
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273182
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273145
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273108
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273073
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273039
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273003
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6272967
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6272932
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6272895
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6272852
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260614
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260585
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260552
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260521
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260488
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260456
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260426
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260396
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260367
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260338
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260309
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260280
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260252
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260224
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260196
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260168
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260139
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260108
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260080
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260052
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260024
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6259996
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6259967
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6259937
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6259909
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6275800
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6275762
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6275728
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6275690
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6275651
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6275613
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6275576
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273777
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273739
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273692
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273651
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273612
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273568
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273528
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273489
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273453
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273416
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273378
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273342
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273304
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273266
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273231
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273196
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273155
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273118
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273082
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273049
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6272976
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6272940
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6272906
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6272861
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260622
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260592
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260558
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260528
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260496
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260464
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260433
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260402
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260374
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260345
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260315
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260288
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260232
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260203
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260175
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260145
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260117
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260087
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260060
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260031
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260003
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6259974
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6259944
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6259916
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6275783
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6275749
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6275716
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6275677
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6275638
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6275598
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273802
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273764
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273720
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273679
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273636
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273601
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273555
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273515
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273476
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273439
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273402
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273367
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273329
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273290
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273255
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273218
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273177
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273141
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273106
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273071
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6273035
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6272999
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6272963
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6272928
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6272892
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6265395
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260611
https://2shou.guilinlife.com/index.php?m=wap&a=show&catid=302&id=6260581