一、基本概念和术语

数据(data)： 对客观事物的符号表示 ，在计算机中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素(data element)：数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。
数据项(data item)： 若干个数据元素组成一个数据元素。数据项是数据的不可分割的最小单位。
数据对象(data object)： 性质相同的数据元素的集合，是数据的一个子集。
数据结构(data structure)： 相互之间存在一种或多种特定关系的数据元素的集合。

结构(structure)： 特定关系的数据元素之间的关系称为结构。
通常有以下四种结构：

1. 集合：
   结构中的数据元素除了 同属于一个集合 外，别无其它关系（与数学中的集合概念一致。

2. 线性结构：
   结构中的数据元素之间存在 一对一 的关系。

3. 树形结构：
   结构中的数据元素之间存在 一对多 的关系。

4. 图状或网状结构：
   结构中的数据元素之间存在 多对多 的关系。

Note: 以上的结构类型均为抽象出来的数学模型。是逻辑上的划分，称之为逻辑结构。

物理结构(physic structure)：数据结构在计算机中的表示，也称存储结构。
物理结构分两种：顺序存储结构 和 链式存储结构。

数据类型(data type)：一个值的集合 和定义在这个值集上的一组操作 的总称。
数据类型分两种： 原子类型 和 结构类型。

抽象数据类型(abstract data type, ADT)：指一个数学模型以及定义在该模型上的一组操作。

---

二、算法和算法分析

1. 算法

算法（algorithm）是对特定问题求解步骤的一种描述，它是指令的有序序列，其中每一条指令表示一个或者多个操作；此外一个算法还有下列5个重要特性：

• 有穷性
  一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，且每一步都在有穷时间（有穷不是纯数学的，而是在实际上合理的，可接受的）内完成。

一直跑不停的算法，要他干嘛?

• 确定性
  算法中每一条指令必须有确切的含义，读者理解是不会产生二义性。并且，在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得到相同的输出。

人读都会有二义性的算法，计算机怎么执行？

• 可行性
  一个算法应当是可行的，即算法中描述的操作都是可以通过以及实现的基础算法执行有限次来实现。

基于某种算法实现的算法，某种就实现不了，那不就一直套下去了？

• 输入
  一个算法有零个或者多个的输入，这些输入取自于某个特定的对象的集合。

有时候没有输入，只想hello world？

• 输出
  一个算法有一个或多个的输出，这些输出是同输入有着某些特定关系的量。

没有输出的算法，比如单纯while(1)，这叫语句序列吧？

2. 算法设计的要求

通常设计一个“好”的算法应考虑以下目标：

• 正确性（correctness）
  算法应当满足具体问题的需求。“正确”一词的含义在通常的用法中很大差别，大体分为一下四个层次：
  • A. 程序不含语法错误
  • B. 程序对于几组输入数据能够得出满足规格说明要求的结果
  • C. 程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满 足规格要求说明的结果
  • D. 程序对于一切合法的输入都能产生满足规格说明要求的结果

显然，达到第D层意义下的正确是极为困难的，所有不同输入数据的数量大得惊人，逐一验证的方法是不现实的。对于大型软件需要进行专业测试，而一般情况下，通常以第C层意义的正确性作为衡量一个程序是否能合格的标准。

• 可读性（readability）
  算法主要是为了人的阅读与交流，其次才是机器执行。可读性好有助于人对算法的理解；晦涩难懂的程序易于隐藏较多错误，难以调试和修改。

• 健壮性（robustness）
  也称鲁棒性。当输入数据非法时，算法也能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。

• 效率与低存储量需求（efficiency & less storage）
  通俗的说，效率指的是算法执行的时间。对于同一个问题如果有多个算法，执行时间段的算法效率高。存储量需求指算法执行过程中所需要的最大存储空间，同一问题的不同算法，占用存储空间小的更优。效率与低存储量需求这两者都与问题的规模有关。

3. 算法效率的度量

度量方法有两种：事后统计的方法，事前分析估算的方法。
事后统计受计算机软硬件环境和需要提前编制统计程序等一系列问题的困扰，常常不采用该方法。常常采用事前分析估算的方法来度量一个算法的执行效率。

• 高级语言所写程序运行时间取决于：
  算法的策略、问题的规模、书写程序的语言、编译程序所产生的机器代码的质量、机器执行指令的速度。

4. 算法的时间复杂度

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n),记作：

T(n) = O(f(n))

它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度(asymptotic time complexity)，简称时间复杂度。

注： “O”的形式定义为：若f(n)是正整数n的一个函数，则Xn = O(f(n)) 表示存在一个正的常数M，使得当n>=n0时都满足|Xn| <= M|f(n)|。

• 上诉式子表示，存在某个值，Xn与f(n)存在常倍数关系，即增长率相同。

5. 算法的存储空间需求

类似与算法的时间复杂度，算法所需存储空间内的度量空间复杂度(space complexity)可以记作：

S(n) = O(f(n)

• 若额外的空间相对于输入数据量来说是常数，则称此算法为原地工作。

明天更新线性表~