第八單元 簡(jiǎn)單算法時(shí)空分析

本文格式為Word版，下載可任意編輯——第八單元簡(jiǎn)單算法時(shí)空分析

第八單元簡(jiǎn)單算法時(shí)空分析

8.1算法分析的概念

算法分析是指通過數(shù)學(xué)方法對(duì)一個(gè)算法的時(shí)間效率和空間效率經(jīng)行評(píng)估，并判斷該算法的優(yōu)劣。

假使算法A的時(shí)空繁雜度均低于算法B，那么我們認(rèn)為算法A優(yōu)于算法B。

有時(shí)也有以空間換時(shí)間或者以時(shí)間換空間的算法，譬如暴搜和記憶化探尋，前者是以時(shí)間換空間的算法，而后者是以空間換時(shí)間。

算法的設(shè)計(jì)要求：

?正確性

?程序不含語法錯(cuò)誤；

?程序?qū)捉M輸入數(shù)據(jù)能夠得出滿足規(guī)格要求的結(jié)果；

?程序?qū)倪x擇的、典型的、苛刻的、帶有刁難性的幾組輸入數(shù)據(jù)能夠得出滿足規(guī)格要求的結(jié)果；

?程序?qū)σ磺泻戏ǖ妮斎霐?shù)據(jù)都能產(chǎn)生滿足規(guī)格要求的結(jié)果。

?可讀性：有助于閱讀和交流、有助于對(duì)算法的理解、有助于對(duì)算法的調(diào)試和修改。

?高效率和低存儲(chǔ)：處理速度快、存儲(chǔ)容量小。

8.2時(shí)間繁雜度

時(shí)間繁雜度，從名字就可以知道，它表示的是算法運(yùn)行的時(shí)間效率。

一個(gè)算法運(yùn)行所花費(fèi)的時(shí)間，除了與所用的計(jì)算軟、硬件環(huán)境有關(guān)外，主要取決于算法中指令重復(fù)執(zhí)行的次數(shù)，即語句的頻度相關(guān)。

一個(gè)算法中所有語句的頻度之和構(gòu)成了該算法的運(yùn)行時(shí)間。

以下為幾個(gè)代碼例子，我們依次分析它們的基本操作次數(shù)，并嘗試分析時(shí)間繁雜度。fact=1;for(inti=1;iusingnamespacestd;intn,k,m,a[110],max3;voidinit(){cin>>n>>m;for(inti=1;i>a[i];}

voidwork(){

for(inti=0;i>k;intmaxleft=-10000,maxright=-10000;for(intj=1;jusingnamespacestd;

inta[501000],leftmax[501000],rightmax[501000];intn,k,m,maxx=0;voidinit(){

cin>>n>>k;

a[0]=0;a[n+1]=0;

for(inti=1;i>a[i];}

voidwork(){

for(inti=1;i=leftmax[i-1])leftmax[i]=a[i-1];

elseleftmax[i]=leftmax[i-1];for(inti=n;i>=1;i--)//預(yù)處理rightmax

if(a[i+1]>=rightmax[i+1])rightmax[i]=a[i+1];

elserightmax[i]=rightmax[i+1];for(inti=1;i>m;

if(leftmax[m]>righ