作者:whisper
链接:http://proprogrammar.com:443/article/dataStructure_introduction
声明:请尊重原作者的劳动,如需转载请注明出处
说明:本文主要说了什么是数据结构,数据结构的基本概念和术语及什么是算法和算法分析(时间复杂度,空间复杂度)
概括说,数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。
基本概念和术语
数据元素(Data Element):是数据的基本单位,在程序中通常作为一个整体进行考虑和处理。
数据结构(Data Structure) :有一个特性相同的数据元素的集合,如果在数据元素之间存在一种或多种特定的关系,则称为一个数据结构。带结构的数据元素的集合指的是数据元素之间存在的关系。数据结构是相互之间存在着某种逻辑关系的数据元素的集合。
从关系或结构分,数据结构可归结为以下四类:
数据结构是一个二元组 Data_Structures = (D, S),其中:D 是数据元素的有限集, S 是 D 上关系的有限集。
逻辑结构是对数据元素之间的逻辑关系的描述,它可以应一个数据元素的集合和定义在此集合上的若干关系来表示;
数据的存储结构—逻辑结构在存储器中的映象
用二进制位的位串表示数据元素。
A = (101)8 = (001000001)2
1)顺序映象
例如:令 y 的存储位置和 x 的存储位置之间差一个常量 C。而 C 是一个隐含值, 整个存储结构中只含数据元素本身的信息。
链式存储方式:以附加信息(指针)表示后继关系。需要用一个和 x 在一起的附加信息(指针)指示 y 的存储位置。
3)索引存储方式
除数据元素存储在一地址连续的内存空间外,尚需建立一个索引表,兼有静态和动态特性。
通过散列函数和解决冲突的方法,将关键字散列在连续的有限的地址空间内,并将散列函数的值解释成关键字所在元素的存储地址。其特点是存取速度快,只能按关键字随机存取,不能顺序存取,也不能折半存取。
数据类型:在一种程序设计语言中,变量所具有的数据种类。
例:在 C 语言中数据类型:
基本类型:整型、浮点型、字符型、指针、枚举型
构造类型:数组、结构、联合
数据对象:某种数据类型元素的集合。
例:整数的数据对象是{…-1,0,1,…} ,英文字符类型的数据对象是{A,B,C,…}
数据对象可以是有限的,也可以是无限的。
数据结构不同于数据类型,也不同于数据对象,它不仅要描述数据类型的数据对象,而且要描述数据对象各元素之间的相互关系。
关于逻辑结构,需特别注意:
(1)逻辑结构与数据元素本身的形式、内容无关。
(2)逻辑结构与数据元素的相对位置无关。
(3)逻辑结构与所含数据元素的个数无关。
(4)逻辑结构与数据的存储无关,它是独立于计算机的。
数据的逻辑结构和存储结构是密切相关的两个方面。
一般地,一种数据的逻辑结构根据需要可用多种存储结构来存储,而采用不同的存储结构,其数据处理的效率往往是不同的。
算法和算法分析
算法
是对特定问题求解步骤的一种描述。算法是指令的有限序列,其中每一条指令表示一个或多个操作。
特性:(1)有穷性(2)确定性(3)可行性(4)输入(5)输出
算法与程序:十分相似,但又有区别。一个程序不一定满足有穷性。程序中的指令必须是机器可执行的,而算法中的指令则无此限制。算法代表了对
问题的解,而程序则是算法在计算机上的特定的实现。一个算法若用程序设计语言来描述,则它就是一个程序。
算法与数据结构:是相辅相承的。解决某一特定类型问题的算法可以选定不同的数据结构,而且选择恰当与否直接影响算法的效率。反之,一种数据
结构的优劣由各种算法的执行来体现。
算法设计要求
评价一个好的算法有以下几个标准:
(1) 正确性(Correctness )
(2)可读性(Readability)
(3)健壮性(Robustness)
(4)效率与存储量需求:效率指的是算法执行的时间;存储量需求指算法执行过程中所需要的最大存储空间。
算法效率的衡量方法和准则
通常有两种衡量算法效率的方法: 事后统计法(缺点:必须执行程序;其它因素掩盖算法本质。) ;事前分析估算法
和算法执行时间相关的因素:
1.算法选用的策略
2.问题的规模
3.编写程序的语言
4.编译程序产生的机器代码质量
5.计算机执行指令的速度
一个特定算法的“运行工作量”的大小,只依赖于问题的规模(通常用整数量n表示),或者说,它是问题规模的函数。
假如,随着问题规模 n 的增长,算法执行时间的增长率和 f(n) 的增长率相同,则可记作:T (n) = O(f(n)) 称 T (n)为算法的(渐近)时间复杂度。
如何估算算法的时间复杂度?
算法 = 控制结构 + 原操作(固有数据类型的操作)
算法的执行时间 =原操作(i)的执行次数×原操作(i)的执行时间
算法的执行时间与原操作执行次数之和成正比
从算法中选取一种对于所研究的问题来说是基本操作的原操作,以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则。
频度:是指该语句重复执行的次数。
f(n)模型例子
常数阶:
例 1:
{++x; s=0;}
将 x 自增看成是基本操作,则语句频度为 1,即时间复杂度为 O(1)。如果将 s=0也看成是基本操作,则语句频度为 2,其时间
复杂度仍为 O(1),即常量阶。
线性阶:
例 2:
for(i=1; i<=n; ++i) {++x;s+=x;}
语句频度为:2n,其时间复杂度为:O(n), 即时间复杂度为线性阶。
对数阶:
例 3:
void f (int n){ int x=1; while (x<n)x=2*x; }
分析:基本运算是语句 x=2*x,设其执行时间为 T(n),则有 2T(n)≤n, 即 T(n)2,n=O(log2 n)。
其时间复杂度为:O(log2n),即时间复杂度为对数阶。
平方阶:
例 4:
for(i=1; i<=n;++i) for(j=1;j<=n;++j) {++x; s+=x;}
语句频度为:2n2,其时间复杂度为:O(n2 ),即时间复杂度为平方阶。
立方阶:
例 5:
for(i=1;i<=n;++i) for(j=1;j<=n;++j){ c[i][j]=0; for(k=1;k<=n;++k)c[i][j]+=a[i][k]*b[k][j]; }
由于是一个三重循环,每个循环从 1 到 n,则总次数为: n×n×n=n3,时间复杂度为 T(n)=O(n3 )
定理:若 A(n)=amnm +am-1nm-1 +…+a1n+a0 是一个 m 次多项式,则 A(n)=O(nm)
例 6:
for(i=2;i<=n;++i) for(j=2;j<=i-1;++j){++x;a[i][j]=x;}
语句频度为: 1+2+3+…+n-2=(1+n-2) ×(n-2)/2=(n-1)(n-2)/2=n2 -3n+2,所以,时间复杂度为 O(n2 ),即此算法的时间复杂度为平方阶。
归纳总结:推导大 O 阶方法
1 .用常数 1 取代运行时间中的所有加法常数。
2 .在修改后的运行次数函数中,只保留最高阶项。
3.如果最高阶项存在且不是 1,则去除与这个项相乘的常数。得到的结果就是大 O 阶。
对于算法的分析:
1.一种方法是计算所有情况的平均值,这种方法称为平均时间复杂度。 平均运行时间是所有情况中最有意义的,因为它是期望的运行时间。可现实
中,平均运行时间很难通过分析得到,一般是通过运行一定数量的实验数据后估算出来的。
2.另一种方法是计算最坏情况下的时间复杂度,这种方法称为最坏时间复杂度。 最坏运行时间是一种保证,那就是运行时间将不会再坏了。 一般在
没有特殊说明的情况下,都是指最坏时间复杂度。
以下六种计算算法时间的多项式是最常用的。 其关系为:
指数时间的关系为:
当 n 取得很大时,指数时间算法和多项式时间算法在所需时间上非常悬殊。因此,只要有人能将现有指数时间算法中的任何一个算法化简为多项式
时间算法,那就取得了一个伟大的成就。
有的情况下,算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。
例 7:
void bubble-sort (int a[],int n)
for (i=n-1,change=TURE; i>1&&change; --i) {
change=false;
for(j=0;j<i;++j)
if (a[j]>a[j+1])
{a[j] ←→a[j+1]; change=TURE;}
}
最好情况:0 次 ;
最坏情况:1+2+3+…+n-1 =n(n-1)/2;
平均时间复杂度为:O(n2 )
归纳总结
例 8:已知程序有 4 个并列的程序段,它们的时间复杂度分别为 T1(n)=O(1), T2(n)=O(n), T3(n)=O(n2 ), T4(n)=O(2n ),整个程序的时间复杂度应是多
少?
解析:整个程序的时间复杂度为T (n)=T1(n) +T2(n)+ T3(n) +T4(n) =O(max(1,n, n2 , 2n ))=O(2n ) ,即并行取时间复杂度最大的
例 9:已知一个程序的时间复杂度为 T1(n)=O(n), 其中调用了两个子函数,一个子函数的时间复杂度为 T2(n)=O(log2n), 另一个子函数的时间复杂度
为 T3(n)=O(n2 ),整个程序的时间复杂度应是多少?
解析:整个程序的时间复杂度为 T (n)=T1(n) *(T2(n)+ T3(n)=O(n(max(log2n, n2 )))=O(n*n2 )=O(n3 ),包含取时间复杂度之乘积
算法的存储空间需求
算法的存储量包括:
1.输入数据所占空间;
2.程序本身所占空间;
3.辅助变量所占空间。
输入数据所占空间只取决与问题本身,和算法无关,则只需要分析除输入和程序之外的辅助变量所占额外空间。
若所需额外空间相对于输入数据量来说是常数,则称此算法为原地工作。
若所需存储量依赖于特定的输入,则通常按最坏情况考虑。
本章学习重点
1.深刻理解数据结构的概念,掌握数据结构的“三要素”:逻辑结构、物理(存储)结构及在这种结构上所定义的操作“运算”。
2.掌握计算语句频度和估算算法时间复杂度的方法。
亲爱的读者:有时间可以点赞评论一下
全部评论