算法归纳法

1. 算法的正确性证明方法二: 结构归纳法

在上一篇文章中谈到在使用循环的算法中，可以利用 循环不变量 证明算法的正确性，那如果是使用递归的算法呢。

递归的算法在计算中会形成某种 递归结构 ，因此可以利用结构归纳法来证明正确性。

看到这个名字，我们会自然想起 数学归纳法 。
其实它是数学归纳法的一般化，也就是说数学归纳法是它的特殊化。

它用于证明，某种递归结构 x（list or tree）满足命题 P (x)，证明方法类似我们熟悉的数学归纳法。
首先提出一个命题 P (x)，证明 最小结构 和 子结构 均满足命题 P (x)，那么这种递归结构满足命题 P (x)。

而这个命题经过结构归纳法证明后，能用作证明相应算法的正确性。

跟上一篇一样，我们使用 归并排序（Merge sort） 作为例子，不过这次用到的是它的递归函数。

了解归并排序的朋友会知道它使用了 分治法
分治法的中心思想是把问题 递归 分割为子问题，一直到不能继续 分割 的最小子问题（base case），最小子问题的解决方法很简单明显，这时递归返回并将子问题的答案逐层 合并 ，最后就是原问题的答案了。

归并排序的 3 个步骤分别如下：

假设原数组为 [ 5 2 4 7 1 3 2 6 ] ，它在 分割 阶段呈现以下的二叉树结构

首先提出命题

然后使用结构归纳法证明：

因此当二叉树高度为最大值时，已递归分割至最底层（数组大小为1不能继续分割），停止递归并将子问题答案通过 merge 函数合并逐层返回，而 merge 函数在 上一篇 中已证明其正确性，因此归并排序算法的正确性得以证明。

2. 算法设计与分析归纳法需要哪两个步骤

总结算法设计的步骤

• 弄清楚题目的意思，列出题目的输入、输出、约束条件

• 思考怎样让算法的时间复杂度尽可能的小

• 编写伪代码或代码

归纳思维

• 是从特殊情况出发

• 推理出一般性的结论

• 作为数据分析的重要思维，应该引起足够的重视。

扩展：介绍 5 种归纳方法，即：求同法、求异法、共用法、共变法和剩余法，其实这些方法早在古代就有，后来培根在《新工具》一书中进行了概括和归纳，最后由穆勒加以系统的整理和说明，因此通常称为“穆勒五法”。

3. 计算机二级数据结构与算法知识点

一、数据结构

（1）数据结构的基本概念

1、数据：数据是客观事物的符号表示，是能输入到计算机中并被计算程序识别和处理的符号的总称，如文档，声音，视频等。

2、数据元素：数据元素是数据的基本单位。

3、数据对象：数据对象是性质相同的数据元素的集合。

4、数据结构：是指由某一数据对象中所有数据成员之间的关系组成的集合。

（2）逻辑结构和存储结构

1、数据结构可分为数据的逻辑结构和存储结构。

1）数据的逻辑结构是对数据元素之间的逻辑关系的描述，与数据的存储无关，是面向问题的，是独立于计算机的。它包括数据对象和数据对象之间的关系。

2）数据的存储结构也称为数据的物理结构，是数据在计算机中的存放的方式，是面向计算机的，它包括数据元素的存储方式和关系的存储方式。

2、存储结构和逻辑结构的关系：一种数据的逻辑结构可以表示成多种存储结构即数据的逻辑结构和存储结构不一定一一对应。

3、常见的存储结构有：顺序，链接，索引等。采用不同的存储结构其数据处理的效率是不同的。

4. C语言里面的算法觉得很难,这样才能学好算法

学好C语言首先要学好他的语法，就比如说英语和语文，你必须要学好他的语法啊，并且要会用他的”单词”，然后就是算法了，这其中要有数学的计算和思想，但是你可以学好的，如果你学好VB那就更好了，因为VB和C语言、很都语法都是共通的．C重要的是思想和算法．．
如果要成为高手的话，那就必须数学基础扎实，因为要到高级的话会用到很多的函数问题，编程也要逻辑性好，而且C就是一种模式，找到了很容易学的。
说实在的，有些东西当初我拿到书的时候是天天琢磨，月月思考，还真别说，有些当初我以为超级老难的问题就愣是这么给琢磨出来了。不过前提是我的数学和逻辑思维真的不错。
慢慢来啊，呵呵，就像当初我以为我自己也学不会，结果还是让我给征服了。其实入门比较困难一些，这都是过程，保持好的心态，如果真的想学就不要放弃，经过时间的积累我想一切都会晴朗的。

5. 如何用归纳法证明算法的时间复杂度 t(n)<=T(n/5)+T(3n/4)+cn<=20cn

1.假设n=1时候，验证
t(1)<=T(1/5)+T(3/4)+c<=20c
2.假设当n=k-1（或者n<=k-1，这两个具体情况具体分析)时候满足：
t(k-1)<=T(k-1/5)+T(3(k-1)/4)+c(k-1)<=20c(k-1)
当n=k时候，
从各个方面分析,t(k-1)与t(k)d的关系，T(k-1)与T(k)的关系，以及c的取值什么的。如果这题目正常的话就应该会的出值了。

6. 数学归纳法中增乘怎么算

即n=1×2×3×...×（n-1）×n。数学归纳法增乘算法公式为，即n=1×2×3×...×（n-1）×n，阶乘亦可以递归方式定义：n=1，n=（n-1）×n，该算法是全日制高级中学教科书《数学》第三册内容。