八、灰度实验

前言 灰度实验的概念 举例 这就证明了2.0系统优于1.0系统 灰度实验的两个主要步骤 分流原理

但现实世界中无法做到时间回退，因此只能在1.1到1.31期间使用两个差不多的集合来验证。

小笑话：错误的分流原理 常见的分流方法 案例一 案例二 分流的实现代码 代码运行的结果 通过指标来对AB实验进行评估 评估的举例 大漂亮获取到的原始数据 可以作为指标的各种率 对大漂亮原始数据计算出的各种率 小结 课后作业

九、通过统计学方法证明灰度实验效果不是偶然得到的

前言 什么是偶然得到的下结果 什么是中心极限定理 中心极限定理实现了任意分布向正态分布的转换 例题 例题代码上部分 代码下部分 代码执行结果 数学计算的结果 中心极限定理的白话解释 均值假设检验的步骤 当总体的标准差已知时计算Z 当总体的标准差未知时计算Z
其中μ₀就是假设的均值，在AB实验中μ₀就是对照组的均值。 Z统计量分布表

这个表的行标签和列标签之和就是Z统计量，矩阵中的每个数字，代表观测结果不是偶然发生的概率。例如第二行第三列的数值，就代表Z=0.12（0.1+0.02）的显著性数值。通常人们选择0.9750作为临界值，也就是说Z统计量的临界值为1.96。人们经常用Z的绝对值和19.6之间的关系判断是否显著，如果大于1.96就认为显著，反之则相反。

例题 计算出Z统计量
查询Z统计量分布表可知2.83对应的值大于1.96的

因此均值出现偏小不是偶然情况。

以此类推 以上一节课的例题为例，人均点击量是不够的 我们要计算着7天里每天的人均点击量 对这7个样本求平均值 计算对照组的采样平均值

根据中心极限定理，可以用采样的平均值作为总体平均值的估计值。

计算出实验组的标准差 最后计算出Z统计量的值，7.06>1.96 小结 练习题

十、复杂度：利用数学推导对程序进行优化

什么事复杂度，怎样优化算法 程序的时间损耗 计算程序的时间损耗，t1和t2分别是程序执行前和执行后的两个时间戳 数据量越大，程序的时间损耗就越大 本节所讲的复杂度均为世间上的复杂度，因为时间复杂度关注得最多 由例子可见，随着n的增大，复杂度的值以线性形势增大 这个例子可以看出，t的大小只与c有关，c是代码的行数，和数组的数据量大小毫无关系 复杂度不太关注常数c和b，因为他们和数据量的大小无关 复杂的复杂度函数 4到11行的时间损耗
6到8行的时间损耗
整体的时间损耗
4～11行复杂度的化简
再加上14、15行的时间复杂度 复杂度的性质和代码结构 利用数学优化时间复杂度的举例 一般程序猿解决这个问题的代码会用到两层循环来嵌套，时间复杂度为O(n^2) 使用亦或方法的代码 另一个例子，代码为普通程序的代码 用数学的角度来看，这就是个等差数列求前n项和的问题 使用等差数列求前n项和的代码 代码执行结果如下，时间复杂度为O(n) 小结 课后习题

十一、利用数学归纳法进行程序开发

本节着重讲解循环结构 多米诺骨牌游戏成立的两个条件 数学归纳法的证明方法 数学归纳法例题1 数学归纳法例题2 用S1、S2、S3、S4来代表不同的程序部分 for循环的执行顺序 for循环举例 for循环也可以写成这样 或者这样 while循环的执行顺序 while循环举例 也可以写成这样 do…while循环的执行顺序 do…while循环举例 也可以写成这样 三种循环结构的区别 for循环可以用下方的代码代替

↓↓↓

使用while循环代替

↓↓↓

使用do…while循环来代替 数学归纳法和循环结构的区别 例题3：使用程序完成数学归纳法的证明
程序执行顺序框架
使用for循环来实现
通过部分结果得出原命题得证 小结 课后作业

十二、递归问题

前言 如图1

汉诺塔游戏规则简介：该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置N个金盘(如图1)。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。

假设将除最底下的大盘子之外的盘子都合并成一个小盘子 image.png 这样就把问题简化成了两个盘子的问题 同样的方法还可以用于上面合并的几个小盘子 汉诺塔问题的数学描述 求解H(N) 得出等比数列 image.png image.png 汉诺塔问题的代码实现，如果数量为1，则直接将盘子移动到z轴 如果盘子的数量不为1 假设盘子的数量为3 程序运行的结果 汉诺塔问题的递归思想 使用递归方式需要注意的事项 递归代码的基本结构，if分支中的条件就是终止条件，else语句中的语句就是递归体 递归思维应用于阶乘问题 计算阶乘的程序代码 递归思维应用于斐波那契数列 斐波那契数列算法的终止条件和递归体 计算斐波那契数列前n项和的代码 使用上述代码计算前10项和 代码计算结果和手动计算结果吻合 使用递归思维编程的优缺点 如果在刚才计算斐波那契数列的代码中加入图中两行代码 我们就会发现，每一个参数都要重复计算两遍 小结递归和循环的异同 递归和循环的差异点 课后作业

十三、二分法和指数爆炸问题

问题引入 转换为数学模型 根据上图可以推导出这个表 再以公里为单位推导 以10的3次公里为单位推导 使用等比数列的思想来验算 使用程序计算的代码 程序运行结果 指数爆炸的反向应用——二分查找 二分查找算法描述 举例：找到7所在的数组下标 第一轮查找并缩小范围 第二轮查找，然后缩小范围 第三轮查找，就得出结果了 假设数组有3.8✖️10的11次方，使用二分法可以节省00小时 我们可以用递归的方式实现二分查找算法 使用二分查找的算法计算刚才的例题，通过开始做下标和结束下表计算出中位数下表，然后使用中位数下标所对应的值和目标值进行对比 程序运行结果 指数运算 对数运算 指数和对数的函数图像 指数函数和对数函数的性质 指数爆炸的正向应用 增加密码的命名空间 小结
注意这个前提条件：搜索控件要有序，搜索控件要有序，搜索控件要有序！！！

课后习题：从数学的角度证明指数函数和对数函数的性质成立。

十四、动态规划：利用最优子结构解决问题

动态规划的定义 路线规划问题就是一个典型的动态规划问题，每个路口的选择就是一个子问题，选择了某一条路，那么原本一些可能会走到的路在选择之后就不存在了 动态规划问题的特点 最优子结构 子问题重叠

注意：二分法就是一种典型的分治法

无后效性，当前要做的决策所考虑的问题与之前所做的决策就没有关系了 最优子结构是动态规划问题的切入点 例题说明 大聪明回家会遇到的路口 解决这个问题的切入点思想

上图的描述很重要，它是本题使用最优子结构的关键使用思想。如果path1和path2都是最优路线，那么整条路线肯定就是最优路线了。

换成数学语言描述刚才的方法陈述

因为回家最开始不是要经过B1就是B2，所以我们肯定要在B1和B2之间做一个选择，因此B1、B2集后续路线的最小值都要进行计算。
此时问题就简化成了判断(A~B1)+min(B1~G)和(A~B2)+min(B2~G)之间谁的消耗更小了。然后再把min(B1~G)和min(B2~G)按照刚才的方式拆分成B到C和C到G。如此就发现，这是一个递归算法。

计算B1到C的最小消耗 计算B2到C的最小消耗 根据无后效性原则，B到C就不用管了，再来计算C到D之间的最小消耗 再来计算D到E之间的最小消耗 再来计算E到F的 最后把F1到G的3和F2到G的4带入，得出此图结果 我们使用一个15行乘以16列矩阵来保存刚才图中的网络，因为G是重点，没法从G出发，所以只有15行

行表示出发点，列表示到达点。如果从行点到列点无法到达，就用0表示。如果非要用16✖️16的矩阵，那么G行就用0代表即可。

使用代码来计算，编写一个minPath函数，将刚才的矩阵和矩阵行数当作参数传入 函数体 程序运行结果

刚才的代码和暴力破解没什么区别，存在着大量的重复计算。

优化后的代码 优化后代码的运行结果 小结

如果不存在子问题重叠，那么分治法和动态规划方法都能使用，只是动态规划有点太麻烦了，但如果存在子问题重叠，就只能使用动态规划方法了。

课后作业