数据结构和算法的基本概念

数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。

 

根据数据元素之间关系的不同特性，通常有下列四类基本结构：

1）集合，结构中的数据元素之间除了“同属一个集合”的关系外，别无其它关系。

2）线性结构，结构中的数据元素之间存在一个对一个的关系。

3）树形结构，结构中的数据元素之间存在一个对多个的关系。

4）图状或网状结构，结构中的数据元素之间存在多个对多个的关系。

 

数据元素之间的逻辑关系又称为数据的“逻辑结构”；数据结构在计算机中的表示又称为数据的“物理结构”，也称为“存储结构”。

数据元素之间的关系在计算机中有两种不同的表示方法：1）顺序映像 2）非顺序映像，并由此得到两种不同的存储结构：1）顺序存储结构 2）链式存储结构。

顺序映像的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。

非顺序映像的特点是借助指示元素存储地址的指针来表示数据元素之间的逻辑关系。

算法的设计取决于选定的数据逻辑结构，而算法的实现依赖于采用的存储结构。

 

 

用计算机解决一个具体问题时，大致需要经过下列几个步骤：

1）从具体问题抽象出一个适当的数学模型。

2）设计一个解此数学模型的算法

3）编写程序，进行测试、调整直至得到最终解答。

 

算法的渐近时间复杂度，简称时间复杂度。“O”表示时间复杂度上限。“”表示时间复杂度下限。当上限等于下限，则是渐近时间复杂度。

 

不同的时间复杂度的比较关系（从左至右复杂度增大）：

O(1) < O( log(n) ) < O(n) < O( n*log(n) ) < O(n^k) < O(2^n) < O(n!)

 

算法的空间复杂度：

若算法所需要的额外空间相对于输入数据量来说是常数，则称此算法为原地工作。