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

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

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

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

=

f(a,b,c)算法算法的描述：自然語言+數(shù)學(xué)語言=>偽代碼算法的特性有窮性：算法必須在有限步操作后結(jié)束。確定性：算法的每個操作應(yīng)有確切的定義。輸入：算法有零個或多個輸入。輸出：算法有若干個輸出。有效性：算法的每個操作應(yīng)足夠簡單，能夠由計算機完成。程序(program)程序是算法的實現(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; }算法?程序查找問題(searchproblem)例2.2有n個不同的整數(shù)，a0，a1，…，an-1

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

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

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

有n個不同的整數(shù)，并且滿足條件a0<a1<…<an-1給定整數(shù)x，判斷是否存在某個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，初始時令i=0，j=n-1。如果區(qū)間[i，j]有數(shù)據(jù)，即i<=j，則重復(fù)(3)-(6)，否則，輸出-1，結(jié)束。計算處于中間位置的數(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ù)組存儲數(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í)行時間和影響因素影響因素軟硬件環(huán)境(Enviroment)算法(Algorithm)問題的輸入(Input)執(zhí)行時間是一個函數(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問題的規(guī)模規(guī)模大，需要的時間長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ù)問題規(guī)模對輸入進行分類：規(guī)模1的輸入、規(guī)模2的輸入、...、規(guī)模n的輸入算法的運行時間就是問題規(guī)模的函數(shù)，記為T(n)。問題的規(guī)模相同規(guī)模的不同輸入問題的規(guī)模68，56，179，81，167，112，90，7868，56，179，81，78，112，90，16778，112，56，81，179，68，90，167執(zhí)行時間：Tworst、Tbest、Tavg問題的規(guī)模當(dāng)有多個問題規(guī)模為n的輸入時：如果將這些輸入中最長的運行時間作為問題規(guī)模n的運行時間，這樣的T(n)叫作最壞運行時間Tworst如果將這些輸入中最短的運行時間作為問題規(guī)模n的運行時間，這樣的T(n)叫作最好運行時間Tbest如果取這些輸入的平均運行時間作為問題規(guī)模n的運行時間，這樣的T(n)叫作平均運行時間Tavg。算法分析對算法的執(zhí)行時間和需要的存儲空間進行定性分析，以了解算法、比較算法、改進算法。假設(shè)程序在一臺抽象的計算機上運行(1)這臺計算機的指令涉及以下的運算：算術(shù)運算比較運算邏輯運算賦值運算移位運算(2)每條指令的執(zhí)行時間為1個單位(3)執(zhí)行時間

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

for(int

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

if(x==a[i])

return

i; }

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

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

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

public

staticlongfactorial(int

n){

if(n==0)

return1;

else

return

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

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

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

1)+2

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

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

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

≥2≤4n

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

BigO的計算

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

BigO運算規(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運算規(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運算規(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??：下界局限性查找問題的2個算法：順序查找：O(n)折半查找：O(logn)當(dāng)n比較大時，折半查找比順序查找快

n比較小時？數(shù)據(jù)無序時？折半查找的實現(xiàn)比順序查找的實現(xiàn)復(fù)雜局限性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重復(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ù)雜性模型只計局部變量的個數(shù)不計執(zhí)行方法時其它必須的空間如方法的返回地址、返回值、中間結(jié)果等占用的空間空間復(fù)雜性計算

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ù)雜性計算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ù)雜性計算

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

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))漸進分析-Θ記號T(n)=o(g(n))，當(dāng)且僅當(dāng)：T(n)=O(g(n))且T(n)!=Ω(g(n))漸進分析-o記號小結(jié)算法分析算法的概念算法特性問題的規(guī)模n執(zhí)行時間和空間是n的函數(shù)。O的含義如何求出T(n)的階常用算法順序和折半查找算法、Horner算法作業(yè)1、編寫程序計算n=1、2、4、8、16、32時，以下函數(shù)的值：1lognnnlognn2n32nn!用excel做表，保存為PDF。提交"漂亮的"表格(log以2為底)作業(yè)2、測試你的機器跑遞歸的階乘程序，當(dāng)n=?時，程序開始拋出:java.lang.StackOverflowError注意：ppt的代碼的返回值是int，能表示的數(shù)太小，要用long或double。記錄下你嘗試的次數(shù)(我的機器n=15000肯定拋出異常)。作業(yè)3、請給出++x的執(zhí)行次數(shù)與n函數(shù)關(guā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ù)類型及實現(xiàn)計算機的用途數(shù)值計算數(shù)據(jù)處理實時控制輔助設(shè)計人工智能......數(shù)值計算的特點早期的計算機多用于數(shù)值計算，例如：彈道計算數(shù)據(jù)比較少計算復(fù)雜應(yīng)用需求催生了數(shù)據(jù)結(jié)構(gòu)這門課數(shù)據(jù)處理的特點計算機用于數(shù)據(jù)處理，例如：銀行業(yè)務(wù)、人口普查數(shù)據(jù)量很大計算比較簡單數(shù)據(jù)種類豐富：數(shù)值、字符、音頻、視頻...數(shù)據(jù)之間的關(guān)系復(fù)雜：時間序列、社交網(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)：線性表、棧、隊列二叉樹、樹經(jīng)典的數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的描述在計算機的存儲器中如何存儲數(shù)據(jù)和數(shù)據(jù)之間的關(guān)系存儲器計算機使用存儲器存儲數(shù)據(jù)內(nèi)存儲器外存儲器內(nèi)存儲器外存儲器內(nèi)存儲器模型0123n……存儲單元地址：0、1、2、......指令：read、write、move數(shù)據(jù)占用若干個相鄰的存儲單元內(nèi)存分配方式存儲大量的數(shù)據(jù)，如何為它們分配存儲單元連續(xù)分配鏈式分配連續(xù)分配方式連續(xù)分配方式將數(shù)據(jù)分配(存儲)于連續(xù)的存儲單元。已知第一個數(shù)據(jù)的地址a，按照以下的公式得到各數(shù)據(jù)的地址。location(i)=a+(i-1)×s鏈式分配方式鏈式分配方式將數(shù)據(jù)分配于離散的存儲單元，通過附加的地址信息將數(shù)據(jù)連接(Link)在一起。存取任何數(shù)據(jù)，必須依次存取第1個、第2個、。。。高級程序設(shè)計語言(C、JAVA)提供了：變量：用于存儲數(shù)據(jù)數(shù)組：用于存儲大量的數(shù)據(jù)高級語言管理內(nèi)存儲器數(shù)據(jù)類型：數(shù)據(jù)占用的存儲單元的數(shù)量和編碼方式int:4個字節(jié)，二進制補碼float:4個字節(jié)，IEEE754編碼double：8個字節(jié)，IEEE754編碼int[]a=new

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

地址a100b108c116......0123n……高級語言管理內(nèi)存儲器高級語言管理內(nèi)存儲器已使用的存儲單元未使用的存儲單元分配存儲單元回存儲單元外存儲器模型0123n……文件：由字節(jié)(存儲單元)組成；字節(jié)有地址(偏移位置)；可以在任何地址讀寫若干字節(jié)。操作系統(tǒng)的文件操作函數(shù)：open、closeread、writeseek通過文件使用外存儲器原子數(shù)據(jù)：基本數(shù)據(jù)類型、引用數(shù)據(jù)類型復(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;}云飛揚17181Id:23浪淘沙18170Id:18萬山紅17165Id:25數(shù)據(jù):對象學(xué)生的基本信息：姓名、年齡、身高和家庭住址nameageheight云飛揚17181浪淘沙18170萬山紅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)系:增加變量云飛揚17181Id:18Id:23浪淘沙18170Id:25Id:18萬山紅17165nullId:25關(guān)系:增加變量云飛揚17181Id:18Id:23浪淘沙18170Id:25Id:18萬山紅17165nullId:25關(guān)系:增加變量箭頭：表示引用關(guān)系:增加變量缺點：需要修改類的定義(修改數(shù)據(jù))一個數(shù)據(jù)同時參與多個關(guān)系？動態(tài)的關(guān)系(隨時間變化)？class