【初阶数据结构与算法】时间空间复杂度和排序稳定性分析

本文目录一时间复杂度1常见情况举例O(1)O(MN)时间复杂度的表示不一定只有一个未知数O(logN)默认为以2为底N的对数二空间复杂度三八大排序算法的复杂度①冒泡排序1.时间复杂度 O(N^2)2.空间复杂度 O(1)②堆排序1.时间复杂度 O(NlogN)a. 向上向下调整算法的时间复杂度logNb 数组建堆的时间复杂度b.1 向下调整建堆 O(N)b.2 向上调整建堆 O(NlogN)综合向下调整建堆O(N)和向上调整建堆O(NlogN)堆排序的时间复杂度2.空间复杂度 O(1)③插入排序1.时间复杂度 O(N^2)2.空间复杂度 O(1)④希尔排序1.时间复杂度 O(N^1.3)2.空间复杂度 O(1)⑤选择排序1.时间复杂度 O(N^2)2.空间复杂度 O(1)⑥快速排序1.时间复杂度 O(NlogN)2.空间复杂度 O(logN)⑦归并排序1.时间复杂度 O(NlogN)2.空间复杂度 O(N)四稳定性五汇总表格一时间复杂度时间复杂度的定义在计算机科学中算法的时间复杂度是一个函数它定量描述了该算法的运行时间。一个算法执行所耗费的时间从理论上说是不能算出来的只有你把你的程序放在机器上跑起来才能知道。但是我们需要每个算法都上机测试吗是可以都上机测试但是这很麻烦所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例算法中的基本操作的执行次数为算法的时间复杂度。实际中我们计算时间复杂度时我们其实并不一定要计算精确的执行次数而只需要大概执行次数那么这里我们使用大O的渐进表示法。时间复杂度有的是固定的但有的是会变的在会变的情况下算最坏情况。1常见情况举例O(1)两种写法都是O(1)第一种写法看似是有未知量但未知量的值是确定的所以和第二种写法一样都是O(1)常数次。intmain(){intn10;for(inti0;in;i)//for(int i 0;i10;i){printf(%d,i);}return0;}O(MN)时间复杂度的表示不一定只有一个未知数当不知道M和N的大小关系时时间复杂度就是O(MN)如果知道M更大那时间复杂度就是O(M)N更大那时间复杂度就是O(N)。intmain(){intmM;for(inti0;im;i){printf(%d,i);}intnN;for(intj0;jn;j){printf(%d,j);}return0;}O(logN)默认为以2为底N的对数intmian(){intnN;for(inti0;in;i*2){printf(%d,i);}return0;}二空间复杂度运行时额外开辟的辅助空间譬如在归并排序中额外开辟的数组和递归时的栈空间这些都是额外的空间。三八大排序算法的复杂度①冒泡排序1.时间复杂度 O(N^2)2.空间复杂度 O(1)没有开辟额外的空间。(像额外的数组或是递归开辟的栈帧)②堆排序1.时间复杂度 O(NlogN)堆排序过程对数组里的数据向下调整建堆后再通过大小堆依次将根节点数据与最后一个数据进行交换从而实现排序。a. 向上向下调整算法的时间复杂度logNb 数组建堆的时间复杂度给一个数组要求对数组建堆。b.1 向下调整建堆 O(N)如果使用向下调整建堆那么就要求正在排序的节点的左右子树已经成堆从数组的前端向后端排序是行不通的(子树不成堆)应该从后向前进行调整叶子节点不用管调整要从第一个非叶子节点开始(循环)以最坏的情况(满二叉树)进行分析如下图所示堆排序指的是通过向下调整建堆实现排序与向上调整建堆无关所以堆排序的时间复杂度为O(N)向下调整建堆跟插入删除数据没有关系。b.2 向上调整建堆 O(NlogN)从第二层开始依次与上方已经成堆的节点数据进行比较(可以看成依次尾插)。综合向下调整建堆O(N)和向上调整建堆O(NlogN)向下调整建堆挪动次数多的节点少挪动后次数少的节点多向上调整建堆挪动次数少的节点少挪动次数多的节点多。所以两者的时间复杂度不同。堆排序的时间复杂度先向下建堆O(N)再不断将首尾交换再调整(N-1)个数据参与交换每次调整都是O(logN)所以堆排序的时间复杂度O(N)(N-1)*O(logN)使用渐进表示法最后为O(NlogN)。2.空间复杂度 O(1)③插入排序1.时间复杂度 O(N^2)求出N-1个数据中涉及到的所有end边界的移动的总和就能算出插入排序的时间复杂度。2.空间复杂度 O(1)④希尔排序1.时间复杂度 O(N^1.3)2.空间复杂度 O(1)⑤选择排序1.时间复杂度 O(N^2)2.空间复杂度 O(1)⑥快速排序1.时间复杂度 O(NlogN)begin和end向中央走确定一个key位置走的步数合计就是N再递归递归的过程像是形成了一棵满二叉树每一层的所有begin和end走的合计步数约等于N那么有多少层就有多少个N(最后一层没有但不影响最后的结果)最终快速排序的时间复杂度是O(NlogN)。不过快速排序存在一个最坏情况O(N^2)。每次确定的key都在同一边界线上这也是为啥我们要三数取中。2.空间复杂度 O(logN)快速排序是原地排序排序过程不额外开辟数组仅递归调用时产生栈帧。单个栈帧只存储索引、局部变量等固定信息和数据规模无关为O(1)。又因为递归是深度优先执行栈帧可以复用同一时刻栈中只保留最深一条递归链的栈帧不用统计整棵递归树的所有栈帧。综上空间复杂度由递归最大深度决定在O(logN)~O(N)之间有了三数取中O(N)的情况一般不会出现了所以快速排序的空间复杂度默认为O(logN)。⑦归并排序1.时间复杂度 O(NlogN)从gap1开始遍历数组在比较中将数组中的元素插入到tmp数组中每个gap都要遍历一遍数组所以每个gap的时间复杂度都是O(N)归并递归时同样会形成一棵完全二叉树能够进入循环的gap的个数为高度-1所以归并排序的时间复杂度为O(NlogN)。最上方一层不进入排序但不影响时间复杂度2.空间复杂度 O(N)四稳定性稳定排序相等的数排完之后相对顺序不变不稳定排序相等的数顺序可能乱掉。五汇总表格排序种类时间复杂度空间复杂度稳定性冒泡排序O(N^2)O(1)稳定选择排序O(N^2)O(1)不稳定堆排序O(NlogN)O(1)不稳定插入排序O(N^2)O(1)稳定希尔排序O(N^1.3)O(1)不稳定快速排序O(NlogN)O(logN)稳定归并排序O(NlogN)O(N)稳定——end——