本課主題： 算法效率的度量和存儲(chǔ)空間需求
教學(xué)目的： 掌握算法的漸近時(shí)間復(fù)雜度和空間復(fù)雜度的意義與作用
教學(xué)重點(diǎn)： 漸近時(shí)間復(fù)雜度的意義與作用及計(jì)算方法
教學(xué)難點(diǎn)： 漸近時(shí)間復(fù)雜度的意義
授課內(nèi)容：
一、算法效率的度量
算法執(zhí)行的時(shí)間是算法優(yōu)劣和問題規(guī)模的函數(shù)。評(píng)價(jià)一個(gè)算法的優(yōu)劣，可以在相同的規(guī)模下，考察算法執(zhí)行時(shí)間的長(zhǎng)短來進(jìn)行判斷。而一個(gè)程序的執(zhí)行時(shí)間通常有兩種方法：
1、事后統(tǒng)計(jì)的方法。
缺點(diǎn)：不利于較大范圍內(nèi)的算法比較。（異地，異時(shí)，異境）
2、事前分析估算的方法。
程序在計(jì)算機(jī)上運(yùn)行所需時(shí)間的影響因素
算法本身選用的策略
問題的規(guī)模 規(guī)模越大，消耗時(shí)間越多
書寫程序的語言 語言越高級(jí)，消耗時(shí)間越多
編譯產(chǎn)生的機(jī)器代碼質(zhì)量
機(jī)器執(zhí)行指令的速度
綜上所述，為便于比較算法本身的優(yōu)劣，應(yīng)排除其它影響算法效率的因素。
從算法中選取一種對(duì)于所研究的問題來說是基本操作的原操作，以該基本操作重復(fù)執(zhí)行的次數(shù)作為算法的時(shí)間量度。 （原操作在所有該問題的算法中都相同）
T(n)=O(f(n))
上示表示隨問題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同，稱作算法的漸近時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度。
求4*4矩陣元素和，T(4)=O(f(4))
f=n*n;
sum(int num[4][4])
{ int i,j,r=0;
for(i=0;i<4;i++)
for(j=0;j<4;j++)
r+=num[i][j]; /*原操作*/
return r;
}
好情況：
T（4）=O（0）
壞情況：
T（4）=O（n*n）
ispass(int num[4][4])
{ int i,j;
for(i=0;i<4;i++)
for(j=0;j<4;j++)
if(num[i][j]!=i*4+j+1)
return 0;
return 1;
}
原操作執(zhí)行次數(shù)和包含它的語句的頻度相同。語句的頻度指的是該語句重復(fù)執(zhí)行的次數(shù)。
語句 頻度 時(shí)間復(fù)雜度
{++x;s=0;} 1 O(1)
for(i=1;i<=n;++i)
{++x;s+=x;}
n O(n)
for(j=1;j<=n;++j)
for(k=1;k<=n;++k)
{++x;s+=x;}
n*n O(n*n)
O(log n)
基本操作的執(zhí)行次數(shù)不確定時(shí)的時(shí)間復(fù)雜度
平均時(shí)間復(fù)雜度 依基本操作執(zhí)行次數(shù)概率計(jì)算平均
壞情況下時(shí)間復(fù)雜度 在壞情況下基本操作執(zhí)行次數(shù)
二、算法的存儲(chǔ)空間需求
類似于算法的時(shí)間復(fù)雜度，空間復(fù)雜度可以作為算法所需存儲(chǔ)空間的量度。
記作：
S(n)=O(f(n))
若額外空間相對(duì)于輸入數(shù)據(jù)量來說是常數(shù)，則稱此算法為原地工作。
如果所占空間量依賴于特定的輸入，則除特別指明外，均按壞情況來分析。
三、總結(jié)
漸近時(shí)間復(fù)雜度
空間復(fù)雜度
教學(xué)目的： 掌握算法的漸近時(shí)間復(fù)雜度和空間復(fù)雜度的意義與作用
教學(xué)重點(diǎn)： 漸近時(shí)間復(fù)雜度的意義與作用及計(jì)算方法
教學(xué)難點(diǎn)： 漸近時(shí)間復(fù)雜度的意義
授課內(nèi)容：
一、算法效率的度量
算法執(zhí)行的時(shí)間是算法優(yōu)劣和問題規(guī)模的函數(shù)。評(píng)價(jià)一個(gè)算法的優(yōu)劣，可以在相同的規(guī)模下，考察算法執(zhí)行時(shí)間的長(zhǎng)短來進(jìn)行判斷。而一個(gè)程序的執(zhí)行時(shí)間通常有兩種方法：
1、事后統(tǒng)計(jì)的方法。
缺點(diǎn)：不利于較大范圍內(nèi)的算法比較。（異地，異時(shí)，異境）
2、事前分析估算的方法。
程序在計(jì)算機(jī)上運(yùn)行所需時(shí)間的影響因素
算法本身選用的策略
問題的規(guī)模 規(guī)模越大，消耗時(shí)間越多
書寫程序的語言 語言越高級(jí)，消耗時(shí)間越多
編譯產(chǎn)生的機(jī)器代碼質(zhì)量
機(jī)器執(zhí)行指令的速度
綜上所述，為便于比較算法本身的優(yōu)劣，應(yīng)排除其它影響算法效率的因素。
從算法中選取一種對(duì)于所研究的問題來說是基本操作的原操作，以該基本操作重復(fù)執(zhí)行的次數(shù)作為算法的時(shí)間量度。 （原操作在所有該問題的算法中都相同）
T(n)=O(f(n))
上示表示隨問題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同，稱作算法的漸近時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度。
求4*4矩陣元素和，T(4)=O(f(4))
f=n*n;
sum(int num[4][4])
{ int i,j,r=0;
for(i=0;i<4;i++)
for(j=0;j<4;j++)
r+=num[i][j]; /*原操作*/
return r;
}
好情況：
T（4）=O（0）
壞情況：
T（4）=O（n*n）
ispass(int num[4][4])
{ int i,j;
for(i=0;i<4;i++)
for(j=0;j<4;j++)
if(num[i][j]!=i*4+j+1)
return 0;
return 1;
}
原操作執(zhí)行次數(shù)和包含它的語句的頻度相同。語句的頻度指的是該語句重復(fù)執(zhí)行的次數(shù)。
語句 頻度 時(shí)間復(fù)雜度
{++x;s=0;} 1 O(1)
for(i=1;i<=n;++i)
{++x;s+=x;}
n O(n)
for(j=1;j<=n;++j)
for(k=1;k<=n;++k)
{++x;s+=x;}
n*n O(n*n)
O(log n)
基本操作的執(zhí)行次數(shù)不確定時(shí)的時(shí)間復(fù)雜度
平均時(shí)間復(fù)雜度 依基本操作執(zhí)行次數(shù)概率計(jì)算平均
壞情況下時(shí)間復(fù)雜度 在壞情況下基本操作執(zhí)行次數(shù)
二、算法的存儲(chǔ)空間需求
類似于算法的時(shí)間復(fù)雜度，空間復(fù)雜度可以作為算法所需存儲(chǔ)空間的量度。
記作：
S(n)=O(f(n))
若額外空間相對(duì)于輸入數(shù)據(jù)量來說是常數(shù)，則稱此算法為原地工作。
如果所占空間量依賴于特定的輸入，則除特別指明外，均按壞情況來分析。
三、總結(jié)
漸近時(shí)間復(fù)雜度
空間復(fù)雜度