《算法与数据结构算法时间效率的分析》由会员分享，可在线阅读，更多相关《算法与数据结构算法时间效率的分析（3页珍藏版）》请在金锄头文库上搜索。
1、算法与数据结构（1）-算法时间效率的分析概述数据结构和算法是一名程序开发人员的必备基本功，不是一朝一夕就能练成绝世高手的。冰冻三尺非一日之寒，需要我们平时不断的主动去学习积累。引入先来看一道题:如果a+b+c=1000,且aA2+b人2=cA2（a,b,c为自然数），如何求出所有a、b、c可能的组合？我们使用穷举法和枚举来分析：循环遍历abc满足条件的输出。代码如下：运行的结果是:我们看到运行代码消耗的时间为：1240.802592算法算法的概念：算法是计算机处理信息的本质，因为计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个指定的任务。一般地，当算法在处理信息时，会从输入设备或数据
2、的存储地址读取数据，把结果写入输出设备或某个存储地址供以后再调用。算法是独立存在的一种解决问题的方法和思想。对于算法而言，实现的语言并不重要，重要的是思想。算法可以有不同的语言描述实现版本（如C描述、C+描述、Python描述等），我们现在是在用Python语言进行描述实现。算法的五大特征1. 输入:算法具有0个或多个输入2. 输出：算法至少有1个或多个输出3. 有穷性：算法在有限的步骤之后会自动结束而不会无限循环，并且每一个步骤可以在可接受的时间内完成4确定性：算法中的每一步都有确定的含义，不会出现二义性5.可行性：算法的每一步都是可行的，也就是说每一步都能够执行有限的次数完成再次分析前面题
3、当我们遍历完a、b,根据条件得知a+b+c=1000,所以我们不用再去遍历c,c=1000-a七修改后代码如下：运行的结果是:我们看到运行代码消耗的时间为：0.667052时间效率执行时间反应算法效率对于同一问题，我们给出了两种解决算法，在两种算法的实现中，我们对程序执行的时间进行了测算，发现两段程序执行的时间相差悬殊（1240.802592秒相比于0.667052秒），由此我们可以得出结论：实现算法程序的执行时间可以反应出算法的效率，即算法的优劣我们拿到这个代码运算时间差，去对比算法的效率，真的可靠吗？假设我们将第二次尝试的算法程序运行在一台配置古老性能低下的计算机中，情况会如何？很可能运行
4、的时间并不会比在我们的电脑中运行算法一的214.583347秒快多少。单纯依靠运行的时间来比较算法的优劣并不一定是客观准确的！程序的运行离不开计算机环境（包括硬件和操作系统），这些客观原因会影响程序运行的速度并反应在程序的执行时间上。那么如何才能客观的评判一个算法的优劣呢？基本运算单位分析代码效率我们假定计算机执行算法每一个基本操作的时间是固定的一个时间单位，那么有多少个基本操作就代表会花费多少时间单位。显然对于不同的机器环境而言，确切的单位时间是不同的，但是对于算法进行多少个基本操作（即花费多少时间单位）在规模数量级上却是相同的，由此可以忽略机器环境的影响而客观的反应算法的时间效率。然后来分
5、析上面的代码:forainrangefe,1001):forbinrarge(6j1091):forcirrange(0j1061):10。诃、单位远箕ifaM2+b*+2=f*2anda+b+c=I960:科00010S:耳6Mc：i；000第一中词1眦个单艇算殆瞬共上呱？1咖巴+1)forairrangefB1601):forbinrangefS.1061-a)：iod吩单庞算c=1000-a-bja加个軸aT=1000*1000*(44-5+1)第二种时间复杂ifa+*2+护*2=c*2:度为T2=1000000*10Xdj%Aa%(ab,c)1个通过T1和T2,可以明显的对比出哪个算法更优。T是什么？这就引出了我们的概念时间复杂度与“大O记法”下一节继续。
