本文共 5155 字,大约阅读时间需要 17 分钟。
数据结构和算法系列共八篇
为什么要学习开始数据结构?
推荐网址
再介绍个工具
什么是数据、数据项、数据元素、数据对象?
数据:是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。比如:数值数据、字符、字符串、声音、图像等
数据对象(data object )是性质相同的数据元素的集合,是数据的子集。(比如:数据库一张表)
数据元素(data element )是数据的基本单位,是数据集合的个体,通常由若干个数据项组成,在计算机程序中通常作为一个整体来进行处理。(比如:数据库一张表里的一行记录)
数据项(data item)具有原子性,是不可分割的最小数据单位。(比如:数据库一张表里的一行记录里的某个列数据)
数据结构(data structure )是指相互之间存在一种或多种特定关系的数据元素的集合。(按照表现形式不同分为)
- 逻辑结构(数据结构的逻辑层面)
- 存储结构(计算机世界的物理层面)
数据结构=逻辑结构+存储结构+运算
数据的逻辑结构指数据元素之间的逻辑关系,而不是物理上。
分类1:线性结构和非线性结构
线性结构 (1对1)
比如:排队,有头有尾,中间一个挨着一个。
非线性结构 (1对多,多对多)
相对应于线性结构,非线性结构的逻辑特征是一个结点元素可能对应多个直接前驱和多个直接后继。比如:树(二叉树等),公司组织关系,地铁交通图
分类2:集合结构、线性结构、树状结构、网络结构
set,元素之间没有关系独立的,没有重复
数据结构中线性结构指的是数据元素之间存在着1:1的线性关系的数据结构。
除了一个数据元素以外每个数据元素有且仅有一个直接前驱元素,但是可以有多个直接后续元素。特点是数据元素之间是1:n的联系
每个数据元素可以有多个直接前驱元素,也可以有多个直接后续元素。特点是数据元素之间是n:n的联系
数据的存储结构主要包括数据元素本身的存储以及数据元素之间关系表示,是数据的逻辑结构在计算机中的表示。(物理的,逻辑在物理上的体现)
常见的存储结构有顺序存储,链式存储,索引存储,以及散列存储。
把逻辑上相邻的节点存储在物理位置上相邻的存储单元中,结点之间的逻辑关系由存储单元的邻接关系来体现
数据元素的存储对应于一块连续的存储空间,数据元素之间的前驱和后续关系通过数据元素。(java中的数组,ArrayList)优点:
缺点:
数据元素的存储对应的是不连续的存储空间,每个存储节点对应一个需要存储的数据元素。(逻辑上相邻的节点物理上不必相邻)
数据元素的存储对应的是不连续的存储空间。(java中的LinkedList)优点:
缺点:
除建立存储结点信息外,还建立附加的索引表来标识结点的地址。
书本的目录,字典的拼音和部首,数据库的表的索引,lucene、es等
根据结点的关键字直接计算出该结点的存储地址 HashSet HashMap
算法是针对于存储结构操作的,而不是逻辑结构。这是很显然的(逻辑是虚拟的,而存储是实际的)。
算法四种境界
学习数据结构不是一日之功,对于初学者要达到境界2,后续学习和工作中不断研究学习
是指令的集合,是为解决特定问题而规定的一系列操作。
算法是利用计算机解决问题的处理步骤,简而言之,算法就是解决问题的步骤。
算法通常来说具有以下特性:
示例:如何求0+1+2+3+…100=?
对于一个问题,可能有多种方法来解决这个问题。
- 高斯解法
- 循环
- 递归求解
出现这么算法,那那种算法好了?
这就引出了算法的优劣判断方法:
- 空间复杂度: 指执行这个算法所需要的内存空间
- 时间复杂度: 指执行算法所需要的计算工作量
Space Complexity
空间复杂度是对一个算法在运行过程中临时占用的存储空间大小的量度,一般也作为问题规模n的函数,以数量级形式给出S(n) = O(g(n))
算法的存储量包括:
输入数据所占空间只取决于问题本身,和算法无关,不参与计算。
演示1
int fun(int n){ int i,j,k,s; s=0; for (i=0;i<=n;i++) for (j=0;j<=i;j++) for (k=0;k<=j;k++) s++; return(s);}
不管for循环了多少层,但是只定义了几个变量。没有参数多余的空间。空间复杂度均为S(n)=O(1)。
演示2
void fun(int a[],int n,int k) //数组a共有n个元素 { int i; if (k==n-1) for (i=0;i
递归算法,每次调用本身都要分配空间,fun(a,n,0)的空间复杂度为O(n)。
上面两种算法比较:
Time Complexity
一个算法需要花多少时间,可能跟机器的位数、性能等有关系,而且每次跑花的时间都可能不一样。
但是一点它们是相同的,那就是算法语句执行的次数是固定的。可以这么认为:哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度,表示为
T(n)
,n表示问题的规模
有时只像知道它变化时呈现什么规律(比如:指数级的),而不是具体的次数,此时引入时间复杂度。
上面介绍过时间频度T(n)
,当某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。
T(n)=O(f(n))
其中:O(f(n))
为算法的渐进时间复杂度,简称时间复杂度
时间复杂度就是时间频度去掉低阶项和首项常数
比如: T ( n ) = 99 n 3 + 10000 n 2 + 1 T(n)=99n^3+10000n^2+1 T(n)=99n3+10000n2+1 和 T ( n ) = n 3 T(n)=n^3 T(n)=n3,它们的时间复杂度是一样的都是 T ( n ) = O ( n 3 ) T(n)=O(n^3) T(n)=O(n3)
用哪个计算?(最坏时间复杂度还是平均时间复杂度?)
最坏情况下的时间复杂度称最坏时间复杂度。一般不特别说明,讨论的时间复杂度均是最坏情况下的时间复杂度。
这样做的原因是:最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界,这就保证了算法的运行时间不会比任何更长。 在最坏情况下的时间复杂度为T(n)=O(n),它表示对于任何输入实例,该算法的运行时间不可能大于O(n)。
平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下,算法的期望运行时间。鉴于平均复杂度
根本没有必要计算时间频度,即使计算处理还要忽略常量、低次幂和最高次幂的系数,所以可以采用如下简单方法:
算法中执行次数最多的那条语句就是基本语句,通常是最内层循环的循环体。
只需计算基本语句执行次数的数量级,这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可,
可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析,并且使注意力集中在最重要的一点上:增长率。
O
记号表示算法的时间性能将基本语句执行次数的数量级放入大
O
记号中。
演示1
int count=0;
时间复杂度为O(1)
演示2
int count=0, count=1; ...省略n行...int count=1000;
不管多少行,时间复杂度为O(1)
演示3
int n=10000, count=0;for (int i=1; i<=n; i++) count++;
for循环,不管n是多少值(1、1百、1万、一亿),只关注是一个for循环,时间复杂度为O(n)
演示4
int n=10000, count=0;for (int i=1; i<=n; i*=2) count++;
for循环,但是按着2幂来出现(1、2、4、8、16、32…)
时间复杂度为 O ( log 2 n ) O(\log_2^{n}) O(log2n)的循环语句。
演示5
int n=1000, count=0;for (int i=1; i<=100n; i++) for (int j=1; j<=10n; j++) count++;
for循环,不管n是多少值(1、1百、1万、一亿),只关注是两个for循环,时间复杂度为 O ( n 2 ) O(n^2) O(n2)
演示6
int n=10000, count=0;for (int i=1; i<=n; i*=2) for (int j=1; j<=n; j++) count++;
for循环,不管n是多少值(1、1百、1万、一亿),只关注是两个for循环,但是其中一个按着2的幂来,时间复杂度为 O ( n log 2 n ) O(n\log_2^{n}) O(nlog2n)
常用的时间复杂度级别
以下六种计算算法时间的多项式是最常用的。其关系为:O(1) < O(logn) < O(n) < O(nlogn) < O(n2)<O(n3)
O(2n)<O(n!)<O(nn)
当n取得很大时,指数时间算法和多项式时间算法在所需时间上非常悬殊。
能读到文章最后,首先得谢谢您对本文的肯定,你的肯定是对博主最大的鼓励。
你觉本文有帮助,那就点个👍
你有疑问,那就留下您的💬 怕把我弄丢了,那就把我⭐ 电脑不方便看,那就把发到你📲转载地址:http://rzhws.baihongyu.com/