2017-2018-1 《程序设计与数据结构》第1周学习总结
又是新的一学期本学期的博客将会是干货满满的吧
0.目录
1. 数据结构
1.1 数据结构的定义及基本术语
#### 1.1.1 数据结构的定义 1. **数据结构**是指相互之间存在着一种或多种关系的***数据元素***的集合和该集合中***数据元素之间的关系***组成。 记为：Data_Structure=(D,R) 其中D是数据元素的集合，R是该集合中所有元素之间的关系的有限集合。- Sartaj Sahni在他的《数据结构、算法与应用》一书中称：
“数据结构是数据对象，以及存在于该对象的实例和组成实例的数据元素之间的各种联系。这些联系可以通过定义相关的函数来给出。”
他将数据对象（data object）定义为“一个数据对象是实例或值的集合”。
1.1.2数据结构的基本术语
-
数据（Data）是信息的载体，它能够被计算机识别、存储和加工处理。是客观对象在计算机中的符号表示。它可以是数值数据，也可以是非数值数据。
-
数值数据是一些整数、实数或复数，主要用于工程计算、科学计算和商务处理等；非数值数据包括字符、文字、图形、图像、语音等。
-
数据元素（Data Element）是数据的基本单位。在不同的条件下，数据元素又可称为元素、结点、顶点、记录等。
-
一个数据元素可由若干个数据项（Data Item）组成。这些数据项可以分为两种：一种叫做初等项，这些数据项是在数据处理时不能再分割的最小单位；另一种叫做组合项，它可以再划分为更小的项。
-
数据对象（Data Object）或数据元素类（Data Element Class）是具有相同性质的数据元素的集合。
1.2 数据结构的要素
2. 算法
2.1 算法的定义
#### 2.1.1 一些难懂的定义 1. **算法（Algorithm）**是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。- 算法是在有限步骤内求解某一问题所使用的一组定义明确的操作序列，能够在有限的时间内，对一定的规范的输入获得所要求的输出。
2.1.2 算法的特征
-
有穷性（Finiteness）：算法的有穷性是指算法必须能在执行有限个步骤之后终止；
-
确切性(Definiteness)：算法的每一步骤必须有确切的定义；
-
输入项(Input)：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件；
-
输出项(Output)：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；
-
可行性(Effectiveness)：算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成（也称之为有效性）。
2.1.3 用自己的话来概括
总的来说，算法是一种在计算机中处理问题的策略。这个策略的执行步骤有限，每一步都有明确的定义，有输入与输出，并且每一步都可以在有限时间内完成。
2.2 算法设计
算法在程序中是以伪代码的形式表示的哦~
2.2.1 算法设计的方法
- 分治法
- 递归法
- 动态规划法
- 贪心算法
- 回溯法
- 分支限界法
2.2.2 算法设计的要求
- 正确性：程序不含语法错误；对于输入数据能得出满足要求的结果。
- 可读性
- 健壮性：算法对不合理的数据具有反应能力和处理能力。
- 高效性：时间效率高，存储空间少。
2.3 算法性能度量
> 算法性能的度量有两种方法，**事后统计法**和**事前分析法**。事后统计法可以使用代码运行来统计，不利于较大范围内的算法比较。
事后统计法代码例子：
以下主要讨论事前分析法：
2.3.1 算法效率的影响因素
- 硬件的速度
- 程序选用的语言
- 目标代码的质量
- 问题的规模
- 算法选用的策略
2.3.2 算法时间效率
事前分析法主要关注程序的时间效率和空间效率。其中，我们主要分析时间效率。
算法运行时间 = 算法中每条语句执行时间之和（每条语句执行的时间即该语句执行的次数）
由此，引入时间频度的概念：
时间频度：一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。因此，可将求算法花费时间的问题转化为求算法中语句的执行次数的问题。若问题的规模为n，一个算法中的语句执行次数称为语句频度或时间频度，记为T(n)。
在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。
时间复杂度：一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。
渐进表示法记号：
2.3.3 大O表示法
-
判断阶数
-
单层循环的情况
Determine the order of the following pseudocode fragment.
for i = 1 to n
print i
next i
O(n) : This loop will be executed n times.
- 循环的次数与n无关时为O(1)
Determine the order of the following pseudocode fragment.
for i = 1 to 10
print n
next i
O(1) : This loop will be executed 10 times, regardless of the value of n.
- 出现循环嵌套的情况时，总阶数为各嵌套的积
Determine the order of the following pseudocode fragment.
for i = 1 to n
for j = 1 to n
print i + j
next j
next i
O(n2) : In general, to determine the time complexity of nested loops you multiply the number of times each loop will be executed.
- 当遇到多种情况时，最终结果取几种情况中最差的那种
Determine the order of the following pseudocode fragment.
for j = 1 to n
if (a > b) then
for i = 1 to n
print i
next i
else
for i = 1 to 10
print i
next i
end if
next j
O(n2) : The worst case time complexity of this code fragment is O(n2). In the best case, it is O(n). It is not possible to find an average-case time complexity without more knowledge about a and b. Unless otherwise specified, the order of an algorithm refers to its worst-case time complexity.
- 一种特殊情况
Determine the order of the following pseudocode fragment.
j = 1
for i = 1 to n
j = j * 2
next i
for k = 1 to j
x = x + 1
next k
O(2n) : The first loop the value of 2n is calculated and stored in j. The second loop, therefore, is executed 2n times.
3. 算法与数据结构
3.1 对于概念的总结
算法 + 数据结构 = 程序
算法：处理问题的策略。
数据结构：描述问题信息的数据模型，计算机存储、组织数据的方式，需要用到检索算法与索引技术。
程序：计算机按照处理问题信息的一组指令。