《数据结构时间复杂度总汇.pdf》由会员分享，可在线阅读，更多相关《数据结构时间复杂度总汇.pdf（3页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、(1)冒泡排序冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。(2)选择排序选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的。例子说明好多了。序列 5 8 5 2 9，我们知道第一遍选择第1 个元素 5 会和 2 交换，那么原序列中 2 个 5 的相对前后顺序就被破坏了，所以选择排序不稳定的排序算法。(3)插入排序插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它
2、大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果和插入元素相等，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变。所以插入排序是稳定的。(4)快速排序快速排序有两个方向，左边的i 下标一直往右走（往后），当ai acenter_index。如果 i 和 j 都走不动了，i j。交换 aj和 acenter_index，完成一趟快速排序。在中枢元素和aj交换的时候，很有可能把前面的元素的稳定性打乱，比如序列为 5 3 3 4 3 8 9 10 11，现在中枢元素 5 和 3(第 5 个元素，下标从 1 开始计)交换就会把元素 3 的稳定性打乱，所以快
3、速排序是一个不稳定的排序算法。（不稳定发生在中枢元素和aj交换的时刻）(5)归并排序归并排序是把序列递归地分成短序列，递归出口是短序列只有1 个元素(认为直接有序)或者 2 个序列(1 次比较和交换),然后把各个有序的段序列合并成一个有序的长序列。不断合并直到原序列全部排好序。相等时不发生交换。所以，归并排序也是稳定的排序算法。(6)基数排序基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序，最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以其
4、是稳定的排序算法。(7)希尔排序(shell)希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell 排序是不稳定的。(8)堆排序我们知道堆的结构是节点i 的孩子为 2*i 和 2*i+1 节点，大顶堆要求父节点大于等于其2个子节点，小顶堆要求父节点小
5、于等于其2 个子节点。在一个长为n 的序列，堆排序的过程是从第 n/2 开始和其子节点共 3 个值选择最大(大顶堆)或者最小(小顶堆),这 3 个元素之间的选择当然不会破坏稳定性。但当为n/2-1,n/2-2,.1 这些个父节点选择元素时，就会破坏稳定性。有可能第n/2 个父节点交换把后面一个元素交换过去了，而第n/2-1 个父节点把后面一个相同的元素没有交换，那么这 2 个相同的元素之间的稳定性就被破坏了。所以，堆排序是不稳定的排序算法一、排序排序法 平均时间最差情形稳定度额外空间备注冒泡O(n2)O(n2)稳定O(1)n 小时较好交换O(n2)O(n2)不稳定O(1)n 小时较好选择O(n
6、2)O(n2)不稳定O(1)n 小时较好插入O(n2)O(n2)稳定O(1)大部分已排序时较好ShellO(nlogn)O(ns)1s2 不稳定O(1)s 是所选分组快速O(nlogn)O(n2)不稳定O(nlogn)n 大时较好归并O(nlogn)O(nlogn)稳定O(1)n 大时较好堆O(nlogn)O(nlogn)不稳定O(1)n 大时较好基数O(logRB)O(logRB)稳定O(n)B 是真数(0-9)，R 是基数(个十百)二、查找二分法平均查找效率是 O(logn)，但是需要数组是排序的。如果没有排过序，就只好先用O（nlogn)的预处理为它排个序了。而且它的插入比较困难，经常需
7、要移动整个数组，所以动态的情况下比较慢。哈希查找理想的插入和查找效率是O(1)，但条件是需要找到一个良好的散列函数，使得分配较为平均。另外，哈希表需要较大的空间，至少要比 O(n)大几倍，否则产生冲突的概率很高。二叉排序树查找也是 O(logn)的，关键是插入值时需要做一些处理使得它较为平衡（否则容易出现轻重的不平衡，查找效率最坏会降到 O(n)），而且写起来稍微麻烦一些，具体的算法你可以随便找一本介绍数据结构的书看看。当然，如果你用的是 c 语言，直接利用它的库类型 map、multimap 就可以了,它是用红黑树实现的，理论上插入、查找时间都是O(logn)，很方便，不过一般会比自己实现的
8、二叉平衡树稍微慢一些。三 树图克鲁斯卡尔算法的时间复杂度为O（eloge）普里姆算法的时间复杂度为O（n2）迪杰斯特拉算法的时间复杂度为O（n2）拓扑排序算法的时间复杂度为O（n+e）关键路径算法的时间复杂度为O（n+e）8.从具有 n 个结点的二叉排序树中查找一个元素时，在平均情况下的时间复杂度大致为(c)。A.O(n)B.O(1)C.O(log2n)D.O(n2)9.从具有 n 个结点的二叉排序树中查找一个元素时，在最坏情况下的时间复杂度为(a)。A.O(n)B.O(1)C.O(log2n)D.O(n2)2.根据 n 个元素建立一棵二叉排序树，其时间复杂度大致为（b）A.O(n)B.O(nlog2n)(log2n)(n2)3 设一个具有t 个非零元素的m*n 大小的稀疏矩阵采用顺序存储结构（即三元组存储结构），其转置矩阵的普通转置算法的时间复杂度为（d）(m)(n)(n*m)(m*t)(n*t)