度量一个程序(算法)执行时间的两种方法：

1) 事后统计的方法
运行比时间，但是有时候运行时间太长，而且依赖硬件

2) 事前估算的方法
通过分析某个算法的时间复杂度来判断哪个算法更优.

算法的时间复杂度

时间频度：
一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为 T(n)。

时间频度有三个可以忽略：
常数项
低次项
高次项的系数（当n的三次方时，曲线分离，但是两者之比会趋向于一个常量，所以也可以忽略）

时间复杂度：
若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n) / f(n) 的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作 T(n)=Ｏ( f(n) )，称Ｏ( f(n) ) 为算法的渐进时间复杂度，简称时间复杂度

常见的算法时间复杂度由小到大依次为：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜ Ο(nk) ＜Ο(2n) ，随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低

平均时间复杂度和最坏时间复杂度：
平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，该算法的运行时间。

空间复杂度

一个算法在运行过程中临时占用存储空间大小的量度。有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元，例如快速排序和归并排序和桶排序算法（快速只用到了递归不占用额外内存空间，而桶排序和归并排序需要new新的数组，所以占用到了内存空间）就属于这种情况

递归

打印问题

递归用于解决什么样的问题

各种数学问题如: 8 皇后问题 , 汉诺塔, 阶乘问题, 迷宫问题, 球和篮子的问题(google 编程大赛)
各种算法中也会使用到递归，比如快排，归并排序，二分查找，分治算法等.
将用栈解决的问题–>递归代码比较简洁

递归需要遵守的重要规则

执行一个方法时，就创建一个新的受保护的独立空间(栈空间)
方法的局部变量是独立的，不会相互影响, 比如 n 变量
如果方法中使用的是引用类型变量(比如数组)，就会共享该引用类型的数据.
递归必须向退出递归的条件逼近，否则就是无限递归,出现 StackOverflowError，死龟了)
当一个方法执行完毕，或者遇到 return，就会返回，遵守谁调用，就将结果返回给谁，同时当方法执行完毕或者返回时，该方法也就执行完毕

八皇后问题（回溯算法）

排序算法

交换排序

冒泡排序O(n^2):

就是前后两两比较，将大的放在后面的位置，第一轮比较好之后，最大的就放在了最后。一共进行数组长度-1次比较。
代码思路，可以先写里面的for循环，在写个大循环包起来，注意条件改下
优化思路就是，如果进行比较就将标识变量置成false，一定不要忘了在下次循环前置回来。

特点:
(1)一共进行数组的大小-1 次大的循环

(2)每一趟排序的次数在逐渐的减少

(3) 如果我们发现在某趟排序中，没有发生一次交换，可以提前结束冒泡排序。这个就是优化

快速排序O(nlogn)

快速排序（Quicksort）是对冒泡排序的一种改进。
基本思想是：通过一趟排序将要排序的数据分割成独立的两
部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

数据大的时候挺快800w两秒

选择排序

从欲排序的数据中按照指定的规则选出某一元素，再依规定交换位置达到排序目的。

简单选择排序O(n^2)

选择排序一共有数组大小 - 1 轮排序
每1轮排序，又是一个循环, 循环的规则(代码)
2.1先假定当前这个数是最小数
2.2 然后和后面的每个数进行比较，如果发现有比当前数更小的数，就重新确定最小数，并得到下标
2.3 当遍历到数组的最后时，就得到本轮最小数和下标
2.4 交换

插入排序

直接插入排序O(n^2)

把 n 个待排序的元素看成为一个有序表和一个无序表，开始时有
序表中只包含一个元素，无序表中包含有 n-1 个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。

希尔排序O(n^2)

直接插入排序可能存在的问题. 数组 arr = {2,3,4,5,6,1} 这时需要插入的数 1(最小），但是1在最后，这样一个个后移，效率低。

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止

归并排序O(nlogn)

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解

一共合并arr.lenth-1次，这里只演示最后一次

合并的时候，就像打擂台。4大于1，把1打下去，加到临时数组里，然后右边的下标往下走，4打2，又比下去，知道一边数组空了，然后将另一个数组剩下的数拷贝到临时数组中。最后拷贝临时数组到原来那个数组中

基数排序(桶排序的扩展)

基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort 或 bin sort），顾名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用。

基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法

基数排序(Radix Sort)是桶排序的扩展

排几轮取决于数组中最大数的位数

好像不能直接排包含0或负数的数组，但是可以通过一些方法，比如同时加上一个数，输出时再减去

思想：
将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

排序算法的比较

查找算法

1) 顺序(线性)查找
2) 二分查找/折半查找
3) 插值查找
4) 斐波那契查找

顺序(线性)查找

给的这个数列可以是有序也可以是无序。

有一个数列： {1,8, 10, 89, 1000, 1234} ，判断数列中是否包含此名称【顺序查找】要求: 如果找到了，就提示找到，并给出下标值

二分查找

递归方式
先排序后查找

把所有相同的数找出来就是加到集合中

非递归方式

非递归参数就不用带着左指引和右指引了

插值查找

上面的二分查找，如果数列是一个比较均匀的数列，比如{1，2，3，4，5，6，7，8}这种，如果你要查1的话，用二分查找就会效率比较低

所以对mid进行优化，自适应查找，上面是left+(right – left) *1/2

这个公式的系数就是所查找数字的位置的长度占总长度的比例，靠左就比例就小。

注意:
对于数据量大，关键字分布比较均匀，插值查找比较块
分布不均匀就不一定了

斐波那契（黄金分割法）查找

斐波那契数列{1，1，2，3，5，8，13，21，34，55}，后面的数是前面两数之和，两个相邻的数的比例无限接近黄金分割值0.618
这种方法可能会对原来数组进行扩容

由斐波那契数列 F[k]=F[k-1]+F[k-2] 的性质，可以得到（F[k]-1）=（F[k-1]-1）+（F[k-2]-1）+1 。该式说明：只要顺序表的长度为F[k]-1，则可以将该表分成长度为F[k-1]-1和F[k-2]-1的两段，即如上图所示。从而中间位置为mid=low+F(k-1)-1
2.
类似的，每一子段也可以用相同的方式分割
3.
但顺序表长度n不一定刚好等于F[k]-1，所以需要将原来的顺序表长度n增加至F[k]-1。这里的k值只要能使得F[k]-1恰好大于或等于n即可，由以下代码得到,顺序表长度增加后，新增的位置（从n+1到F[k]-1位置），都赋为n位置的值即可

斐波那契查找的优点是它只涉及加法和减法运算，而不用除法，而除法比加减法要占用更多的时间

算法