20172304 《程序设计与数据结构》 第一周学习总结
教材学习内容总结
-
第一章 概述
正确性：软件在多大程度上满足其特定需求
1.1软件质量：
高质量软件的几个特征：
可靠性：软件故障发生频率和危险程度
健壮性：出错情况下可以得到恰当处理的程度
可用性：用户学习和执行任务的难易程度
可维护性：对软件进行修改的难易程度
可重用性：软件组件可重用于其他软件系统开发的难易程度
可移植性：软件组件可以在多个计算机环境下使用的难易程度
运行效率：在不浪费资源的情况下软件完成其目标的程度
1.2数据结构（计算机存储、组织数据的方式）
程序=数据结构+算法
软件=程序+软件工程 第二章 算法分析
2.1算法效率分析
算法效率通常用CPU使用时间来表示
算法分析是从效率的角度对算法进行分析
算法分析是计算机科学的基础
2.2增长函数与大O记法
增长函数：表示问题（n）大小与我们希望最优化的值之间的关系该函数表示了该算法的时间复杂度（CPU的使用时间）和空间复杂度（内存空间）
算法的渐进复杂度（随着n增长时增长函数的一般性质）
主要关注函数的主项（即增长速度最快的的那一项）
渐进复杂度称为算法的阶次
增长函数的项之间的比较
| 盘子的数量 | 15n² | 15n | 15n²+45n |
|---|---|---|---|
| 1 | 15 | 45 | 60 |
| 2 | 60 | 90 | 150 |
| 5 | 375 | 225 | 600 |
| 10 | 1500 | 450 | 1950 |
| 100 | 150 000 | 4500 | 154500 |
| 1000 | 15 000 000 | 45000 | 15045000 |
| 10 000 | 1 500 000 000 000 | 450 000 | 1 5000 450 000 |
| 100 000 | 150 000 000 000 | 4 500 000 | 150 004 500 000 |
| 1 000 000 | 15 000 000 000 000 | 15 000 000 | 15 000 045 000 000 |
| 10 000 000 | 1 500 000 000 000 000 | 450 000 000 | 1 500 000 450 000 000 |
一些增长函数及其渐进复杂度
| 增长函数 | 阶次 | 标记 |
|---|---|---|
| t(n)=17 | O(1) | 常量型 |
| t(n)=3log n | O(log n) | 对数型 |
| t(n)=20n-4 | O(n) | 线性 |
| t(n)=12n log n+100n | O(n log n) | n log n |
| t(n)=3n²+5n-2 | O(n²) | 平方型 |
| t(n)= 8n^3+3n² | O(n^3) | 立方型 |
| t(n)=2^n+18n²+3n | O(2^n) | O(2^n) |
如果两个算法完成相同任务具有不同的增长函数，比如都是O(n²),那么从运行效率上来说，两者大体上是相等的。
2.3增长函数的比较
2.4 时间复杂度分析
2.4.1 循环运行的复杂度分析
要确定某个算法的阶次，常常需要确定某个特定语句或某个语句集运行的次数。要确定该循环的阶数n，然后要运行的次数乘以它。
count = 1
while (count <n)
{
count *=2
/*复杂度为O(1)的步骤系列*/
}2.4.2 嵌套循环的复杂度分析
用内层循环的复杂度乘以外层循环的复杂度。例如，下面嵌套循环
for(int count =0; count<n; count++)
{
for(int count2 = 0: count2 < n; count2++:)
{
/*复杂度为O(1)的步骤系列*/
}
}其复杂程度为O(n²),内层循环体的复杂度为O(1),并且该内层循环将运行n次。这意味着内层循环的复杂度为O(n).
2.4.3 方法调用的复杂度分析
要确定循环体的阶要先确定调用方法的阶
教材学习中遇到的问题和解决的方法
问题一：为什么java拥有良好的可移植性
1.java作为一种编程语言：源代码可移植性
作为一种编程语言java提供了一种最简单同时也是人们最熟悉的的可移植性--源代码可移植。这就意味着任何一个java程序，不论它运行在何种cpu、操作系统或者java编译器器上都产生一样的结果。这是不是一个新概念，人们使用c或者c++也产生同样的效果，但是使用c或者c++的人们有太多的选择，在许多细节上它都没有严格的定义。这样就导致了同一段程序在不同的环境下会产生不同意外的结果。而java就不同了，由于严密的语义结构，而使编译器不承担这一职责。
2.java作为一个虚拟机：cpu可移植性
大多数编译器产生的目标代码只能运行在一种cpu(如Intel的x86系列),即使那种支持多种编译器的目标代码，也不能产生适合多种cpu的目标代码。 而java不一样，java编译器产生的目标代码针对的是一种并不存在的cpu--java虚拟机，而不是一种具体的cpu。java虚拟机能掩盖不同cpu之间的差别，从而使java-code运行在安装有虚拟机的机器上。
3.java作为一种虚拟的操作系统和图形用户界面：操作系统的可移植。
即使经过重新编译，大多数的用C和C++编写的Windows程序也不能在Unix或Macintosh系统上运行。这是为什么呢?因为程序员在编写Windows程序时使用了大量的WindowsAPI和中断调用，而Windows程序对系统功能的调用与Unix和Macintosh程序有很大的差别，所以除非将全套WindowsAPI移植到其它操作系统上，否则重编译的程序仍不能运行。
JAVA采用了提供一套与平台无关的库函数(包括AWT、UTIL、LANG等等)的方法来解决这个问题。就象JVM提供了一个虚拟的CPU一样，JAVA库函数提供了一个虚拟的GUI环境。
课后习题
练习题
EX2.1 下列增长函数的阶次是多少
a.10n² + 100n + 1000
解答：易知最高次项为10n²故阶次表示为O(n²)
b.10n^3 - 7
解答：易知最高次项为n^3故阶次表示为O(n^3)
c.2^n + 100n^3
解答：易知最高次项为2^n所以阶次表示为O(2^n)
d.n²logn
解答：易知阶次为O(n²logn)
EX2.4
请确定下面代码段的增长函数和阶次
for (int count = 0: count < n: count ++)
for (int count = 0;count2 < n; count2 < n: count2 = count2 +2)
{
System.out.println(count, count2);
}
}解答：因为内循环进行的次数是n/2，外循环进行的次数是n,故增长函数f（n）=n²/2，阶次为O（n）= n²。
EX2.5
请确定下面代码段的增长函数和阶次
for (int count = 0: count < n: count ++)
for (int count = 1;count2 < n; count2 < n: count2 = count2 * 2)
{
System.out.println(count, count2);
}
}解答：因为内循环进行的次数是log 2 n（以二为底n的对数），外循环进行的次数是n次，故增长函数为f（n）= nlog 2 n，阶次为O（n）= nlog 2 n。
结对互评
20172301 郭恺
博客中的问题和值得学习的地方：
郭恺同学的博客中体现了自己的思考，对很多问题进行了解答。充分体现了其认真的态度以及严谨的学习作风。-
20172328 李馨雨
博客中的问题和值得学习的地方。李馨雨同学充分的概括了教材的知识，整个界面简洁大方而不散乱，布局井井有条。各个环节设计充分。学习进度条
| 代码行数（新增/累积） | 博客量（新增/累积） | 学习时间（新增/累积） | 重要成长 | |
|---|---|---|---|---|
| 目标 | 5000行 | 30篇 | 400小时 | |
| 第一周 | 30/30 | 1/1 | 10/10 |
感悟
新学期又开始了又见到了阔别已久的同学，又有了新的助教，感觉这又会是一个不平凡的新学期，又是一个在未知的道路上探索的过程，又要去体会无知---抓狂----懵懂------抓狂--------懵懂的过程希望在新的学期能更好地提升自己。