Python数据结构与算法-第2章-算法复杂度分析

一案例导入：一个简单的搜索引擎案例：一个简单的搜索引擎案例描述

假设你正在开发一个简单的搜索引擎，需要实现一个搜索函数，能够在一堆文本中找到指定的关键词并返回相关信息。最朴素的方法就是从文本的第一个字符开始，一个一个地比较，直到找到目标字符串或者到达文本的结尾。这个案例将会介绍一个简单的字符串搜索算法：暴力匹配算法。案例：一个简单的搜索引擎案例实现

暴力匹配算法（Brute-ForceAlgorithm）又称为朴素字符串匹配算法（NaiveStringMatchingAlgorithm）上图为“字符串暴力匹配过程”案例：一个简单的搜索引擎进阶思考

假设我们是在一个文本文件中查找某个单词，文件大小为n个单词，如果我们上述对待查找文本进行文本处理，借助简单的数据结构和算法，应该如何实现代码?二算法复杂度的概念算法复杂度的概念算法什么是

算法

？算法是指解决问题的一系列清晰而有限的指令。算法就是一种用来解决问题的方法。在计算机科学中，算法是一种旨在通过计算机程序来解决计算问题的方法和技术。算法是计算机科学的核心和基础，是许多计算机应用领域的基础。算法复杂度的概念算法复杂度1.确保有解目

标2.寻找最优解1.时间复杂度算法复杂度2.空间复杂度又快又省大O表示法算法复杂度的概念重要性算法复杂度是衡量算法性能的关键指标。例：假设现在需要你对10000000个整数进行排序。现有如下两种排序解决方案：PLANA:使用每秒执行10亿条指令的计算机A(1GHz)，与一个排序n个整数大约需要执行2n^2指令的算法。PLANB:使用每秒执行1亿条指令的计算机B(100MHz)，与一个排序n个整数大约需要执行50nlgn指令的算法。三时间复杂度的分析方法时间复杂度的分析方法时间复杂度的概念时间复杂度通常用大O表示法来表示，即

O(f(n))。常见的时间复杂度常数阶O(1)线性阶O(n)对数阶O(logn)平方阶O(n2)指数阶O(2n)随着数据规模n的增长而增长的最慢速度时间复杂度的分析方法时间复杂度的作用找到算法的瓶颈，进行优化评估、比较不同算法的效率选择复杂度较低的算法，以提高执行效率时间复杂度的分析方法时间复杂度的分析方法找出算法中的基本操作，例如循环、条件语句、赋值语句等1计算每个基本操作的执行次数2将每个基本操作的执行次数乘以其所需的时间复杂度，得到所有基本操作的时间复杂度之和3简化时间复杂度之和，得到算法的时间复杂度4时间复杂度的分析方法常见的时间复杂度示例常数阶O(1)————执行次数不随输入规模的变化而变化———如：访问数组中的元素线性阶O(n)————执行次数随输入规模成线性关系————-—如：遍历数组对数阶O(logn)—--执行次数随输入规模以对数的形式变化--—如：二分查找算法平方阶O(n2)——-—执行次数随输入规模的平方变化————-—如：插入排序算法指数阶O(2n)——-—执行次数随输入规模的指数级别变化-—--—如：求解旅行商问题时间复杂度的分析方法案例分析

具体来说，如果文本长度为n，目标字符串长度为m，那么最坏情况下需要比较n-m+1次，时间复杂度为O(nm)。四空间复杂度的分析方法空间复杂度的分析方法空间复杂度的概念上图为“空间复杂度统计范畴”空间复杂度的分析方法空间复杂度的概念空间复杂度也可以用大O表示法来表示，即

O(f(n))。常见的空间复杂度常数阶O(1)线性阶O(n)对数阶O(logn)平方阶O(n2)指数阶O(2n)空间复杂度的分析方法空间复杂度的概念常见空间复杂的的关系如下:常数阶O(1)<线性阶O(n)<

对数阶O(logn)<

平方阶O(n2)<

指数阶O(2n)空间复杂度的分析方法空间复杂度的概念上图为“算法空间复杂度与输入数据规模大小的关系”空间复杂度的分析方法空间复杂度的作用空间复杂度时间复杂度空间复杂度的分析方法空间复杂度的分析方法空间复杂度更关注算法运行过程中的内存空间使用极大值，也就是最差空间复杂度。空间复杂度的分析方法常见的空间复杂度示例常数阶O(1)————占用空间不随输入规模的变化而变化线性阶O(n)————占用空间随输入规模成线性关系对数阶O(logn)—--占用空间随输入规模以对数的形式变化平方阶O(n2)——-—占用空间随输入规模的平方变化指数阶O(2n)——-—占用空间随输入规模的指数级别变化空间复杂度的分析方法案例分析

从最差的空间复杂度来说，案例中所提供算法的最差空间复杂度为O(n)。五最好、最坏和平均情况分析最好、最坏和平均情况分析概念最好情况时间复杂度最坏情况时间复杂度平均情况时间复杂度最好、最坏和平均情况分析分析示例例：假设我们有一个长度为n的列表，其中的元素都是整数。我们想要从中找到指定的值。1.最好情况分析2.最坏情况分析3.平均情况分析：假设输入列表是随机的，也就是我们访问所有元素都是等概率的，那么每次查找平均需要遍历n/2个元素，时间复杂度为O(n)六小结与习题小结与习题本章小结1算法复杂度23时间复杂度空间复杂度小结与习题习题？？在算法复杂度的概念中，复杂度的度量标准是什么?A.时间

B.空间C.时间和空间

D.程序的长度下列哪种情况是算法的最坏时间复杂度?A.最优输入情况

B.平均输入情况C.最坏输入情况

D.随机输入情况小结与习题习题？？对于一个时间复杂度为O(n^2)的算法，当n增加10倍时，其时间复杂度的增长率是多少?A.增长了10倍

B.增长了100倍C.增长了1000倍

D.增长了10000倍在进行算法的空间复杂度分析时，我们通常更关注算法的?A.最好空间复杂度

B.最坏空间复杂度C.平均空间复杂度

D.最优空间复杂度小结与习题习题×/√时间复杂度为O(1)的算法一定比时间复杂度为O(n)的算法更快。×/√空间复杂度的分析方法只考虑程序所需的内存空间大小。×/√最好情况时间复杂度是指在最理想的情况下，算法所需的最少时间复杂度。七实训任务实训任务任务1任务2编写一个函数，接受一个列表作为参数，返回列表中