2020-04-02 18:25 已编辑华东师范大学算法工程师

关注

具体数学-第3课（递归式转化为求和求解）

原文链接：

今天讲了一种将递归式转化为求和的方法。

考虑如下递归式：
${a_n}{T_n} = {b_n}{T_{n - 1}} + {c_n}$
两边同时乘以 $sn$ 得到：
${s_n}{a_n}{T_n} = {s_n}{b_n}{T_{n - 1}} + {s_n}{c_n}$
要想转化成可以求和的递归式，那么必须有：
${s_n}{b_n} = {s_{n - 1}}{a_{n - 1}}$
也就是：
${s_n} = \frac { { {a_{n - 1}}{a_{n - 2}} \cdots {a_1}}}{ { {b_n}{b_{n - 1}} \cdots {b_2}}}$
这时令
${S_n} = {s_n}{a_n}{T_n}$
得到：
${S_n} = {S_{n - 1}} + {s_n}{c_n}$
这时就可以转化为求和了，解出：
${S_n} = {s_0}{a_0}{T_0} + \sum\limits_{k = 1}^n { {s_k}{c_k}}$
所以
${T_n} = \frac{1}{ { {s_n}{a_n}}}({s_0}{a_0}{T_0} + \sum\limits_{k = 1}^n { {s_k}{c_k}} )$

例题1

设 $n$ 个数快速排序的操作次数为 $C_n$ ，那么有
$\begin{array}{l}{C_0} = 0\\{C_n} = n + 1 + \frac{2}{n}\sum\limits_{k = 0}^{n - 1} { {C_k}} ,n > 0\end{array}$
用 $n-1$ 取代 $n$ 可以得到
${C_{n - 1}} = n + \frac{2}{ {n - 1}}\sum\limits_{k = 0}^{n - 2} { {C_k}} ,n > 1$
两式相减可以得到
$\begin{array}{l}{C_0} = 0\\n{C_n} = (n + 1){C_{n - 1}} + 2n,n > 0\end{array}$
由上面方法可以得到
${a_n} = n,{b_n} = n + 1,{c_n} = 2n$
所以
${s_n} = \frac{2}{ {n(n + 1)}}$
进而可以求出
${C_n} = 2(n + 1)\sum\limits_{k = 1}^n {\frac{1}{ {k + 1}}}$
这里介绍一个概念叫做调和级数：
${H_n} = 1 + \frac{1}{2} + \cdots + \frac{1}{n} = \sum\limits_{k = 1}^n {\frac{1}{k}}$
所以
${C_n} = 2(n + 1){H_n} - 2n$

求和三大定律

结合律、分配率、交换律。这里就不展开说了，相信你们都知道的。
来两题简单的例题说明一下。

例题2

求
$S = \sum\limits_{0 \le k \le n} {(a + bk)}$
普通的方法每个人应该都会，等差数列嘛。这里用求和定律来做一做。
用 $n-k$ 取代 $k$ ，得到
$S = \sum\limits_{0 \le n - k \le n} {(a + b(n - k))}$
即
$S = \sum\limits_{0 \le k \le n} {(a + b(n - k))}$
两式相加得到
$2S = \sum\limits_{0 \le k \le n} {(2a + bn)} = (2a + bn)\sum\limits_{0 \le k \le n} 1 = (2a + bn)(n + 1)$
所以
$S = (2a + bn)(n + 1)/2$

例题3

求
$S = \sum\limits_{0 \le k \le n} {k{x^k}}$
这里用到另一种求和的方法。
两边同时加上第 $n+1$ 项，得到
$\begin{array}{l}S + (n + 1){x^{n + 1}}\\ = \sum\limits_{0 \le k \le n + 1} {k{x^k}} \\ = \sum\limits_{1 \le k \le n + 1} {k{x^k}} \\ = \sum\limits_{0 \le k \le n} {(k + 1){x^{k + 1}}} \\ = x\sum\limits_{0 \le k \le n} {(k{x^k} + {x^k})} \\ = xS + x\sum\limits_{0 \le k \le n} { {x^k}} \\ = xS + x\frac{ {1 - {x^{n + 1}}}}{ {1 - x}}\end{array}$
所以
$S = \frac{ {x - (n + 1){x^{n + 1}} + n{x^{n + 2}}}}{ { { {(1 - x)}^2}}}$
这里介绍另一种方法来求解。
令
$f(x) = \sum\limits_{0 \le k \le n} { {x^k}} = \frac{ {1 - {x^{n + 1}}}}{ {1 - x}}$
求导得到
$f'(x) = \sum\limits_{0 \le k \le n} {k{x^{k - 1}}} = \frac{1}{x}S$
所以
$\frac{1}{x}S = \frac{ {\partial f}}{ {\partial x}}(\frac{ {1 - {x^{n + 1}}}}{ {1 - x}}) = \frac{ {1 - (n + 1){x^n} + n{x^{n + 1}}}}{ { { {(1 - x)}^2}}}$
同样可以得到
$S = \frac{ {x - (n + 1){x^{n + 1}} + n{x^{n + 2}}}}{ { { {(1 - x)}^2}}}$

算法码上来文章被收录于专栏

公众号「算法码上来」。godweiyang带你学习算法，不管是编程算法，还是深度学习、自然语言处理算法都一网打尽，更有各种计算机新鲜知识和你分享。别急，算法码上来。

全部评论

推荐最新楼层

03-19 17:38

已编辑

华北电力大学（保定） Java

滴滴-测开一面

简单做一下自我介绍，介绍个人学习、项目、实习经历。你对软件测试的理解是什么？测试分为哪些类型？什么是黑盒、白盒、灰盒测试？分别在什么场景使用？常用的测试用例设计方法有哪些？你做过的AI 相关测试 / 模型评测具体是怎么做的？介绍一下你做的RAG 智能志愿填报系统，测试部分是怎么开展的？你是如何做自动化测试的？用到哪些工具和框架？自动化测试的适用场景和不适用场景分别是什么？描述一下Bug 的生命周期，提交 Bug 需要包含哪些信息？对Redis、MySQL、MQ这些中间件了解多少？Redis 和 MySQL 数据不一致怎么处理？事务对测试有什么影响？为什么想做测试开发？未来职业规划是什么？你认为...

查看16道真题和解析

点赞评论收藏

03-19 21:35

已编辑

华南理工大学后端工程师

💡PDD 服务端研发面经：在“尬笑”中进阶，在“撕题”中成长

刚面完拼多多（PDD）的服务端岗，这一波面试下来，真的深刻体会到了什么叫“基础不牢，地动山摇”。把面试题总结出来分享给大家，顺便附上我的内推码，大家一起冲！1. 网络基础：那些“送命”的细节TCP断电感知： 我随口说 send 函数返回 -1。面试官微微一笑：“你确定吗？”真相： 客户端断电，OS 没机会发 FIN 包。如果服务器不发数据，send 根本没机会返回错误。此时需要依靠 TCP Keepalive（保活机制） 或者应用层的心跳包来感知。TCP 八股文连招： * 握手/挥手顺序、流量控制、拥塞控制（慢启动、拥塞避免、快重传、快恢复）。报文有序性： 依靠 Sequence Number...

点赞评论收藏

03-15 18:50

中南林业科技大学 Web前端

27双非本前端简历求锐评

本人双非本，大佬们能不能帮我看看我简历哪里有问题，真的很努力地写了，可ssob上投好多已读不回😓😓，要么直接说不合适，小中大厂都投了，真是没招了

Ryan188：我觉得你简历最核心的问题就是太大众化。你要有一个认知就是，如果你是面试官，你是HR，其实他们每天都会收到非常多大量重复的像你这种简历。就是说你的项目不是一个真实的上线的项目，可能是从网上学习而来的，或者是直接copy别人的项目，没有新意，没有展现出你自己对技术的思考，而且你的学历也不占优，自然而然就很难有人去选择你。所以要做的实际上是差异化方向的工作，也就是“给我一个选择你的理由”，比如最近很火的ai，你可以写一个ai相关项目比如问答应用或者mcp编写或者agent搭建，需要你先花点时间学习，34天吧，展现你对这方面相较于其他人特有的思考; 或者写相关技术博客输出一些技术内容，有具体可以量化的成果等等去增加你的竞争力。但以上这些都是后话，我去年在你这个时候也是没人理我，咱们双非学历也没实习，难找也正常，我当时整个3月份都没人鸟我，直到有个新招的岗位，很缺人很急，流程很快，所以我一下子进去了，所以运气方面也很重要，需要你一直坚持喝复盘，直到看到光明，加油兄弟

简历被挂麻了，求建议

点赞评论收藏