聊一聊数学中的基本定理（五）——主定理

早点关注我&＃xff0c;精彩不迷路&＃xff1a;

本系列文章介绍的前面几个定理&＃xff0c;分别在算术&＃xff0c;代数以及分析领域的基本定理起着各自领域基石的作用&＃xff0c;相关内容请戳&＃xff1a;

聊一聊数学中的基本定理&＃xff08;四&＃xff09;——微积分基本定理

聊一聊数学中的基本定理&＃xff08;三&＃xff09;——代数基本定理

聊一聊数学中的基本定理&＃xff08;二&＃xff09;——算术基本定理的价值

聊一聊数学中的基本定理&＃xff08;一&＃xff09;——算术基本定理的证明

而接下来这个定理&＃xff0c;名字上虽然已经没有了基本&＃xff08;fundamental&＃xff09;二字&＃xff0c;但是其名——主定理&＃xff08;main theorem&＃xff09;的响度一点也不压于基本定理的声音。想讲它还有一个原因是&＃xff0c;它是难得的一个在离散数学为主导的计算机科学中&＃xff0c;用分析的思想来解决的问题的例子。而且还是那么的基础和优雅&＃xff0c;说它是整个计算机理论的基石之一也不为过。

主定理的基本内容

主定理谈的是一个由分治算法得到递推关系式的时候&＃xff0c;如何来推导时间和空间复杂度的问题。具体如下&＃xff1a;

假设有递归关系式&＃xff0c;其中 &＃xff0c;为问题规模&＃xff0c;为递归的子问题数量&＃xff0c;为每个子问题的规模&＃xff08;假设每个子问题的规模基本一样&＃xff09;&＃xff0c;为递归以外进行的计算工作。

情形一

如果存在常数&＃xff0c;有&＃xff08;可不严谨地视作多项式地小于&＃xff09;

则

情形二

如果存在常数&＃xff0c;有则

情形三

如果存在常数&＃xff0c;有

&＃xff08;多项式地大于&＃xff09;同时存在常数以及充分大的&＃xff0c;满足

则

关于主定理的思考

在实际应用中&＃xff0c;主要用主定理来计算在递归算法中的复杂度为多少&＃xff0c;操作的时候主要看的就是a和b的相对大小的复杂度表达n ^ (log_b a)和f(n)之间的关系&＃xff0c;来决定谁占主要因素。如果是小于&＃xff0c;对应情形1&＃xff0c;复杂度就直接为O(n ^ (log_b a))&＃xff0c;即占主要影响的是递推造成的问题数量的增加&＃xff0c;比如二叉树的遍历&＃xff1b;如果是大于&＃xff0c;对应情形3&＃xff0c;那么占主要因素的就是合并这些小规模问题时候的操作&＃xff0c;一般来说这种时候比较少&＃xff0c;因为合并占据太多资源证明问题减小规模的方向不太好&＃xff0c;使得恢复成本还是太大&＃xff1b;最典型的一种是相等&＃xff0c;对应情形2&＃xff0c;比如二分搜索算法&＃xff0c;这时候的结论是神奇的O(n ^ (log_b a) * log n)&＃xff0c;一般取的就是上面epson &＃61; 0的那种情况&＃xff0c;这时候其规模缩小带来的问题增加以及合并的成本相当&＃xff0c;其总的复杂度是其中之一的复杂度乘以log n。

一个神奇的事情是&＃xff0c;这个公式在进行时间和空间复杂度分析的时候&＃xff0c;方法和结果都是一样的&＃xff0c;一定程度上体现了时空的统一性。

关于这个公式的详细证明&＃xff0c;其实用到基本的等比数列求和公式就可以了&＃xff0c;但是这里我重点想强调的是这里O(f(n))符号标记的真实意义。

给定两个定义在实数某子集上的关于的函数和&＃xff0c;当趋近于无穷大时&＃xff0c;当且仅当存在正常量&＃xff0c;使得对于所有足够大&＃xff08;sufficiently_large&＃xff09;的&＃xff0c;都有的绝对值小于等于乘以的绝对值&＃xff0c;那么我们就可以说&＃xff0c;当时&＃xff0c;也就是说&＃xff0c;假如当且仅当存在正实数和实数0&＃xff0c;使得对于所有的&＃xff0c;均有&＃xff1a;成立&＃xff0c;我们就可以认为&＃xff0c;。

实际应用中&＃xff0c;g(x)是一些标准的&＃xff0c;不带系数的幂函数&＃xff0c;对数函数和指数函数的乘积&＃xff0c;f(x)是我们实际问题中遇到的需要计算复杂度的函数&＃xff0c;不同于o(x)表示的极限下的无穷小量&＃xff0c;大O的渐进符号表示的是一个无穷大的大的程度究竟是多少&＃xff0c;用的是x趋于无穷的上极限来定义的。这里很能体现主定理所描述的思想&＃xff0c;比如一个多项式&＃xff0c;其增长速度由其最高项的次数来决定&＃xff0c;指数则远远快于多项式也远远快于对数式。而对于系数这件事情我们不关心&＃xff0c;只是常数部分罢了。目前非量子的计算机&＃xff0c;对于任何多项式级别的算法都很有信心&＃xff0c;但是指数级别的算法我们总是需要相反设法去化简。

主定理的工程化思考

在实际计算机算法复杂度分析的时候&＃xff0c;和这里理论上说明的有两点差别。其中一个就是我们在工程上还是很关心系数的&＃xff0c;毕竟10x的时间变成x的时间&＃xff0c;相当于要缩短到10%的时间完成同一项工作&＃xff0c;这已经是很不得了的工程优化了&＃xff0c;以前可能要第二天才能同步的数据现在可以提前1天了。但是&＃xff0c;这种优化&＃xff0c;计算机科学家是看不上的&＃xff0c;因为在主定理的体系下&＃xff0c;丝毫没有缩减其在无穷规模下所需要的运算时间的级别。

另一个差别也是源于这个定义的数学化和理想化。我们考察的是问题规模趋于无穷时候的增长速度&＃xff0c;但实际问题虽然有规模很大的时候&＃xff0c;但是和无穷还是两回事。因此我们把什么变量作为这里无穷考察的对象都是有偏差的&＃xff0c;比如我们做query分析&＃xff0c;query长度作为n&＃xff0c;可是我们却会限定query不可以超过128个字等等&＃xff0c;那这个规模其实是很有限的&＃xff0c;哪怕指数级别的复杂度其实并不是扛不住&＃xff0c;这里算法上有科学价值的复杂度上的优化&＃xff0c;有时候还不如一些直接的工程优化。因为你处理的是一个不存在的无穷大的问题&＃xff0c;而实际问题的规模其实是很有限的。再举个例子&＃xff0c;我们在分析并行的分治算法复杂度的时候&＃xff0c;理论上a的值就是1&＃xff0c;即分解出来的问题都可以同步完成。但实际上&＃xff0c;问题完成速度又快有慢&＃xff0c;得等最慢的那个完成&＃xff0c;而cpu的核数&＃xff0c;hadoop或者spark集群给你提供的计算节点数实际上是远小于你真实需要并行的数量的&＃xff0c;假设最大1000个同时并行的任务&＃xff0c;那提速就顶多1000倍&＃xff0c;时间变成1 / 1000&＃xff0c;这便是一件并没有提升理论算法复杂度的一项并行优化了&＃xff0c;但是在工程上目前确是几乎唯一&＃xff0c;也有效的并行计算框架了。我们的计算速度也很大程度上受益于了这样1000倍的提速&＃xff0c;这个绝对提升实在比那推演到无穷规模的不屑有实际意义多了。

这个就是计算机科学和工程的区别&＃xff0c;前者注重理论完备&＃xff0c;后者则经世致用。我们应当用前者当成一把尺子来计算一个理论上的极限&＃xff0c;用后者给我们的经验去不断达到前者&＃xff0c;而在一定时候&＃xff0c;用理论反过来指导我们努力的方向&＃xff0c;不至于走向一个死胡同&＃xff0c;犯那种发明永动机的错误。

好了&＃xff0c;到此&＃xff0c;我们整个基本定理系列的文章就全部结束了&＃xff0c;从算术开始&＃xff0c;到代数&＃xff0c;微积分和离散数学&＃xff0c;借着这个线索又过了一遍数学世界各个领域的精华思想&＃xff0c;让我有一种谈笑有鸿儒的兴奋感&＃xff0c;也希望你能有所收获&＃xff0c;谢谢支持&＃xff0c;我们下个系列再见&＃xff01;

我们是谁&＃xff1a;

MatheMagician&＃xff0c;中文“数学魔术师”&＃xff0c;原指用数学设计魔术的魔术师和数学家。既取其用数学来变魔术的本义&＃xff0c;也取像魔术一样玩数学的意思。文章内容涵盖互联网&＃xff0c;计算机&＃xff0c;统计&＃xff0c;算法&＃xff0c;NLP等前沿的数学及应用领域&＃xff1b;也包括魔术思想&＃xff0c;流程鉴赏等魔术内容&＃xff1b;以及结合二者的数学魔术分享&＃xff0c;还有一些思辨性的谈天说地的随笔。希望你能和我一起&＃xff0c;既能感性思考又保持理性思维&＃xff0c;享受人生乐趣。欢迎扫码关注和在文末或公众号留言与我交流&＃xff01;

扫描二维码

关注更多精彩

聊一聊数学中的基本定理&＃xff08;四&＃xff09;——微积分基本定理

Gilbreath原理中的数学与魔术&＃xff08;九&＃xff09;——Max Maven作品选

魔术的逻辑&＃xff08;三&＃xff09;——明明是假的&＃xff0c;但为何奇迹依旧美妙&＃xff1f;

扒一扒那些叫欧拉的定理们&＃xff08;十二&＃xff09;——经济学里的欧拉定理

点击阅读原文&＃xff0c;往期精彩不错过&＃xff01;