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

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

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

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

人們越來越客觀地看待學(xué)界與業(yè)界研究工作的價值，學(xué)界與業(yè)界的對立逐漸消除、逐漸認(rèn)可對方的價值

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

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

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

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

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

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

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

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

多項式函數(shù)（運行時間隨著問題規(guī)模n的增加呈多項式增長）

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

符號（BigOmega）-

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

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

n0，f(n)

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

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

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

(g(n))。

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

O符號（BigOh）-O(f)：增長不比f快的函數(shù)（增長不比f快，效率不比f對應(yīng)算法低）

令f(n)和g(n)是從自然數(shù)集到非負(fù)實數(shù)集的兩個函數(shù)，若存在一個自然數(shù)n0和一個正常數(shù)c，使得對所有的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ù)，若存在一個自然數(shù)n0和兩個正常數(shù)c1和c2，使得對所有的n

n0，c1g(n)

f(n)

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

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

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

(g(n))。(3)

符號-(f)：增長與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))利用極限比較增長次數(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時，有F(n)

c1f(n)；

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

n2時，有G(n)

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

n3時有

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

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

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

target:10

搜索過程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中最后一個元素匹配；target不在list中-target與list中的每一個元素進(jìn)行比較-最多n次比較，時間復(fù)雜度為O(n)

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

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

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

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

的求和表達(dá)式，即增長率函數(shù)；5、通過數(shù)學(xué)運算和公式化簡，確定增長率。算法運行時間估計(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.解遞推式，確定增長率。使用