算法

• 算法： 算法是指解题方案的准确而完整的描述，是一系列解决问腿的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。
• 算法的效率： 是指算法执行的时间，算法执行时间需要通过算法编制的程序在计算机上运行时所消耗的时间来衡量。
• 一个算法的优劣可以用空间复杂度和时间复杂度来衡量
  
  

时间复杂度

• 时间复杂度：
  在代码编程中指的是要测量的代码在运行中会执行多少个步骤。步骤越少，肯定执行的效率越高。用一些算法函数来表示，它定性描述该算法的运行时间。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。相同大小的不同输入值仍可能造成算法的运行时间不同，因此我们通常使用算法的最坏情况复杂度，记为T(n)，定义为任何大小的输入n所需的最大运行时间。
  一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f (n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。(大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势)。

在长度为n的数组中，代码执行步骤大小指数为：
直接通过下标去访问元素，时间复杂度为O(1)。
需要遍历查找元素的时候，时间复杂度为O(n)。
需要遍历二维数组的时候，时间复杂度为O(n²)。

以此类推按数量级递增排列，常见的时间复杂度有：
- 常数阶O(1)：无论问题规模多大执行时间不变.(hashMap.get)
- 对数阶O(log2n)：将一个数据集分成两半,然后将分开的每一半再分成两半（二叉树）
- 线性阶O(n)：执行时间随问题规模增长呈正比例增长(遍历算法)
- 线性对数阶O(nlog2n)：可以看成n乘以logn：将一个数据集分成两半,然后将分开的每一半再分成两半,依此类推,在此过程中同时遍历每一半数据，以归并排序为例，可以把排序的过程看成一个倒立的二叉树。这个复杂度高于线性低于平方。归并排序就是O(nlogn)的时间复杂度。
- 平方阶O(n^2)：O(n^ 2)，就代表数据量增大n倍时，耗时增大n的平方倍，这是比线性更高的时间复杂度。比如冒泡排序，就是典型的O(n^2)的算法，对n个数排序，需要扫描n×n次。
- 立方阶O(n^3)：n的立方
- n次方阶O(n^n)：n的n次方
- 指数阶O(2^n)： 2^n=2*2*2*……*2 (n有2个)
- O(n!)：       n!=1*2*3*4*……*n(n个数字)
随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

大O阶推导
推导大O阶就是将算法的所有步骤转换为代数项，然后排除不会对问题的整体复杂度产生较大影响的较低阶常数和系数。
有条理的说，推导大O阶，按照下面的三个规则来推导，得到的结果就是大O表示法：
运行时间中所有的加减法常数用常数1代替
只保留最高阶项
去除最高项常数

• 大O表示法O(f(n)中的f(n)的值可以为1、n、logn、n²等，因此我们可以将O(1)、O(n)、O(logn)、O(n²)分别可以称为常数阶、线性阶、对数阶和平方阶
• T(n) =O(n) 的算法被称作“线性时间算法”,例如有O(n)葛罗佛搜索算法。
• T(n) =O(M^n) 和M= O(T(n)) ，其中M≥n> 1 的算法被称作“指数时间算法”
• T(n) =O(logn)，则称其具有对数时间。常见的具有对数时间的算法有二叉树的相关操作和二分搜索。
• T(n) = O((logn))，则称其具有幂对数时间。例如，矩阵链排序可以通过一个PRAM模型.被在幂对数时间内解决。

那么如何推导出f(n)的值呢？推导大O阶，我们可以按照如下的规则来进行推导，得到的结果就是大O表示法

------------------------------------------------------------intdo(void){printf("xxx");//  需要执行 1 次return0;// 需要执行 1 次}
这个方法需要执行2次运算,该函数(算法)的时间复杂度为O(n)。常系数2省略------------------------------------------------------------intdo(int n){for(int i=0; i<n; i++){// 需要执行 (n + 1) 次printf("xxx");// 需要执行 n 次}return0;// 需要执行 1 次}
这个方法需要(n+1+n+1)=2n+2 次运算。,该函数(算法)的时间复杂度也为O(n)。------------------------------------------------------------

我们把 算法需要执行的运算次数用输入大小n 的函数 表示，即 T(n) 。
此时为了 估算算法需要的运行时间 和 简化算法分析，我们引入时间复杂度的概念。
定义：存在常数 c 和函数 f(N)，使得当 N >= c 时 T(N) <= f(N)，表示为 T(n) = O(f(n)) ，如图：

当 N >= 2 的时候，f(n) = n^2 总是大于 T(n) = n + 2 的，于是我们说 f(n) 的增长速度是大于或者等于 T(n) 的，也说 f(n) 是 T(n) 的上界，可以表示为 T(n) = O(f(n))。

因为f(n) 的增长速度是大于或者等于 T(n) 的，即T(n) = O(f(n))，所以我们可以用 f(n) 的增长速度来度量 T(n) 的增长速度，所以我们说这个算法的时间复杂度是 O(f(n))。

算法的时间复杂度，用来度量算法的运行时间，记作: T(n) = O(f(n))。它表示随着 输入大小n 的增大，算法执行需要的时间的增长速度可以用 f(n) 来描述。
显然如果 T(n) = n^2，那么 T(n) = O(n^2)，T(n) = O(n^3)，T(n) = O(n^4) 都是成立的，但是因为第一个 f(n) 的增长速度与 T(n) 是最接近的，所以第一个是最好的选择，所以我们说这个算法的复杂度是 O(n^2) 。

• 常数项对函数的增长速度影响并不大，所以当 T(n) = c，c 为一个常数的时候，我们说这个算法的时间复杂度为 O(1)；如果 T(n) 不等于一个常数项时，直接将常数项省略
• 高次项对于函数的增长速度的影响是最大的。n^3 的增长速度是远超 n^2 的，同时 n^2 的增长速度是远超 n 的。 同时因为要求的精度不高，所以我们直接忽略低此项。
• 因为函数的阶数对函数的增长速度的影响是最显著的，所以我们忽略与最高阶相乘的常数。
  1.用常数1来取代运行时间中所有加法常数。
  2.修改后的运行次数函数中，只保留最高阶项
  3.如果最高阶项存在且不是1，则去除与这个项相乘的常数。
  综合起来：如果一个算法的执行次数是 T(n)，那么只保留最高次项，同时忽略最高项的系数后得到函数 f(n)，此时算法的时间复杂度就是 O(f(n))，称此为 大O推导法。

O后面的括号中的函数，指明的是某个算法的耗时/耗空间与数据增长量之间的关系。
其中的n代表输入数据的量(排序则为数组的长度)。代码演示如下：

------------------------------------------------------------
let sum=0,
    n=100;// 执行一次
sum=(1+n)*n/2;// 执行一次
console.log(sum);// 执行一次
上面算法的运行次数的函数是f(n)=3，则有O(f(n)=3)即O(3)，
常数项用常数1表示，则最终的表示法为==O(1)常数阶==
常数阶：最低的时空复杂度，也就是耗时与输入数据大小无关，
无论输入数据增大多少倍，耗时/耗空间都不变。 哈希算法就是
典型的O(1)时间复杂度，无论数据规模多大，都可以在一次计算后找到目标。------------------------------------------------------------intbinarySearch(int a[],int key){int low=0;int high= a.length-1;while(low<= high){int mid= low+(high- low)/2;if(a[mid]> key)
            high= mid-1;elseif(a[mid]< key)
            low= mid+1;elsereturn mid;}return-1;}
数组a每次都是对半查找，则mid=log₂n，通过mid下表再对半查找，
因此得到这个算法的时间复杂度为==O(logn)对数阶，也叫O(log2n)==
对数阶：当数据增大n倍时，耗时增大logn倍，二分查找就是O(logn)的算法，
每找一次排除一半的可能，256个数据中查找只要找8次就可以找到目标。
（这里的log是以2为底的，比如，当数据增大256倍时，耗时只增大8倍，
是比线性还要低的时间复杂度）。------------------------------------------------------------
String str[]={"","xx","xxx"}；for(String string:str){if(string.equal("xx""){return string;}
此时时间复杂度为O(n ×1)，即==O(n)线性阶==
线性阶：就代表数据量增大几倍，复杂度也增大几倍
例如当前数组长度为3，则为O(3),当数组长6时，则为O(6),复杂度增长一倍------------------------------------------------------------publicvoidmergeSort(int[] arr,int p,int q){if(p>= q){return};int mid=(p+q)/2;mergeSort(arr, p, mid);mergeSort(arr, mid+1,q);merge(arr, p, mid, q);}privatevoidmerge(int[] arr,int p,int mid,int q){int[] temp=newint[arr.length];int i= p, j= mid+1，iter= p;while(i<= mid&& j<= q){if(arr[i]<= arr[j]){
			temp[iter++]= arr[i++]；}else{
			temp[iter++]= arr[j++];}}while(i<= mid){
		temp[iter++]= arr[i++];}while(j<= q){
 		temp[iter++]= arr[j++];}for(int t= p; t<= q; t++){
		arr[t]= temp[t];}}
时间复杂度O(nlogn)—线性对数阶，就是n乘以logn，当数据增大256倍时，耗时增大256*8=2048倍。这个复杂度高于线性低于平方。归并排序就是O(nlogn)的时间复杂度。------------------------------------------------------------voiddo(int n){for(int i=0; i< n; i++){// 循环次数为 nfor(int j=0; j< n; j++){// 循环次数为 nprintf("xxx");// 循环体时间复杂度为 O(1)}}}
此时时间复杂度为O(n × n ×1)，即==O(n^2)平方阶==
时间复杂度O(n^2)—平方阶, 就代表数据量增大n倍时，耗时增大n的平方倍，
这是比线性更高的时间复杂度。比如冒泡排序，就是典型的O(n x n)的算法，
对n个数排序，需要扫描n x n次------------------------------------------------------------voiddo(int n){// 第一部分时间复杂度为 O(n^2)for(int i=0; i< n; i++){for(int j=0; j< n; j++){printf("xxx");}}// 第二部分时间复杂度为 O(n)for(int j=0; j< n; j++){printf("xxx");}}
此时时间复杂度为max(O(n^2),O(n))，即O(n^2)。取影响最大的复杂度------------------------------------------------------------voiddo(int n){if(n>=0){// 第一条路径时间复杂度为 O(n^2)for(int i=0; i< n; i++){for(int j=0; j< n; j++){printf("输入数据大于等于零\n");}}}else{// 第二条路径时间复杂度为 O(n)for(int j=0; j< n; j++){printf("输入数据小于零\n");}}}
对于条件判断语句，总的时间复杂度等于其中 时间复杂度最大的路径的时间
复杂度，即此时时间复杂度为max(O(n^2),O(n))，即O(n^2)。------------------------------------------------------------
其他常见复杂度f(n)=nlogn时，时间复杂度为O(nlogn)，可以称为nlogn阶。f(n)=n³时，时间复杂度为O(n³)，可以称为立方阶。f(n)=2ⁿ时，时间复杂度为O(2ⁿ)，可以称为指数阶。f(n)=n!时，时间复杂度为O(n!)，可以称为阶乘阶。f(n)=(√n时，时间复杂度为O(√n)，可以称为平方根阶。
效率排序：O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2ⁿ)<O(n!)------------------------------------------------------------

O(n)、O(logn)、O(√n )、O(nlogn )随着n的增加，复杂度提升不大，因此这些复杂度属于效率高的算法，反观O(2ⁿ)和O(n!)当n增加到50时，复杂度就突破十位数了，这种效率极差的复杂度最好不要出现在程序中，因此在动手编程时要评估所写算法的最坏情况的复杂度。

空间复杂度

时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长得有多快。

一个程序的空间复杂度是指运行完一个程序所需内存的大小。利用程序的空间复杂度，可以对程序的运行所需要的内存多少有个预先估计。一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。程序执行时所需存储空间包括以下两部分。　　
（1）固定部分。这部分空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等所占的空间。这部分属于静态空间。
（2）可变空间，这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等。这部分的空间大小与算法有关。
一个算法所需的存储空间用f(n)表示。S(n)=O(f(n))　　其中n为问题的规模，S(n)表示空间复杂度。

算法的空间复杂度并不是计算实际占用的空间，而是计算整个算法的辅助空间单元的个数，与问题的规模没有关系。算法的空间复杂度S(n)定义为该算法所耗费空间的数量级。
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度，同样反映的是一个趋势，我们用 S(n) 来定义。
空间复杂度比较常用的有：O(1)、O(n)、O(n²)

S(n)=O(f(n)) 若算法执行时所需要的辅助空间相对于输入数据量n而言是一个常数，则称这个算法的辅助空间为O(1);
递归算法的空间复杂度：递归深度N*每次递归所要的辅助空间， 如果每次递归所需的辅助空间是常数，则递归的空间复杂度是 O(N).

1. 空间复杂度 O(1)
   如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1)

int i=1;int j=2;++i;
j++;int m= i+ j;------------------------------------------------------------------
代码中的 i、j、m 所分配的空间都不随着处理数据量变化，
因此它的空间复杂度S(n)=O(1)

2. 空间复杂度 O(n)

int[] m=newint[n]for(i=1; i<=n;++i){
   j= i;
   j++;}------------------------------------------------------------------
第一行new了一个数组出来，这个数据占用的大小为n，这段代码的2-6行，虽然有循环，
但没有再分配新的空间，因此，这段代码的空间复杂度主要看第一行即可，即S(n)=O(n)

3.空间复杂度：O( log2 N )

template<typename T>
T*BinarySearch(T* left,T* right,const T& data){assert(left);assert(right);if(right>=left){
              T* mid=left+(right-left)/2;if(*mid== data)return mid;else