案例:在学期前学生评优中,根据每个班级同学不同的分数段给出评级,而每个班级中不同分段的人数不等的,且有着峰值和低谷。如何实现呢?如不及格1人,及格2人,中等4人,良好2人,优秀1人。
程序1:if(a<60){
b="不及格";
}else if(a<70){
b="及格";
}else if(a<80){
b="中等";
}else if(a<90){
b="良好";
}else {
b="优秀";
}
执行次数:1×1+2×2+4×3+2×4+1×5=30
完全没利用到数据本身特点。
程序2:if(a<80){
b="中等40";
}else if(a<70){
b="及格20";
}else if(a<90){
b="良好20";
}else if(a<60){
b="不及格10";
}else {
b="优秀10";
}
执行次数:4×1+2×2+2×3+1×4+1×5=23
利用情况一般。
程序3:if(a<80){
if(a<70){
if(a<60){
a="不及格"
}
a="及格";
}
a="中等";
}else{
if(a<90){
a="良好"
}
a="优秀"
}
程序3的设计其实就是数据结构里的赫夫曼树,发明目的是解决远距离通信的数据传输最优化问题,我们写程序的时候多考虑一些执行效率上的问题,自然很多算法和数据结构都有用武之地,算法和数据结构这个东西分开谈没意义,就向上例,数据之间没有一定的树层级关系,你用极差的算法。对了,上例的优化不针对树,如果数据中间峰值两边低谷这个顺序,用二分查找效率也是刚刚的,当然会麻烦一点,而且数据不是这个顺序怎么办,当然这是不同情况下的适应性问题了。
为什么会有这个思路呢?因为数据结构里讲到过四种数据逻辑结构,上例明显是从树形结构出发的,我们学过就会想想用集合和线性结构下的最优解,自然思路就出来了。其他运用如栈的应用,四则运算表达式求值,编译器使用栈实现递归,函数出入栈。