1.数据结构与算法分析概述

2019-03-13 本文已影响0人 a9f9e33f60c3

1.数据结构的概念

存储数据和数据之间的关系的一个集合。不仅存储数据，还支持数据的访问和操作（添加，删除）。

Java语言描述：

抽象数据类型（ADT），带有一组操作的一些对象的集合

2.数据结构的概念关系图

数据结构概念关系图

2.1顺序存储与链式存储比较：

顺序存储：开辟一段连续空间存储顺序表，相邻数据的地址也是相邻的，要求存储内存中存储单元地址是连续的。

优点：存储密度大（=1），存储空间利用率高，便于查找数据（因为所有数据都按顺序排放，想查询第几个就可以查询第几个）

缺点：不便于插入和删除，因为插入需要在指定位置插入，后面的数据都要相应后移，删除时后面所有数据要相应前移。

链式存储：相邻数据可以随意存放，一个存储单元中不仅存储节点值，还存储指向下一节点的指针（java中描述的是下一节点的链）

优点：便于删除和插入数据，插入数据时只需要将上一个位置的指针指向该数据，将该数据的指针指向下一位置；删除时只需将指向该节点的上一节点的指针指向该节点指向的下一节点数据。

缺点：存储密度小（<1），存储空间利用率低，因为不仅存储数据还要存储指针，数据的查找不方便

2.2数据逻辑结构概述（后面会详细学习）：

集合：数据结构中的元素除了存储于一个集合中，没有其他的关系；

线性结构:数据结构中的元素存在一对一的关系；

树形结构：数据结构中的元素存在一对多的关系；

图形结构：数据结构中的元素存在多对多的关系；

3.算法分析

算法是为求解一个问题需要遵循的、被清除指定的简单指令的集合。一种算法若是正确的，重要的一步便是确定该算法的时间复杂度和空间复杂度。

3.1时间复杂度（执行该算法所需要的计算量，一般考虑最坏情况的运行时间而非平均运行时间）

算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得T(n)/f(n)的极限值（当n趋近于无穷大时）为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

随着模块n的增大，算法执行的时间的增长率和 f(n) 的增长率成正比，所以 f(n) 越小，算法的时间复杂度越低，算法的效率越高。 f(n)是T(n)的一个上界。

重要法则：

1）若T1(n)=O(f(n))，T2(n)=O(g(n))，则T1(n)+T2(n)=O(f(n)+g(n));

2）若T1(n)=O(f(n))，T2(n)=O(g(n))，则T1(n)*T2(n)=O(f(n)*g(n));

注意：

1）不能将常数或者低阶项放进大O

2) 总能够通过计算极限来确定两个函数的相对增长率

3.2时间复杂度的计算

在计算时间复杂度的时候，先找出算法的基本操作，然后根据相应的各语句确定它的执行次数，再找出 T(n) 的同数量级（它的同数量级有以下：1，log2n，n，n log2n ，n的平方，n的三次方，2的n次方，n!），找出后，f(n) = 该数量级，若 T(n)/f(n) 求极限可得到一常数c，则时间复杂度T(n) = O(f(n))。

简化分析：抛弃一些前导常数，抛弃低阶项，要计算的就是大O运算时间。

一般法则：

1）for循环：运行时间至多是for循环内部语句的运行时间乘以迭代次数。

2）嵌套for循环：从里向外分析，循环内部语句执行时间乘以该组所有for循环大小。

3）顺序语句：各个语句运行时间求和即可，这意味着，最大值便是所得运行时间。

4）递归语句：求解一个递推关系

3.3最大子序列和的问题求解（演示不同时间复杂度的算法）

问题描述：给定一组整数，A1,A2,A3,..AN,求 $\sum_{k=i}^j$ Ak的最大值。