ds-1

第一章绪论

1.1数据结构基本概念

*数据结构：是指数据元素及其相互关系的集合

​ 这种相互关系即数据的组织形式，可分为数据的逻辑结构（集合、线性、树、图）和数据的储存结构（物理结构）（顺序储存结构、链接~）。

1.2算法和算法评价

1.2.1算法的基本概念

a）算法

​ 是指计算机求解特定问题的方法和步骤，是指令的有限序列。通常一个问题可以有多种算法，一个给定算法解决一个特定的问题。

b）算法的特性

1. 输入：一个算法有0个好多个输入（即算法可以无输入），这些输入通常取自于某个特定的对象集合
2. 输出：一个算法有一个或多个输出（即算法必须要有输出），通常输出与输入之间有着某种特定的关系。
3. 有穷性：对于任何合法的输入，一个算法必须在执行又穷步之后结束，且每一步都在有穷时间内完成。
4. 确定性：算法中的每一条指令都必须有确切的含义，即不存在二义性。而且，在任何条件下，给定的算法对于相同输入只能得到相同的输出。
5. 可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。

c）算法的评价

1. 正确性。算法能满足具体问题的需求，即对于任何合法的输入，算法都会得出正确的结果。

2. 健壮性（鲁棒性）：算法对非法输入的抵抗能力，即对于错误的输入，算法应能识别并作出处理，而不是产生错误动作或陷入瘫痪。

3. 可读性：好的算法应该便于人们理解和相互交流。可读性好的算法有助于人们对算法的理解；反之难懂的算法易于隐藏错误，且难于调试和修改了。

4. 高效率：算法的效率通常是指算法的执行时间，对于同一个问题，如果有多个算法可以使用那么执行时间短的算法效率高。

5. 低储存空间需求：算法需要的储存空间是指算法在执行过程中所需要的最大的储存空间，它与问题规模有关。一个“好”算法应该再用较少的辅助空间。

1.2.2算法的时间复杂度

1. 概念：算法执行过程中所需要的基本运算次数。

   

1.2.3算法的空间复杂度

1. 概念：空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，*记做S(n)=O(f(n))*。
2. 算法分析的两个主要方面？
   • 算法分析的两个主要方面是时间复杂度和空间复杂度

1.3递归算法

• 算法概述

递归算法是一种直接或者间接调用自身函数或者方法的算法。说简单了就是程序自身的调用。

• 算法实质

递归算法就是将原问题不断分解为规模缩小的子问题，然后递归调用方法来表示问题的解。（用同一个方法去解决规模不同的问题）

• 算法思想

递归算法，顾名思义就是有两个大的阶段：递和归，即就是有去（递去）有回（归来）。

​ 递去：将递归问题分解为若干个规模较小，与原问题形式相同的子问题，这些子问题可以用相同的解题思路来解决

​ 归来：当你将问题不断缩小规模递去的时候，必须有一个明确的结束递去的临界点（递归出口），一旦达到这个临界点即就从该点原路返回到原点，最终问题得到解决。

• 编写递归算法的思路是什么？

  递归思维是一种从下向上的思维方式，使用递归算法往往可以简化我们的代码，而且还帮我们解决了很复杂的问题。递归算法的难点就在于它的逻辑性，一般设计递归算法需要考虑以下几点:

1. 明确递归的终止条件
2. 提取重复的逻辑，缩小问题的规模不断递去
3. 给出递归终止时的处理办法