Algorithm and Data Structure

算法与数据结构

2023-06-18 约 885 字预计阅读 2 分钟

结构性数据结构对其数据元素之间的相关关系都做了一些明确规定，元素之间确实满足某种关系（如线性关系等），通常遵循该关系对数据进行存储方式设计和实现增删改查操作，典型的有集合结构、线性结构、层次结构、树形结构、图结构等。

功能性数据结构并未对其元素的相互关系提出任何结构性的规定，而是要求实现某种计算中非常有用的功能，同时只要求具备数据存储和使用（元素访问）功能，对其数据如何存储、元素之间如何关联，并不做明确要求，因此该种支持元素存储和访问的数据集结构也被称为容器。

由于只有功能性要求，功能性数据结构理论上可以使用任何技术实现。而在实际使用中，通常是首先把功能性数据结构映射到结构性数据结构，而后采用相应的实现技术，如栈和队列通常使用线性结构，以列表或者链表方式具体实现。

枚举法

根据具体问题枚举出各种可能，从中选取有用信息或者问题的解。
贪心法

根据问题的信息尽可能做出部分的解，并基于部分解逐步扩充得到完整的解。
分治法

将复杂问题分解为相对简单的子问题，分别求解，最后通过组合起子问题解的方式得到原问题的解。
回溯法

专指通过搜索的方式求解，如果问题很复杂，没有清晰的求解路径，可能就需要分步骤进行，由于每一步骤都有很多选择，因此只能采用试探的方式，根据实际情况选择一个可能方向，然其后续步骤无法进一步求解时，就需要退回到前面的步骤，选择其他求解路径，如此往复的动作称作回溯。
动态规划法

在一些复杂情况下，问题求解很难直截了当进行，因此需要在前面的步骤中积累信息，在后续步骤中根据已知信息，动态选择一致的最好求解路径（同时可能进一步积累信息），如此方式称作动态规划。
分支限界法

作为搜索方法的一种改良形式，如果在搜索过程中可以得到一些信息，确定某些可能的选择实际上并不真正有用，就可以及早将其删除，以缩小可能的求解空间，加速问题求解过程。

算法复杂度分析包括时间复杂度和空间复杂度。