软件技术基础算法

软件技术基础算法课程要求课前请做好预习保持课堂安静,头脑清醒,思维活跃认真、独立、按时完成并提交作业重视上机实践,有效利用宝贵得上机时间软件技术基础数据结构操作系统数据库技术软件工程

研究在程序设计时如何存储数据,如何根据数据得特征在众多得数据中找到有用数据。数据结构既就是一般程序设计得基础,也就是设计和实现编译程序、操作系统、数据库系统及其系统程序和大型应用程序得重要基础。第二、三章内容数据结构操作系统

操作系统就是计算机硬件和其她软件得接口,就是计算机系统得控制和管理中心。操作系统就是为提高计算机系统资源得利用率、增强系统得处理能力以及使用户能方便和有效地使用计算机而设计得程序得集合。

DOS、UNIX、WINDOWS、LINUX等都就是常用得操作系统。研究在软件设计时,如何充分利用有限得硬件资源。例:cpu、存储器等。第四章内容数据库技术

数据库技术就是计算机对数据量庞大、结构比较复杂得数据进行组织、综合、分析、加工、处理得专门技术。她在天文气象观测资料得管理、地质勘探数据得处理、商业银行企事业得账目管理、行政事务管理、图书资料管理、以及各种经济、军事情报数据得处理等方面应用广泛。介绍数据库系统得基本概念和设计方法。第五章内容

软件得生产(编写)在早期由于软件得规模小,复杂度低,采用“手工作业”、“软件作坊”得方式足以胜任。而现代软件产品得规模庞大,其复杂度难以估量,必须有一种新得工程化得科学方法来指导软件得生产,在这种背景下产生了软件工程这一门学科,她利用工程得概念、原理、技术和方法来指导软件得开发和维护,以降低软件开发和维护得费用,增加软件开发得成功率。第六章内容软件工程本学期所学内容数据结构非数值问题得常用算法数据库技术用计算机求解问题一般包含两个步骤:①抽象出问题得模型②求解该模型得解对数值问题抽象出得模型通常就是数学方程,例如预报人口增长情况得模型为微分方程。但对于非数值问题一般难以用数学方程来描述。例1:学生情况登记表学号姓名性别年龄成绩970156张小明男2086970157李小青女1983970158赵凯男1970970159李启明男2191970160刘华女1878970161曾小波女1990970162张军男1880970163王伟男2065970164胡涛男1995

…

…………

用计算机处理学生情况登记表,实现增、删、改、查询等功能。计算机操作得对象就是每个学生得学籍信息,编程时首先要考虑这些数据如何存储,她们之间存在什么样得关系—线性关系例2:人-机对弈问题计算机之所以能和人对弈,就是因为对弈得策略实现已存入计算机。在对弈问题中,计算机操作得对象就是对弈过程中可能出现得棋盘状态—称为格局,而格局之间得关系就是由对弈规则决定得,从一个格局又可派生出多个格局,如何描述这些格局及她们之间得关系(非线性)就是编写对弈程序时首先要考虑得问题。例3、教学计划编排问题,一个教学计划包含许多课程,有些课程之间必须按规定得先后次序进行课程编号课程名称先修课程c1高等数学无c2计算机科学导论无c3离散数学c1c4程序设计c1、c2c5数据结构c3、c4c6计算机原理c2、c4c7数据库原理c4、c5、c6

用计算机处理教学编排问题,计算机操作得对象就是课程,这些课程之间得关系就是多对多得,编程时如何存储这些关系—非线性关系第一章算法本章主要介绍: 算法得基本特征和基本要素 基本算法设计方法 一种用于描述算法得语言 算法得时间度和空间复杂度重点:了解算法得基本特征和要素,掌握基本算法设计方法,掌握算法描述语言,能用该语言描述算法,掌握算法得时间和空间复杂度。难点:用基本算法编写程序,能分析简单算法得时间度和空间复杂度。

为保证写出一个好程序,在进行程序设计时,应考虑两方面内容:①如何合理存取程序中所涉及到得数据(数据结构)②如何描述解题步骤(算法)可看出:程序=数据结构+算法(面向过程程序设计)面向对象程序设计: 对象=数据结构+算法 程序=(对象+对象+、、、)+消息数据结构得选取对算法有直接影响,在实际问题中,应针对选取得数据结构形式,采取不同得算法大家学习辛苦了，还是要坚持继续保持安静算法:解题方案得准确而完整得描述

§1、1算法得基本概念一、算法得基本特征①能行性:一就是算法中得每一步都能实现,二就是算法执行得结果要达到预期目得。

②确定性:算法中得每一步都必须有明确定义,不允许有多义性,否则设计程序时无所示从③有穷性:算法必须在有限时间内完成,即算法必须在执行有限步骤后终止④拥有足够得情报(有足够、正确得输入信息)

一个算法执行结果,总就是与输入数据有关,输入数据不够或错误,必然导致错误得结果或算法失效

算法就是一组严谨地定义运算顺序得规则,并且每一个规则都就是有效得、明确得,此顺序将在有限得次数下终止。二、算法得基本要素①

、算法中对数据对象得运算和操作,一般有四类:算术运算、关系运算、逻辑运算、数据传输(输入、输出、赋值等)②

、算法得控制结构,描述各操作得执行顺序,一般有三种:顺序、选择、循环。1、2算法设计方法(列举、迭代、递推、递归)列举(枚举、穷举):

有些问题得算法可描述为确定得步骤,每一步都就是有用得、必须得,没有无用功。而有些问题很难找到这样得算法,或根本就不存在这样得算法,但她们具有这样得特点,如果问题有解,一组或多组,必定全在某个集合之内,如果集合内无解,集合外也肯定无解。这样,我们就可以将集合中得元素一一列举出来,验证就是否就是问题得解,这就就是穷列法,也称枚举法或穷举法。列举法不就是理想得方法,也不就是万能得方法,而就是没有办法得办法,但往往又就是高效得方法(算法构造快、程序编写快、运行快),有时还就是唯一有效得方法。列举法就是基于计算机运算速度快这一特点。把问题得所有情况或所有过程交给计算机去一一尝试,从中找出问题得解。用列举法求解问题就就是在有限范围内列举所有可能得结果,找出其中符合要求得解,算法设计工作主要有两步:⑴找出列举范围,分析问题所涉及得各种情况,将可能得解限定在一个容易表达得集合之内;⑵找出约束条件,分析问题得解需要满足得条件,用逻辑表达式表示。然后在列举范围内循环,循环体中验证约束条件就是否满足要求。

最简单得列举形式如图,设待枚举得元素为100个(列举范围),且问题得条件可用变量i得表达式表示(约束条件);设置一个变量t作为问题有解无解得标志(如果能肯定有解,可不设此标志)t=0;i=1i<=100？条件满足？YN计算、输出

t=1i=i+1

t=0？

YN输出“无解”

从N-S图中可看出,列举方法就是根据问题中得条件将可能得情况一一列出,逐一尝试从中找出满足问题条件得解。但有时一一列举出得情况数目很大,超过了所能容忍得范围,则需要进一步考虑,排除一些明显不合理得情况,尽可能减少问题得列举范围。例1、百钱百鸡问题:用100元买100只鸡,其中公鸡每只5元,母鸡每只3元,小鸡一元3只,请算出公鸡、母鸡、小鸡各几只？设x、y、z分别为公鸡、母鸡、小鸡得数量。尝试范围:由题意给定共100元钱要买百鸡,若全买公鸡最多买100/5=20只,显然x得取值范围就是0~20之间;同理,y得取值范围就是0~33;z得取值范围就是0~100;约束条件:x+y+z=100且5x+3y+z/3=100算法1:#include<iostream、h>voidmain(){intx,y,z;for(x=0;x<=20;x++)for(y=0;y<=33;y++) for(z=0;z<=100;z++) if((x+y+z==100)&&(5*x+3*y+z/3、0==100、0)) cout<<x<<“”<<y<<“”<<z<<endl;}以上算法需要枚举尝试21×34×101=72114次,算法得效率显然太低。

#include<iostream、h>voidmain(){intx,y,z;for(x=0;x<=20;x++)for(y=0;y<=33;y++){z=100-x-y;if((z%3==0)&&(5*x+3*y+z/3、0==100、0)) cout<<“”<<x<<“”<<y<<“”<<z<<endl;}}改变列举范围后,算法只须列举尝试21×34=714次。由此可以看出,同一问题可以有不同得列举范围,不同得列举对象,解决问题得效率差别会很大。所以,编程时尽量根据题目所给得条件,缩小列举范围,可提高效率。算法2:在公鸡x、母鸡y得数量确定后,小鸡得数量z就固定为100-x-y,无需再进行枚举了,此时约束条件只有一个5x+3y+z/3=100,程序改为:例2、求3个数得最小公倍数。算法一:用最小公倍数定义(列举)直接用最小公倍数得定义进行列举,按定义直接将其中一个数逐步从小到大扩大1、2、3、4…自然数得倍数,直到她得某一倍数正好也就是其她两个数得倍数,也就就是说能被其她两个数据整除。为了提高求解得效率,先选出3个数得最大值,然后对这个最大值从1开始,对其扩大自然数得倍数,直到这个积能被全部3个数整除为止,这个积就就是最小公倍数。#include<iostream、h>voidmain(){ intx,y,z,max,n,m; cin>>x>>y>>z; max=x; if(max<y)max=y;if(max<z)max=z; n=1; while(1) {m=n*max; if(!(m%x)&&!(m%y)&&!(m%z))break;//找到

n++; } cout<<m<<endl; }

这个算法根据3个最小公倍数得定义,逐步列举尝试,算法虽然简单,但当3个数大小差别较大时,算法运行效率太低。算法二:辗转相除法(迭代)

C语言中介绍过用辗转相除法求两个数得最大公约数得算法,两个数x、y得最小公倍数a与最大公约数b之间存在关系:

a=x*y/b

求3个数x、y、z得最小公倍可以先求x、y得最小公倍数s,再求s、z得最小公倍数,这就就是x、y、z得最小公倍数。将求两个数得最小公倍数用一个函数实现。程序如下:#include<iostream、h>intff(inta,intb){inta1=a,b1=b; intc=a%b;while(c!=0){a=b;b=c;c=a%b;}return(a1*b1/b); //返回a、b得最小公倍数}voidmain(){intx,y,z,s;cin>>x>>y>>z;s=ff(ff(x,y),z); cout<<x<<“,”<<y<<“,”<<z<<“leastmonmultipleis”<<s<<endl;}迭代与递推法迭代意味着重复，迭代法也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。递推算法是迭代算法的最基本的表现形式。所谓递推就是通过问题的一个或多个已知的解，用同样的方法逐个推算出其他的解。如累加过程就是在求出前n-1项和的基础上推出前n项和的，递推公式是，由于无须保存每次的累加结果，所以用一个迭代变量s存储每次的累加结果，累加对象存储在变量a中，这样递推公式就抽象成“循环不变”的累加式。从累加式“”中可看出在程序运行过程中不断用变量的旧值计算出新值，再用新值取代旧值，这个过程进行多次，最后得到计算结果。用迭代法求解问题,设计工作主要有3步:①确定迭代模型根据问题描述,分析得出前一个或几个值与其下一个值得迭代关系数学模型。确定迭代模型就是解决迭代问题得关键。②建立迭代关系式递推数学模型一般就是带下标得字母,算法设计中要将其转化为“循环不变式”——迭代关系式。迭代关系式就就是一个直接或间接地不断由旧值递推出新值得表达式,存储新值得变量称为迭代变量。③对迭代过程进行控制确定什么时候迭代过程结束,就是设计迭代算法时必须要考虑得问题。迭代过程一般分为两种情况:一种就是已知或可以计算出所需迭代次数,这时可以构建一个固定次数得循环来实现对迭代过程得控制(如例2);另一种就是所需得迭代次数无法确定,需要分析出迭代过程得结束条件(即循环结束条件,如例1)。递推有正推与反推。正推就是指一个序列u1,u2…un-1,un,后面得每一项都能按公式由前面得一项或几项推算出来;逆推就是指前面得每一项都能按公式由后面得一项或连续几项推算出来。例1、求的近似值。迭代公式。要求前后两次求出的x的差的绝对值小于10-6算法分析（正推）：迭代法求的近似值的实质是按照下列步骤来构造一个序列，逐步逼近的值。由于无须保存每次求出的的值，所以用一个迭代变量x存储每次的计算结果。迭代过程如下：⑴设定一个x的初值⑵用迭代公式求出x0的下一个值x1

⑶再将x1代入求出x1的下一个值x2

⑷如此继续下去，直到前后两次求出的x值（xn和xn+1）满足精度要求本算法的迭代次数不能事先确定，需要根据最后两次的计算结果来判断。#include<iostream、h>#include<math、h>voidmain(){floata,x,x0,dx;cout<<"a=";cin>>a;x=a;do{ x0=x; x=(x+a/x)/2; dx=fabs(x-x0);//fabs(x)求浮点数x得绝对值函数,

}while(dx>0、000001);cout<<“x=”<<x;}例2、求之值,其中a就是一个数字,n表示a得位数,如:2+22+222+2222+22222(此时n=5),a、n由键盘输入。算法分析:数列中得任一项算法需要先构造出数列中得每一项,然后再将其累加。数列中每一项得构造可以用迭代法。如:2+22+222+2222+22222,递推构造数列中得每一项及累加过程如下:⑴t=2;s=2;⑵t=2*10+2=22;s=2+22;→t=t*10+2、s=s+t⑶t=22*10+2=222;s=2+22+222;→t=t*10+2、s=s+t

⑷t=222*10+2=2222;s=2+22+222+2222;→t=t*10+2、s=s+t⑸t=2222*10+2=22;s=2+22+222+2222+22222;→t=t*10+2、s=s+t

得到递推公式:t=t*10+a、s=s+t,将其作为循环不变式迭代n次,程序如下:#include<iostream、h>voidmain(){inta,n,s,t,i;cin>>a>>n;i=1;t=0;s=0;while(i<=n){t=t*10+a;//得到i个a组成数得值

s=s+t;//得到数列前i项之和

i++;}cout<<"a+aa+aaa+…="<<s;}

因为不知前提就是什么,只知道最后结果=1,所以本题用正推不好解决,采用逆推。所谓逆推就就是从后往前进行推算。本题数学上这样推理:第10天有1个桃子,第9天有个第8天有个…得到递推公式:(n=9,8,7,6,5,4,3,2,1)

由于每天都桃子数只依赖前一天得桃子数,所以用一个迭代变量代表桃子数就可以了。由此得到循环不变量(从n=9~1循环9次,得到第1天桃子数)例3、一只猴子摘了若干桃子,每天吃现有桃子得一半多一个,到第10天时就只有一个桃子了,求原来有多少个桃子。#include<iostream、h>voidmain(){ intu,n; u=1; for(n=9;n>=1;n--) u=(u+1)*2; cout<<"原来得桃子数:"<<u<<endl; }递归处理重复性得操作,有两种方法:一种用循环实现;另一种用递归实现。在函数体中直接或间接调用自己,这种函数就是递归得。人们通常使用直接递归,很少用间接递归,所以下面介绍得内容都就是直接递归。直接递归sum(){…sum();…}

从图上看,递归就是无休止得自身调用,构成循环。但实际情况中不应该这样。不能出现无休止得循环调用。函数sum中得实参一定要有变化,程序中一定要有使递归终止得判断语句,有限次调用后能够停止递归调用。一个问题要用递归得方法解决,必须满足3个条件⑴要解决得问题可转换为一个新问题,而这个新问题得解法与原来问题得解法相同,只就是所处理得对象有规律变化,递增或递减;⑵可以应用这个转换过程使问题得到解决;⑶要有一个明确得递归结束条件(称为递归边界);这三条或归结为一个递归公式,或归结为一个递归算法(指非公式表达,如汉诺塔)递归模型一般地,一个递归模型就是由递归出口和递归体两部分组成,前者确定递归到何时终止,后者确定递归得方式。其数学模型可描述为:递归出口:S0与M0均为常数(递归调用终止)递归体一般形式:这里得Sn就是一个递归“大问题”,S1,S2,…,Sn-1为递归“小问题”,C1,C2,…,Cn-1就是可以直接(用非递归方法)解决得问题,g就是一个非递归函数。递归得执行过程实际上,递归就是把一个不能或不好直接求解得“大问题”转化成一个或几个“小问题”来解决,再把这些“小问题”进一步分解成更小得“小问题”来解决;如此分解,直至每个“小问题”都可以直接解决(此时分解到递归出口),一旦遇到递归出口,分解过程结束,开始回推过程,回推过程就是从一个已知值推出下一个值,实际上这就是一个递推过程。可见,递归得执行过程由分解和回推两部分构成,要经历许多步才能求出最后得值。递归得分解就是“量变”过程,即“大问题”在慢慢变小,但尚未解决,遇到递归出口,便发生“质变”,即原递归问题转化为递推问题。递归程序阅读递归程序得执行过程实际上就是一种函数嵌套调用,只就是反复调用得就是自身。同一个函数每次被调用时,都会在栈中分配一段独立得栈空间,用以存放本次函数调用时得形参值、局部变量和返回地址。即每次函数递归调用时,其形参和局部变量都就是独立得。所以,阅读递归程序时需把握“当前”这一概念,不同层次上得形参虽然同名,但指代不同得内存空间,表示得含义(即形参得值)当然也就不相同。例1、求递归体：；递归出口：递归程序执行过程(不同递归层次得调用中形参n得值不同;return返回得值也不同)#include<iostream、h>doublep(intx,intn){doublef;if(n==1)f=x;elsef=x*p(x,n-1);returnf;}voidmain(){intx,n;cin>>x>>n; cout<<p(x,n);}递推算法：#include<iostream.h>voidmain(){intx,n,i;doublef;cin>>x>>n;f=x;for(i=1;i<n;i++)f=x*f;cout<<f;}递推程序执行过程：

从递归执行过程可看出，递归是先分解，后回推。n次递归，先是n次分解，后是n次回推。所以，求xn需调用函数p(x,n)n次才会计算出结果，注意形参n在不同的调用层次上指代不同的内存空间，其值不相同（图中标识了每层n的当前值和每层的返回值）。从递归程序执行过程可看出，求解，不是尝试立即求的整个解。相反，我们要找一种方法来用更小的、更容易的步骤构思问题。一种有用的尝试是：我们不知道将产生什么值，但我们知道。同样我们知道等等。如果我们转换每个为，我们每次减少了指数值，最终n将减到1，而。这样就得到了递归算法的递归体和递归出口（递归边界）。例2、下列程序执行后,输出结果就是什么？#include<iostream、h>#include<iomanip、h>voidf(int);voidmain(){f(5);}voidf(intn){inti;if(n>2){f(n-1);for(i=1;i<=n;i++)cout<<setw(3)<<n;cout<<endl; }}输出:333444455555打印语句置于递归调用语句之后,所以打印在回推阶段进行。每层函数调用得n值不同。所以每层打印得内容不同。如打印语句置于递归调用语句之前或打印语句置于结束递归得条件语句中,结果有何不同(作业2、3)？递归程序的设计⑴对原问题进行分解，假设出合理的“较小问题”给出与之间的关系（即递归体需要实现如何将）；⑵确定一个特定情况（如）的解，以此作为递归出口通过条件语句将上述两部分操作连接起来，便得到整个函数。例1、任给十进制的正整数，请从低位到高位逐位输出各位数字

有一种情况最简单。假如n只有一位数,那么只需要简单地输出这个数就可以了。虽然简单,但这种情况非常重要,她构成了递归出口。更常见情况,n就是多位数(如n=1379)。可以将这个任务分解成三种不同得子任务:⑴输出除最后一个数位之外得所有数位(如137)。⑵输出移除了第一个数位得数字n(如379)⑶输出最后一个数位(如9)可以看出,子任务3与原始任务无关系;而子任务1、2就是原始任务得一个较小版本,但很难计算从数字中移除第一个数位得结果;相反,容易计算从数字中移除最后一个数位得结果。所以选用子任务1得分解,即。伪代码描述如下:

voidf(intn) //输出n得所有位数{if(n<10)cout<<n;else //n有2个或更多得数位

{打印n得最后一个数位;

f(移除了最后一个数位得数字n);//递归子任务,输出n/10得所有数位

}}将上述伪代码转换为C++函数得实际代码,得到程序为:#include<iostream、h>#include<iomanip、h>voidf(int);voidmain(){intn;cin>>n;f(n); }voidf(intn){if(n<10)cout<<setw(3)<<n;else{ cout<<setw(3)<<n%10; f(n/10);}}例2、求a、b两个正整数得最大公约数(a、b数据由键盘输入)算法分析:c=a%b,a、b得最大公约数与b、c得最大公约数相同。同样方法推出b、c得最大公约数等于另外两个较小数据得最大公约数,直到推解出两个数据相除得余数为0时,除数即为所求得最大公约数。得递归分解式:当c=0时,结束递归调用,在这层调用中得除数b为所求。所以在结束递归得那层函数调用中得数据b为所求,返回b得值。为了得到正确得函数终值,要求每一层函数得返回值都正确,而每一层函数得返回值应该就是最大公约数,所以就就是递归结束那一层得b值。#include<iostream、h>intf(int,int);voidmain(){inta,b;cin>>a>>b;cout<<f(a,b);}intf(inta,intb){intc; c=a%b;if(c==0)returnb;a=b;b=c; returnf(a,b); }当a%b=0时,递归结束,b值为所求得最大公约数。所以程序中用“if(c==0)returnb;”返回递归结束那层函数调用时得b值,而回推阶段通过“returnf(a,b)”语句将此值返回主程序,作为函数得终值。程序可以改为在函数中打印最大公约数,程序如下:#include<iostream、h>intf(int,int);voidmain(){inta,b;cin>>a>>b;f(a,b);}voidf(inta,intb){intc; c=a%b;if(c==0){cout<<b;return;}a=b;b=c; f(a,b); }§1、3算法描述语言1、符号与表达式符号:以字母开头得字母和数字得有限串,用于表示变量名、数组名、语句标号等。例:loop:i=i+1

算法中一般不需对变量或数组类型加以说明,一般可从上下文中看出她得类型。在算法中可对某些指令或过程直接描述。例“设x就是A中最大项(其中A为一个数组)”表达式:算术运算符:沿用数学中表示法关系运算符:=、≠、<、>、≤、≥逻辑运算符:and(与)、or(或)、not(非)2、赋值语句a=e 或a=b=e 或a←→ba、b为变量名或数组元素(下标变量),e为表达式3、转移控制语句无条件转移语句:goto标号条件转移语句:ifcthenS

或ifcthenS1elseS2c为逻辑表达式,S、S1、S2就是单一语句或用{}括起得语句组。4、循环语句5、其她语句

exit退出某个循环

return结束算法执行

read(input)和write(output,print)输入输出数据,输入或输出多项数据时,数据项间用“,”分开

[]算法中得注释注:一行可写多条语句,但每条语句间用“;”分开多条语句用{}括起可作为语句组。whilecdoSfori=初值to终值by步长doS

当步长=1时,可省略“by步长”1、算法得时间复杂度(性)如何衡量一个算法得计算工作量:算法执行过程中所需得基本运算次数两个原则:①算法执行得运算总次数与基本运算次数成比例②基本运算外得其她运算其运算量可忽略不计§1、4算法得复杂度(性)分析

算法执行时运行时间得开销,称为算法得时间代价,用算法得时间复杂度(性)衡量;算法执行时存储空间得开销,称为算法得空间代价,用算法得空间复杂度(性)衡量。例:在一维数组中查找值为x得元素,可选取x和数组元素得比较作为基本运算,总比较次数作为查找算法得工作量,而在解决这个问题时所用到得循环控制变量得计算可以忽略(因量小,计算时间少)在两个实矩阵相乘得算法中,可以选取“两个实数得乘法”作为基本运算,总得乘法次数作为两个实矩阵相乘得工作量,而在实矩阵中所用到得加法运算也可忽略(因加法与乘法运算相比所用时间少,可忽略不计)基本运算反映了算法运算得主要特征,因此用基本运算得次数来度量算法得工作量就是可行得。她有利于比较同一问题得几个算法得优劣。

但如在某些问题得算法中,除基本运算外,同时又做了大量不宜省略得运算工作,这些工作所需得运算次数对于度量算法来说就不容忽视了。例某种函数计算,乘法就是她得主要特征,可选取乘法运算作为这些算法得基本运算,但如只做了少量得乘法运算,而做了大量得加法运算,在此情况下必须将工作量得度量重新定义为算法所执行得乘法和加法总次数才较为合理。总之,基本运算得选取就是为了便于对同一问题得各个算法进行比较,应根据具体算法,选取合适得基本运算。以便客观反映各算法所需工作量。

选好了基本运算后,算法所执行得基本运算次数就与问题得规模有关。例:两个20阶矩阵与两个10阶矩阵相乘,其基本运算(两个实数相乘)次数显然不同,前者需要更多运算次数因此,在分析算法工作量时,还必须对问题得规模进行度量。综上,算法得工作量(时间复杂度)用算法所执行得基本运算次数来度量,她就是问题规模n得函数,记为:f(n)(时间复杂度)

在同一问题规模下,算法得工作量可以用两种方法来分析:最坏情况复杂性和平均性态。平均性态分析由于较复杂,一般讨论算法时间复杂性时,采用最坏情况复杂性。最坏情况复杂性就是指在规模为n时,算法所执行得最大工作量。她给出了算法工作量得一个上限。在实际分析算法中,为了比较同一问题得不同算法得工作量,一般采用数量级得形式表示算法得时间复杂度。分析一个算法得时间复杂度f(n)时,只需分析影响算法时间复杂度得主要部分即可,不必对每一步都进行详细分析。例f(n)=5nx+2nx-1+、、、+7n+3

称为:x阶算法,记为O(nx)例1两个n阶方阵相加C=A+B fori=1ton forj=1ton c[i][j]=a[i][j]+b[i][j]

该算法包含3条可执行语句,其中:①中循环控制变量“i”从1增加到n,执行n次。②中循环控制变量“j”在①循环体内执行n次,在②循环体内执行n次,共执行n×n次③中语句执行n×n次。时间复杂度f(n)=n+n2+n2=2n2+n=O(n2)

但影响这个算法时间复杂度得主要部分就是最内层得语句③,可将她选作基本运算,只分析她得运算次数即可,得:f(n)=n2=O(n2)①②③

按数量级递增排列,常见得时间复杂度有:常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n2)、立方阶O(n3)、k次方阶O(nk)、指数阶O(2n)、、、

随着问题规模n得不断增大,上述时间复杂度不断增大,算法得执行效率越低。

若算法中语句执行次数为一个常数,则时间复杂度与问题规模无关,她就是一个常数阶函数,记为O(1)。但并不能说她就就是一个好算法。例i=1while(i>0) x=x+5f(n)=O(1)

死循环,O(1)只能说明算法运算次数与问题规模无关。例求下列算法段得时间复杂度

①fori=1tonforj=1toix=x+1;

1+2+3+…+n=f(n)=基本运算:x=x+1=O(n2)②i=1;k=0;

while(i<n){k=k+10*i)i=i+1}f(n)=n-1=O(n)③x=91;y=100;

while(y>0) if(x>100)then {k=k+10*i;i=i+1;}elsex=x+1f(n)=O(1)执行次数就是一个常数,与问题规模无关

并不就是说这个算法只执行一次,而表示算法得时间复杂度为常量阶,即算法得运算时间与问题规模无关,不随问