(
课件网) 第五章 数据结构与算法 选修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时，算法在最优的情况下的效率。 算法的平均效率：在实际的假设情况下，算法所可能发生的正推推断下所具有的效率。一般是通过得到或者是假设各类输入的概率分布，以推导出我们所希望的基本操作次数。 两个经验性的规则： 最优效率的分析远远不如最差效率分析重要（因为最差效率可以确定算法运行时间的上界） 如果一个算法的最优效率都不能满足我们的要求，那么我们就可以立即抛弃它。 算法效率 如果一个算法在输入规模变大时，但运行时间平缓增长，那么我们就可以说它就是一个效率高的算法。 ... ...
