国二复习必备数据结构市公开课一等奖省赛课微课金奖PPT课件.pptx

该【国二复习必备数据结构市公开课一等奖省赛课微课金奖PPT课件 】是由【1875892****】上传分享，文档一共【57】页，该文档可以免费在线阅读，需要了解更多关于【国二复习必备数据结构市公开课一等奖省赛课微课金奖PPT课件 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。数据元素集合
元素间关系集合
数据结构（data structure)—数据元素和数据元素关系集合 Data_Structure = {D, R}
数据逻辑结构—抽象反应数据元素逻辑关系
从逻辑关系上描述数据，与数据存放无关
从详细问题抽象出来数据模型；
与数据元素本身形式、内容无关；
与数据元素相对位置无关。
第1页
数据结构（data structure)—数据元素和数据元素关系集合 Data_Structure = {D, R}
数据逻辑结构—抽象反应数据元素逻辑关系
数据逻辑结构分为：
（集合）——数据元素间除“同属于一个集合”外，无其它关系
线性结构——一个对一个，如线性表、栈、队列
树形结构——一个对多个，如树
图状结构——多个对多个，如图
第2页
数据存放结构（物理结构）—数据逻辑结构在计算机存放器中实现
存放结构分为：
次序存放结构—借助元素在存放器中相对位置来表示
数据元素间逻辑关系
链式存放结构—借助指示元素存放地址指针表示数据
元素间逻辑关系
第3页
时间复杂度：
同一问题可用不一样算法处理，各种算法中，语句执行次数越多，则该算法花费时间越长。
一个算法中语句执行次数称为语句频度或时间频度，记为T(n)。
T(n)= ∑语句执行次数×该语句执行时间
≈ ∑语句执行次数
该方法可独立于机器软件、硬件系统来分析算法在效率方面优劣
第4页
例 x = 0;
y = 0;
for ( k = 0; k < 2*n; k ++ )
x ++;
for ( i = 0; i < n; i++ )
for ( j = 0; j < n; j++ )
y ++;
1
1
2n
n2
时间花费T(n) = 4+ 6n+ 2n2
当n充分大时，T(n)与n2在数量级上相同，
记T(n)=O(n2)
2n+1
n+1
n*(n+1)
执行次数
第5页
时间复杂度：算法耗用时间相对问题规模n增加率，普通指基本操作重复执行次数阶数
大O表示法：T(n)=O(f(n))
加法规则与乘法规则
1、O(f(n))+O(g(n)) = max{O(f(n)), O(g(n)) }
2、O(f(cn)) = O(f(n)), c是正整数
3、O(f(n))*O(g(n)) = O( f(n)*g(n))
第6页
T1(n) = O(1)
T2(n) = O(n)
T3(n) = O(n2)
T(n) = T1(n)+T2(n)+T3(n) = O( max( 1, 2n, n2 ) ) = O(n2)
例 x = 0; y = 0;
for ( k = 0; k < 2n; k ++ )
x ++;
for ( i = 0; i < n; i++ )
for ( j = 0; j < n; j++ )
y ++;
频度最大语句重复执行次数阶数
第7页
例：n×n矩阵相乘
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]=c[i][j]+a[i][k]*b[k][j];
}
第8页
时间复杂度：基本操作重复执行次数阶数（算法耗用时间增加率 ）
（渐近）空间复杂度：S(n)=O(f(n))
辅助存放空间增加率或者说是算法所需存放空间量度
惯用时间复杂度：
O(1)-----常量型
O(n)、 O(n2)、 O(n3)------多项式型
O(log2n)、 O(nlog2n)-------对数型
O(2n) 、O(en)------指数型
O(1)
O(log2n)
O(n)
O(nlog2n)
O(n2)
O(n3)
O(nk)
O(2n)
……
第9页
线性结构特点：在数据元素非空有限集中
存在唯一一个被称作“第一个”数据元素
存在唯一一个被称作“最终一个”数据元素
除第一个外，集合中每个数据元素均只有一个前驱
除最终一个外，集合中每个数据元素均只有一个后继
第10页