资源简介

(共13张PPT)
第五章 数据结构与算法
选修1《数据与数据结构》
5.1 数据结构与算法效率
算法效率
算法是解决某一特定类型问题的有限求解步骤。描述一个算法可以采用某一计算机语言，也可以才用自然语言和流程图等
·算法的概念
·算法的特征
有穷性
确定性
可行性
有0个或多个输入
有1个或多个输出
算法效率
算法效率
·时间复杂度
反映了算法执行所需要的时间
·空间复杂度
反映了算法执行所需要占用的存储空间
·算法效率
抽算法效率的高低可由算法复杂度来度量。
算法效率
算法效率
·推导大O阶的方法
算法效率
1、用常数1取代运行时间中的所有加法常数，即O(1)
2、在修改后的运行次数函数中，只保留最高阶项。
例如： 的时间效率为O( )
3、如果最高阶项存在且不是1，那么去除与这个项相乘的常数，得到的结果就是大O阶。
例如： 的时间效率为O( )
算法效率
·实例
算法效率
算法一：
n = int(input()) #执行1次
s = (1 + n) * n / 2 #执行1次
print(s) #执行1次
算法二：
n = int(input()) #执行1次
s = 0 #执行1次
for i in range(1, n + 1): #执行n次
s = s + i #执行n次
print(s) #执行1次
算法一是顺序结构，语句总的执行次数为3次，时间复杂度为O(1)，称为常量阶。
算法二是一重循环，语句总的执行次数为2n+3次，时间复杂度为O(n)，称为线性阶。
小组讨论
n=int(input())
s=0
x=0
for i in range(1,n+1):
for j in range(1,n+1):
x=x+1
s=s+x
print(s)
算法的时间复杂度是指该算法的时间耗费，是该算法中基本操作重复执行的次数与问题规模n的某个函数。
算法效率
一般将算法中语句的执行次数作为时间复杂度的度量标准。我们在分析时间复杂度的时候也只关注执行次数的增长次数及其常数倍。
语句总的执行次数T(n)是关于问题规模n的函数。
时间复杂度常用符号O()表示。
·时间复杂度
算法效率
在分析算法的时间复杂度时，我们需要知道三个方面：
·输入规模
不管使用什么算法，输入规模越大，运行效率肯定会更长。
·算法的平均效率、最差效率和最优效率
在输入最优情况下的算法就叫最优效率。
在输入最坏情况下的算法就叫最差效率。
·增长次数
在大规模的输入情况下考虑执行次数的增长次数。
注意：经过半个多世纪的发展，计算机的速度和存储容量都已经提升了好几个数量级。现在空间效率已经不是我们关注的重点。
算法效率
·输入规模 （各种排序算法的效率）
算法效率
利用随机数，随机生成区间0 ~ K之间的序列，共计N个数字，利用各种算法进行排序，记录排序所需时间，测试环境为i7+vs2015+Debug版本。
算法效率
·算法的平均效率、最差效率和最优效率
算法效率
在以顺序查找算法为例：
算法的最差效率：n个数据，在最后一次判断才找到，效率为n。
算法的最优效率：n个数据，第一次就判断就找到，效率为1
算法的平均效率：n个数据，我们先假设能找到的概率，然后我们需要求得在第一次查找到的概率、第二次查找到的概率等等一直求，然后算得总的操作次数，得出算法的平均效率
算法的最差效率：当输入规模为n时，算法在最坏情况下的效率。
算法的最优效率：当输入规模为n时，算法在最优的情况下的效率。
算法的平均效率：在实际的假设情况下，算法所可能发生的正推推断下所具有的效率。一般是通过得到或者是假设各类输入的概率分布，以推导出我们所希望的基本操作次数。
两个经验性的规则：
最优效率的分析远远不如最差效率分析重要（因为最差效率可以确定算法运行时间的上界）
如果一个算法的最优效率都不能满足我们的要求，那么我们就可以立即抛弃它。
算法效率
如果一个算法在输入规模变大时，但运行时间平缓增长，那么我们就可以说它就是一个效率高的算法。
如果一个算法在输入规模变大时，它的运行时间成指数级增长，那就可以说这个算法的效率很差。
·增长次数
算法效率
对时间复杂度O的计算，其实就是求解算法的增长函数。
算法效率
·时间复杂度的耗时比较
算法效率
由上图可知：
O(1)数据结构对算法效率的影响
·数据结构与算法的关系
算法效率
1、在计算机科学中，数据结构与算法有着密不可分的关系。解决实际问题时，数据总是以一定的组织结构关系体现并存储，数据结构的设计和选择关注的是数据的逻辑结构、存储结构以及基本操作；算法的设计和选择更多的是关注如何在数据结构的基础上综合运用各种基本操作来解决实际问题。
2、数据组织成不同的结构，是为了满足不同问题的需求，便于算法对数据的操作，提高孙发处理数据的效率。算法的设计和选择总是依赖于数据结构，算法设计的同时也伴随着数据结构设计，两者都是为最终解决问题服务。算法是编程思想，数据结构则是这些思想的基础。
数据结构对算法效率的影响
·实例
算法效率
现有一组n个数据需要存储。
第一种用数组的数据结构来存储记为n1
第二种用链表的数据结构来存储记为n2
1、若要随机访问其中的一个数据，则n1的时间复杂度为O(1)。
n2的时间复杂度为O(n)。
2、若要对元素进行插入和删除操作，则n1的时间复杂度为O(n)。
n2的时间复杂度为O(1)。
由此可见：数据结构的不同选择会影响算法的运行效率。

展开更多......

收起↑