时间复杂度空间复杂度课件

时间复杂度+空间复杂度+二分+三分+快速排序+归并排序时间复杂度+空间复杂度+二分+三分+快速排序+归并排序1算法分析（AlgorithmAnalysis）：对算法所需要的两种计算机资源——时间和空间进行估算时间复杂性（TimeComplexity）空间复杂性（SpaceComplexity）算法分析的目的：设计算法——设计出复杂性尽可能低的算法选择算法——在多种算法中选择其中复杂性最低者算法分析（AlgorithmAnalysis）：对算法所需2和算法执行时间相关的因素：

1）问题中数据存储的数据结构2）算法采用的数学模型3）算法设计的策略

4）问题的规模

5）实现算法的程序设计语言

6）编译算法产生的机器代码的质量

7）计算机执行指令的速度但我们更加关注前四项，并可以用时间复杂度和空间复杂度来衡量和算法执行时间相关的因素：但我们更加关注前四项，并可以用时间3在计算机科学中，算法的时间复杂度是一个函数，它定性描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。时间复杂度描述的就是算法中基本操作执行的次数在计算机科学中，算法的时间复杂度是一个函数，它定性描述了该算4时间复杂度常用大O符号表述，不包括这个函数的低阶项和系数。注意这里的忽略低阶项和系数！！！！即O（C）(C是常数)->O(1)O(3)->O(1)O(n^2+3*n+10)->O(n^2)O(5*n!+n^3)->O(n!)O(n+logn)->O(logn)时间复杂度常用大O符号表述，不包括这个函数的低阶项和系数。注5时间复杂度空间复杂度课件6f(n)f(n)7常用时间复杂度常用时间复杂度81sCPU最多可执行的语句数=1e8左右如n<=1000时，O（n^3）是不可接受的！！因为n取1000时，执行语句大约为1e9>1e8所以会超时！！！所以需要重新考虑别的算法1sCPU最多可执行的语句数=1e8左右如n<=10009空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度10二分

二分查找用于有序表的查找首先需要查找的数据是必须是有序的，升序或降序关键思想在于一半一半地缩小范围！！二分 二分查找用于有序表的查找11时间复杂度空间复杂度课件12时间复杂度空间复杂度课件13二分查找每次将待选范围缩半，假设时间复杂度为O（X）2^X=nX=log(n)所以二分查找的时间复杂度为O（logn），空间复杂度O（1）所以特别快！！！二分查找每次将待选范围缩半，假设时间复杂度为O（X）14二分不仅适用于离散型数据的查找，同样也适用于连续性数据的查找二分不仅适用于离散型数据的查找，同样也适用于连续性数据的查找15二分法求零点

二分法求零点 16时间复杂度空间复杂度课件17三分类似于二分查找，三分搜索法也是比较常用的基于分治思想的高效查找方法。但是和二分不同，二分只适用于单调函数，比如常用的对单调递增或单调递减的一个序列中的某一个元素进行查找，三分却突破了这种限制，可以用于左边递增右边递减或者相反的，这么一类函数，也就是常说的凸函数和凹函数。三分类似于二分查找，三分搜索法也是比较常用的基于分治思想的高18时间复杂度空间复杂度课件19排序之前的冒泡排序的时间复杂度O（n^2）,当n>10000时，显然会超时！！我们需要更快的排序方法，那就是快速排序和归并排序，它们的时间复杂度均是O（nlogn）。排序之前的冒泡排序的时间复杂度O（n^2）,当n>1000020快速排序（听名字就比较快

快速排序的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。冒泡排序的过程可见，冒泡排序是一个增加有序序列长度的过程，也是一个缩小无序序列长度的过程，每经过一趟起泡，无序序列的长度只缩小1。试设想：若能在经过一趟排序，使无序序列的长度缩小一半，则必能加快排序的速度。快速排序（听名字就比较快

快速排序的基本思想是：通过一趟排21快速排序(1)基本思想通过一趟排序将待排序列以枢轴为标准划分成两部分，使其中一部分记录的关键字均比另一部分小，再分别对这两部分进行快速排序，以达到整个序列有序。

通常取第一个记录的值为基准值或枢轴。快速排序(1)基本思想22快速排序(2)具体做法附设两个指针low和high，初值分别指向第一个记录和最后一个记录，设枢轴为key；1.从high所指位置起向前搜索，找到第一个不大于基准值的记录与枢轴记录相互交换；2.从low所指位置起向后搜索，找到第一个不小于基准值的记录与枢轴记录相互交换。3.重复这两步直至low=high为止。快速排序(2)具体做法23快速排序算法过程§10.3交换排序无序的记录序列无序记录子序列(1)无序子序列(2)

枢轴

一次划分分别进行一趟快速排序有序的记录序列……快速排序算法过程§10.3交换排序无序的记录24时间复杂度空间复杂度课件25归并排序归并排序的基本思想是：将两个(或以上)的有序表组成新的有序表。更实际的意义：可以把一个长度为n的无序序列看成是n个长度为1的有序子序列，首先做两两归并，得到

n/2

个长度为2的子序列；再做两两归并，…，如此重复，直到最后得到一个长度为n的有序序列。归并排序归并排序的基本思想是：将两个(或以上)的有序表组成新26归并排序初始关键字：[49][38][65][97][76][13][27]一趟归并后：[3849][6597][1376][27]二趟归并后：[38496597][132776]三趟归并后：[13273849657697]看成是n

个有序的子序列(长度为1)，然后两两归并。得到

n/2个长度为2或1的有序子序列。归并排序初始关键字：[49][38][627归并排序例：关键字序列T=（21，25，49，25*，93，62，72，08，37，16，54），请给出归并排序的具体实现过程。归并排序例：关键字序列T=（21，25，49，25*，9328212525*9362720837165449212525*4962930872163754163754212525*490862729308212525*496272930816212525*374954627293len=1len=2len=4len=8len=16163754整个归并排序仅需

log2n

趟212525*9362720837165449212525*29时间复杂度空间复杂度课件30归并排序算法分析

时间效率O(nlog2n)一趟归并排序的操作是：调用[n/2h]次算法merge将SR[1..n]中前后相邻且长度为h的有序段进行两两归并，得到前后相邻长度为2h的有序段，并存放在TR[1..n]