时间复杂度空间复杂度课件.pptx
时间复杂度+空间复杂度+二分+三分+快速排序+归并排序,算法分析（Algorithm Analysis）：对算法所需要的两种计算机资源时间和空间进行估算 时间复杂性（Time Complexity）空间复杂性（Space Complexity）,算法分析的目的：设计算法设计出复杂性尽可能低的算法 选择算法在多种算法中选择其中复杂性最低者,和算法执行时间相关的因素：,1）问题中数据存储的数据结构 2）算法采用的数学模型 3）算法设计的策略4）问题的规模 5）实现算法的程序设计语言 6）编译算法产生的机器代码的质量 7）计算机执行指令的速度,但我们更加关注前四项，并可以用时间复杂度和空间复杂度来衡量,在计算机科学中，算法的时间复杂度是一个函数，它定性描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。,时间复杂度描述的就是算法中基本操作执行的次数,时间复杂度常用大O符号表述，不包括这个函数的低阶项和系数。,注意这里的忽略低阶项和系数！,即O（C）(C是常数)-O(1)O(3)-O(1)O(n2+3*n+10)-O(n2)O(5*n!+n3)-O(n!)O(n+logn)-O(logn),f(n),常用时间复杂度,1sCPU最多可执行的语句数=1e8左右,如 n1e8所以会超时！所以需要重新考虑别的算法,空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n)。,二分,二分查找 用于有序表的查找首先需要查找的数据是必须是有序的，升序或降序关键思想在于一半一半地缩小范围！,二分查找每次将待选范围缩半，假设时间复杂度为O（X）2X=n X=log(n)所以二分查找的时间复杂度为O（logn），空间复杂度O（1）所以特别快！,二分不仅适用于离散型数据的查找，同样也适用于连续性数据的查找,二分法求零点,三分,类似于二分查找，三分搜索法也是比较常用的基于分治思想的高效查找方法。但是和二分不同，二分只适用于单调函数，比如常用的对单调递增或单调递减的一个序列中的某一个元素进行查找，三分却突破了这种限制，可以用于左边递增右边递减或者相反的，这么一类函数，也就是常说的凸函数和凹函数。,排序,之前的冒泡排序的时间复杂度O（n2）,当n10000时，显然会超时！我们需要更快的排序方法，那就是快速排序和归并排序，它们的时间复杂度均是O（nlogn）。,快速排序（听名字就比较快,快速排序的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。,冒泡排序的过程可见，冒泡排序是一个增加有序序列长度的过程，也是一个缩小无序序列长度的过程，每经过一趟起泡，无序序列的长度只缩小1。试设想：若能在经过一趟排序，使无序序列的长度缩小一半，则必能加快排序的速度。,快速排序,(1)基本思想 通过一趟排序将待排序列以枢轴为标准划分成两部分，使其中一部分记录的关键字均比另一部分小，再分别对这两部分进行快速排序，以达到整个序列有序。通常取第一个记录的值为基准值或枢轴。,快速排序,(2)具体做法 附设两个指针low和high，初值分别指向第一个记录和最后一个记录，设枢轴为key；1.从high 所指位置起向前搜索，找到第一个不大于基准值的记录与枢轴记录相互交换；2.从low 所指位置起向后搜索，找到第一个不小于基准值的记录与枢轴记录相互交换。3.重复这两步直至low=high为止。,快速排序算法过程,10.3 交换排序,无 序 的 记 录 序 列,无序记录子序列(1),无序子序列(2),枢轴,一次划分,分别进行一趟快速排序,有 序 的 记 录 序 列,归并排序,归并排序的基本思想是：将两个(或以上)的有序表组成新的有序表。更实际的意义：可以把一个长度为n的无序序列看成是 n 个长度为 1 的有序子序列，首先做两两归并，得到 n/2 个长度为 2 的子序列；再做两两归并，如此重复，直到最后得到一个长度为n 的有序序列。,归并排序,初始关键字：49 38 65 97 76 13 27,一趟归并后：38 49 65 97 13 76 27,二趟归并后：38 49 65 97 13 27 76,三趟归并后：13 27 38 49 65 76 97,看成是 n 个有序的子序列(长度为 1)，然后两两归并。,得到 n/2 个长度为2 或 1 的有序子序列。,归并排序,例：关键字序列T=（21，25，49，25*，93，62，72，08，37，16，54），请给出归并排序的具体实现过程。,len=1,len=2,len=4,len=8,len=16,整个归并排序仅需log2n趟,归并排序算法分析,时间效率 O(nlog2n)一趟归并排序的操作是：调用n/2h次算法merge将SR1.n中前后相邻且长度为h的有序段进行两两归并，得到前后相邻长度为2h的有序段，并存放在TR1.n中，整个归并排序需要进行log2n趟，所以算法总的时间复杂度为O(nlog2n)。空间效率 O(n)因为需要一个与原始序列同样大小的辅助序列(TR)。这正是此算法的缺点。稳定性：稳定,归并排序应用：快速求逆序对个数,
