20172327 2018-2019-1 《程序设计与数据结构》第一周学习总结
教材学习内容总结
第一章 概述
| 软件质量 |
1.软件工程（Software Engineering）：一门关于高质量软件的技术和理论的学科。
2.软件工程的目标：
- 解决正确性问题
- 按时且在预算之内给出解决方案
- 给出高质量的解决方案。
- 以合情合理的方式完成上面的事情
3.软件质量特征
| 质量特侦 | 描述 |
|---|---|
| 正确性 | 软件在多大程度上满足其特征需求 |
| 可靠性 | 软件故障发生的频率和危险程度 |
| 健壮性 | 出错情况下可以得到恰当处理的程度 |
| 可用性 | 用户学习和执行任务的难易程度 |
| 可维护性 | 对软件进行修改的难易程度 |
| 可重用性 | 软件组件可重用于其他软件系统的开发的难易程度 |
| 可移植性 | 软件组件可以在多个计算机环境下使用的难易程度 |
| 运行效率 | 在不浪费的情况下软件完成其目标的程度 |
4.运行效率：
- 软件必须高效地使用诸如CPU时间和储存器之类的资源。
- 软件系统应该有效地利用分配给它们的资源如内存和CPU时间。
5.质量问题：
- 必须优先考虑质量特征，并尽最大努力实现。
- 某些特征彼此之间有时是互斥的，我们必须认真地把某一特定项目的相关问题排列出一个优先次序，然后在这些范围内，尽可能地最大限度地满足所有质量特征。
| 数据结构 |
1.程序=数据结构+算法
2.软件=程序+软件算法
3.数据结构：计算机储存、组织数据的方式。
第二章 算法分析
| 算法效率分析 |
1.软件质量的分析特征是资源的使用效率。CPU的使用时间是最重要的资源之一。
2.算法分析是计算机科学的一个基础，并涉及多种技术和概念。
| 增长函数与大O记法 |
1.算法的效率可以根据该问题的大小和处理步奏数来定义。
2.增长函数表示与该问题大小相对应的时间或空间的使用。
3.增长函数（growth function）表示问题（n）大小与我们希望最优化的值之间的关系。该函数表示了该算法的时间复杂度（time complexity）或空间复杂度（space complexity）。
3.渐进复杂度称为算法的阶次（order）。
4.O()记法称为大O记法。
5.算法的阶次是忽略该算法的增长函数中的常量和其他次要项，只保留主项而得出的。
6.不管问题是大是小，运行赋值语句和if语句一次，其复杂度就为O(1)。
7.循环语句和方法调运语句可能会导致更高阶次的增长函数。
8.增长函数及其渐进复杂度
9.算法的阶次为增长函数提供了一个上界。
10.所有具有相同阶次的算法，从运行效率的角度来说都认为是等价的。
| 增长函数的比较 |
1.处理器速度和储存器并不能弥补算法效率的差异。
2.如果算法的效率底，那么从长远来说，使用更快的处理器也无济于事。
3.在n很小时算法差别很小，但是当n很大时，增长函数之间的差别就很明显。
| 时间复杂度计算 |
循环运行的复杂度分析
1.要分析循环运行，首先要确定该循环体的阶次n，然后用该循环要运行的次数乘以它。
2.要分析算法的复杂度，通常需要分析循环的运行。
3.循环的时间复杂度等于循环的复杂度乘以该循环的次数。
嵌套循环的复杂度度分析
1.循环出现嵌套时，计算其复杂度需要考虑内层循环和外层循环的复杂度，需要用内层循环的复杂度乘以外层循环的复杂度。
方法调运的复杂度分析
1.循环体可能包含方法的调用
2.要确定循环体的阶，需要考虑调运方法的阶。
教材学习中的问题和解决过程
问题1：请问O(k^2*n^k/k!) 渐进性到O(n^k)的推导，是否是先取对数变为多项式log(k^2) + log(n^k) - log(k!)，然后舍去log(k^2)和-log(k!)得出？
分析：这个问题其实是用穷举法求解独立集问题。
首先有C(n,k)种方法求图的k个点的方法数
然后对于这k个点，有O(k^2)种方法判断是否右边关联
所以根据乘法规则
T(n)=O(k^2C(n,k))
这里C(n,k)<=n^k/k!
带入之后
T(n)=O(k^2n^k/k!)
由于k^2和k!相对n^k来说是低阶项，所以
T(n）=O(n^k)
教材布置习题解答
- EX2.1 下列增长函数的阶次是多少？
a. 10n^2+100n+1000
b. 10n^3-7
c. 2^n+100n^3
d. n^2*logn
解答：
a.平方型：因为渐进复杂度称为算法的阶次，因此该增长函数的阶次为：O(n^2)。
b.立方型：因为n^3增长速度快，因此该增长函数的阶次为：O(n^3)。
c.指数型：因为2^n增长速度比n^3要快，因此该增长函数的阶次为：O(2^n)。
d.复合型：因为是乘法，因此该增长函数的阶次为：O(n^2*log)。- EX2.4 请确定下面代码段的增长函数和阶次：
for(int count = 0 ; count < n ; count++)
for(int count2 = 0 ; count2 < n ; count2 = count2 + 2)
{
System.out.println(count,count2);
}
}
解答：这个是嵌套循环，内层循环的循环次数是n/2，外层循环的循环次数是n，所以增长函数为：F(n)=(n^2)/2
又因为阶数与增长函数的最高阶项有关，所以忽略次项与常数项。所以阶次为O(n^2)。- EX2.5 请确定下面代码段的增长函数和阶次：
for(int count = 0 ; count < n ; count++)
for(int count2 = 0 ; count2 < n ; count2 = count2 * 2)
{
System.out.println(count,count2);
}
}
解答：这个是嵌套循环，内层循环的循环次数是log2(n)，外层循环的循环次数是n，所以增长函数为：F(n)=n·log2(n)
又因为阶数与增长函数的最高阶项有关，所以忽略次项与常数项。所以阶次为O(n·log2(n))。代码托管
本周不存在所要托管的代码
结对及互评
暂无
其他（感悟、思考等，可选）
概念很多，嘚仔细看，有很多细节，上课刚开始听突然有点懑，但是课后仔细将书读了一遍之后，发现并不难。
学习进度条
| 代码行数（新增/累积） | 博客量（新增/累积） | 学习时间（新增/累积） | 重要成长 | |
|---|---|---|---|---|
| 目标 | 5000行 | 30篇 | 400小时 | |
| 第一周 | 0/0 | 1/1 | 8/8 |
计划学习时间:10小时
实际学习时间:8小时
改进情况：
(有空多看看现代软件工程 课件
软件工程师能力自我评价表)