人工智能算法（Python語(yǔ)言版）PPT第1章-算法設(shè)計(jì)與分析基礎(chǔ)

提綱概述算法的基本概念算法效率分析算法的最優(yōu)、最壞和平均效率算法運(yùn)行時(shí)間估計(jì)總結(jié)概述(1)人工智能的三大基石：數(shù)據(jù)，算法，算力；人工智能的本質(zhì)是算法；算法的優(yōu)劣決定了智能系統(tǒng)水平高低算法對(duì)工程教育畢業(yè)要求的支撐：-工程知識(shí)：能夠?qū)?shù)學(xué)、自然科學(xué)、工程基礎(chǔ)和專業(yè)知識(shí)用于解決計(jì)算機(jī)領(lǐng)域的復(fù)雜工程問(wèn)題。-設(shè)計(jì)/開(kāi)發(fā)解決方案：能夠設(shè)計(jì)針對(duì)復(fù)雜工程問(wèn)題的解決方案，設(shè)計(jì)滿

足特定需求的軟件系統(tǒng)、模塊/組件，并能夠在設(shè)計(jì)環(huán)節(jié)中體現(xiàn)創(chuàng)新意識(shí)，考慮社會(huì)、健康、安全、法律、文化以及環(huán)境等因素。-研究：能夠基于計(jì)算機(jī)科學(xué)與工程的技術(shù)和方法對(duì)復(fù)雜工程問(wèn)題進(jìn)行分析與研究，包括設(shè)計(jì)實(shí)驗(yàn)、分析與解釋數(shù)據(jù)、并通過(guò)信息綜合得到合理有效的結(jié)論。概述(2)

學(xué)界與業(yè)界為實(shí)現(xiàn)同樣的目標(biāo)而努力

人們?cè)絹?lái)越客觀地看待學(xué)界與業(yè)界研究工作的價(jià)值，學(xué)界與業(yè)界的對(duì)立逐漸消除、逐漸認(rèn)可對(duì)方的價(jià)值

計(jì)算機(jī)科學(xué)的特點(diǎn)需要業(yè)界做科研、學(xué)界解決實(shí)際問(wèn)題，算法助力克服技術(shù)瓶頸學(xué)界與業(yè)界的合作成為常態(tài)，算法的價(jià)值得到雙方認(rèn)可當(dāng)代計(jì)算機(jī)專業(yè)人才工程能力

算法“駕駛員”+“算法造車人”算法設(shè)計(jì)與分析助力程序設(shè)計(jì)能力的提升、程序設(shè)計(jì)水平的提高程序設(shè)計(jì)能力提升算法設(shè)計(jì)與分析水平提綱概述算法的基本概念算法效率分析算法的最優(yōu)、最壞和平均效率算法運(yùn)行時(shí)間估計(jì)總結(jié)算法的基本概念(1)算法：解決問(wèn)題的一步一步的方法數(shù)據(jù)結(jié)構(gòu)+算法=程序

-有了好的算法和數(shù)據(jù)結(jié)構(gòu)，以某種程序設(shè)計(jì)語(yǔ)言予以實(shí)現(xiàn)

-算法不依賴于特定程序語(yǔ)言，描述求解問(wèn)題的通用的一般步驟算法的定義與特點(diǎn)算法是一系列解決問(wèn)題的步驟；對(duì)于符合一定規(guī)范或約束的輸入，能在有限時(shí)間內(nèi)得到所要求的輸出；用偽代碼（Pseudocode）描述；特點(diǎn)：（1）有窮性：算法在有限時(shí)間內(nèi)完成。（2）確定性：算法的每一步必須是確定的，不能有二義性的解釋。（3）可行性：算法中的每一步必須是有意義的，且能達(dá)到預(yù)期目的。（4）輸入：輸入的值域必須仔細(xì)定義。（5）輸出：得到問(wèn)題的解。（6）同一問(wèn)題可能存在幾種不同的算法，執(zhí)行效率也會(huì)有所差異。算法的基本概念(2)算法的偽代碼描述示例提綱概述算法的基本概念算法效率分析算法的最優(yōu)、最壞和平均效率算法運(yùn)行時(shí)間估計(jì)總結(jié)算法效率分析(1)效率：運(yùn)行時(shí)間，存儲(chǔ)空間計(jì)算時(shí)間-將操作的執(zhí)行次數(shù)作為計(jì)算復(fù)雜度-不依賴于程序運(yùn)行軟硬件環(huán)境和編程語(yǔ)言等因素且具有一般性的算法效率分析結(jié)果-并不是實(shí)際執(zhí)行的分和秒之類的時(shí)間（對(duì)于相同的運(yùn)行環(huán)境有意義，但在不同處理器和內(nèi)存等環(huán)境下并無(wú)意義）增長(zhǎng)率

-基本操作：算法中最重要（對(duì)算法運(yùn)行時(shí)間的貢獻(xiàn)最大）的操作-關(guān)注：隨著輸入規(guī)模的增加，算法執(zhí)行時(shí)間變化的趨勢(shì)-討論：針對(duì)較大規(guī)模的輸入，運(yùn)行時(shí)間的增長(zhǎng)率或增長(zhǎng)的階（Order）基于漸進(jìn)時(shí)間（增長(zhǎng)率）對(duì)算法進(jìn)行比較和分組算法效率分析(2)小規(guī)模輸入會(huì)掩蓋算法效率的顯著差異，因此需要考慮大規(guī)模輸入x2/83*x

2x+102*logx算法效率分析(3)2類重要操作-比較操作（Comparison）

計(jì)算從數(shù)值計(jì)算發(fā)展到數(shù)據(jù)處理，比較是數(shù)據(jù)處理中最重要的操作之一

(1)所有元素比較操作等價(jià)(2)搜索和排序算法中的基本操作-算術(shù)操作（Arithmetic）(1)加法操作（additive）：+,－,遞增（increment）,遞減（decrement）(2)乘法操作（multiplication）：×,÷,取模（modulus）(3)算法分析中，加法操作和乘法操作分別考慮算法效率分析(4)如何計(jì)算增長(zhǎng)率？算法運(yùn)行的漸進(jìn)時(shí)間：去除了低階項(xiàng)和首項(xiàng)系數(shù)后的算法運(yùn)行時(shí)間函數(shù)，用漸進(jìn)時(shí)間來(lái)表示算法的時(shí)間復(fù)雜度對(duì)規(guī)模為n的輸入，若算法運(yùn)行時(shí)間為cn2，隨著n的增大，正常量c的作用逐漸降低；當(dāng)與其他運(yùn)行時(shí)間為dn3的算法相比，常量c并沒(méi)有多大作用若算法運(yùn)行時(shí)間為n2logn+3n2+5n，n越大，低階項(xiàng)3n2+5n對(duì)算法效率影響越小以上算法的運(yùn)行時(shí)間是n2階、n3階和n2logn階的哪幾類常見(jiàn)的增長(zhǎng)率？

多項(xiàng)式函數(shù)（運(yùn)行時(shí)間隨著問(wèn)題規(guī)模n的增加呈多項(xiàng)式增長(zhǎng)）

指數(shù)函數(shù)（運(yùn)行時(shí)間隨著問(wèn)題規(guī)模n的增加而爆炸性增長(zhǎng)，例如2n）-logn、n、n2和n3，分別稱為對(duì)數(shù)函數(shù)、線性函數(shù)、平方函數(shù)和立方函數(shù)-nc和nclogn（0<c<1）稱為次線性函數(shù)，nlogn和n1.5稱為次平方函數(shù)算法效率分析(5)漸進(jìn)時(shí)間的符號(hào)(1)

符號(hào)（BigOmega）-

(f)：增長(zhǎng)至少與f一樣快的函數(shù)（增長(zhǎng)不比f(wàn)慢，效率不比f(wàn)對(duì)應(yīng)算法高）

-描述了一個(gè)運(yùn)行時(shí)間的下界令f(n)和g(n)是從自然數(shù)集到非負(fù)實(shí)數(shù)集的兩個(gè)函數(shù)，若存在一個(gè)自然數(shù)n0和一個(gè)正常數(shù)c，使得對(duì)所有的n

n0，f(n)

cg(n)，則稱f(n)為

(g(n))，記為f(n)

(g(n))或f(n)=

(g(n))。

算法效率分析(6)(2)

O符號(hào)（BigOh）-O(f)：增長(zhǎng)不比f(wàn)快的函數(shù)（增長(zhǎng)不比f(wàn)快，效率不比f(wàn)對(duì)應(yīng)算法低）

令f(n)和g(n)是從自然數(shù)集到非負(fù)實(shí)數(shù)集的兩個(gè)函數(shù)，若存在一個(gè)自然數(shù)n0和一個(gè)正常數(shù)c，使得對(duì)所有的n

n0，f(n)

cg(n)，則稱f(n)為O(g(n))，記為f(n)

O(g(n))或f(n)=O(g(n))。

算法效率分析(7)令f(n)和g(n)是從自然數(shù)集到非負(fù)實(shí)數(shù)集的兩個(gè)函數(shù)，若存在一個(gè)自然數(shù)n0和兩個(gè)正常數(shù)c1和c2，使得對(duì)所有的n

n0，c1g(n)

f(n)

c2g(n)，則稱f(n)為

(g(n))，記為f(n)

(g(n))或f(n)=

(g(n))。(3)

符號(hào)-(f)：增長(zhǎng)與f一樣快的函數(shù)

算法效率分析(8)(1)f(n)=(n2

n)/2,g(n)=6n.f(n)=O(g(n))?g(n)=O(f(n))?

g(n)=O(f(n))(2)f(n)=n4+3,g(n)=n5.f(n)=O(f(n))?g(n)=O(f(n))?f(n)=O(g(n))利用極限比較增長(zhǎng)次數(shù)算法效率分析(9)

算法效率分析(10)O(f)+O(g)=O(f+g)

證明（根據(jù)O的定義證明）:

假設(shè)F(n)=O(f),G(n)=O(g)

那么，存在c1和n1，使得n

n1時(shí)，有F(n)

c1f(n)；

同理，存在c2和n2，使得n

n2時(shí)，有G(n)

c2g(n)。假設(shè)c3=max{c1,c2}，n3=max{n1,n2}，當(dāng)n

n3時(shí)有

F(n)+G(n)=O(f)+O(g)

c1f(n)+c2g(n)

c3(f(n)+g(n))，

即O(f)+O(g)

c3(f(n)+g(n))。

因此，O(f)+O(g)=O(f+g)。O(f)·O(g)=O(f·g)特性：某些算法是由兩個(gè)（以上）執(zhí)行部分組成，該算法的整體效率由具有較大增長(zhǎng)率的部分決定，即它效率最差的部分漸進(jìn)符號(hào)的有用特性提綱概述算法的基本概念算法效率分析算法的最優(yōu)、最壞和平均效率算法運(yùn)行時(shí)間估計(jì)總結(jié)算法的最優(yōu)、最壞和平均效率(1)最優(yōu)情況-當(dāng)輸入規(guī)模為n時(shí)算法的最短運(yùn)行時(shí)間-無(wú)法有效描述算法在一般情況下的時(shí)間復(fù)雜度，實(shí)際中一般不予考慮最壞情況-當(dāng)輸入規(guī)模為n時(shí)算法的最長(zhǎng)運(yùn)行時(shí)間-算法運(yùn)行時(shí)間的上界平均情況-所有規(guī)模為n的輸入的平均運(yùn)行時(shí)間-實(shí)際上，考慮以計(jì)算時(shí)間為依據(jù)的不同輸入類（計(jì)算時(shí)間意義上的等價(jià)類），計(jì)算所有不同輸入類的平均運(yùn)行時(shí)間算法的執(zhí)行時(shí)間只與問(wèn)題的規(guī)模有關(guān)、而與輸入值無(wú)關(guān)算法的最優(yōu)、最壞和平均效率(2)順序搜索算法的效率分析假設(shè)-列表list[1

n]，無(wú)重復(fù)元素-目標(biāo)不在列表中，則返回0算法

SequentialSearch(list,target,n)fori=1tondoif(target=list[i])thenreturniendifendforreturn0list:12,5,6,3,9,10,2,11

target:10

搜索過(guò)程12,5,6,3,9,10,2,1112,5,6,3,9,10,2,1112,5,6,3,9,10,2,1112,5,6,3,9,10,2,1112,5,6,3,9,10,2,1112,5,6,3,9,10,2,11算法的最優(yōu)、最壞和平均效率(3)最壞情況分析-2種情況：target與list中最后一個(gè)元素匹配；target不在list中-target與list中的每一個(gè)元素進(jìn)行比較-最多n次比較，時(shí)間復(fù)雜度為O(n)

平均情況分析(1)target總能成功找到（n個(gè)位置等概率）

第i個(gè)位置匹配，執(zhí)行i次元素比較操作

(2)target未必能成功找到一共n+1種情況（target在list中：n種；target不在list中：1種）

n+1種情況等概率，平均比較次數(shù)：平均情況時(shí)間復(fù)雜度O(n)提綱概述算法的基本概念算法效率分析算法的最優(yōu)、最壞和平均效率算法運(yùn)行時(shí)間估計(jì)總結(jié)算法運(yùn)行時(shí)間估計(jì)(1)非遞歸算法的效率分析步驟：1、確定輸入規(guī)模；2、確定基本操作；3、考慮基本操作的執(zhí)行次數(shù)是否僅僅與輸入規(guī)模有關(guān)，則按需要進(jìn)行最優(yōu)、最壞和平均效率分析；4、建立基本操作執(zhí)行次數(shù)與輸入規(guī)模n

的求和表達(dá)式，即增長(zhǎng)率函數(shù)；5、通過(guò)數(shù)學(xué)運(yùn)算和公式化簡(jiǎn)，確定增長(zhǎng)率。算法運(yùn)行時(shí)間估計(jì)(2)遞歸算法的效率分析步驟：1、確定輸入規(guī)模；2、確定基本操作；3、考慮基本操作的執(zhí)行次數(shù)是否僅僅與輸入規(guī)模有關(guān)。若還與其他因素有關(guān)，則按需要進(jìn)行最優(yōu)、最壞和平均效率分析;4、建立基本操作數(shù)與規(guī)模的函數(shù)關(guān)系，即遞推關(guān)系/遞推式（Recurrencerelation）和初始條件：5.解遞推式，確定增長(zhǎng)率。使用