《數(shù)據(jù)結(jié)構(gòu)》 (java版) 課件 牛小飛2算法與算法分析、3數(shù)據(jù)結(jié)構(gòu)

2算法與算法分析主要內(nèi)容算法算法分析：

問(wèn)題規(guī)模、模型、漸進(jìn)分析算法(algorithm)算法沒(méi)有統(tǒng)一的定義，一般認(rèn)為：算法是一個(gè)意義明確的指令(操作)序列。指令序列描述了計(jì)算過(guò)程，即給定一組數(shù)據(jù)，得到一個(gè)計(jì)算結(jié)果，計(jì)算過(guò)程一定會(huì)結(jié)束。算法例2.1求一元二次方程ax2+bx+c=0的實(shí)根

算法算法是一個(gè)變換：Out=translate(In)定義了一個(gè)部分函數(shù)(partialfunction):定義域內(nèi)有解算法的描述：自然語(yǔ)言+數(shù)學(xué)語(yǔ)言=>偽代碼x1,2

=

f(a,b,c)算法算法的描述：自然語(yǔ)言+數(shù)學(xué)語(yǔ)言=>偽代碼算法的特性有窮性：算法必須在有限步操作后結(jié)束。確定性：算法的每個(gè)操作應(yīng)有確切的定義。輸入：算法有零個(gè)或多個(gè)輸入。輸出：算法有若干個(gè)輸出。有效性：算法的每個(gè)操作應(yīng)足夠簡(jiǎn)單，能夠由計(jì)算機(jī)完成。程序(program)程序是算法的實(shí)現(xiàn)

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; }算法?程序查找問(wèn)題(searchproblem)例2.2有n個(gè)不同的整數(shù)，a0，a1，…，an-1

給定整數(shù)x，判斷是否存在ai與x相等，如果存在，則輸出ai的下標(biāo)i，否則，輸出-1。

順序查找算法基本思想是從左至右，將x和n個(gè)整數(shù)逐一比較，算法如下：使用變量i表示要與x比較的數(shù)據(jù)的下標(biāo)，初始時(shí)，令i=0。如果i<n，即尚有未與x比較過(guò)的數(shù)據(jù)，則轉(zhuǎn)(3)；否則，輸出-1，

結(jié)束。如果條件x==ai成立，則輸出i，結(jié)束。否則令i=i+1，轉(zhuǎn)(2)。使用數(shù)組存儲(chǔ)數(shù)據(jù)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; }查找問(wèn)題例2.3

有n個(gè)不同的整數(shù)，并且滿足條件a0<a1<…<an-1給定整數(shù)x，判斷是否存在某個(gè)ai與x相等，如果存在，則輸出ai的下標(biāo)i，否則，輸出-1。折半查找算法基本思想是不斷地循環(huán)，每次將查找區(qū)間縮小一半，算法如下：使用變量i，j表示數(shù)據(jù)的下標(biāo)，查找區(qū)間記為[i,j]，即從下標(biāo)i到下標(biāo)j的有序數(shù)據(jù)中查找x，初始時(shí)令i=0，j=n-1。如果區(qū)間[i，j]有數(shù)據(jù)，即i<=j，則重復(fù)(3)-(6)，否則，輸出-1，結(jié)束。計(jì)算處于中間位置的數(shù)據(jù)的下標(biāo)m，m=i+(j-i)/2。如果x<am，則x只可能出現(xiàn)在區(qū)間[i，m-1]，令j=m-1，轉(zhuǎn)(2)。如果x>am，則x只可能出現(xiàn)在區(qū)間[m+1，j]，令i=m+1，轉(zhuǎn)(2)。如果條件x==am成立，輸出m，結(jié)束。使用數(shù)組存儲(chǔ)數(shù)據(jù)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)執(zhí)行時(shí)間和影響因素影響因素軟硬件環(huán)境(Enviroment)算法(Algorithm)問(wèn)題的輸入(Input)執(zhí)行時(shí)間是一個(gè)函數(shù)：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問(wèn)題的規(guī)模規(guī)模大，需要的時(shí)間長(zhǎng)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根據(jù)問(wèn)題規(guī)模對(duì)輸入進(jìn)行分類(lèi)：規(guī)模1的輸入、規(guī)模2的輸入、...、規(guī)模n的輸入算法的運(yùn)行時(shí)間就是問(wèn)題規(guī)模的函數(shù)，記為T(mén)(n)。問(wèn)題的規(guī)模相同規(guī)模的不同輸入問(wèn)題的規(guī)模68，56，179，81，167，112，90，7868，56，179，81，78，112，90，16778，112，56，81，179，68，90，167執(zhí)行時(shí)間：Tworst、Tbest、Tavg問(wèn)題的規(guī)模當(dāng)有多個(gè)問(wèn)題規(guī)模為n的輸入時(shí)：如果將這些輸入中最長(zhǎng)的運(yùn)行時(shí)間作為問(wèn)題規(guī)模n的運(yùn)行時(shí)間，這樣的T(n)叫作最壞運(yùn)行時(shí)間Tworst如果將這些輸入中最短的運(yùn)行時(shí)間作為問(wèn)題規(guī)模n的運(yùn)行時(shí)間，這樣的T(n)叫作最好運(yùn)行時(shí)間Tbest如果取這些輸入的平均運(yùn)行時(shí)間作為問(wèn)題規(guī)模n的運(yùn)行時(shí)間，這樣的T(n)叫作平均運(yùn)行時(shí)間Tavg。算法分析對(duì)算法的執(zhí)行時(shí)間和需要的存儲(chǔ)空間進(jìn)行定性分析，以了解算法、比較算法、改進(jìn)算法。假設(shè)程序在一臺(tái)抽象的計(jì)算機(jī)上運(yùn)行(1)這臺(tái)計(jì)算機(jī)的指令涉及以下的運(yùn)算：算術(shù)運(yùn)算比較運(yùn)算邏輯運(yùn)算賦值運(yùn)算移位運(yùn)算(2)每條指令的執(zhí)行時(shí)間為1個(gè)單位(3)執(zhí)行時(shí)間

=指令條數(shù)時(shí)間復(fù)雜度模型順序查找的執(zhí)行時(shí)間T(n)=3n+2 publicstaticintsequentialSearch(inta[],intx){

for(int

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

if(x==a[i])

return

i; }

return-1; }問(wèn)題的規(guī)模：數(shù)據(jù)的個(gè)數(shù)，即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; } 每循環(huán)1次：9折半查找的執(zhí)行時(shí)間循環(huán)多少次？分析一個(gè)特殊情形，假設(shè)查找區(qū)間的數(shù)據(jù)個(gè)數(shù)：2m-12m-2……2221202m

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

折半查找的執(zhí)行時(shí)間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; }問(wèn)題的規(guī)模：n遞推的階乘的執(zhí)行時(shí)間遞推式：T(0)=1T(n)=T(n-1)+2

public

staticlongfactorial(int

n){

if(n==0)

return1;

else

return

n*factorial(n-1); } 遞歸的階乘的執(zhí)行時(shí)間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遞歸的階乘的執(zhí)行時(shí)間漢諾塔問(wèn)題遞歸程序的執(zhí)行時(shí)間

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); } }問(wèn)題的規(guī)模：n假設(shè)move方法的用時(shí)為1個(gè)時(shí)間單位：T(1)=2

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

1)+2

n>1遞歸程序的執(zhí)行時(shí)間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遞歸程序的執(zhí)行時(shí)間執(zhí)行時(shí)間的比較以下的兩個(gè)算法哪個(gè)用時(shí)少(速度快)？T1(n)=3n+2

漸進(jìn)時(shí)間復(fù)雜度分析時(shí)間復(fù)雜度是對(duì)算法所需時(shí)間的定性度量，忽略了很多因素比較兩個(gè)算法的快慢時(shí)，不宜比較某個(gè)具體的問(wèn)題規(guī)模，如n=5、n=100時(shí)誰(shuí)快誰(shuí)慢而應(yīng)比較當(dāng)n充分大時(shí)，誰(shuí)快誰(shuí)慢，即比較時(shí)間復(fù)雜度函數(shù)的增長(zhǎng)率。BigO的定義

BigO的常見(jiàn)形式 常數(shù)階 O(1)對(duì)數(shù)階 O(logn)線性階 O(n)線性對(duì)數(shù)階 O(nlogn)平方階 O(n2)立方階 O(n3)k次方階 O(nk)指數(shù)階 O(2n)BigO的常見(jiàn)形式BigO的計(jì)算T1(n)=3n+2≤3n+n當(dāng)n

≥2≤4n

n0=2，c=4T1(n)=O(n)BigO的計(jì)算

BigO的計(jì)算

對(duì)數(shù)的換底公式所以，不關(guān)注對(duì)數(shù)的底T2(n)=O(log2n)?T2(n)=O(logn)BigO的用途由于O(n)的增長(zhǎng)率比O(log2n)高，所以，隨著n的增大，T2(n)比T1(n)需要的時(shí)間少。即折半查找比順序查找快。BigO運(yùn)算規(guī)則

BigO運(yùn)算規(guī)則的應(yīng)用 publicstaticintbinarySearch(inta[],intx){

int

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

while(i<j){O(1)，循環(huán)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運(yùn)算規(guī)則的應(yīng)用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運(yùn)算規(guī)則的應(yīng)用例: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??：下界局限性查找問(wèn)題的2個(gè)算法：順序查找：O(n)折半查找：O(logn)當(dāng)n比較大時(shí)，折半查找比順序查找快

n比較小時(shí)？數(shù)據(jù)無(wú)序時(shí)？折半查找的實(shí)現(xiàn)比順序查找的實(shí)現(xiàn)復(fù)雜局限性coff[0]=a0coff[1]=a1......coff[n]=an多項(xiàng)式求和：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重復(fù)多少次？？？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算法的乘法操作少空間復(fù)雜性模型只計(jì)局部變量的個(gè)數(shù)不計(jì)執(zhí)行方法時(shí)其它必須的空間如方法的返回地址、返回值、中間結(jié)果等占用的空間空間復(fù)雜性計(jì)算

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)空間復(fù)雜性計(jì)算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; }空間復(fù)雜性計(jì)算

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)程序性能的測(cè)量

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++) sequentialSearch(a,n-1);//找最后一個(gè)

long

end=System.nanoTime(); System.out.println((end-start)/n); }T(n)=Θ(h(n))，如果存在正常數(shù)c1、c2和n0，n

≥

n0，c1h(n)≤

T(n)≤

c2h(n)叫做漸近確界T(n)=Θ(h(n))T(n)=O(h(n))且T(n)=Ω(h(n))漸進(jìn)分析-Θ記號(hào)T(n)=o(g(n))，當(dāng)且僅當(dāng)：T(n)=O(g(n))且T(n)!=Ω(g(n))漸進(jìn)分析-o記號(hào)小結(jié)算法分析算法的概念算法特性問(wèn)題的規(guī)模n執(zhí)行時(shí)間和空間是n的函數(shù)。O的含義如何求出T(n)的階常用算法順序和折半查找算法、Horner算法作業(yè)1、編寫(xiě)程序計(jì)算n=1、2、4、8、16、32時(shí)，以下函數(shù)的值：1lognnnlognn2n32nn!用excel做表，保存為PDF。提交"漂亮的"表格(log以2為底)作業(yè)2、測(cè)試你的機(jī)器跑遞歸的階乘程序，當(dāng)n=?時(shí)，程序開(kāi)始拋出:java.lang.StackOverflowError注意：ppt的代碼的返回值是int，能表示的數(shù)太小，要用long或double。記錄下你嘗試的次數(shù)(我的機(jī)器n=15000肯定拋出異常)。作業(yè)3、請(qǐng)給出++x的執(zhí)行次數(shù)與n函數(shù)關(guān)系(嚴(yán)格，不用O) staticintfun(intn){

int

x=1;

for(int

i=0;i<n;i++)

for(int

j=0;j<i;++j)

for(int

k=0;k<j;++k) ++x; returnx; }作業(yè)(自我練習(xí))輸入：a0≤a1≤……≤an-1，x修改折半查找算法:1、找到x的第1次出現(xiàn)的位置2、找到x的最后1次出現(xiàn)的位置3、給出x出現(xiàn)的次數(shù)作業(yè)(自我練習(xí))31502746abcdefhig3數(shù)據(jù)結(jié)構(gòu)主要內(nèi)容數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的描述抽象數(shù)據(jù)類(lèi)型及實(shí)現(xiàn)計(jì)算機(jī)的用途數(shù)值計(jì)算數(shù)據(jù)處理實(shí)時(shí)控制輔助設(shè)計(jì)人工智能......數(shù)值計(jì)算的特點(diǎn)早期的計(jì)算機(jī)多用于數(shù)值計(jì)算，例如：彈道計(jì)算數(shù)據(jù)比較少計(jì)算復(fù)雜應(yīng)用需求催生了數(shù)據(jù)結(jié)構(gòu)這門(mén)課數(shù)據(jù)處理的特點(diǎn)計(jì)算機(jī)用于數(shù)據(jù)處理，例如：銀行業(yè)務(wù)、人口普查數(shù)據(jù)量很大計(jì)算比較簡(jiǎn)單數(shù)據(jù)種類(lèi)豐富：數(shù)值、字符、音頻、視頻...數(shù)據(jù)之間的關(guān)系復(fù)雜：時(shí)間序列、社交網(wǎng)絡(luò)...數(shù)據(jù)結(jié)構(gòu)房屋結(jié)構(gòu)鋼結(jié)構(gòu)分子結(jié)構(gòu)……牛津字典nounthearrangementofandrelationsbetweenthepartsorelementsofsomethingcomplextheorganizationofasocietyorothergroupandtherelationsbetweenitsmembers,determineitsworkingabuildingorotherobjectconstructedfromseveralpartsverbstructureddatastructuringofdatastructure線性結(jié)構(gòu)：層次結(jié)構(gòu)：線性表、棧、隊(duì)列二叉樹(shù)、樹(shù)經(jīng)典的數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的描述在計(jì)算機(jī)的存儲(chǔ)器中如何存儲(chǔ)數(shù)據(jù)和數(shù)據(jù)之間的關(guān)系存儲(chǔ)器計(jì)算機(jī)使用存儲(chǔ)器存儲(chǔ)數(shù)據(jù)內(nèi)存儲(chǔ)器外存儲(chǔ)器內(nèi)存儲(chǔ)器外存儲(chǔ)器內(nèi)存儲(chǔ)器模型0123n……存儲(chǔ)單元地址：0、1、2、......指令：read、write、move數(shù)據(jù)占用若干個(gè)相鄰的存儲(chǔ)單元內(nèi)存分配方式存儲(chǔ)大量的數(shù)據(jù)，如何為它們分配存儲(chǔ)單元連續(xù)分配鏈?zhǔn)椒峙溥B續(xù)分配方式連續(xù)分配方式將數(shù)據(jù)分配(存儲(chǔ))于連續(xù)的存儲(chǔ)單元。已知第一個(gè)數(shù)據(jù)的地址a，按照以下的公式得到各數(shù)據(jù)的地址。location(i)=a+(i-1)×s鏈?zhǔn)椒峙浞绞芥準(zhǔn)椒峙浞绞綄?shù)據(jù)分配于離散的存儲(chǔ)單元，通過(guò)附加的地址信息將數(shù)據(jù)連接(Link)在一起。存取任何數(shù)據(jù)，必須依次存取第1個(gè)、第2個(gè)、。。。高級(jí)程序設(shè)計(jì)語(yǔ)言(C、JAVA)提供了：變量：用于存儲(chǔ)數(shù)據(jù)數(shù)組：用于存儲(chǔ)大量的數(shù)據(jù)高級(jí)語(yǔ)言管理內(nèi)存儲(chǔ)器數(shù)據(jù)類(lèi)型：數(shù)據(jù)占用的存儲(chǔ)單元的數(shù)量和編碼方式int:4個(gè)字節(jié)，二進(jìn)制補(bǔ)碼float:4個(gè)字節(jié)，IEEE754編碼double：8個(gè)字節(jié)，IEEE754編碼int[]a=new

int[3];length3componentTypeint高級(jí)語(yǔ)言管理內(nèi)存儲(chǔ)器變量、數(shù)組就是存儲(chǔ)單元地址的助記符通過(guò)符號(hào)表完成轉(zhuǎn)換變量名

地址a100b108c116......0123n……高級(jí)語(yǔ)言管理內(nèi)存儲(chǔ)器高級(jí)語(yǔ)言管理內(nèi)存儲(chǔ)器已使用的存儲(chǔ)單元未使用的存儲(chǔ)單元分配存儲(chǔ)單元回存儲(chǔ)單元外存儲(chǔ)器模型0123n……文件：由字節(jié)(存儲(chǔ)單元)組成；字節(jié)有地址(偏移位置)；可以在任何地址讀寫(xiě)若干字節(jié)。操作系統(tǒng)的文件操作函數(shù)：open、closeread、writeseek通過(guò)文件使用外存儲(chǔ)器原子數(shù)據(jù)：基本數(shù)據(jù)類(lèi)型、引用數(shù)據(jù)類(lèi)型復(fù)合數(shù)據(jù)數(shù)據(jù)classAddress{

String

road;

String

city;}復(fù)合數(shù)據(jù)地址：街道、城市學(xué)生的基本信息：姓名、年齡、身高和家庭住址復(fù)合數(shù)據(jù)public

classStudent{

char

name[];

int

age;

float

height; Addressaddress;}public

classStudent{

char

name[];

int

age;

float

height;}云飛揚(yáng)17181Id:23浪淘沙18170Id:18萬(wàn)山紅17165Id:25數(shù)據(jù):對(duì)象學(xué)生的基本信息：姓名、年齡、身高和家庭住址nameageheight云飛揚(yáng)17181浪淘沙18170萬(wàn)山紅17165數(shù)據(jù)處理經(jīng)常遇到表處理，數(shù)據(jù)一行一行的出現(xiàn)，即行與行之間有先后關(guān)系例如，有3位學(xué)生關(guān)系s2s3s1public

classStudent{

char

name[];

int

age;

float

height;

Student

next;}關(guān)系:增加變量云飛揚(yáng)17181Id:18Id:23浪淘沙18170Id:25Id:18萬(wàn)山紅17165nullId:25關(guān)系:增加變量云飛揚(yáng)17181Id:18Id:23浪淘沙18170Id:25Id:18萬(wàn)山紅17165nullId:25關(guān)系:增加變量箭頭：表示引用關(guān)系:增加變量缺點(diǎn)：需要修改類(lèi)的定義(修改數(shù)據(jù))一個(gè)數(shù)據(jù)同時(shí)參與多個(gè)關(guān)系？動(dòng)態(tài)的關(guān)系(隨時(shí)間變化)？class