《数据结构》 (java版) 课件 2算法与算法分析

主要内容算法算法分析：

问题规模、模型、渐进分析算法(algorithm)算法没有统一的定义，一般认为：算法是一个意义明确的指令(操作)序列。指令序列描述了计算过程，即给定一组数据，得到一个计算结果，计算过程一定会结束。算法例2.1求一元二次方程ax2+bx+c=0的实根

算法算法是一个变换：Out=translate(In)定义了一个部分函数(partialfunction):定义域内有解算法的描述：自然语言+数学语言=>伪代码x1,2

=

f(a,b,c)算法算法的描述：自然语言+数学语言=>伪代码算法的特性有穷性：算法必须在有限步操作后结束。确定性：算法的每个操作应有确切的定义。输入：算法有零个或多个输入。输出：算法有若干个输出。有效性：算法的每个操作应足够简单，能够由计算机完成。程序(program)程序是算法的实现

public

static

booleanrealroot(double

a,double

b,double

c,

double[]roots){

double

deta=b*b-4.0*a*c;

if(deta<0)

return

false;

roots[0]=(-b+Math.sqrt(deta))/(2.0*a);

roots[1]=(-b-Math.sqrt(deta))/(2.0*a);

return

true; }算法≃程序查找问题(searchproblem)例2.2有n个不同的整数，a0，a1，…，an-1

给定整数x，判断是否存在ai与x相等，如果存在，则输出ai的下标i，否则，输出-1。

顺序查找算法基本思想是从左至右，将x和n个整数逐一比较，算法如下：使用变量i表示要与x比较的数据的下标，初始时，令i=0。如果i<n，即尚有未与x比较过的数据，则转(3)；否则，输出-1，

结束。如果条件x==ai成立，则输出i，结束。否则令i=i+1，转(2)。使用数组存储数据a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]6856179811671129078顺序查找程序

public

staticintsequentialSearch(int

a[],int

x){

for(int

i=0;i<a.length;i++){

if(x==a[i])

return

i; }

return-1; }查找问题例2.3

有n个不同的整数，并且满足条件a0<a1<…<an-1给定整数x，判断是否存在某个ai与x相等，如果存在，则输出ai的下标i，否则，输出-1。折半查找算法基本思想是不断地循环，每次将查找区间缩小一半，算法如下：使用变量i，j表示数据的下标，查找区间记为[i,j]，即从下标i到下标j的有序数据中查找x，初始时令i=0，j=n-1。如果区间[i，j]有数据，即i<=j，则重复(3)-(6)，否则，输出-1，结束。计算处于中间位置的数据的下标m，m=i+(j-i)/2。如果x<am，则x只可能出现在区间[i，m-1]，令j=m-1，转(2)。如果x>am，则x只可能出现在区间[m+1，j]，令i=m+1，转(2)。如果条件x==am成立，输出m，结束。使用数组存储数据ja[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]5668788190112167179ipp=i+(j-i)/2折半查找程序

public

staticintbinarySearch(int

a[],int

x){

int

p,i=0,j=a.length-1;

while(i<=j){

p=i+(j-i>>>1);

if(x<a[p])

j=p-1;

else

if(x>a[p])

i=p+1;

else

return

p; }

return-1; } 阶乘：递推

public

staticlongfactorial(int

n){

if(n==0)

return1;longf=1;

for(int

i=2;i<=n;i++)

f*=i;

return

f; }阶乘：递归5!=5×4!4!=4×3!3!=3×2!2!=2×1!1!=1×0!0!=1

阶乘：递归

public

staticlongfactorial(int

n){

if(n==0)

return1;

else

return

n*factorial(n-1); } f(5)f(4)f(3)f(2)f(1)f(0)执行时间和影响因素影响因素软硬件环境(Enviroment)算法(Algorithm)问题的输入(Input)执行时间是一个函数：T(E,A,I)T(A,I)T(I)=>=>68，56，179，81，167，112，90，7868，56，179，81，78，112，90，16778，112，56，81，179，68，90，167问题的规模规模大，需要的时间长a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]6856179811671129078a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]…?6856179811671129078…32根据问题规模对输入进行分类：规模1的输入、规模2的输入、...、规模n的输入算法的运行时间就是问题规模的函数，记为T(n)。问题的规模相同规模的不同输入问题的规模68，56，179，81，167，112，90，7868，56，179，81，78，112，90，16778，112，56，81，179，68，90，167执行时间：Tworst、Tbest、Tavg问题的规模当有多个问题规模为n的输入时：如果将这些输入中最长的运行时间作为问题规模n的运行时间，这样的T(n)叫作最坏运行时间Tworst如果将这些输入中最短的运行时间作为问题规模n的运行时间，这样的T(n)叫作最好运行时间Tbest如果取这些输入的平均运行时间作为问题规模n的运行时间，这样的T(n)叫作平均运行时间Tavg。算法分析对算法的执行时间和需要的存储空间进行定性分析，以了解算法、比较算法、改进算法。假设程序在一台抽象的计算机上运行(1)这台计算机的指令涉及以下的运算：算术运算比较运算逻辑运算赋值运算移位运算(2)每条指令的执行时间为1个单位(3)执行时间

=指令条数时间复杂度模型顺序查找的执行时间T(n)=3n+2 publicstaticintsequentialSearch(inta[],intx){

for(int

i=0;i<a.length;i++){

if(x==a[i])

return

i; }

return-1; }问题的规模：数据的个数，即a.length，记为n publicstaticintbinarySearch(inta[],intx){

int

p,i=0,j=a.length-1;

while(i<j){

p=i+((j-i)>>>1);

if(x<a[p])

j=p-1;

else

if(x>ap)

i=p+1;

else

return

p; }

return-1; } 每循环1次：9折半查找的执行时间循环多少次？分析一个特殊情形，假设查找区间的数据个数：2m-12m-2……2221202m

即m=log2nnm+1次，即log2n+1

折半查找的执行时间T(0)=1

n=0T(n)=4(n-1)+4=4n

n≥1

public

staticlongfactorial(int

n){

if(n==0)

return1;longf=1;

for(int

i=2;i<=n;i++)

f*=i;

return

f; }问题的规模：n递推的阶乘的执行时间递推式：T(0)=1T(n)=T(n-1)+2

public

staticlongfactorial(int

n){

if(n==0)

return1;

else

return

n*factorial(n-1); } 递归的阶乘的执行时间T(n)=T(n-1)+2=(T(n

-

2)+2)+2=T(n

-

2)+2×2=(T(n

-

3)+2)+2×2=T(n-3)+3×2....=T(1)+(n-1)×2=(T(0)+2)+(n-1)×2=1+2n递归的阶乘的执行时间汉诺塔问题递归程序的执行时间

public

staticvoidhanoi(int

n,char

x,char

y,char

z){

if(n==1) move(x,1,z);

else{ hanoi(n-1,x,z,y); move(x,n,z); hanoi(n-1,y,x,z); } }问题的规模：n假设move方法的用时为1个时间单位：T(1)=2

n=1T(n)=2T(n-

1)+2

n>1递归程序的执行时间T(n)=2T(n

-

1)+2=2(2T(n

-

2)

+

2)

+

2=22T(n

-

2)+22+2=22(2T(n

-

3)+

2)+22+2=23T(n

-

3)+23+22+2=……=2n-1T(1)

+

2n-1

+…

+

22

+

2=2(2n-1

+

2n-2

+…

+

2

+

1)=2(2n

-

1)=2n+1-

22n-1+2n-2+…+2+1=(111......11)2

(2n-1+2n-2+…+2+1)+1=(111......11)2+(1)2=(1000......00)2=2n递归程序的执行时间执行时间的比较以下的两个算法哪个用时少(速度快)？T1(n)=3n+2

渐进时间复杂度分析时间复杂度是对算法所需时间的定性度量，忽略了很多因素比较两个算法的快慢时，不宜比较某个具体的问题规模，如n=5、n=100时谁快谁慢而应比较当n充分大时，谁快谁慢，即比较时间复杂度函数的增长率。BigO的定义

BigO的常见形式 常数阶 O(1)对数阶 O(logn)线性阶 O(n)线性对数阶 O(nlogn)平方阶 O(n2)立方阶 O(n3)k次方阶 O(nk)指数阶 O(2n)BigO的常见形式BigO的计算T1(n)=3n+2≤3n+n当n

≥2≤4n

n0=2，c=4T1(n)=O(n)BigO的计算

BigO的计算

对数的换底公式所以，不关注对数的底T2(n)=O(log2n)⟹T2(n)=O(logn)BigO的用途由于O(n)的增长率比O(log2n)高，所以，随着n的增大，T2(n)比T1(n)需要的时间少。即折半查找比顺序查找快。BigO运算规则

BigO运算规则的应用 publicstaticintbinarySearch(inta[],intx){

int

p,i=0,j=a.length;O(1)+O(1)

while(i<j){O(1)，循环O(logn)次

p=i+((j-i)>>>1);O(1)+O(1)+O(1)+O(1)

if(x<a[p])O(1)

j=p-1;

else

if(x>a[p])O(1)

i=p+1;O(1)+O(1)

else

return

p; }

return-1; } BigO运算规则的应用O(1)+O(1)+O(1)+O(logn)(O(1)+......+O(1))O(1)+O(1)+O(1)=O(1+1+1)=O(1)O(1)+......+O(1))=O(1)O(1)+O(logn)O(1)=O(1)+O(1×logn)=O(1)+O(logn)=O(1+logn)=O(logn)BigO运算规则的应用例:n×n矩阵的元素值的和floatsum(floata[][]){ result=0;O(1)for(i=0;i<n;i++)O(n)for(j=0;j<n;j++)O(n) result+=a[i][j];O(1) returnresult;}T(n)=O(1)+O(n)O(n)O(1)=O(1)+O(n×n×1)=O(1)+O(n2)=O(1+n2)=O(n2)Big𝛀

BigO:上界Big𝛀：下界局限性查找问题的2个算法：顺序查找：O(n)折半查找：O(logn)当n比较大时，折半查找比顺序查找快

n比较小时？数据无序时？折半查找的实现比顺序查找的实现复杂局限性coff[0]=a0coff[1]=a1......coff[n]=an多项式求和：anxn+an-1xn-1+...+a2x2+

a1x

+a0

public

staticfloatpolyEval(float

coff[],float

x){

float

y=1,value=coff[0];

for(int

i=1;i<coff.length;i++){

y*=x;

value+=y*coff[i]; }

return

value; }T(n)=7n+4=O(n)局限性a3x3

+

a2x2

+

a1x

+

a0=(a3x2

+

a2x

+

a1)x

+

a0=((a3x

+

a2)x

+

a1)x

+

a0bx

+

ai-1重复多少次？？？Horner算法：局限性

publicstaticfloatpolyHorner(float

coff[],float

x){

int

n=coff.length-1;

float

value=coff[n];

for(int

i=1;i<=n;i++)

value=value*x+coff[n-i];

return

value; }T(n)=6n+5=O(n)局限性T(n)=6n+5=O(n)T(n)=7n+4=O(n)Horner算法的基本操作少Horner算法的乘法操作少空间复杂性模型只计局部变量的个数不计执行方法时其它必须的空间如方法的返回地址、返回值、中间结果等占用的空间空间复杂性计算

public

staticlongfactorial(int

n){

if(n==0)

return1;longf=1;

for(int

i=2;i<=n;i++)

f*=i;

return

f; }S(n)=3=O(1)空间复杂性计算S(n)=3=O(1)

public

staticintsequentialSearch(int

a[],int

x){

for(int

i=0;i<a.length;i++){

if(x==a[i])

return

i; }

return-1; }空间复杂性计算

public

staticintfactorial(int

n){

if(n==0)

return1;

else

return

n*factorial(n-1); } f(5)f(4)f(3)f(2)f(1)f(0)S(n)=n+1=O(n)程序性能的测量

public

static

voidmain(String[]args){

int

n=100000;

int[]a=new

int[n];

for(int

i=0;i<a.length;i++)

a[i]=i;

long

start=System.nanoTime();//纳秒

for(int

i=0;i<n;i+