数据结构及算法总结（概述）

淡淡的烟草味﹌ 2022-05-31 00:19 228阅读 0赞

**开头瞎逼逼**

程序的本质：程序是为了实际的问题而存在的，从本质上而言，程序是解决问题的步骤描述。

首先要理解实际问题，确认问题类型（如：数值计算、求最小值），确认求解的步骤（如：打开文件、读数据、关闭文件、计算和）。

优秀的开发者需要追求代码的高“性价比”，用尽量少的内存空间解决问题，用尽量少的步骤解决问题。

程序是为了具体问题而存在的，程序需要围绕问题的解决进行设计，同一个问题可以有多种解决方案。

**数据结构-->数据的艺术**

数据结构主要研究非数值计算程序问题中的操作对象以及它们之间的关系。

数据 – 程序的操作对象，用于描述客观事物。

数据的特点：。1.可以输入到计算机；2.可以被计算机程序处理。

数据是一个抽象的概念，将其进行分类后得到程序设计语言中的类型。如：int，float，char等等。

数据对象 – 性质相同的数据元素的集合。

数据元素 – 组成数据的基本单位。

数据项：一个数据元素由若干数据项组成。

![SouthEast][]

![SouthEast 1][]

数据元素之间不是独立的，存在特定的关系，这些关系即结构。

数据结构指数据对象中数据元素之间的关系。如：数组中各个元素之间存在固定的线性关系。

编写一个“好”的程序之前，必须分析待处理问题中各个对象的特性，以及对象之间的关系。

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

按照视点的不同，数据结构可以分为逻辑结构和物理结构。

![SouthEast 2][]

集合结构：数据元素之间没有特别的关系，仅同属相同集合。  
线性结构：数据元素之间是一对一的关系。  
树形结构：数据元素之间存在一对多的层次关系。  
图形结构：数据元素之间是多对多的关系。

![SouthEast 3][]

物理结构：逻辑结构在计算机中的存储形式。  
顺序存储结构：将数据存储在地址连续的存储单元里。  
链式存储结构：将数据存储在任意的存储单元里，通过保存地址的方式找到相关联的数据元素。

![SouthEast 4][]

**算法-->程序的灵魂**

**程序 =数据结构 \+ 算法**

程序并不是越短越好，也不是别人看不懂就证明自己很厉害。

数据结构只是静态的描述了数据元素之间的关系。

高效的程序需要在数据结构的基础上设计和选择算法。

![SouthEast 5][]

**算法的定义：**

算法是特定问题求解步骤的描述，在计算机中表现为指令的有限序列。

算法是独立存在的一种解决问题的方法和思想。

对于算法而言，语言并不重要，重要的是思想。

**算法的特性：**

输入：算法具有0个或多个输入。  
输出：算法至少有1个或多个输出。  
有穷性：算法在有限的步骤之后会自动结束而不会无限循环。  
确定性：算法中的每一步都有确定的含义，不会出现二义性。  
可行性：算法的每一步都是可行的。

**算法设计的准则**

正确性  
1.算法对于合法数据能够得到满足要求的结果。  
2.算法能够处理非法输入，并得到合理的结果。  
3.算法对于边界数据和压力数据都能得到满足要求的结果。  
注意：正确性是算法最需要满足的基本的准则，但是作为计算机程序，不可能无限制的满足这条准则。

可读性：算法要方便阅读，理解和交流。

健壮性：算法不应该产生莫名其妙的结果。

高性价比：利用最少的时间和资源得到满足要求的结果。  
注意：算法可读性是最容易被忽视的，然而，程序是写给人看的，而不是计算机。

算法是为了解决实际问题而设计的，数据结构是算法需要处理的问题载体，数据结构与算法相辅相成。

**审判程序的灵魂-->算法的优劣**

**算法效率的度量**

1.事后统计法：比较不同算法对同一组输入数据的运行处理时间。  
缺陷  
1.1.为了获得不同算法的运行时间必须编写相应程序；  
1.2.运行时间严重依赖硬件以及运行时的环境因素；  
1.3.算法的测试数据的选取相当困难。  
事后统计法虽然直观，但是实施困难且缺陷多，一般不予考虑。

2.事前分析估算:依据统计的方法对算法效率进行估算。  
影响算法效率的主要因素  
 2.1.算法采用的策略和方法；  
 2.2.问题的输入规模；  
 2.3.编译器所产生的代码；  
 2.4.计算机执行速度。

**算法的时间复杂度-->执行时间**

**算法效率的简单估算**

**1**

**![SouthEast 6][]**

![SouthEast 7][]

**3**

![SouthEast 8][]

三种求和算法中求和的关键部分的操作数量分别为2n, n和1。  
随着问题规模n的增大，它们操作数量的差异会越来越大，因此实际算法在时间效率上的差异也会变得非常明显。

![SouthEast 9][]

![SouthEast 10][]

判断一个算法的效率时，往往只需要关注操作数量的最高次项，其它次要项和常数项可以忽略。

**大O表示法**  
1.算法效率严重依赖于操作(Operation)数量；  
2.在判断时首先关注操作数量的最高次项；  
3.操作数量的估算可以作为时间复杂度的估算。  
O(5) = O(1)  
O(2n + 1) = O(2n) = O(n)  
O(n2  \+ n + 1) = O(n2)  
O(3n3\+1) = O(3n3) = O(n3)

**常见时间复杂度类型**

![SouthEast 11][]

关系：

![SouthEast 12][]

当算法在最坏情况下仍然能满足需求时，可以推断，算法的最好情况和平均情况都满足需求。在没有特殊说明时，

我们所分析的算法的时间复杂度都是指最坏时间复杂度。

**算法的空间复杂度-->内存使用情况**

复杂度通过计算算法的存储空间实现，

S(n) = O(f(n))  
其中，n为问题规模，f(n)为在问题规模为n时所占用存储空间的函数

大O表示法同样适用于算法的空间复杂度，当算法执行时所需要的空间是常数时，空间复杂度为O(1)。

多数情况下，算法执行时所用的时间更令人关注。如果有必要，可以通过增加空间复杂度来降低时间复杂度。同理，也可以通过

增加时间复杂度来降低空间复杂度。

在实现算法时，需要分析具体问题对执行时间和空间的要求。

[SouthEast]: /images/20220531/e2e8c3e1387f4cc6937b0e405bff23ec.png
[SouthEast 1]: /images/20220531/fc4858e94c334f0a9ce6b0c86e4e4fcf.png
[SouthEast 2]: /images/20220531/f99cd6161cd141daa2042101dd709a9c.png
[SouthEast 3]: /images/20220531/6e1ba35875e1411181f01b6c20a2b564.png
[SouthEast 4]: /images/20220531/25fc18a4173949328cc6628705dd402f.png
[SouthEast 5]: /images/20220531/3b5814d982ee4304808e69bac3781a83.png
[SouthEast 6]: /images/20220531/bb6d18a7b75b457ca812de0d9ad84400.png
[SouthEast 7]: /images/20220531/640c979706184b40a0aaca662e50eb14.png
[SouthEast 8]: /images/20220531/a7150583074842e1bc6a9818230ba959.png
[SouthEast 9]: /images/20220531/b4328df6b2534c03805e59ee822f13ba.png
[SouthEast 10]: /images/20220531/cedd047cc49d42a6be82384d82722c98.png
[SouthEast 11]: /images/20220531/b66d4454fc684ca099556346973b1eb7.png
[SouthEast 12]: /images/20220531/2975d4a77a2c493397b1de23d1ca4922.png