第三章算法基础 算法算法的特性有穷性：执行有穷步之后结束，且每一步都可在有穷时间内完成。确定性（无二义性）：算法中每一条指令都必须有确切的含义，不能含糊不清。输入(>=0)即可以没有输入。输出(>=1)即必须有输出。有效性(可行性)：算法的每个步骤都能有效执行并能在执行有限次后得到确定的结果。例如a=0，b/a就无效。时间复杂度与空间复杂度时间复杂度    时间复杂度是指程序运行从开始到结束所需要的时间。    通常分析时间复杂度的方法是从算法中选取一种对于所研究的问题来说是基本运算的操作，以该操作重复执行的次数作为算法的时间度量。一般来说，算法中原操作重复执行的次数是规模n的某个函数T(n)。由于许多情况下要精确计算T(n)是困难的，因此引入了渐进时间复杂度在数量上估计一个算法的执行时间。其定义如下：    如果存在两个常数c和m，对于所有的n，当n≥m时有f(n)≤cg(n)，则有f(n)=O(g(n))。也就是说，随着n的增大，f(n)渐进地不大于g(n)。例如，一个程序的实际执行时间为T(n)=3n3+2n2+n，则T(n)=o(n3)    常见的对算法执行所需时间的度量:O(1) < O(log2n) < O(n) < O(nlog2n) < O(n2) < 0(n3) < 0(2n)空间复杂度    空间复杂度是指对一个算法在运行过程中临时占用存储空间大小的度量。一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小。时间复杂度O(1)单条语句k = 1;整个程序都没有循环语句，或复杂函数的调用void main(){ char *x = "ABCADAB"; int m = strlen(x); printf("len:%d\n",m);时间复杂度O(n)单层循环void main() { int i,j; k = 0; for(i = 0;i < n; i++){ b[i]=0; } }时间复杂度O(n2)双层循环void main() { int i,s = 0, n = 1000; for(i = 1;i < n; i++){ for(j = 1;j < n; j++) s+=j printf("结果为:%d",s); }由此可知时间复杂度O(n3)则为三层循环时间复杂度O(log2n)常为二分、二叉树等int search (int array[], int n, int v) int left, right, middle; left=0,right=n - 1; while(left <= right ){ middle=(left + right) / 2; if(array[middle] > v){ right=middle-1; } else if (array[middle] < v){ left=middle+1; } else{ return middle ; } } return-1; }时间复杂度O(nlog2n)典型代表：堆排序，每次重建堆的时间复杂度是log2n，n个元素基本上就是nlog2n。时间复杂度O(2n)典型代表：LCS最长公共子序列、钢管切割问题，动态规划法自顶向下，时间复杂度为O(2n)。常见算法策略算法策略概述一、分治法特征：把一个问题拆分成多个小规模的相同子问题，一般可用递归解决。经典问题：斐波那契数列、归并排序、快速排序、矩阵乘法、二分搜素、大整数乘法、汉诺塔二、贪心法（一般用于求满意解）特征：局部最优，但整体不见得最优。每步有明确的，既定的策略。经典问题：背包问题（如装箱）、多机调度、找零钱问题三、动态规划法（用于求最优解）--“最优子结构”和递归式特征：划分子问题，并把子问题结果使用数组存储，利用查询子问题结果构造最终问题结果。（一般自顶向下时间复杂度为O(2n),自底向上时间复杂度为O(n2)效率更高）经典问题：斐波那契数列、矩阵乘法、背包问题、LCS最长公共子序列四、回溯法特征：系统的搜索一个问题的所有解或任一解。经典问题：N皇后问题、迷宫、背包问题常见算法总结算法名称关键点特征典型问题分治法递归技术把一个问题拆分成多个小规模的相同子问题，一般可用递归解决。归并排序、快速排序、二分搜素贪心法一般用于求满意解，特殊情况可求最优解（部分背包）局部最优，但整体不见得最优。每步有明确的，既定的策略。背包问题（如装箱）、多机调度、找零钱问题动态规划法最优子结构和递归式、中间解数组划分子问题（最优子结构），并把子问题结果使用数组存储，利用查询子问题结果构造最终问题结果。矩阵乘法、背包问题、LCS最长公共子序列回溯法探索和回退系统的搜索一个问题的所有解或任一解。有试探和回退的过程。N皇后问题、迷宫、背包问题算法策略判断：回溯，大家比较熟悉，有尝试探索和回退的过程。这个比较好识别。分治，分治与动态规划法其实最难区分，分治不好解决问题，从而记录中间解、解决问题，有了动态规划法，但是在软设考试中，分治目前只有二分的思想，二分以外的思想都用动态规划法解决了。二分的时间复杂度，与O(nlog2n)相关，注意有没有外层嵌套循环。（结合归并排序、快速排序的过程，也是二分的）动态规划法，有递归式，经常考查递归式，此时自底向上实现时，中间解基本上是查表可得的，所以时间复杂度一般是O(n^k),具体k是多少，根据for循环的嵌套。此时循环变量能够看到，是从0或1开始，到n结束，这种情况就是从小规模到大规模，自底向上的。如果用到自顶向下，其实跟分治的实现就差不多了，查表的意义基本上可以忽略不计了，时间复杂度为O(2^n),递归的变量一般由开始，向1缩小，所以是大规模到小规模，也就是自顶向下的。（一般动态规划法涉及递归式，递归式还会经常用在代码填空中让大家补充缺失的填空，然后会有“最优子结构”的描述，会有表（数组）记录中间解。）贪心法，有时候也会出现“最优子结构”的描述，但是没有递归式。考虑的当前最优，求得的是满意解。（特殊情况下，贪心法有时候得到的也可以是最优解，比如部分背包问题）分治法    对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决；否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。递归// 斐波拉契数列 int F(int n) { if(n==0)return 1; if(n==1)return 1; if(n>1) return F(n-1)+F(n-2); }二分function Binary_Search(L,a,b,x){ if(a>b) return(-1); else{ m=(a+b)/2; if(x==L[m]) return(m); else if(x>L[m]) return(Binary_Search(L,m+1,b,x); else return(Binary_Search(L,a,m-1,x)); } }贪心法    总是做出在当前来说是最好的选择，而并不从整体上加以考虑，它所做的每步选择只是当前步骤的局部最优选择，但从整体来说不一定是最优的选择。由于它不必为了寻找最优解而穷尽所有可能解，因此其耗费时间少，一般可以快速得到满意的解，但可能得不到最优解。【贪心法解决部分背包问题可得最优解】动态规划法    在求解问题中，对于每一步决策，列出各种可能的局部解，再依据某种判定条件舍弃那些肯定不能得到最优解的局部解，在每一步都经过筛选，以每一步都是最优解来保证全局是最优解。（问题中如果出现“最优子结构”这类描述，并且结果用递归式表示，一般为动态规划法）回溯法    回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当搜索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择。这种走不通就退回再走的技术就是回溯法。试探部分：满足除规模之外的所有条件，则扩大规模。（扩大规模）回溯部分：（缩小规模）当前规模解不是合法解时回溯（不满足约束条件D）。求完一个解，要求下一个解时，也要回溯。查找算法顺序查找    顺序查找的思想：将待查找的关键字为key的元素从头到尾与表中元素进行比较，如果中间存在关键字为key的元素，则返回成功；否则，则查找失败。查找成功时，顺序查找的平均查找长度为（等概率情况下）：二分查找二分法查找的基本思想是：(设R[low,...,high]是当前的查找区)(1) 确定该区间的中点位置：mid=[(low+thigh)/2]；(2) 将待查的k值与R[mid].key比较，若相等，则查找成功并返回此位置，否则需确定新的查找区间，继续二分查找，具体方法如下：若R[mid].key>k，则由表的有序性可知R[mid,…,n].key均大于k，因此若表中存在关键字等于k的结点，则该结点必定是在位置mid左边的子表R[low,…,mid-1]中。因此，新的查找区间是左子表R[low,…, high]，其中high=mid-1。若R[mid].key<k，则要查找的k必在mid的右子表R[mid+1,…,high]中，即新的查找区间是右子表R[low,…,high]，其中low=mid+1。若R[mid].key=k，则查找成功，算法结束。(3) 下一次查找是针对新的查找区间进行，重复步骤(1)和(2)。(4) 在查找过程中，low逐步增加，而high逐步减少。如果 high<low，则查找失败，算法结束。折半查找在查找成功时关键字的比较次数最多为log2n+1次。折半查找的时间复杂度为O(log2n)次。折半查找的前提：有序顺序存储。哈希散列表    散列表查找的基本思想是：已知关键字集合U，最大关键字为m，设计一个函数Hash，它以关键字为自变量，关键字的存储地址为因变量，将关键字映射到一个有限的、地址连续的区间T[0...n-1]（n<<m）中，这个区间就称为散列表，散列查找中使用的转换函数称为散列函数。例:记录关键码为(3,8,12,17,9)，取m=10(存储空间为10)，p=5，散列函数h=key%p。    开放定址法是指当构造散列表发生冲突时，使用某种探测手段，产生一个探测的散列地址序列，并且逐个查找此地址中是否存储了数据元素，如果没有，则称该散列地址开放，并将关键字存入，否则继续查找下一个地址。只要散列表足够大，总能找到空的散列地址将数据元素存入。排序算法插入类排序直接插入排序    即当插入第i个记录时，R1，R2，…，R1均已排好序，因此，将第个记录R依次与R1，…，R2，R1进行比较，找到合适的位置插入。它简单明了，但速度很慢。    直接插入排序是一种稳定的排序方法，时间复杂度为O(n2)。在排序过程中仅需要一个元素的辅助空间，空间复杂度为O(1)。    适用于基本有序的情况，此时时间复杂度近乎线性，即O(n)。希尔排序    先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2 < d1重复上述的分组和排序，直至所取的增量d1=1(dt < dt-1 < O <> d2 < d1 )，即所有记录放在同组中进行直接插入排序为止。该方法实质上是一种分组插入方法。    希尔排序是一种不稳定的排序方法，据统计分析其时间复杂度约为O(n1.3)。在排序过程中仅需要一个元素的辅助空间用于数组元素的交互，空间复杂度为O(1)。选择类排序直接选择排序    直接选择排序的过程是，首先在所有记录中选出排序码最小的记录，把它与第1个记录交换，然后在其余的记录内选出排序码最小的记录，与第2个记录交换……依次类推，直到所有记录排完为止。    直接选择排序是一种不稳定的排序方法，其时间复杂度约为O(n2)。在排序过程中仅需要一个元素的辅助空间用于数组元素的交互，空间复杂度为O(1)。堆排序    堆排序的基本思想为：先将序列建立堆，然后输出堆顶元素，再将剩下的序列建立堆，然后再输出堆顶元素，依此类推，直到所有元素均输出为止，此时元素输出的序列就是一个有序序列。    对于大量的记录来说，堆排序是很有效的。    堆排序的算法步骤如下（以大顶堆为例）:初始时将顺序表R[1...n]中元素建立为一个大顶堆，堆顶位于R[1],待序区为R[1...n]。循环执行步骤3~步骤4，共n-1次。假设为第i运行，则待序区为R[1..n-i+1]，将堆顶元素R[1]与待序区尾元素R[n-i+1]交换，此时顶点元素被输出，新的待序区为R[1...n-i]。待序区对应的堆已经被破坏，将之重新调整为大顶堆。    堆排序的时间复杂度为O(nlog2n)，空间复杂度为O(1)。交换类排序冒泡排序    冒泡排序的基本思想是，通过相邻元素之间的比较和交换，将排 序码较小的元素逐渐从底部移向顶部。由于整个排序的过程就像水底 下的气泡一样逐渐向上冒，因此称为冒泡算法。    冒泡排序是一种稳定的排序方法，其时间复杂度约为O(n2)。在排序过程中仅需要一个元素的辅助空间用于数组元素的交互，空间复杂度为O(1)。快速排序    快速排序采用的是分治法，其基本思想是将原问题分解成若干个规模更小但结构与原问题相似的子问题。通过递归地解决这些子问题，然后再将这些子问题的解组合成原问题的解。    在 O(nlog2n) 时间量级上，平均性能最好。    快速排序通常包括两个步骤：    第一步，在待排序的n个记录中任取一个记录，以该记录的排序码为准，将所有记录都分成两组，第1组都小于该数，第2组都大于该数，如图所示。    第二步，采用相同的方法对左、右两组分别进行排序，直到所有记录都排到相应的位置为止。    快速排序的基准元素：一般是第一个元素，也可以设置中位数。    快速排序是一种不稳定的排序方法，平均和最优情况下时间复杂度约为O(log2n)。快速排序的最差情况-基本有序以第一个元素为基准元素，此时时间复杂度为O(n2)。以中位数为基准元素，此时时间复杂度为O(log2n)。辅助空间(1)需要辅助空间存储左侧数组和右侧数组时，空间复杂度为O(n)。(2)需要记录所有基准元素时，空间复杂度度为O(log2n)。归并排序    归并也称为合并，是将两个或两个以上的有序子表合并成一个新的有序表。若将两个有序表合并成一个有序表，则称为二路合并。合并的过程是：比较A[i]和A[j]的排序码大小，若A[i]的排序码小于等于A[j]的排序码，则将第一个有序表中的元素A[i]复制到R[k]中，并令i和k分别加1；如此循环下去，直到其中一个有序表比较和复制完，然后再将另一个有序表的剩余元素复制到R中。    归并排序是一种稳定的排序方法，其时间复杂度约为O(nlog2n)。在排序过程中仅需要一个元素的辅助空间用于数组元素的交互，空间复杂度为O(n)。基数排序    基数排序是一种借助多关键字排序思想对单逻辑关键字进行排序的方法。基数排序不是基于关键字比较的排序方法，它适合于元素很多而关键字较少的序列。基数的选择和关键字的分解是根据关键字的类型来决定的，例如关键字是十进制数，则按个位、十位来分解。    基数排序是一种稳定的排序方法，其时间复杂度约为O(d(n+rd))。在排序过程中仅需要一个元素的辅助空间用于数组元素的交互，空间复杂度为O(rd)。排序算法对比 类别 排序方法 时间复杂度 空间复杂度 稳定性 平均情况 特殊情况 辅助存储 插入排序 直接插入 O(n2) 基本有序最优O(n) O(1) 稳定 Shell排序 O(n1.3) - O(1) 不稳定 选择排序 直接选择 O(n2) - O(1) 不稳定 堆排序 O(nlog2n) - O(1) 不稳定 交换排序 冒泡排序 O(n2) - O(1) 稳定 快速排序 O(nlog2n) 基本有序最差O(n2) O(log2n) 不稳定 归并排序 O(nlog2n) - O(n) 稳定 基数排序 O(d(n+rd)) - O(rd) 稳定     在选取排序方法时需要考虑的因素有待排序的记录个数n、记录本身的大小、关键字的分布情况、对排序稳定性的要求、语言工具的条件和辅助空间的大小。据这些因素，可以得到以下几点结论：若待排序列的记录数目n较小，可采用直接插入排序和简单选择排序。由于直接插入排序所需的记录移动操作较简单选择排序多，因而当记录本身信息量大时用简单选择排序方法较好。若待排记录按关键字基本有序，宜采用直接插入排序或冒泡排序。当n很大且关键字位数较少时，采用基数排序较好。若n很大，则应采用时间复杂度为0(nlog2n)的排序方法，例如快速排序、堆排序或归并排序：(1)快速排序目前被认为是内部排序中最好的方法，当待排序的关键字为随机分布时，快速排序的平均运行时间最短；(2)堆排序只需要一个辅助空间，并且不会出现在快速排序中可能出现的最快情况。(3)快速排序和堆排序都是不稳定的排序方法，若要求排序稳定，可选择归并排序。