1 基本概念和术语
-
数据(Data)——对客观事物的符号表示,在计算机科学中指能输入到计算机中并被计算机程序处理的符号的总成。数据的含义极广,如图像、声音等都可以通过编码而归之于数据的范畴。
-
数据元素(Data Element)——数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。
-
数据项(Data Item)——数据项是数据的不可分割的最小单位。
-
数据对象(Data Object)——性质相同的数据元素的集合,是数据的一个子集。
-
数据结构(Data Structure)——相互之间存在的一种或多种特定关系的数据元素的集合。
-
物理结构(存储结构)——数据结构在计算机中的表示,包括数据元素的表示和关系的表示。计算机中表示信息的最小单位是位(bit),可以使用多个位形成的位串表示一个数据元素,通常称这个位串为元素(element)或结点(node)。
-
数据类型(Data Type)——刻画操作对象的特性,是一个值的集合和定义在这个值集上的一组操作的总称。
2 四种数据结构
-
图(网)状结构——结构中的数据元素之间存在多对多的关系
3 数据结构的形式定义
Data_Structure = (D,S)
D——数据元素的有限集
S——D上关系的有限集
4 算法及评价
算法是解决某一特定类型问题的有限运算序列。
算法的时间复杂度是衡量一个算法好坏的重要指标。
时间复杂度是指算法中所包含简单操作执行次数的数量级。
语句的频度是需要精确计算算法中某一语句执行的次数。
算法花费的时间与算法中语句的执行次数成正比,一个算法中的语句执行次数称为语句频度或时间频度,记为T(n),也叫做问题规模。一般情况下,算法中基操作重复执行的次数是问题规模n的某个函数,用T(n)表示。
按数量级递增排列,常见的时间复杂度有:
常数阶O(1)
对数阶O(log2n)
线性阶O(n)
线性对数阶O(nlog2n)
平方阶O(N^2)
立方阶O(N^3)
例1:
for(i=0;i<n;i++){
y=y+1;
for(j=0;j<2*n;j++){
x++;
}
}
例1中的时间复杂度计算方法:
首先找最里层的循环,发现x++这段代码应该是循环次数最多的语句,根据两层循环的循环量计算x++语句的频度:
n * 2n = 2n^2 = O(n^2)
则该例子的时间复杂度为:O(n^2)
例2
int fn(int n){
if(n<=1){
return 1;
}
return n*fn(n-1);
}
例2中不存在循环标识for,while等,但是却是递归函数,本身就具备循环含义,这样一来,就需要把递归函数转化为循环函数之后再用循环标识来计算时间复杂度。
一般计算项为:
fn(n) = fn(n-1)*n;
可转化为:
int fn(n){
int i,s;
for(i=1;i<=n;i++){
s = s*i;
}
return s;
}
这样一来,就可以轻松得到时间复杂度为:O(n)
例3:
i=1;
while(i<=n){
i=i*2;
}
循环语句为i=i*2,一层循环,执行频度计算方法为:2^t<=n -> t = log2n
则该例子的时间复杂度为:log2n
例4:
for(int i=0;i<m;i++){
for(int j=0;j<n;j++)
a[i][j] = i*j;
}
此例子中,共两层循环,最里层语句为a[i][j] = i * j,执行频度为 m * n次,但是它的时间复杂度应改为O(n^2),因为这两个n是不一样的含义的,m*n中的n是此处实实在在执行次数的n,而O(n^2)表示的是问题规模的n,也就是说m * n中的m和n都演化为问题规模的n,从而得到O(n^2)这个结果。
计算时间复杂度的一般方法:
(1)找循环标识for,while的关键字
(2)如果是递归函数,先将递归函数化为循环函数
(3)找出每一层循环的循环量
(4)计算最里层循环语句的频度
(5)取数量级最大的最为时间复杂度
分享到:
相关推荐
数据结构概论.ppt ,初步认识数据结构,在此基础上学习算法
福师11秋《数据结构概论》在线作业一标准答案.doc
数据结构概论PPT学习教案.pptx
自考数据结构概论
数据结构的详细介绍课件,很好,我们学校的资料,独家喔 数据结构的概论知识
自然辩证法概论开卷试题自然辩证法概论开卷试题自然辩证法概论开卷试题
15春福师《数据结构概论》在线作业二试卷(最新).pdf
陈越《数据结构》DS01_概论PPT(“数据结构”在计算机科学中是一门综合性的专业基础课,数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。数据结构这一门课的内容不仅是一般程序设计(特别是非...
一、数据结构的章节结构及重点构成 数据结构学科的章节划分基本上为:概论,线性表,栈和队列,串,多维数组和广义 表,树和二叉树,图,查找,内排,外排,文件,动态存储分配。 对于绝大多数的学校而言,"外排,...
算法与数据结构各章学习要点 第1章 概论 一、学习要点: 1、 熟练掌握各基本概念:数据、数据元素、数据项、数据结构、逻辑结构、存储结构、顺序存储结构、链式存储结构的定义。 2、 掌握逻辑结构、存储结构的基本...
15春福师《数据结构概论》在线作业一试卷(最新)[参照].pdf
5. 在顺序表中访问任意一结点的时间复杂度均为 O(1) ,因此,顺序表也称为 随机存取 的数据结构。 ....... 第8章 查找 自测卷 姓名 班级 一、填空题(每空1分,共10分) 1. 在数据的存放无规律而言的线性表中进行...
可把数据结构从逻辑上分为 " " " "A、静态结构与动态结构 " "B、内部结构与外部结构 " " " "C、紧凑结构与非紧凑结构 " "D、线性结构与非线性结构 " " " " " " " " 5、下列哪一个可以作为某个算法时间复杂度的表示...
大连理工数据结构与算法 1.概论.ppt
简单地说,数据结构是计算机组织数据和存储数据的方式。更进一步地说,数据结构 是指一组相互之间存在一种或多种特定关系的数据的组织方式和它们在计算机内的存储 方式,以及定义在该组数据上的操作。合理的数据...
上海交通大学2021自然辩证法期末复习材料
DS01-概论-陈越主编-数据结构.ppt该文档详细且完整,值得借鉴下载使用,欢迎下载使用,有问题可以第一时间联系作者~
数据结构基础概论PPT学习教案.pptx
研究生自然辩证法概论期末考试题库
自然辨证法概论(2018版)思考题答案(网上综合)