算法的意义在于让代码可行、高效、低占用资源。明白代码底层逻辑，方便使用和阅读代码。

算法就是任何明确定义的计算过程，它接收一些值或集合作为输入，并产生一些值或集合作为输出。这样，算法就是将输入转换为输出的一系列计算过程。

·有穷性：如果你设计的算法永无休止地尝试解决问题，那么它是无用的。
·确定性：算法的每一步都必须准确定义，在任何场景下指令都应当没有歧义。
·可行性：一个算法被设计用以解决某个问题，那么它就应当能解决这个
问题，并且仅仅使用纸和笔就能证明该算法是收敛的。

1.计算运行时间

import time

start_time = time.time()

a=1
b=2
print(a+b)

end_time = time.time()
print("程序已完成,总计用时:%f" % (end_time-start_time))

2.大O表示法与时间复杂度

称一个函数f(n)是O(g(n))，当且仅当存在常数c>0和n0>=1，对一切n>n0均有0<=|f(n)|<=c|g(n)|成立，也称函数f(n)以g(n)为界或者称f(n)囿于g(n)。记作f(n)=O(g(n))。我们使用O记号来给出函数的一个在常量因子内的上界。

新定义：我们将算法执行运算的操作数丢弃掉低阶项，再去掉所有的系数，就是算法的时间复杂度。

在它前面加一个O，就是大O表示法：O（n）,其中n为操作数

操作数                   时间复杂度                     名称
3                         O(1)                         常数
105logn+2                 O(logn)                      对数 
2n+4                      O(n)                         线性
7n+9nlogn+39              O(nlogn)                     nlogn
3n^2+2n+5                 O(n^2)                       平方
n^3+20000n^2              O(n^3)                       多项式
2^n                       O(2^n)                       指数

#所消耗的时间从小到大：
 O(1) < O(logn) <O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

3.算法分析法则及其他渐进符号

①一般法则
法则1：（循环结构，时间复杂度按乘法进行计算）
for循环：假设循环体时间复杂度为O(n)，循环次数为m，则时间复杂度为O(nm)
法则2：（循环结构，时间复杂度按乘法进行计算）
嵌套的for循环：O(nm*p)
法则3：（顺序结构，时间复杂度按加法进行计算）
顺序语句：第一个循环为O(n)，第二个循环为O(n^{2)，则求和（取较大值），即O(n}2)
法则4：（分支结构，时间复杂度取最大值）
if-else语句：类比法则3

②3个概念
最优、平均、最坏时间复杂度
算法完成工作最少需要多少基本操作，即最优时间复杂度 --- 其价值不大
算法完成工作最多需要多少基本操作，即最坏时间复杂度（**） --- 提供了一种保证，表名算法在此中程度的基本操作中一定能完成工作
算法完成工作平均需要多少基本操作，即平均时间复杂度

③其他渐进符号

例题：
快速排序的平均时间复杂度和最坏时间复杂度是?
O(nlgn) , O(n^2)
平均复杂度相当于目标index在中间，类似二分法，最坏情况，每次从头到尾遍历整个数组

4.二分法查找（折半查找）

就是一种在有序数组中查找某一特定元素的搜素算法

先决条件：有序数组

主要思想是:(设查找的数组区间为array[low, high])
(1)确定该区间的中间位置K(2)将查找的值T与array[k]比较。若相等，查找成功返回此位置;否则确定新的查找区域，继续二分查找。

最坏/平均时间复杂度：O(logn)
最优时间/空间复杂度：O(1)

def binary_search(arr,key):
    start = 0
    end = len(arr) - 1
    while start <= end:
        mid=(start+end)//2
        if arr[mid]<key:
            start = mid + 1
        elif arr[mid] > key:
            end = mid - 1
        else:
            return mid
    return -1

alist = [12, 21, 24, 32, 39, 43, 67, 90]
print(binary_search(alist, 39))

5.数组和链表

在内存中，数组是一块连续的区域。
在使用前需要提前申请所占内存的大小，这样不知道需要多大的空间，就预先申请可能会浪费内存空间，即数组空间利用率低
插入数据时，待插入位置的的元素和它后面的所有元素都需要向后搬移
删除数据时，待删除位置后面的所有元素都需要向前搬移
因为数组的内存是连续的，想要访问那个元素，直接从数组的首地址处向后偏移就可以访问到了，类比网络电视可以选集播放

在内存中，链表元素的空间可以在任意地方，空间是分散的，不需要连续
链表中的元素都会两个属性，一个是元素的值，另一个是指针，此指针标记了下一个元素的地址
每一个数据都会保存下一个数据的内存的地址，通过此地址可以找到下一个数据
因为链表的空间是分散的，所以不具有随机访问性，如要需要访问某个位置的数据，需要从第一个数据开始找起，依次往后遍历，直到找到待查询的位置，故可能在查找某个元素时，时间复杂度达到O(N)，类比有限电视可以顺序播放
任意位置插入元素和删除元素效率较高，时间复杂度为O(1)

操作                        链表                       数组
查找                        O(n)                       O(1)
在头部插入/删除              O(1)                       O(n)
在尾部插入/删除              O(n)                       O(1)                
在中间插入/删除              O(n)                       O(n)

当插入删除很少，查询非常多，采用数组
当频繁的插入，遍历，查询检索很少，采用链表

6.顺序表和链表

线性表是最基本、最简单、也是最常用的一种数据结构。主要由顺序表示或链式表示，即包括顺序表和链表。在实际应用中，常以栈、队列、字符串等特殊形式使用。

数组的元素的位置称之为索引。通过索引可以引用数组，类比python中的应用

顺序表和链表的比较：

1. 顺序表可以顺序存取，也支持随机存取；链表只能顺序存取。
2. 顺序表逻辑上相邻的物理上也相邻；而链表不一定，它是用指针来描述元素之间的关系。
3. 顺序表插入和删除要移动大量元素；链表只需修改指针即可

7.栈和队列

栈是一端受限，一段允许进行操作的线性表。理解成一个装书的盒子。放书，取书，就是进行的操作。这个的特点就是，你放了一踏书，现在你想取书，你只能先把上面的书一个个取出来，即：先放的后取，后放的先取。放在栈上说，就是先进后出。
队列：是一种限定性的线性表。这样理解比较好，学生排队买饭。有什么特点呢？当然，你先来，就先打饭，先吃饭。抽象到队列上说，有队头，队尾，要想加入（入队），只能从队尾加，想走（出队），只能从队头走。即：先进先出。

8.二叉排序树：

满足的性质：
1）若他的左子树不空，则左子树上所有的节点的值均小于根节点的值
2）若他的右子树不空，则右子树上所有的节点的值均大于根节点的值
3）他的左子树和右子树也分别是一颗二叉排序树。
4）对于二叉排序树的中序遍历得到一个递增序列

二叉排序树的查找：
1）若给定的值等于根节点的值，则查找成功
2）若给定的值小于根节点值，则继续在左子树上查找
3）若给定的值大于根节点的值，则继续在右子树上进行查找

9.二叉树（前、中、后、层序遍历）

二叉树的遍历：是指从根节点出发，按照某种次序依次访问二叉树中的所有节点，使得每个节点被访问一次且仅被访问一次。
（这里的前中后是指的根节点的遍历次序）
1）前序遍历（DLR），根-左-右

2）中序遍历（LDR），左-根-右

3）后序遍历（LRD），左-右-根

4）层序遍历：从根节点出发，依次访问左右孩子结点，再从左右孩子出发，依次它们的孩子结点，直到节点访问完毕

10、二叉树的计算相关定义

①二叉树的深度定义为：从根节点到叶子结点依次经过的结点形成树的一条路径,最长路径的长度为树的深度。
1）如果根节点为空，则深度为0；
2）如果左右节点都是空，则深度为1；
3）递归思想：二叉树的深度=max（左子树的深度，右子树的深度）+ 1

深度是从根节点数到它的叶节点，高度是从叶节点数到它的根节点。
二叉树的深度是从根节点开始（其深度为1）自顶向下逐层累加的；而二叉树高度是从叶节点开始（其高度为1）自底向上逐层累加的。

②二叉树的宽度定义为：各层节点数的最大值。

③二叉树所有节点数=左子树节点数+右子树节点数+1

④二叉树某层中的节点数
1）根节点为空，则节点数为0；
2）层为1，则节点数为1（即根节点）
3）递归思想：二叉树第k层节点数=左子树第k-1层节点数+右子树第k-1层节点数

⑤二叉树叶子节点数
叶子节点，又叫终端节点，是左右子树都是空的节点。

⑥二叉树最大距离（二叉树的直径）
二叉树中任意两个节点都有且仅有一条路径，这个路径的长度叫这两个节点的距离。二叉树中所有节点之间的距离的最大值就是二叉树的直径。
有一种解法，把这个最大距离划分了3种情况：
1）这2个节点分别在根节点的左子树和右子树上，他们之间的路径肯定经过根节点，而且他们肯定是根节点左右子树上最远的叶子节点（他们到根节点的距离=左右子树的深度）。
2）这2个节点都在左子树上
3）这2个节点都在右子树上
综上，只要取这3种情况中的最大值，就是二叉树的直径。

⑦翻转二叉树
翻转二叉树，又叫求二叉树的镜像，就是把二叉树的左右子树对调（当然是递归的）

⑧判断二叉树是否完全二叉树
完全二叉树定义为：若设二叉树的高度为h，除第h层外，其它各层的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布。
完全二叉树必须满足2个条件：
1）如果某个节点的右子树不为空，则它的左子树必须不为空
2）如果某个节点的右子树为空，则排在它后面的节点必须没有孩子节点

⑨ 判断二叉树是否满二叉树
满二叉树定义为：除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树
满二叉树的一个特性是：叶子数=2^(深度-1)，因此我们可以根据这个特性来判断二叉树是否是满二叉树。

⑩判断二叉树是否平衡二叉树
平衡二叉树定义为：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树又叫AVL树。

注：
节点的度：节点拥有的子树的个数，度为0的节点称之为叶子节点
树的度：是树内所有节点度的最大值
树的深度：树内所有节点深度的最大值，也就是所有叶子节点深度的最大值，也就是树的层数
树的高度：树内所有节点高度的最大值，也就是根节点的高度，也就是数的层数

11、二叉树的计算

假定树根的高度为0，则高度为6的二叉树最多有_______个叶节点。
答：64
一棵树当中没有子结点（即度为0）的结点称为叶子结点。所以2^6=64

已知一棵树具有10个节点，且度为4，那么：
答：该树的高度至多是7
树的高度：从所有叶节点开始数高度到根节点，其中的最大值；也就是从结点x向下到某个叶结点最长简单路径中边的条数。
树的深度：树根下中所有分支结点层数的最大值，递归定义。（一般以根节点深度层数为0）

对于以下关键字{55，26，33，80，70，90，6，30，40，20}，增量取5的希尔排序的第一趟的结果是：
答：55，6，30，40，20，90，26，33，80，70
{55，26，33，80，70，90，6，30，40，20} 增量为5， 从55开始每隔5个距离取值分为1组，共分为5组，
分别为{55，90} {26,6}{33,30}{80,40}{70,20}
先组内排序取最小值：55，6，30，40，20，
后取剩余值：90，26，33，80，70

设二叉排序树中关键字由1到999的整数构成，现要查找关键字为321的节点，下面关键字序列中，不可能出现在二叉排序树上的查找序列是：
答：888、231、911、244、898、256、362、366
2、252、400 、398、300、344、310、321；888、200、666、240、312、330、321；2、398、387、219、266、283、298、321
二叉排序树的特点就是
若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值
若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值
左、右子树也分别为二叉排序树
看B选项的最后两个数，321 和 362 比较以后，明显321< 362 ，必然会去寻找362的左子树，此时应该去寻找362的左子树，但是366大于362肯定不是左子树
二叉排序树的算法就是
首先将待查关键字key与根节点关键字t进行比较：
a.如果key = t, 则返回根节点指针。
b.如果key < t,则进一步查找左子书。
c.如果key > t,则进一步查找右子树。

12.

1、一般二叉树的性质
性质1、在非空二叉树的i层上，至多有2^i个结点。
性质2、高度为K的二叉树中，最多有2^(k+1)-1个结点。
性质3、对于任何一棵非空的二叉树，如果叶结点的个数为n0，度为2的结点个数为n2，则有n0=n2+1。
2、完全二叉树
定义：如果一棵二叉树中，只有最下面的两层结点度数小于2，其余各层结点度数都等于2，并且最下面一层的结点，都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。
性质1、具有n个结点的完全二叉树的高度k为[log^2n]。
性质2、对于具有n个结点的完全二叉树，如果按照从上（根结点）到下(叶结点)和从左到右的顺序对二叉树中的所有结点从0开始到n-1进行编号，则对于任意的下标为i的结点，有：
（1）如果i=0，则它是根结点，它没有父结点；如果i>0,则它的父结点的下标为（i-1）/2。
（2）如果2i+1<=n-1，则下标为i的结点的左子结点的下标为2i+1；否则，下标为i的结点没有左子结点。
（3）如果2i+2<=n-1，则下标为i的结点的右子结点的下标为2i+2；否则，下标为i的结点没有右子结点。
3、满二叉树
定义：如果一棵二叉的任何结点或者是树叶，或有两棵非空子树，则此二叉树称作满二叉树。
性质、在满二叉树中，叶结点的个数比分支结点个数多1。
4、扩充二叉树
定义：扩充二叉树是对一个已有二叉树的扩充，扩充后原二叉树的结点都变为度数为2的分支结点。也是就是说，如果原结点的度数为2，则不变；度数为1，则增加一个分支；度数为0，则增加两个分支。
性质1、在扩充二叉树中，外部结点的个数比内部结点的个数多1。
性质2、对任意扩充二叉树，外部路径长度E和内部路径长度I之间满足以下关系：E=I+2n，其中n是内部结点个数。

1.n个节点的二叉树一共有((2n)!)/(n! * (n+1)!)种
2.n层二叉树的第n层最多为2^(n-1)个
3.二叉树节点计算公式 N = n0+n1+n2，度为0的叶子节点比度为2的节点数多一个。N=1n1+2n2+1
4.对任何一棵二叉树T，如果其终端节点数为n0，度为2的节点数为n2，则n0=n2+1
5.具有n个节点的完全二叉树的深度为log2(n) + 1

http://www.360doc.com/content/16/1022/08/37504570_600396077.shtml