资源简介

(共12张PPT)
第9课
算法的评价方法
主要内容：
1.算法评价的方法。
2.多种算法的效率比较。
解决某个问题可能会有多种不同的算法，如何评价算法的“好”与“差”呢？
针对某个问题，可以设计多个算法来解决，但不同的算法的效率是有差异的。算法有“好”与“差”之分，在一定条件下，当然要选择“好”的算法。
“好”的算法，除了符合“正确性、有效性”等标准外，还需要有较高的算法运行效率，即算法运行所消耗的时间较短。
一
算法评价的方法
一般情况下，算法运行需要的时间与待求问题的规模有关，如通过循环的方式求100个人的总分与求1000个人的总分，循环体执行的次数是不一样的，执行时间显然有差别。估算该算法的运行时间，可以在问题规模相同的情况下，将算法中循环语句的执行次数作为度量标准。
一
算法评价的方法
例如，用顺序查找算法在1-100内查找37的程序如下：
#执行37次
一
算法评价的方法
上述程序在执行时，变量cai的数值决定了循环语句while会执行的次数，当变量cai的值为37时，while语句总的执行次数为37次。
一
算法评价的方法
ci=1
,”累计用的次数为：”,ci
ci=ci+1
二
算法评价体验
解决同一个问题的不同算法，在执行时的运行时间是有一定差异的。同样是在1-100范围内查找目标数37，利用二分查找算法时，中间值一次去50、25、37，也就是说，循环只需执行3次，与顺序查找算法相比，循环少执行34次，显然运行时间更短。
二
算法评价体验
在1-100范围内，分别采用顺序查找和二分查找算法查找目标数1、50和100，估算循环的执行次数？
目标数 查找算法 循环执行次数
1 顺序 1
二分 6
50 顺序 50
二分 1
100 顺序 100
二分 7
谢谢聆听，
下节课再见！

展开更多......

收起↑