課件2算法和復(fù)雜度

1.3-1.4

算法和算法分析一個算法通常具有五個重要特性:有窮性

有限步結(jié)束確定性

唯一執(zhí)行路徑（無歧義）可行性輸入輸出零個或多個輸入一個或多個輸出AlKhwarizmi（阿勒.霍瓦里松）首次提出算法概念，十分強調(diào)求解問題有條理的步驟。這是算法2/24算法和復(fù)雜度可以通過基本運算實現(xiàn)（理論上能夠由亙?nèi)斯庞貌患堊兒偷墓P核完成）心。1.3.1

算法的概念算法:是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作。算法和數(shù)據(jù)結(jié)構(gòu)是兩個不可分割的統(tǒng)一體程序=數(shù)據(jù)結(jié)構(gòu)+算法數(shù)據(jù)結(jié)構(gòu)通過算法實現(xiàn)操作算法根據(jù)數(shù)據(jù)結(jié)構(gòu)設(shè)計程序注意：不要把算法和計算機程序等同起來，后者只是描述前者的手段之一，我們還可以用流程圖、形式語言與自動機甚至自然語言描述一個算法。3/24算法和復(fù)雜度算法設(shè)計的要求:4/24算法和復(fù)雜度正確性正確反映需求(通過測試)可讀性有助于理解、調(diào)試和維護健壯性

完備的異常和出錯處理高效率與低存儲的需求

時間、空間的要求1.3.2

算法設(shè)計5/24算法和復(fù)雜度算法設(shè)計與分析是計算機科學(xué)的核心問題。常用的算法設(shè)計方法有：窮舉法將問題空間中的所有求解對象一一列舉出來，逐一分析、處理，并驗證結(jié)果是否滿足給定的條件。（例：C++switch語句）回溯法將問題的候選解按某種順序逐一枚舉和檢驗，來尋找一個滿足預(yù)定條件的解。當(dāng)發(fā)現(xiàn)當(dāng)前候選解不可能是解時，就退回到上一步重新選擇下一個候選解（回溯）。（例：八皇后、迷宮、深度優(yōu)先搜索）分治法和遞歸法遇到一個難以直接解決的大問題時，將其分割成一些規(guī)模較小的子問題，以便各個擊破，分而治之，然后把各個子問題的解合并起來，得出整個問題的解。（例：快速排序、歸并排序、二分檢索等）貪心法和動態(tài)規(guī)劃法貪心法的基本思想是從問題的初始狀態(tài)出發(fā)，依據(jù)某種貪心標(biāo)準(zhǔn)，通過若干次的貪心選擇而得出局部最優(yōu)解，寄希望于局部的最優(yōu)解構(gòu)建最終的全局最優(yōu)解。（Prim和Kruskal算法、Dijkstra算法）動態(tài)規(guī)劃是一種將問題實例分解為更小的、相似的子問題，并存儲子問題的解而避免計算重復(fù)的子問題，以解決最優(yōu)化問題的算法策略。動態(tài)規(guī)劃法和分治法相似？區(qū)別？（例：Floyd算法、矩陣連乘積）6/24算法和復(fù)雜度1.4

算法分析7/24算法和復(fù)雜度算法效率的衡量方法1?事后統(tǒng)計–利用計算機內(nèi)記時功能。–缺點：必須先運行依據(jù)算法編制的程序；所得時間統(tǒng)計量依賴于硬件、軟件等環(huán)境因素，掩蓋算法本身的優(yōu)劣1.4

算法分析8/24算法和復(fù)雜度算法效率的衡量方法2事前分析估計一個高級語言程序在計算機上運行所消耗的時間取決于：依據(jù)的算法選用何種策略問題的規(guī)模程序語言編譯程序產(chǎn)生機器代碼質(zhì)量機器執(zhí)行指令速度時間復(fù)雜度和空間復(fù)雜度算法的時間度量9/24算法和復(fù)雜度從算法中選取一種對于研究的問題來說是基本操作的原操作，以該基本操作重復(fù)執(zhí)行的次數(shù)作為算法執(zhí)行的時間度量。for (

i

=

1

；i<=n

；i++

)for (

j

=

1

；j<=n

；j++

)X

=

X

+1；(c)for (

i

=

1

；i<=n

；i++

)X

=

X

+1；(b)例，X=X+1；(a)基本操作重復(fù)執(zhí)行的次數(shù)分別為1，n，n2算法復(fù)雜度10/24算法和復(fù)雜度問題的規(guī)模(n)：或大小。如：矩陣的階數(shù)、圖的結(jié)點個數(shù)、被分類序列的正整數(shù)個數(shù)……時間復(fù)雜度：算法的所需的時間和問題規(guī)模的函數(shù)。記為T(n)。當(dāng)n->∞時的時間復(fù)雜性，被稱之為漸進時間復(fù)雜度?？臻g復(fù)雜度：算法的所需的空間和問題規(guī)模的函數(shù)。記為S(n)。當(dāng)n->∞時的時間復(fù)雜性，被稱之為漸進空間復(fù)雜度。

給定兩個正值函數(shù)f和g，考慮以下定義：定義1：如果存在正數(shù)c

和N

，對于所有的n≥N

，有f(n)≤cg(n),則f(n)=O(g(n))。上述定義表明，如果對于足夠大的n，或大于某自然數(shù)N的n，存在正數(shù)c，使f

不大于cg，則f

是g的大O符號。11/24算法和復(fù)雜度大O符號例如：f(n)=2n2+3n+1=O(n2)在這里，g(n)=n2，c和N的可選值如表所示：表對于函數(shù)f(n)=2n2+3n+1=O(n2)，根據(jù)大O定義計算得到的c和N的不同值N

1

2

345

…∞c

≥6

≥3

3

≥43

≥192≥13162

…162512/24算法和復(fù)雜度大O符號算法分析中常見的復(fù)雜度O(1) <

O(lgn)

<

O(n)

<

O(nlgn) <

O(n2)

<

O(n3)

<

O(2n) <

O(n!)

<

O(nn)常數(shù)

對數(shù)

多項式

指數(shù)13/24算法和復(fù)雜度復(fù)雜度舉例Input

Size

(n)O(nx)O(n)O(

lg

n)O(1)O(an)14/24算法和復(fù)雜度復(fù)雜度舉例算法的重要性：·計算機不是萬能的，并非所有的算法，計算機都能夠計算出有用的結(jié)果。差的算法不一定有實際意義。舉一個例子加以說明。假定時間復(fù)雜性函數(shù)的時間單位為us。函數(shù)n=20n=50n=100n=5001000n.02s.05s.15s.5s1000nlogn.09s.3s.6s4.5s100n2.04s.25s1s25s10n3.02s1s10s21分nlogn.4s1.1小時220天5×108世紀(jì)2n/3.0001s0.1s2.7小時5×108世紀(jì)2n1s35年3×104世紀(jì)3n58分2×109世紀(jì)易性算法頑性算法在大多數(shù)的情況下，我們只對時間復(fù)雜度感興趣，它通常計算程序執(zhí)行過程中賦值和比較操作的次

數(shù)。例1：for

(i=sum=0;

i<n;

i++)Sum

+=a

[i];賦值2+2n次，漸近復(fù)雜度O(n)。16/24算法和復(fù)雜度確定漸近復(fù)雜度確定漸近復(fù)雜度17/24算法和復(fù)雜度例2：for

(

i

=

0;

i

<

n;

i++

){for

(

j

=

1,

sum=a

[0]; j

<=

i; j++

)sum

+=a

[j];subarray

0

through”<<

icout<<“sum

for<<“is”<<sum<<endl;}n-11

+

3n

+

2i

=1

+

3n

+

2(1

+

2

+

3

++

n

-1)

=1

+

3n

+

n(n

-1)

=

O(n)

+

O(n2

)

=

O(n2

)i=1Θ符號18/24算法和復(fù)雜度Θ符號–如果存在正數(shù)c1,c2及N，對于所有的n≥N，有c1g(n))≤f(n)

≤

c2g(n),

則f(n)=

Θ(g(n))。最好、平均和最壞情況19/24算法和復(fù)雜度有時，算法中基本操作重復(fù)執(zhí)行的次數(shù)隨問題的輸入不同而不同。例，順序查找算法Status search

(

int a[

]

，int n

，int e

){for

(

i

=

0；i

<=n

-

1

；++i

)if (

e

==

a[i]

)

return TRUE

；return

FALSE

；}比較次數(shù)的復(fù)雜度是多少？最好、平均和最壞情況20/24算法和復(fù)雜度Cavg

=

i

p(inputi

)steps(inputi

)最好情況：算法需要的最少步驟最壞情況：算法需要的最多步驟平均復(fù)雜度：將處理每個輸入所執(zhí)行的步驟數(shù)與該輸入出現(xiàn)的概率相乘，然后將所有相乘的結(jié)果相加。Cavg

=

i

p(inputi

)steps(inputi

)最好、平均和最壞情況21/24算法和復(fù)雜度有時，算法中基本操作重復(fù)執(zhí)行的次數(shù)隨問題的輸入不同而不同。例，順序查找算法Status serch

(

int a[

]，int n

，int e

){for

(

i

=

0；i

<=n

-

1

；++i

)if (

e

==

a[i]

)

return TRUE

；return

FALSE

；}最好1

次比較，最壞n

次