数据结构与算法分析1.绪论

---

点击进入我的博客

1 主要内容

在解决问题的过程中，写出一个工作的程序并不够，因为一旦程序要处理的数据集变得巨大，那么运行时间就变成了重要的问题。这时需要就需要对大量输入的时候对程序的运行时间做出估计，尤其是如何在尚未具体编码的情况下比较两个程序的运行时间。我们还将看到彻底改进程序速度以及确定程序瓶颈的方法。

2 基本概念和术语

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

3 基本结构

1. 集合：结构中的数据元素除了“同属一个集合”的关系之外，别无其他关系
2. 线性结构：结构中的数据元素之间存在一个对一个的关系
3. 树形结构：结构中的数据元素之间存在一个对多个的关系
4. 图状结构或网状结构：结构中的数据元素之间存在多个对多个的关系

4 算法和算法分析

4.1 算法

算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作，它有5个特性：

1. 有穷性：一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，且每一步都可在有穷时间内完成。
2. 确定性：算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。即对于相同的输入只能得出相同的输出。
3. 可行性：一个算法是可行的，即算法中描述的操作都是吋以逋过已经实现的基本运算执行有限次来实现的。
4. 输入：一个算法有零个或多个的输入，这些输入取自于某个特定的对象的集合。
5. 输出：一个算法有一个或多个的输出，这些输出是同输入有着某种特定关系的量。

4.2 算法设计的要求

1. 正确性：算法应当能够正确地解决求解问题。
2. 可读性：算法应当具有良好的可读性，以助于人们理解。
3. 健壮性：当输入非法数据时，算法也能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。
4. 效率与低存储量需求：效率是指算法执行的时间，存储量需求是指算法执行过程中所需要的最大存储空间，这两者都与问题的规模有关。

4.3 时间复杂度

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间度量记作：T(n) = O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的时间复杂度。

4.4 空间复杂度

一个算法的空间复杂度S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数：S(n) = O(f(n))。

5 递归

当一个函数用他自己来定义时就称为是递归的（recursive）的。

递归的基本法则

1. 基准情形：必须总要有某些基准的情形，它们不能用递归就能求解。
2. 不断推进：对于那些要递归求解的情形，递归调用必须总能朝着一个基准情形不断推进。
3. 设计法则：假设所有的递归调用都能运行。
4. 合成效益法则：在求解一个问题的同一实例时，切勿在不同的递归调用中做重复的工作。

6 抽象数据类型

抽象数据类型（abstract data type，ADT）是带一组操作定一些对象的集合。