《微观经济学》绪论

1第1章

绪

论1.1为什么学习数据结构

1.2有关概念和术语

1.3算法和算法分析1.3.1算法特性1.3.2算法效率的度量方法和准则2【重点掌握】：1．数据结构、逻辑结构、存储结构等术语及其含义2．计算原操作的语句频度、估算算法渐近时间复杂度【掌

握】：1．为什么学习数据结构2．数据、数据项、数据元素等术语及其含义3．数据结构与算法之间的关系4．算法5个特性、设计算法的基本要求5．常见算法的渐近时间复杂度主要问题：信息的表示信息的处理3

1.1为什么学习数据结构计算机科学是一门研究用计算机进行信息表示和处理的科学学习数据结构的主要目的：

使学生了解数据对象的特征，学会数据组织的方法，能够把现实世界中的问题在计算机内部进行表示，以及培育基本的、良好的程序设计技能。计算机解决问题的步骤：实际问题－数学模型－算法－程序－结果4【例1】图书信息检索系统。登录号：书名：作者名：分类号：价格：书目卡片书目文件线性表按书名按作者名按分类号索引表5【例2】教学计划编排问题。C1C2C3C4C5C6C7C8C9C10C11C12无C1C1,C2C1C3,C4C11C3,C5C3,C6无C9C9C1,C9,C10课程代号

课程名称

先修课程序设计基础离散数学数据结构汇编语言语言的设计和分析计算机原理编译原理操作系统高等数学线性代数普通物理数值分析图C1C2C3C4C5C6C7C8C9C10C11C12姓名项目1项目2项目3丁一跳高跳远100米马二标枪铅球张三标枪100米200米李四铅球200米跳高王五跳远200米例3、田径赛的时间安排问题跳高跳远200米铅球标枪100米比赛项目和选手如表所示，（共有5名选手，6个项目）要求在最短的时间内安排完比赛。一种颜色代表一个比赛时间ABCDEF档案学专业研究的数据对象

信息管理与信息系统专业的培养目标：“培养具备现代管理学理论基础、计算机科学技术知识及应用能力、掌握系统思想和信息系统分析与设计方法以及信息管理等方面的知识和能力,能在国家各级管理部门、工商企业、金融机构、科研单位等部门从事信息管理以及信息系统分析、设计、实施、管理和评价等方面的高级专门人才”。91.2有关概念和术语1.数据(data)：是对客观信息的描述，它是由能够被计算机识别与处理的数值、字符等符号构成的集合。2.数据元素(dataelement):数据的基本单位，也称结点（node）或记录（record）。可由多个数据项组成。3.数据项(dataitem):有独立含义的数据最小单位。4.关键码（key）：数据元素中具有标识作用的数据项。5.数据类型（datatype）：具有相同性质的计算机数据的集合及在这个数据集合上的一组操作。6.数据结构(datastructure)：数据元素和数据元素关系的集合。10根据数据元素间关系的基本特性，有3种基本数据结构：线性结构——一个对一个，如线性表、栈、队列树形结构——一个对多个，如树图状结构——多个对多个，如图117.数据的逻辑结构：抽象反映数据元素的逻辑关系。8.数据的存储(物理)结构：指数据的逻辑结构在计算机中的表示或实现。存储结构分为：顺序存储结构——借助元素在存储器中的相对位置表示

数据元素间的逻辑关系。链式存储结构——借助指示元素存储地址的指针表示数据

元素间的逻辑关系。学生成绩表姓名数学分析物理代数平均成绩王小林90859590陈红80859085刘建平95919995张立立70848680……..……..…….…….（结点、直接前趋、直接后继、开始结点、终端结点）逻辑结构（１）线性结构：有且仅有一个开始结点和一个终端结点，并且所有结点最多只有一个直接前趋和一个直接后继。 例如：线形表（２）非线形结构：一个结点可能有多个直接前趋和直接后继。 例如：树、图（1）顺序存储方法： 把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。存储方法ABCDEF::123456:（2）链接存储方法： 不要求逻辑上相邻的结点在物理位置上也相邻，结点间的逻辑关系由附加的指针字段来表示。A5D6C2B4::::DataPointer123456:161、数据的逻辑结构

2、数据的存储结构

*[3]数据的运算：检索、排序、插入、删除、修改等

线性结构

非线性结构顺序存储

链式存储

线性表栈队列树形结构图形结构数据结构(物理结构)171.3算法和算法分析

1.3.1算法性能1.算法(algorithm)：解决某一特定问题的具体步骤的描述，是指令的有限序列。2.算法特性有穷性：一个算法必须在执行有限步骤之后结束。确定性：算法的每一步必须是确切定义的，不能产生二义性可行性：每条指令的执行时间是有限的。输入：一个算法有零个或多个输入。输出：一个算法有一个或多个输出。3.算法的评价（衡量算法优劣的标准）

正确性

可读性

健壮性

效率与低存储量18

算法=控制结构+原操作（固有数据类型的操作）

即：算法的执行时间与原操作执行次数之和成正比。1.3.2算法效率的衡量方法和准则执行算法所耗费的时间=算法中每条语句的执行时间之和每条语句的执行时间＝该语句的执行次数（频度）与该语句执行一次所需时间的乘积。假设执行每条语句所需的时间均是单位时间，则一个算法的时间耗费是所有语句的频度之和。时间复杂度20估算算法的时间复杂度的具体方法及步骤从算法中选取一种对于所研究的问题来说是基本操作的原操作;计算该原操作在算法中重复执行的次数(语句频度)，以它做为算法运行时间的衡量准则，它通常只依赖于问题的规模(通常用整数量n表示)，或者说，它是问题规模的函数，通常记为f(n);一般没有必要精确地计算出算法的时间复杂度，只要大致计算出相应的数量级即可;如果随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同，则可记作：T(n)=O(f(n))，称T(n)为算法的渐近时间复杂度。

例：时间复杂度T(n)＝f(n)=2n3+3n2+2n+1渐进时间复杂度T(n)＝O(f(n))=n3常见的渐进时间复杂度：O(1) 常量阶 O(n) 线性阶O(n2) 平方阶O(logn) 对数阶O(2n) 指数阶例２{x++;s=s+x;}时间复杂度:Ｏ(1)，常量阶。例３、for(I=1;I<=n;I++){x++; s=s+x;}时间复杂度:O(n),线性阶。例４、for(I=1;I<=n;++I)

for(j=1;j<=n;++j){++x;s+=x;}时间复杂度为：O(n2),平方阶。定理：若A(n)=amnm+am-1nm-1+…+a1n+a0是一个m次多项式，则A(n)=O(nm)例5 i=1;while(i<=n) i=i*2解：语句频度为f(n)

则2f(n)<=n

得到f(n)=log2n24例6估算“顺序查找”的算法的时间复杂度。i=1;while(i<=n&&a[i]!=key)i++;if(i<=n)pos=i;elsepos=0;123456789101151319213756647580889225(3)平均时间复杂度:O(n)

假设每一个元素为key的概率是相等的(1/n)，则第i个元素查找成功时需要比较的次数为i，n个元素的平均比较次数为:(1+2+……+n)/n=(n+1)/2。(1)最好时间复杂度:O(1)a[0]=key的情况。一个复杂度为O(1)的算法，它的原操作的执行次数是固定的，与规模n无关。(2)最坏时间复杂度:O(n)a[n-1]=key的情况。263.常见时间复杂度(1)多项式时间的上限

以下6种