計(jì)算機(jī)算法基礎(chǔ) 第2版 課件 第1章 概述

1第1章

概述什么是計(jì)算機(jī)算法?

2算法的偽碼表示

3算法復(fù)雜度的分析

6函數(shù)增長(zhǎng)漸近性態(tài)的比較

11算法復(fù)雜度與問題復(fù)雜度的關(guān)系

19計(jì)算機(jī)算法研究的課題是：如何分析一個(gè)給定算法的時(shí)間復(fù)雜度。如何為一個(gè)計(jì)算問題設(shè)計(jì)有最小復(fù)雜度的算法。什么是(計(jì)算機(jī))算法(algorithm)?

簡(jiǎn)單地說，算法是為解決某計(jì)算問題而設(shè)計(jì)的一個(gè)過程，其每一步必須能在計(jì)算機(jī)上實(shí)現(xiàn)并在有限時(shí)間內(nèi)完成。為了理論分析的嚴(yán)格性和方便，要求算法所解決的問題有無窮多個(gè)可能的輸入規(guī)模，而且不斷增大的輸入規(guī)模要趨向無窮大。

21.什么是計(jì)算機(jī)算法？算法需要用某種語言去描述，但希望不依賴于某一語言。這個(gè)語言稱為偽語言，偽語言所表述的算法稱為偽碼

(Pseudocode)。偽碼不受繁瑣和嚴(yán)格的語法約束，簡(jiǎn)化了對(duì)算法的表述。偽碼著重表達(dá)解題的思路和方法。不同的人可用不同的偽碼，只要讓讀者清楚地看懂即可。要求偽碼中每一步可在計(jì)算機(jī)上實(shí)現(xiàn)。32.算法的偽碼表示

一個(gè)例子:選擇排序輸入: A[1],A[2],…,A[n]輸出: 重排數(shù)組中數(shù)字，使得A[1]

A[2]

…

A[n]Selection-Sort(A[1..n])for(i

1,i

n-1,i++)

key

i

for(j

i,j

n,j++)

ifA[j]<A[key]

then

key

j

endif endfor

A[i]

A[key]endforEnd這個(gè)偽碼可以更簡(jiǎn)潔地用下面?zhèn)未a表述。4選擇排序的另一種描述Selection-Sort(A[1..n])for

(i

1,i

n-1,i++) findjsuchthatA[j]=min{A[i],A[i+1],…,A[n]}

A[i]

A[j]endforEnd這個(gè)偽碼顯然更清楚地反映出這個(gè)排序算法的思路和方法。53.

算法復(fù)雜度的分析目的：找出運(yùn)算所需時(shí)間和輸入規(guī)模之間的函數(shù)關(guān)系。

輸入規(guī)模的度量模型

通常用輸入數(shù)據(jù)中數(shù)字的個(gè)數(shù)，或輸入的集合中元素的個(gè)數(shù)，n，作為輸入規(guī)模大小的度量。有些情況下，用二進(jìn)制表示輸入數(shù)據(jù)時(shí)的比特?cái)?shù)。

運(yùn)算時(shí)間的度量

用算法中一個(gè)主要的基本運(yùn)算被執(zhí)行的次數(shù)作為時(shí)間復(fù)雜度。主要的基本運(yùn)算是指它被執(zhí)行的次數(shù)是最多的。6為什么這樣做？大大簡(jiǎn)化分析的工作。與實(shí)際復(fù)雜度之間最多差一個(gè)常數(shù)因子。這是因?yàn)? (1)任一算法只用常數(shù)個(gè)基本運(yùn)算，例如加、減、乘、除等。 (2)不同基本運(yùn)算所需時(shí)間最多相差一個(gè)常數(shù)倍因子。 (3)通常，一個(gè)基本運(yùn)算所需時(shí)間不因數(shù)據(jù)大小而不同。復(fù)雜度好壞取決于輸入規(guī)模n

時(shí)，其增長(zhǎng)的快慢。差常數(shù)倍因子的兩個(gè)復(fù)雜度函數(shù)認(rèn)為是等階的。高階與低階的兩個(gè)復(fù)雜度在

n

時(shí)，它們之比一定無界。為了理論上正確和方便，要求算法必須允許

n

！7舉例：選擇排序的復(fù)雜度分析：

我們用輸入數(shù)據(jù)之間的比較作為主要的基本運(yùn)算。分析如下：選出最小的數(shù)并放入A[1]需要(n-1)次比較;選出第二小的數(shù)并放入A[2]需要(n-2)次比較;…選出第i小的數(shù)并放入A[i]需要(n-i)次比較;…選出第n-1小的數(shù)，即第二大數(shù)，并放入A[n-1]需要1次比較;選出第n小的數(shù)，即最大數(shù)，并放入A[n]不需要比較。

所以，總共需要的比較次數(shù)，即復(fù)雜度是

T(n)=(n-1)+(n-2)+…+1=n(n-1)/2。89最好情況、最壞情況和平均情況的復(fù)雜度分析不同的輸入數(shù)據(jù)，既使有相同規(guī)模n，每次算法執(zhí)行的時(shí)間可能會(huì)大不相同。要分析三種情況的復(fù)雜度：最好情況復(fù)雜度：

在遇到最有利的一組輸入數(shù)據(jù)時(shí)，算法所需要的時(shí)間。(2) 最壞情況復(fù)雜度：

在遇到最不利的一組輸入數(shù)據(jù)時(shí)，算法所需要的時(shí)間。平均情況復(fù)雜度：

各種輸入情況下，算法所需要的時(shí)間的平均值。

往往假設(shè)各種輸入情況為均勻分布。舉例:線性搜索10Linear-search(x,A[1..n])輸入: 數(shù)組A[1..n]和要找的數(shù)x輸出: 如果A[i]=x,1≤i≤n，輸出i，否則輸出0。i

1while(i≤n

and

x≠A[i]) i

i+1endwhileifi≤n

thenreturn(i)

elsereturn(0)endifEnd最好:A[1]=x，算法只需一次比較最壞:

x不在數(shù)組中或者A[n]=x，算法需要n次比較。平均:(1+2+…+n)/n=(n+1)/2。4.函數(shù)增長(zhǎng)漸近性態(tài)的比較11定義1.1

設(shè)f(n)和g(n)是兩個(gè)定義域?yàn)樽匀粩?shù)的正函數(shù)。如果存在一個(gè)常數(shù)c>0和某個(gè)自然數(shù)n0使得對(duì)任一n

n0,都有關(guān)系f(n)≤cg(n)，我們則說f(n)的階不高于g(n)的階，并記作f(n)=O(g(n))。

例1.4 證明n3+2n+5=O(n3)證明：因?yàn)楫?dāng)n≥1時(shí),我們有n3

+2n+5

n3+2n3+5n3=8n3,所以n3

+2n+5=O(n3)。(取c=8,n0=1。) 12定義1.2

設(shè)f(n)和g(n)為兩個(gè)定義域?yàn)樽匀粩?shù)的正函數(shù)。如果存在一個(gè)常數(shù)c>0和某個(gè)自然數(shù)n0使得對(duì)任一n

n0,都有關(guān)系f(n)

cg(n)，我們則說f(n)的階不低于g(n)的階，并記作f(n)=

(g(n))。

例1.5 證明

n2=

(nlgn)證明：因?yàn)楫?dāng)n

1時(shí),我們有n>lgn，從而有n2>nlgn。所以n2=

(nlgn)。(取c=1,n0=1。)13定義1.3

設(shè)f(n)和g(n)為兩個(gè)定義域?yàn)樽匀粩?shù)的正函數(shù)。如果關(guān)系f(n)=O(g(n))和f(n)=

(g(n))同時(shí)成立，我們則說f(n)與g(n)同階，并記作f(n)=

(g(n))。例1.6

證明

n3+2n+5=

(n3) 證明：例1.4已證明了n3+2n+5=O(n3)，我們只須證明

n3

+2n+5=

(n3)。注意到當(dāng)n

1時(shí)，n3

+2n+5>n3，所以n3+2n+5=

(n3)，這樣也就證明了n3+2n+5=

(n3)。表示算法復(fù)雜度的常用函數(shù)從增長(zhǎng)慢到快：O(1),lglgn,lgn,(lgn)2,…，（對(duì)數(shù)多項(xiàng)式）nlglgn,n(lgn),n2(lgn)2,…n2,n3,… （多項(xiàng)式）2n,n!,nn… （超多項(xiàng)式）

1415定理1.1

假設(shè)p(n)=aknk

+ak-1nk-1+ak-2nk-2

+…+a1n1

+a0是一個(gè)多項(xiàng)式，其中ak

>0，那么p(n)=

(nk)。證明

我們先證明p(n)=O(nk)。我們有以下演算：p(n)=aknk

+ak-1nk-1

+ak-2nk-2

+…+a1n1

+a0

aknk

+|ak-1|nk-1

+|ak-2|nk-2

+…+|a1|n1

+|a0|

aknk

+|ak-1|nk

+|ak-2|nk

+…+|a1|nk

+|a0|nk

(ak

+|ak-1|

+|ak-2|

+…+|a1|

+|a0|)nk

Cnk這里，常數(shù)C=(ak

+|ak-1|

+|ak-2|

+…+|a1|

+|a0|)

>0，所以

p(n)=O(nk)。下面證明p(n)=

(nk)。16

17

該例說明任何多項(xiàng)式函數(shù)比指數(shù)函數(shù)的階要小。18

該例說明任何對(duì)數(shù)函數(shù)比多項(xiàng)式函數(shù)的階要小。195.算法復(fù)雜度與問題復(fù)雜度的關(guān)系問題的復(fù)雜度任何解決該問題的算法所需要的最少的運(yùn)算次數(shù)。例子用比較大小的辦法將n個(gè)數(shù)排序的任何算法需要至少

lgn!

次比較才行。這個(gè)結(jié)果將在第4章討論。

lgn!

就是(基于比較的)排序問題的復(fù)雜度。問題的復(fù)雜度是算法復(fù)雜度的下界例如，

lgn!

是基于比較的排序算法復(fù)雜度的下界。通常指的是在大omega意義下的下界，即任一比較排序算法的復(fù)雜度必定為

(lgn!)或

(nlgn)。20算法復(fù)雜度是問題復(fù)雜度的上界如果某一算法的復(fù)雜度是O(f(n)),那么它所解決的問題的復(fù)雜度不會(huì)超過O(f(n))。因此任一算法的復(fù)雜度也是其所解決的問題的復(fù)雜度的上界。算法工作者的任務(wù)就是努力尋找復(fù)雜度小的算法。同時(shí)，找出問題的復(fù)雜度，即找出其算法復(fù)雜度的下界，也是一重要的工作，因?yàn)樗梢愿嬖V我們是否還有改進(jìn)當(dāng)前算法的余地而省去許多徒勞無功的努力。最佳算法如果某算法A的復(fù)雜度f(n)等于或不超過其問題的復(fù)雜度g(n)，f(n)=O(g(n))，那么稱為最優(yōu)算法。絕對(duì)相等很難，一般指漸近相等，漸近二字往往省略。21易處理問題和難處理問題如果某一問題的復(fù)雜度是超多項(xiàng)式的,則稱為難處理問題(intractable)。反之，則稱為易處理問題(tractable)。如果是難處理問題，那么我們只能依賴近似算法或啟發(fā)式算法來解決。NP完全問題判斷一個(gè)問題是易處理還是難處