数据结构基础知识
基本数据类型
编程语言内置支持的数据类型，无须调用外部模块即可使用。基本数据类型总是包括整数、浮点数以及对它们的一般性操作 （加法、减法、除法），大部分语言还内置支持在变量中存储文本、布尔 值以及其他简单的数据类型。
而《数据结构与算法分析—C语言描述》讲的则是那些内置数据类型以外的知名抽象数据类型，它们是基本数据类型的补充。
一、数学知识
指数
\(X^AX^B = X^{A+B}\)
\(X^A/ X^B = X^{A-B}\)
\({X^A}^B = X^AB\)
\(X^N + X^N = 2*X^N != X^{2N}\)
\(2^N + 2^N = 2^{N+1}\)
对数
仅当 \(logxB=A\) 时 \(x^A=B\)
在 \(logxB=A\) 表达式中:
\(x\): 底数
\(B\): 真数
\(A\): 以 \(x\) 为底 \(B\) 的对数
在计算机科学中，当底数省略时，默认为2
常数 \(e\): 单位时间内增长率为100%的情况下，在单位时间内复合增长率的最大值为 \(e\)， \(e\) 是一个无理数， 约为2.7182804 详解文章
推导1
\(设:\)
\(C>0\)
\(X=logCB\)
\(Y=logCA\)
\(Z=logAB\)
\(可以得出:\)
\(C^X=B\)
\(C^Y=A\)
\(A^Z=B\)
\(因为:\)
\(C^Y=A\)
\(A^Z=B\)
\(所以:\)
\({C^Y}^Z=B\)
\(因为:\)
\(C^X=B\)
\(所以:\)
\({C^Y}^Z=C^X\)
\(所以:\)
\(X=YZ\)
\(所以:\)
\(Z=X/Y\)
\(根据设得出以下公式:\) \(logAB = logCB / logCA\)
推导2
\(设:\)
\(X=log A\)
\(Y=log B\)
\(Z=log AB\)
\(可以得出:\)
\(2^X=A\)
\(2^Y=B\)
\(2^Z=AB\)
\(因为:\)
\(2^X=A\)
\(2^Y=B\)
\(所以:\)
\(2^X * 2^Y = AB\)
\(2^{X+Y} = AB\)
\(因为:\)
\(2^Z=AB\)
\(所以:\)
\(2^Z = 2^{X+Y}\)
\(所以:\)
\(Z = X+Y\)
\(根据设得出以下公式:\) \(log AB = log A + log B\)
\(同理:\) \(log A/B = log A - log B\)
推导3
\(设:\)
\(A = 2 ^ N\)
\(则:\)
\(log A = N\)
\(则:\)
\(A^B = {2^N}^B = 2^{NB}\)
\(所以:\)
\(log A^B = NB\)
\(因为:\)
\(log A = N\)
\(根据设得出以下公式:\) \(B log A = log A^B\)
简单公式:
\(log X < X (X>0) 对数小于真数\)
\(log 1=0 |2^0=1\)
\(log 2=1 |2^1=2\)
\(log 1024=10 |2^{10}=1024\)
\(log 1048576=20 |2^{20}=1048576\)
级数
级数是数学中一个有穷或无穷的序列之和
二、策略
迭代
递归
蛮力法
回溯法
启发法
分治法
动态规划
分支定界法
三、复杂度
四、ADT
对于给定的数据类型， 抽象数据类型（ADT）是一组有意义的操作规范。ADT 定义的接口用于处理保存给定类型数据的变量——数据在内存中存储与操作的所有细节都被隐藏起来。
- 例如列表这个数据结构，我们不仅需要一个列表结构，还需要对其进行创建、访问、删除、添加、插入等操作，这些过程（或者方法、函数 都是一个意思）的定义（名称与用途）就是一种列表 ADT。
ADT的优点
-
简单：ADT 使代码更容易理解和修改。不考虑数据处理过程中的各种细节，我们可以专注于从宏观层面考虑算法求解问题的过程。
-
灵活：可以采用不同的方法在内存中构造数据，因此可以为同一种数据类型创建不同的数据处理模块。应根据实际情况做出最佳选择。由于实现相同 ADT 的模块将提供相同的过程，只要换用不同的数据处理模块，就能改变数据的存储与操作方式。汽车与之类似：电动汽车与燃油汽车的驾驶界面并无不同，任何会开车的人都能毫不费力地驾驶两种汽车。
-
可重用性：如果多个项目需要处理相同类型的数据，可以在这些项目中使用相同的数据处理模块。
-
组织：我们经常需要对数字、文本、地理坐标、图像等各种数据类型进行操作。为更好地组织代码，可以创建不同的模块，每种模块包含特定于一种数据类型的代码。这就是所谓的关注点分离 ，即应将处理相同逻辑问题的代码置于相互独立的模块中。如果实现不同功能的代码纠缠在一起，就会出现所谓的面条式代码 。
-
便捷：我们可以获取他人编写的数据处理模块， 研究如何使用由 ADT 定义的过程，之后马上就能利用这些过程对其他数据类型的变量进行操作，而无须了解数据处理模块的工作机制。
-
漏洞修复：如果使用的数据处理模块毫无瑕疵，代码将免受数据处理错误的困扰。如果发现数据处理模块中存在漏洞，修复它就意味着修复了所有受该漏洞影响的代码。