教材学习内容总结
第 1 章 概述
- 软件质量的特征:正确性、可靠性、健壮性、可用性、可维护性、可重用性(别人写的组件自己可以拿过来用)、可移植性、运行效率
- 数据结构:计算机存储、组织数据的方式
程序 = 数据结构 + 算法
第 2 章 算法分析
a. 增长函数:表示问题(n)大小与我们希望最优化的值之间的关系(该函数表示了该算法的时间或空间复杂度)
b. 大O记法:
- 渐进复杂度称为算法的阶次;
- 渐进复杂度这一特性基于该表达式的主项(即表示问题大小n的表达式中增长最快的那一项),随着n的增长,常量与次项很快可以忽略不计
- 大O记法的类别有多种,但相同两个类别的算法具有相同的算法,但是其增长函数不一定相同
c. 算法效率:通常用CPU的使用时间表示
d. 更快的CPU并不能影响主项,只会给增长函数增加常量(由此可见,需要重视算法分析)
e. 时间复杂度分析
- 循环运行的复杂度分析:等于循环体的复杂度乘以该循环运行的次数
- 嵌套循环的复杂度分析:需要考虑内层和外层循环
- 方法调用的复杂度分析:(注:只有可运行的语句才会增加时间复杂度)
教材学习中的问题和解决过程
问题1:软件质量特征中的可靠性与健壮性的区别?
问题1解析:书本上定义:可靠性 “ 软件故障发生的频率和危险程度 ” ;健壮性 “ 出错情况下可以得到恰当处理的程度 ”。虽然说得清楚,一个是表示故障发生前的预测故障发生的频率,一个是故障发生后的机器处理的程度。但还是觉得理解不够清晰:健壮性是指程序在运行过程中出现一般性的错误,程序会自动进行错误处理函数(出错了也能继续运行的能力);可靠性(程序出错的概率的高低)是指程序在运行过程中出现错误的概率,一般会做一些可靠性试验来测试
【参考资料】百度知道
课后练习题
EX 2.1 下列增长函数的阶次是多少?
a. 10n^2+100n+1000 (找主项,忽略次项与常量:O(n^2))
b. 10n^3-7 (同上,O(n^3))
c. 2n+100n3 (随着n的增大,指数爆炸,O (2^n) )
d. n^2 ·log(n) (O(n^2 ·log(n)))
EX 2.4 确定下面代码段的增长函数和阶次:
for(int count = 0 ; count < n ; count++)
for(int count2 = 0 ; count2 < n ; count2 = count2 + 2)
{
System.out.println(count,count2);
}
}
这是一个嵌套循环的复杂度分析。内层循环每次都增加2,故循环了n/2次,外层循环了次,根据乘法准则,增长函数为 (n/2)*n = n2/2,则阶次为O(n2)
EX 2.5 确定下面代码段的增长函数和阶次:
for(int count = 0 ; count < n ; count++)
for(int count2 = 1 ; count2 < n ; count2 = count2 * 2)
{
System.out.println(count,count2);
}
}
这是一个嵌套循环的复杂度分析。内层循环每次变为前一次的2倍,则有2^x = n,即内层循环的次数x = (以2为底n的对数 - 1)次;外层循环了n次,根据乘法准则,增长函数为n(log(2)n-1),忽略掉次项,则阶次为O(O(nlog2n))(2是对数的底)
结对及互评
-
博客中值得学习的或问题:
- 侯泽洋同学的博客排版工整,界面很美观
- 问题总结做得很全面
- 对于书上的疑惑总会想办法解决它,这种探索的精神值得我去学习
-
本周结对学习情况
- 20172302
- 结对学习内容
- 第一、二章内容
学习进度条
代码行数(新增/累积) | 博客量(新增/累积) | 学习时间(新增/累积) | 重要成长 | |
---|---|---|---|---|
目标 | 5000行 | 30篇 | 400小时 | |
第一周 | 0/0 | 1/1 | 4/4 |