20172308《Java软件结构与数据结构》第一周学习总结

教材学习内容总结

第 1 章 概述

  1. 软件质量的特征:正确性、可靠性、健壮性、可用性、可维护性、可重用性(别人写的组件自己可以拿过来用)、可移植性、运行效率
  2. 数据结构:计算机存储、组织数据的方式

    程序 = 数据结构 + 算法

第 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
上一篇:使用 MyEclipse远程调试 Java 应用程序


下一篇:改进duilib的richedit控件的部分功能